Effizienter Algorithmus

Eigener Bereich für die Entwickler unter uns! Add-Ins, aber auch andere Programme.
Antworten
Benutzeravatar
Nobby1805
Moderator
Beiträge: 21372
Registriert: 6. Jun 2009, 17:40
Wohnort: Essen

Effizienter Algorithmus

Beitrag von Nobby1805 »

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
WHS:inzwischen abgeschaltet Acer H340 mit 1x 1 TB (WD10EAVS), 3x 2 TB (2 WD20EARS und 1 ST2000DM001), PP3+UR2
Server:
Intel Celeron J3455 auf Gigabyte Board, Win 10 Pro x64 21H2, 640 GB (System), 16 TB (Backup), 4 TB (Daten), Lindenberg Backup und LightsOut 3
5 Clients:
1 Intel i5-4670K, ASUS H87-PRO, 32 GB, 250 GB SSD, 2x 500 GB, Win 10 Pro x64 21H2
1 Lüfterlos fürs Wohnzimmer, Intel Celeron N4100, 4 GB, 128 GB, Win 11 Pro x64 21H2
1 AMD Ryzen 7 3700X, Gigabyte AORUS, 32 GB, Win 10 Pro x64 2009
1 Sony Vaio EB 2H4E, Win 10 Home x64 2009
1 Samsung NP-R540-JS09DE, Win 10 Pro x64 2009


WHSListTombstones, ein Tool zur Auflistung aller Tombstones
WHSDisks, ein Tool zur Darstellung und Prüfung der DriveExtender-Konfiguration
WHSDiskNames, ein Tool zur Änderung der Plattennamen in der Konsole
WHSBackup, Infos und Tool zur Backup-DB (2011-Version (auch für WSE2012))
Bitte schreibt bei Fragen und Problemen eure Konfig in die Signatur
Benutzeravatar
larry
Moderator
Beiträge: 9998
Registriert: 22. Dez 2007, 16:13

Re: Effizienter Algorithmus

Beitrag von larry »

Ich würde da einen MS SQL Express Server verwenden.
Hauptserver: Intel I3-2100, MSI H67MA-E45, WHS 2011
System: Corsair Force GT 90GB - Datenplatten: 2*Seagate 3TB + ext. WD 500 GB für Serversicherung(nur System),8 GB Ram, Fractal Design R3, be quiet! L7-300W, 2*Digital Devices cineS2(Mediaportal)
Archivserver: Intel Cel.G530, Intel DB65AL, WHS 2011, Drivebender
System: SamsF4 320GB - Datenplatten: 5*2TB SamsF4. + VHD für Serversicherung(nur System), 4 GB Ram, Lancool K-11X, be quiet! L7-300W
Backupserver: AMD Athl. X2 4850e, Gigabyte GA-MA780G-UD3H, 3*Asrock SATA3 + 1* DeLOCK 70154 SATA Controller, WHS 2011, Drivebender
System: SamsF4 320 GB - Datenplatten: 15 diverse Platten + VHD für Serversicherung(nur System) ,4 GB Ram, Seasonic ss 330 Watt
Router: AVM FRITZ!Box 7270, Kabel Deutschland
Clients: 2* HTPC, Win7 HP 32 Bit - 2*Arbeitsrechner Win7 HP 64 Bit - 1*Laptop Win7 HP 32-Bit
JoachimL
WHS-Experte
Beiträge: 1228
Registriert: 21. Sep 2009, 22:48

Re: Effizienter Algorithmus

Beitrag von JoachimL »

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
WHS r.i.p. - Software die nicht mehr gewartet wird sollte man nicht mehr einsetzen.
Bei mir laufen drei Dell T20, inzwischen alle unter Hyper-V-2019. Darauf viele virtuelle Maschinen, darunter Windows 10 Pro, Ubuntu 18.04/20.04 LTS (teilweise mit Docker), und auch mal andere. Ein T20 läuft 7*24 und stellt u.a. Mailcow-Dockerized und einen Samba-Domain-Controller (ein 2. läuft auf einem NUC) bereit. Klingt vielleicht seltsam, aber so ist das System - alle - mit Bitlocker verschlüsselt und kann vollständig und konsistent gesichert werden - beides sonst unter Linux schwierig bis unmöglich. Zum Sichern dient das von mir entwickelte Lindenberg Software Backup.
Fragen bitte nicht per PN sondern im Forum - dann haben andere auch was davon. Ich poste hier in meiner Freizeit, Ungeduld ist meiner Meinung nach fehl am Platz...
Benutzeravatar
Nobby1805
Moderator
Beiträge: 21372
Registriert: 6. Jun 2009, 17:40
Wohnort: Essen

Re: Effizienter Algorithmus

Beitrag von Nobby1805 »

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
WHS:inzwischen abgeschaltet Acer H340 mit 1x 1 TB (WD10EAVS), 3x 2 TB (2 WD20EARS und 1 ST2000DM001), PP3+UR2
Server:
Intel Celeron J3455 auf Gigabyte Board, Win 10 Pro x64 21H2, 640 GB (System), 16 TB (Backup), 4 TB (Daten), Lindenberg Backup und LightsOut 3
5 Clients:
1 Intel i5-4670K, ASUS H87-PRO, 32 GB, 250 GB SSD, 2x 500 GB, Win 10 Pro x64 21H2
1 Lüfterlos fürs Wohnzimmer, Intel Celeron N4100, 4 GB, 128 GB, Win 11 Pro x64 21H2
1 AMD Ryzen 7 3700X, Gigabyte AORUS, 32 GB, Win 10 Pro x64 2009
1 Sony Vaio EB 2H4E, Win 10 Home x64 2009
1 Samsung NP-R540-JS09DE, Win 10 Pro x64 2009


WHSListTombstones, ein Tool zur Auflistung aller Tombstones
WHSDisks, ein Tool zur Darstellung und Prüfung der DriveExtender-Konfiguration
WHSDiskNames, ein Tool zur Änderung der Plattennamen in der Konsole
WHSBackup, Infos und Tool zur Backup-DB (2011-Version (auch für WSE2012))
Bitte schreibt bei Fragen und Problemen eure Konfig in die Signatur
Antworten