schnellster dynamischer array?

MamboKurt

Ahoi,
Ich hab eine Frage. Nix Exotisches. Es geht nur darum, dass ich Daten generiere, aber vorher nicht weiß wieviele. das Problem ist, dass die Anzahl dieser daten sehr schnell wächst mit der Dimension. Eine kleine Abschätzung ist A_n = A_n-1 *(10+5n), wobei A_0 = 6. Für n=7 ist das schon 22.985.512.
Bei den daten handelt es sich immer um n Pointer, also A_n mal n Pointer.
Welches ist nun die effektivste/schnellste Methode diese festzuhalten.

Ich bin für alle vorschläge offen.
(Das Problem ist absichtlich so vage formuliert, da ich noch keine Ahnung hab, wie ich an die Sache ran gehen soll, oder ober ich da vielleicht was aus der STL nehmen soll.

EDIT: natürlich sollte das Einfügen, aber vor allem der Zugriff schnell sein.

mfg
MamboKurt

Nexus

Wahrscheinlich fährst du mit std::vector nicht schlecht. Die MSVC++-Implementierung verdoppelt den Speicherbereich zum Beispiel bei jeder Reallokation. Zusätzlich könntest du mit reserve() und deiner Abschätzung etwas nachhelfen.

Allerdings solltest du darauf achten, dass max_size() bei grossen Zahlen überschritten werden könnte. Vielleicht vorher abfragen...

knivil

Du kannst auch erstmal eine Liste fuer die Generierung der Daten benutzen und dann fuer die weitere Verarbeitung in ein std::vector kopieren. Da du aber das Problem zu vage haelts, ist alles irgendwie nur raten, was fuer dich am besten ist ... Eine Problembeschreibung waere hilfreich (nein, damit meine ich keine moegliche Implementationsbeschreibung oder Probleme die bei solcher auftreten).

MamboKurt

was ich dann mit der daten machen will sieht ungefähr so aus:

for A in DATEN
    for B in DATEN
        // CRAZY SHIT

ich muss also für alle zweierpaare in DATEN was anstellen.

Ich würde std::vector nehmen

knivil

Also moechtest du fuer alle Paare in Daten irgendwas machen. Angenommen n=7 und deine Abschaetzung ist gut und du hast etwa 22*10^6 Elemente. So wird crazy shit also etwa 48*10^13 mal aufgerufen. Weiter angenommen crazy shit benoetigt 100 Takte und du hast einen 2 GHz Prozessor. Dann brauchst du fuer die Berechnung etwa
24*10^6 Sekunden oder 6666 Stunden oder 277 Tage.

Sorry, dein Problem wird nicht ueber ein schnelles dynamisches Array geloest.