Homeserver Forum

Hier eine Frage an die aktiven Programmierer unter euch ... vielleicht hat ja jemand eine Idee für einen effizienten Algorithmus

Ich habe einen Indexbereich von 0 bis MaxIndex und möchte ermitteln, wie viele der vorhandenen Indices einmal und wie viele mehrfach verwendet werden.

Wenn es sich jetzt hier um "normale" Größenordnungen handeln würde hätte ich mehrere Lösungen ... ABER: MaxIndex liegt z.Zt. bei 1,5 Milliarden und die Listen mit den Indices enthalten zwischen einigen Tausend und 180 Millionen Einträge ... und das Ganze muss auf einem Rechner mit 32-Bit Windows laufen

Ich würde da einen MS SQL Express Server verwenden.

Nobby1805 hat geschrieben:Hier eine Frage an die aktiven Programmierer unter euch ... vielleicht hat ja jemand eine Idee für einen effizienten Algorithmus

Ich habe einen Indexbereich von 0 bis MaxIndex und möchte ermitteln, wie viele der vorhandenen Indices einmal und wie viele mehrfach verwendet werden.

Wenn es sich jetzt hier um "normale" Größenordnungen handeln würde hätte ich mehrere Lösungen ... ABER: MaxIndex liegt z.Zt. bei 1,5 Milliarden und die Listen mit den Indices enthalten zwischen einigen Tausend und 180 Millionen Einträge ... und das Ganze muss auf einem Rechner mit 32-Bit Windows laufen

Runden wir mal etwas auf.. 2GBit brauchst Du für einen Bitvektor mit der Information ob ein Index vorkommt, weitere 2GBit für "mehrfach", macht zusammen 4GBit oder 0,5GByte und ist kein Problem mit 32Bit! Wenn die Speicherverwaltung keine so großen Blöcke liefert, dann musst Du halt segmentieren, z.B. auf 64KB, aber dafür brauchst Du auch nur 0,5GB/64KB 4Byte Pointer oder 4KB - fast vernachlässigbar. Wenn Du (wie mein Ace) nur 2GB RAM hast, dann ist vermutlich Threshing angesagt, dürfte aber allemal besser performen als

larry hat geschrieben:Ich würde da einen MS SQL Express Server verwenden.

Richtig problematisch wird es erst wenn Dein Maxindex die Größenordnung 4 * [maximal für diesen Zweck allokierbarer (freier) Speicher in Bytes] überschreitet.
Oder wo hab ich jetzt einen Denkfehler?
Gruß Joachim

Hallo Joachim,

Das war im Prinzip auch mein erster Ansatz, bin dann aber daran gescheitert, dass bei einem "Array of Boolean" für ein Boolean ein ganzes Byte verwendet wird inzwischen habe ich gefunden, dass es in .Net die BitArray Klasse gibt ... Mal schaun wie dort die Performance ist, ich werde berichten