Vergleich zweier CSV Dateien - PowerShell zu langsam - Python als Alternative?

[KitKat::new()]

Du willst generell immer auf dem gesamten Dataframe arbeiten, also nicht einzelne Zeilen rausgreifen und die dann einzeln editieren. Ein Beispiel wie das aussehen könnte:

Tut er doch gar nicht - er moechte doch nur wissen, ob es mindestens einen Treffer gibt und mit dieser Information weiterarbeiten.
Dass es genau nur einen Treffer gibt, ist Zufall:

Zurückgegeben wird immer ein DataFrame mit den Ergebnissen, in diesem Fall genau ein Treffer.

(es sei denn er moecht es fuer alle User machen)

 

[BeBur]

er moechte doch nur wissen, ob es mindestens einen Treffer gibt und mit dieser Information weiterarbeiten.

Wenn ich mir das Thema des Threads so anschaue vermute ich ein XY-Problem. Oder ist das eigentliche Thema schon durch und der TE fragt jetzt was ganz anderes noch zusätzlich hier?

 

[firespot]

Ich schlage vor, vor Umsetzung von irgendeiner Lösung in irgendeiner Programmiersprache nochmals das Problem wie vom TE im Eingangspost zu überdenken, und dann die Lösung algorithmisch daran anpassen:

ich habe zwei CSV Dateien. Die Zeilenwerte sind identisch bis auf einen Wert. Im Moment iteriere ich durch Datei A (Referenzdatei), suche mir diese Zeile in Datei B und übernehme den Wert, falls sich dieser unterscheidet.

Daher ist pro Zeile nur der Wert von Spalte "Passed" wirklich relevant, und der andere Zeilenrest dient einfach zum matchen der Zeilen zwischen den Dateien. Diesen Rest kann ich als einen zusammenhängenden Wert auffassen, womit sich das Problem logisch gesehen auf 2 Spalten reduziert: "Passed", und der "Rest".

Gegeben die Dateien sind nicht extreeeeem riesig und man kann die Daten einlesen und im RAM behalten, dann ist der Algorithmus ganz einfach:
1) Lese Dateien A und B ein
2) Wenn in den Daten von Datei B der Wert von "Passed" der gesuchte ist (eine 1), suche die entsprechende Zeile in den Daten von Datei A (über matching von "Rest") und setze dort den neuen Wert
Falls "Passed" mehrere Zielwerte haben kann und die einfach 1:1 übernommen werden sollen (egal welcher Wert genau), suche einfach die entsprechende Zeile von B in den Daten von A und schreibe dort den "Passed"-Wert von B hinein.
3) Schreibe die Daten von A wieder raus

Und in dieser Form und mit einem schlauem matching von "Rest" (siehe unten) ist das Suchen und Ersetzen eine vollkommen vektorisierbare Operation gemäß SIMD. Mit R als Beispiel-Programmiersprache wäre das ganze somit in ein paar Code-Zeilen erledigt und sollte laufzeitmäßig so schnell sein wie eine interpretierte Sprache halt schnell sein kann.

Wie matcht man "Rest" effizient zwischen den Daten?
Prinzipiell kann man "Rest" als eine Sammlung multipler Spalten auffassen und jedes Feld zwischen den Daten von A und B auf Identität vergleichen. Um das ganze aber effizient zu vektorisieren, kann man alle Spaltenwerte von "Rest" auch ganz einfach zu einem einzigen String-Wert zusammenlegen und dann einfach diesen String in Daten A & B suchen bzw. direkt auf Identität vergleichen. 100% vektorisierbar, minimaler Codeaufwand und maximale Vergleichseffizienz.
Und in diesem Sinne kann ich beim Einlesen der Dateien auch gleich mächtig Aufwand sparen, indem ich die Dateien nicht als CSVs mit getrennten Feldern einlesen, sondern einfach zeilenweise als plain-text und mir dann diese Zeilen (z.B. per regex) einfach in die strings "Rest" und "Passed" splitte und somit gleich alle relevanten strings direkt habe.

Ob man das so in R oder Python oder sonstwas umsetzt ist ja dann egal.

 

[BeBur]

Das hauptsächliche worauf man achten sollte ist imHo, dass man nicht manuell verschachtelt iteriert:

for each_line in FileA
  for each_line in FileB
    do_stuff()

Direkt vergleichbar wichtig ist vermutlich, nicht auf den CSV-Dateien selber zu arbeiten.

Und in diesem Sinne kann ich beim Einlesen der Dateien auch gleich mächtig Aufwand sparen, indem ich die Dateien nicht als CSVs mit getrennten Feldern einlesen, sondern einfach zeilenweise als plain-text und mir dann diese Zeilen (z.B. per regex) einfach in die strings "Rest" und "Passed" splitte und somit gleich alle relevanten strings direkt habe.

Ja, in einer zweiten Code-Iteration, wenn dieser Teil zu langsam ist.

 

[maloz]

Danke.
Fand das aber doof mit empty und bin auf index gestoßen. Dann kann man mit len(index) die Anzahl der gefundenen Rows widergeben.

@BeBur
Es handelt sich um dasselbe "Problem".

Daher ist pro Zeile nur der Wert von Spalte "Passed" wirklich relevant, und der andere Zeilenrest dient einfach zum matchen der Zeilen zwischen den Dateien. Diesen Rest kann ich als einen zusammenhängenden Wert auffassen, womit sich das Problem logisch gesehen auf 2 Spalten reduziert: "Passed", und der "Rest".

Danke, treffender hätte ich es nicht formulieren können. ^^

 

[KitKat::new()]

Gegeben die Dateien sind nicht extreeeeem riesig und man kann die Daten einlesen und im RAM behalten, dann ist der Algorithmus ganz einfach:
1) Lese Dateien A und B ein
2) Wenn in den Daten von Datei B der Wert von "Passed" der gesuchte ist (eine 1), suche die entsprechende Zeile in den Daten von Datei A (über matching von "Rest") und setze dort den neuen Wert
Falls "Passed" mehrere Zielwerte haben kann und die einfach 1:1 übernommen werden sollen (egal welcher Wert genau), suche einfach die entsprechende Zeile von B in den Daten von A und schreibe dort den "Passed"-Wert von B hinein.
3) Schreibe die Daten von A wieder raus

Der Algorithmus hat ne Laufzweitkomplexitaet von O(nlogn), wenn wie beschrieben umgesetzt.
Unserer ist O(n)

Wie hast du eigentlich vor mit Python (SIMD Instruktionen?) zu vektorisieren?
(sorry, bin da absoluter noob - ich weiss, dass numpy Vektorisierung nutzt, aber das ist ja auch nicht in Python geschrieben, wuerde mich aber interessieren; vor allem in Kombination mit strings)

Und in diesem Sinne kann ich beim Einlesen der Dateien auch gleich mächtig Aufwand sparen, indem ich die Dateien nicht als CSVs mit getrennten Feldern einlesen, sondern einfach zeilenweise als plain-text und mir dann diese Zeilen (z.B. per regex) einfach in die strings "Rest" und "Passed" splitte und somit gleich alle relevanten strings direkt habe.

Sh. meinen Code 😉
Sogar ohne den "Rest"-string

 

[firespot]

Hier mal eine komplette & kommentierte R-Lösung für das Problem wie vom OP beschrieben - da sich Python mit pandas & numpy etc und R ähnlich sind, vermute ich dass man das so auch ziemlich direkt in Python-Code übersetzen könnte (?):

FileA <- "C:/CSV_Processing/File_A.csv" # richtigen Pfad setzen
FileB <- "C:/CSV_Processing/File_B.csv" # richtigen Pfad setzen

# Dateien einlesen, jedes Feld als string, mit richtigem Encoding (hier UTF-8 angenommen)
DataA <- read.csv(FileA, encoding = "UTF-8", colClasses = "character")
DataB <- read.csv(FileB, encoding = "UTF-8", colClasses = "character")

# "Rest" erstellen - alle Felder bis auf "Passed" zu einem einzigen string verknüpfen
RestA <- apply(DataA[, colnames(DataA) != "Passed"], 1, paste, collapse = "")
RestB <- apply(DataB[, colnames(DataB) != "Passed"], 1, paste, collapse = "")

# match von A nach B, mit Überschreiben von Passed gemäß der Werte von B
Result <- DataA
M <- match(RestA, RestB)
# Variante 1: übernehme nur eine "1" von B (andere Werte werden ignoriert)
Result$Passed <- ifelse(DataB$Passed[M] == "1", DataB$Passed[M], Result$Passed)
# Variante 2: übernehme den Wert von B (egal was der ist):
Result$Passed <- DataB$Passed[M]

# Ergebnis rausschreiben
write.csv(Result, "Result.csv", quote = FALSE, row.names = FALSE)

Das hauptsächliche worauf man achten sollte ist imHo, dass man nicht manuell verschachtelt iteriert:

Wie hast du eigentlich vor mit Python (SIMD Instruktionen?) zu vektorisieren?

In meinem Beispiel erschlage ich das direkt über die Sprache, indem ich nur R-Sprachfeatures nutze die selbst vektorisiert sind und für eine interpretierte Sprache damit sehr effizient sind (beachte dass ich keine einzige selbst codierte Schleife verwende!).
Mein R-Skript ist einfach gehalten und R wird die vektorisierten Operationen intern vermutlich sequentiell abarbeiten. Von der Logik her könnte ich aber auch auf parallelisierte Funktionen für SIMD zugreifen (gibts in R über eigene packages; zu Python kann ich nix sagen).

Der Algorithmus hat ne Laufzweitkomplexitaet von O(nlogn), wenn wie beschrieben umgesetzt.
Unserer ist O(n)

Ich weiß nicht was du meinst. So wie in R codiert hat der matching-Algorithmus vermutlich eine Komplexität von O(n1 * n2) (mit n1 und n2 die Anzahl der Zeilen in den Dateien), weil ich davon ausgehe dass R in der Funktion match einfach sequentiell vergleicht.
Man könnte die B-Daten vorsortieren. Dann wird zwar das lookup schneller, aber die vorherige Sortierung von B alleine kostet auch wieder bis zu O(n2 log-n2), und dann muss ich nachher noch immer alle n1 Zeilen im table aufsuchen (zu konstanten Kosten). Im Detail hängt hier die Effizienz u.a. davon ab wie "sortiert" oder "unsortiert" die input-Daten sind und wieviel somit die Sortieroperationen im Vergleich zur anschließenden Zeitersparnis kosten.
Wie du auf O(n) kommst weiß ich nicht, denn das hätte man wenn jede Zeile in A ohne irgendwelchen Zusatzaufwand (wie sortieren) und konstanter Komplexität direkt die passende Zeile in B finden würde. Wie soll das gehen?

Schlußendlich kann ich dir sagen, dass zumindest in R diese Überlegungen nicht wichtig sind denn in R wird das Matchen & Ersetzen sowie sehr schnell sein (bei den vom OP genannten Datei-größen), aber das Einlesen der Daten wird das bottleneck werden, denn:

Ja, in einer zweiten Code-Iteration, wenn dieser Teil zu langsam ist.

Es gibt mehrere Gründe warum es sinnvoll sein kann, von Haus aus NICHT mit CSV-Feldern sondern direkt mit Ganze-Zeile-Strings zu arbeiten (einlesen) die dann später in "Rest" und "Passed" gesplittet werden:

-) zumindest R neigt dazu, csv-Daten ziemlich langsam einzulesen weil es im Hintergrund zahlreiche checks macht (z.B. welcher Datentyp das gerade eingelesene Feld ist - etwa string, integer, double etc., und ob dieser Datentyp kompatibel ist mit allen anderen zuvor eingelesenen Feldern derselben Spalte) - mit package data.table kann man da aber auch effizientere Einlesefunktionen nutzen.
In meinem Beispiel habe ich dieses Problem abgefedert, indem ich alle Felder per definitionem als strings einlesen lasse. Aber wenn man R diesbezüglich keine guidance gibt kann es die performance erheblich beeinflussen.
-) CSV auch bzgl. Feldformatierung interpretiert wird, siehe z.B. quotations innerhalb character-strings, missing values etc.. Das kann wiederum auch die exakte Formatierung des zu generierenden Outputs beeinflussen (z.B. werden quotations beibehalten oder eliminiert?).

Wenn ich von Haus aus nur strings einlese und damit arbeite (und mir Passed / "Rest" raussplitte) sollte die Effizienz beim Einlesen deutlich steigen und gleichzeitig bin ich jegliche CSV-Interpretationsgeschichten auch los und der Output sollte ident zu den Input-Feldenr sein.
Selbstverständlich kann ich das mit R ganz leicht machen, allerdings wird der Code durch die regex-Operationen fürs String-splitten weniger übersichtlich. Daher hab ich im Beispiel oben csv genutzt; wenn ich weiß dass die Dateien aber dutzende von MB haben, würde ich (mit R) direkt nur auf string-basis arbeiten weil ich weiß wie langsam csv-Einlesen bei R sein kann ...

Wie sehr diese Überlegungen auch für Python gültig sind kann ich nicht beurteilen.

 

[KitKat::new()]

Man könnte die B-Daten vorsortieren. Dann wird zwar das lookup schneller, aber die vorherige Sortierung von B alleine kostet auch wieder bis zu O(n2 log-n2)

Annahme n2~n1=n
Einmal O(nlogn) fuers sortieren, und einmal fuers durchiterieren + passenden Eintrag finden
O(nlogn)+O(nlogn) = O(nlogn)

Wie du auf O(n) kommst weiß ich nicht, denn das hätte man wenn jede Zeile in A ohne irgendwelchen Zusatzaufwand (wie sortieren) und konstanter Komplexität direkt die passende Zeile in B finden würde. Wie soll das gehen?

Die einsen (bzw. die noetigen Infos zur Identifizierung) in B in eine Hashmap packen und dann ueber A iterieren und bei jedem Eintrag von A die Hashmap checken (siehe die "irgendeine Loesung", die einige implementiert haben: https://www.computerbase.de/forum/t...-python-als-alternative.2032156/post-25837850 und https://www.computerbase.de/forum/t...-python-als-alternative.2032156/post-25832963 )

Es gibt mehrere Gründe warum es sinnvoll sein kann, von Haus aus NICHT mit CSV-Feldern sondern direkt mit Ganze-Zeile-Strings zu arbeiten (einlesen) die dann später in "Rest" und "Passed" gesplittet werden:

Noch besser waere nicht einzeilen-Strings zu verwenden, sondern die Datei in einem Rutsch zu lesen und dann zeilenweise drueberzuscannen (und Strings erst bei Bedarf zu erstellen), aber das haut wahrscheinlich nicht hin mit R.

 

[firespot]

Annahme n2~n1=n

Das kann nur der OP beantworten. In Post #1 schrieb er von 25 vs. 77 MB, von daher dann kann diese Näherung hinhauen oder auch nicht.

Einmal O(nlogn) fuers sortieren, und einmal fuers durchiterieren + passenden Eintrag finden
O(nlogn)+O(nlogn) = O(nlogn)

O(n2 log-n2) fürs in-place Sortieren von B
O(n1) fürs Durchiterieren über alle Zeilen von A (das Auffinden in B ist dann, bei sortiertem B, konstant)
macht: O(n2 log-n2 n1)

Die einsen (bzw. die noetigen Infos zur Identifizierung) in B in eine Hashmap packen

Aber das Erstellen der Hashmap für B kostet ja auch was!
Wenn ich einen neuen Container erstelle und die Elemente einfach 1:1 rüberkopiere, dann wäre die Komplexität O(n2) fürs Kopieren plus der overhead für das memory-management des neuen Containers. Für die Hashmap ist das Finden der Position für get/put O(1) (bester Fall) bis O(n2) (worst case); selbst im Idealfall landen wir damit nach wie vor noch bei O(n2) plus eben dem ganzen memory-management overhead. Und da die Hashmap eher viele memory-chunks alloziieren werden wird und memory allocation per se nicht billig ist, kann man den ganzen overhead nicht vernachlässigen.

Bei in-place Sortierung, also die Elemente in einem bestehenden Container umsortieren, ist die Komplexität O(n2 log-n2), dafür fällt der memory-management overhead weg. Und je nach Programmiersprache und Verfügbarkeit von einem move-constructor (wie in C++) können die einzelnen Verschiebeoperationen auch deutlich billiger sein als Kopieroperationen in einen neuen Container. Das führt aber schon sehr ins Detail und lässt sich schwer verallgemeinern.

Noch besser waere nicht einzeilen-Strings zu verwenden, sondern die Datei in einem Rutsch zu lesen und dann zeilenweise drueberzuscannen (und Strings erst bei Bedarf zu erstellen), aber das haut wahrscheinlich nicht hin mit R.

In R kann man schon den ganzen Dateiinhalt als einen einzigen string einlesen und nachher parsen. Dieses Parsen von einem Riesen-string würde aber in R ziemlich lästig/kompliziert werden.
Die "natürlichste" R-Lösung wäre, zuerst alle Zeilen einzulesen (readLines) und dann eine der Regex-Operationen (z.B. sub) vektorisiert über diese Zeilen loszulassen um die Strings in zeilenweises "Rest" und Passed zu splitten.


Bzgl. eines korrekt funktionierenden Programms ist die Hauptschwierigkeit, überhaupt die CSV-Struktur der Daten ausreichend zu berücksichtigen, inklusive der möglichen Sonderfälle. Ein Feld kann z.B. selbst Kommas beinhalten, wie in:

ID,Value,Text
102,3.141,"This is quoted text which, unfortunately, contains itself comma characters"

Man kann also nicht einfach pauschal beim n-ten Komma den string splitten. Und da Text-Felder natürlich auch wiederum selbst quotation-characters als Textelemente enthalten können, wie in:

ID,Value,Text
102,3.141,"This is quoted text which, unfortunately, mentions ""Mister X"" as quoted person"

muss man beim parsen von quotes auch das wieder berücksichtigen.

Wie sehr das ein Problem ist oder nicht hängt natürlich sehr von der Struktur der tatsächlichen Datei ab (können solche Fälle vorkommen? Sind, wenn Textfelder quotiert werden, ALLE quotiert oder ev. nur ein paar, z.B. diejenigen die wegen darin enthaltenen Kommas die Quotierung zwingend brauchen)?

Und beim Rückschreiben der neuen CSV-Datei spielt sich dasselbe in Grün ab: Es ist nicht so leicht hier sicherzustellen, dass bis auf Feld "Passed" alle anderen Characters exakt dieselben sind wie in der Ursprungsdatei sind.

Man könnte das so angehen:
a) Einmal die Datei als CSV-Einlesen -> die Spalten werden nun automatisch nach dem korrekten Komma gesplittet, aber aufgrund von Interpretation von Sonderzeichen stimmt der character-Inhalt der einzelnen gelesenen Felder ev. NICHT mehr mit der ursprünglichen character-Sequenz der entsprechenden Felder in der Rohdatei überein.
b) pro Zeile abzählen, wieviele Kommas insgesamt in Feldern vor und nach der Zielspalte (hier: "Passed") vorkommen - solche Kommas können z.B. wie oben illustriert in Textelementen vorkommen
c) Die Datei neu einlesen, diesmal zeilenweise als reiner (uninterpretierter) Text, und nun die Info aus b) nutzen um pro Zeile gezielt Spalte "Passed" rauszuextrahieren und den String vor/nach dieser Spalte exakt so zu belassen wie er ist (inklusive Sonderzeichen und Spalten-separatoren)
d) Daten matchen und bei Bedarf ersetzen, und die Felder aus c) zusammen mit dem aktualisierten "Passed"-Wert und ein Komma als Separator vor&nach dem Passed-Wert rausschreiben.

 

[KitKat::new()]

O(n2 log-n2) fürs in-place Sortieren von B
O(n1) fürs Durchiterieren über alle Zeilen von A (das Auffinden in B ist dann, bei sortiertem B, konstant)
macht: O(n2 log-n2 n1)

das macht keinen Sinn.
1. ist das Auffinden in B nicht konstant, wenn sortiert, sondern benoetigt log(n) pro Element, macht nlogn
2. Warum du die Komplexitaeten mulitplizierst, verstehe ich auch nicht, weil du ja nicht fuer jedes Element aus A B neu sortierst

Wenn ich einen neuen Container erstelle und die Elemente einfach 1:1 rüberkopiere, dann wäre die Komplexität O(n2) fürs Kopieren plus der overhead für das memory-management des neuen Containers.

Erhoeht also zumindest nicht die Komplexitaetsklasse und bleibt bei O(n) wie angegeben, zumal ich den Container gar nicht erstellen muss.
Meinte uebrigens gar keine Hashmap, sondern ein Hashset (macht eh nicht viel Unterschied)

Im Durchschnitt hat das Hashset auch O(1) im Schnitt pro Element (einfuegen und pruefen)

Bei in-place Sortierung, also die Elemente in einem bestehenden Container umsortieren, ist die Komplexität O(n2 log-n2), dafür fällt der memory-management overhead weg.

Man hat schon einen Haufen memory overhead ueberhaupt den Container zu erstellen.
Mit dem Hashset muss ich nur allokieren was ich benoetige statt den ganzen Datensatz.

Ich habs mal kurz ausprobiert:

Spoiler: Code

use std::collections::HashSet;
use csv::{Error, ByteRecord};

fn main() -> Result<(), Error> {
    let t0 = std::time::Instant::now();
    let set = read_hash_set("1000000 Sales Records.csv")?;
    println!("hash set created: {} {}", t0.elapsed().as_secs_f64(), set.capacity());
    let sorted_vec = read_vec("1000000 Sales Records.csv")?;
    println!("sorted_vector_created: {} {}", t0.elapsed().as_secs_f64(), sorted_vec.capacity());
    Ok(())
}

fn read_hash_set(file_name: &str) -> Result<HashSet<(Vec<u8>, Vec<u8>)>, Error> {
    let mut reader = csv::Reader::from_path(file_name)?;
    let mut set = HashSet::new();
    let mut record = csv::ByteRecord::new();
    while reader.read_byte_record(&mut record)? {
        set.insert((record[2].to_owned(), record[6].to_owned()));
    }
    Ok(set)
}

fn read_vec(file_name: &str) -> Result<Vec<csv::ByteRecord>, Error> {
    let mut reader = csv::Reader::from_path(file_name)?;
    let mut vec: Vec<ByteRecord> = reader.byte_records()
        .map(|r|r.unwrap())
        .collect();
    vec.sort_unstable_by(|a,b| a[0].cmp(&b[0]));
    Ok(vec)
}

hash set created: 1.0325959 917504
sorted_vector_created: 2.3941179 1048576

Macht bei mir geschaetzt im Schnitt etwa 30% Differenz alleine schon beim Einlesen der Map bzw. des sortierten Vektors (die Werte sind allgemein hoeher als zuvor, da auf 10 Jahre alten Rechner getestet).
Der Overhead durch den logn Lookup mit binary search (produziert wahrscheinlich auch einen Haufen Cache-Misses) kommt dann noch oben drauf

Zugegeben: Mit kleineren/anderen Datensaetzen koennte sich das Blatt wenden und es ist nicht garantiert, dass es bei seinen Daten nicht ploetzlich nur Hashcollisionen gibt, o.ae.

 

[firespot]

das macht keinen Sinn.
1. ist das Auffinden in B nicht konstant, wenn sortiert, sondern benoetigt log(n) pro Element, macht nlogn
2. Warum du die Komplexitaeten mulitplizierst, verstehe ich auch nicht, weil du ja nicht fuer jedes Element aus A B neu sortierst

Ja da hab ich mich vertan, und es sollte natürlich auch nicht multiplikativ sein.

Zugegeben: Mit kleineren/anderen Datensaetzen koennte sich das Blatt wenden und es ist nicht garantiert, dass es bei seinen Daten nicht ploetzlich nur Hashcollisionen gibt, o.ae.

Es hängt von allerlei ab, u.a. auch vom Containertyp selbst und natürlich den Daten. Ich kann kein Rust, aber zumindest in C++ wäre ein std::vector (zumindest ohne passendem vector::reserve) keine gute Wahl um effizient eine größere, unbekannte Menge an Daten einzulesen, weil es so natürlich ständig zu Neuallokationem samt Hin-und-Her Kopieren der Daten kommt.

 

[KitKat::new()]

Ich kann kein Rust, aber zumindest in C++ wäre ein std::vector (zumindest ohne passendem vector::reserve) keine gute Wahl um effizient eine größere, unbekannte Menge an Daten einzulesen, weil es so natürlich ständig zu Neuallokationem samt Hin-und-Her Kopieren der Daten kommt.

Rust ist nicht viel anders wie C++ (vector = vec)
Was waere deine Wahl?
Wenn du vorher nicht weisst wieviele Elemente du hast, ist das afaik das beste, das zur Verfuegung steht
(immerhin amortisiert O(1) beim einfuegen)

Man koennte jetzt sagen, dass man davon ausgeht, dass man weiss wieviele Elemente hat, aber das kann man beim Hashset auch 😉

 

[firespot]

C++ ist nicht viel anders wie C++ (vector = vec)
Was waere deine Wahl?
Wenn du vorher nicht weisst wieviele Elemente du hast, ist das afaik das beste, das zur Verfuegung steht
(immerhin amortisiert O(1) beim einfuegen)

Als erster std-container fällt mir std::deque ein, der beim einfügen am Ende linear in der Anzahl der hinzugefügten Elemente ist (und, eine halbwegs intelligente Implementierung angenommen, auch nur gelegentlich neue memory-chunks alloziieren muss).

Ein anderer Ansatz wäre std::vector, aber probieren die Gesamtgröße intelligent zu schätzen und ein passendes std::reserve zu setzen. Man könnte z.B. die gesamte Dateigröße in Relation zu den bytes der sagen wir ersten 1000 Zeilen setzen, und so die vermutete Zeilenzahl / Endgröße des vectors hochrechnen (+ etwas dazu als Buffer) um möglichst früh ein gut geschätztes vector::reserve zu machen.

 

[KitKat::new()]

Als erster std-container fällt mir std::deque ein, der beim einfügen am Ende linear in der Anzahl der hinzugefügten Elemente ist (und, eine halbwegs intelligente Implementierung angenommen, auch nur gelegentlich neue memory-chunks alloziieren muss).

guter Vorschlag, nun zwischen 10-20% (eher 20) (haette ich bestimmt schon brauchen koennen 😀)

hash set created: 1.1479792 917504
sorted_vector_created: 2.5156799 1048575

Unterschied zum vorallokierten Vektor (1001000 Eintraege): innerhalb vom Rauschen (beim Set hab ichs nicht getestet)

 

[BeBur]

Hat jemand gute Beispiel Daten generiert und kann die Online stellen? Dann bau ich nachher noch eine Julia Implementierung .

 

[KitKat::new()]

Hat jemand gute Beispiel Daten generiert

Hat bisher jeder verwendet

Mit den Testdaten aus on http://eforexcel.com/wp/downloads-18-sample-csv-files-data-sets-for-testing-sales/ 1.000.000 Zeilen

 

[T_55]

Als erster std-container fällt mir std::deque ein,

Jes wollte ich auch gerade schreiben, ein sehr feiner Container für solche Anwendungsfälle der auch Stärken aus der nicht-sequenziellen Welt mitbringt.

ps: meine zu Beginn beschriebene "Performance-Vorgehensweise" der Speicherung von Daten auf der Platte, also Binäre Daten in Chunks abzulegen, ist nämlich konzeptionell gesehen nichts anderes als ein persitentes std::deque.
https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl/6292437#6292437