Großes Array mit 0ern überschreiben - memset zu langsam

[testo]

Hallo,

ich habe Arrays die sehr groß werden können (10^6 und größer). Diese möchte ich muss/will ich in einer schleife ständig komplett mit Nullern überschreiben. Laut meinem Profiling geht da sehr sehr viel Zeit verloren - memset braucht da einfach zu lang. Gäbe es eine alternative? Oder muss ich mir ernsthafte gedanken an meinen algorithmen machen?

Danke

[pumuckl]

testo schrieb:

Hallo,

ich habe Arrays die sehr groß werden können (10^6 und größer). Diese möchte ich muss/will ich in einer schleife ständig komplett mit Nullern überschreiben. Laut meinem Profiling geht da sehr sehr viel Zeit verloren - memset braucht da einfach zu lang. Gäbe es eine alternative? Oder muss ich mir ernsthafte gedanken an meinen algorithmen machen?

Danke

Ne Alternative wäre die C++-Variante vom C-Style memste, nämlich std::fill. Allerdings bezweifle ich dass das schneller ist.
Du solltest da wohl eher deine Algorithmen überdenken, insbesondere wieso es nötig sein soll, das Array ständig zu nullen (wenn dus danach scheinbar gleich wieder beschreibst, sonst würde einmal nullen ja reichen).
Wenn du uns ein wenig Kontext verrätst kann dir vielleicht geholfen werden

[testo]

ich hab vergessen dazuzusagen dass es keine c++ -arrays sind. Von daher ist mein post wohl im c++ forum fehl am platz. Ich benutze im moment reine int* arr. Also keine vectoren oder ähnliches...

[pumuckl]

testo schrieb:

ich hab vergessen dazuzusagen dass es keine c++ -arrays sind. Von daher ist mein post wohl im c++ forum fehl am platz. Ich benutze im moment reine int* arr. Also keine vectoren oder ähnliches...

Auch unter C++ gibts Arrays, ganz ohne vector & Co.

[knivil]

Wenn du mehr Informationen rausruecken wuerdest, dann kann dir vielleicht geholfen werden ...

Wozu dienen denn Arrays der Groesse 10^6? Und wie wird mit ihnen gearbeitet?

[testo]

ok - ich versuche darzustellen was der subcode macht.

ich habe eine unterschiedliche anzahl an arrays die jeweils eine unterschiedliche anzahl an indizes tragen. Die Länge jedes einzelnen arrays habe ich separat in einem anderen array gespeichert. Ich möchte jetzt für diese gegebenen arrays eine Indexmenge erstellen (ein array) welches mir sozusagen die vereinigung aller indizes der arrays darstellt.

Bsp:
arr1 = 0,1 ->len=2
arr2 = 2,4 ->len=2
arr3 = 1,2,4->len=3

ergebnis wäre: arr_erg = 0,1,2,4

Jedes der arr* kann maximal eine größe von m haben. Somit kann auch arr_erg maximal m groß werden.

Ich mache es grob so dass ich am Anfang ein boolsches array (arr_map) bereitstelle welches die dimension m hat. Ich laufe jedes arr* ab und dann auch jeden Index und falls in arr_map noch nicht gesetzt ist dann wird hier ein true-value gesetzt und der Index in arr_erg geschrieben. Falls da schon ein true-wert drin steht wird einfach zum nächsten Index gesprungen.

Damit entsteht aber das Problem dass ich im Falle das m groß ist (10^6 z.B.) ich zuerst ein riesieges arr_map baue obwohl es sein kann das die arr* nur sehr klein sind.

Ein Ansatz wäre irgendwie ein pre-processing schritt zu machen und festzustellen wie groß mein arr_map maximal sein wird. Und erst dann die Index-Arrays zu vereinigen. Evtl. gäbe es auch eine Alternative mit einem dictionary oder ähnlichem - C++ - Mittel sind ja erlaubt - ist ein C++-code.

[rean]

Was genau hält dich davon ab ein std::set zu verwenden?

Das überprüft eigenständig ob ein Wert bereits vorhanden ist und wenn du das ganze unbedingt als im Speicher zusammenhängendes Array brauchst schreibst dus am schluss mit std::copy in einen std::vector.

[knivil]

Die Datenstruktur "Array" ist fuer dein Problem ungeeignet.

[testo]

hmm ja - kann sein. Angenommen wir würden in C programmieren müssen (ich weiß dass wir im c++ forum sind). Was wäre dann hier eine performante alternative?

[knivil]

Man wuerde sich std::set in C nachbauen. Alternativ kannst du auch eine fertige Implementation eines RB-Tree's nehmen.

[volkard]

ein binärbaum wäre üblich und sehr schnell. eine hashtable wäre vermutlich noch schneller. wenn ich das machen sollte, würde ich es zum anlaß nehmen, mal eine cuckoo-hashtable zu basteln.

außerdem besteht ernsthaft die frage, warum du das array überhaupt dauern nullen mußt.
du benutzt es doch als bit-array. machst du einfach nur zu programmstart einmal nullsetzten. außerdem setzt du die globale zeit auf 0.

ein indexmengenvereinigungszähldurchlauf ist ja dann ungefähr so:

++globaleZeit;
int result=0;
for each a in zuBetrachtendeIndexmengen
{
  for each i in a
  {
    if feld[i]!=globaleZeit
    {
      feld[i]=globaleZeit;
      ++result;
    }
  }
}
return result;

und du brauchst im lauf keine nullsetzungen mehr. ok, beim überlauf. also den noch schnell wegmachen.

static globaleZeit=0;
static short* feld=malloc...
if(globaleZeit==0)
  for(hierDochMalFeldNullsetzen
++globaleZeit;
...
rest wie gehabt;

mit short brauchst du dann nur alle 65535 durchläufe einmal das feld zu nullen. dürfte selten genug sein. ich vermute, das macht jede baum- oder hasttable-geschichte platt und ist dazu noch total einfach programmiert.

[knivil]

indexmengenvereinigungszähldurchlauf