Fun-Soft - Programmierforum

Autor

Thread - Seiten: [ 1 ] > 2 < [ 3 ] [ 4 ] [ 5 ]

010
16.01.2009, 15:42 Uhr
~krrronos
Gast

@raspo: Wie mapst du auf Bits?

Ich würde entweder sortieren und dabei doppelte markieren und nachher filtern oder durchlaufen und in ein set inserten. Komplexität ist die selbe (n log n).

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

011
16.01.2009, 15:48 Uhr
0xdeadbeef
Gott
(Operator)

Performancetechnisch dürfte das wichtige hier sein, die Überprüfung auf doppelte Einträge möglichst schnell zu halten. Die 100 Millionen Einträge wirst du durchlaufen müssen, und üblicherweise veranschlagt man für Suchaufgaben log(n), also peilen wir erst mal n * log(n) als Laufzeit an.

Die einfachste Möglichkeit, das hinzukriegen ist std::set, wie es hier schon angemerkt wurde. Das liefe dann schlicht auf

C++:

std::vector<int> v(100000000);

// v mit Elementen füllen

std::set<int> s(v.begin(), v.end());

...natürlich wäre zu überlegen, ob du statt des Vektors nicht gleich das set bevölkern willst, aber um das zu beurteilen, kenne ich deinen use case nicht gut genug.

Ansonsten, wenn vorher abschätzen kannst, wie viele eindeutige Elemente übrig bleiben, bietet sich unordered_set an, sofern dein Compiler die TR1-Bibliothekserweiterungen unterstützt. In diesem Fall liefe das etwa auf

C++:

std::tr1::unordered_set<int> us(v.begin(), v.end(), 500000);

hinaus. 500000, weil du 400000 Elemente erwartest, und ein bisschen Luft zur Kollisionsvermeidung lassen willst. Ich gehe davon aus, dass, wenn du schon 400MB für den Vektor aufbringen kannst, ein paar hundert Kilobyte mehr für die Hashtable nicht weiter ins Gewicht fallen. Und wie das mit Hashtables so ist, je nach erwarteter Verteilung der Werte kann es sinnvoll sein, einen eigenen Hash dafür zu schreiben.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 16.01.2009 um 15:49 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

012
16.01.2009, 16:02 Uhr
rapso

Zitat von ~krrronos:

@raspo: Wie mapst du auf Bits?

Ich würde entweder sortieren und dabei doppelte markieren und nachher filtern oder durchlaufen und in ein set inserten. Komplexität ist die selbe (n log n).

du hast ja gesagt, dass jede zahl nur einmal vorkommen soll, deswegen map ich anhand der zahl (also dem eintrag im urspruenglichen array) im bitarray

int index = vector[...];

/8, weil du 8 bit pro byte hast
&7 weil du damit dann in den bits indizieren kannst.

mit
Bitarray[Index/8]&(1<<(Index&7));
fragst du ein bit ab

mit
Bitarray[Index/8]|=1<<(Index&7)
setzt du ein bit.

mehr brauchst du nicht.

laufzeitverhalten duerfte O(n) sein.

Dieser Post wurde am 16.01.2009 um 16:04 Uhr von rapso editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

013
16.01.2009, 17:16 Uhr
0xdeadbeef
Gott
(Operator)

Naja, um doppelte zu markieren, musst du wissen, dass sie doppelt sind. Das Problem, in das du da unweigerlich läufst, ist, dass du einen großen Haufen RAM brauchst. Auf einer 32-Bit-Maschine sind das schon 512MiB, zusätzlich zu den 400MB, die der Vektor frisst und der unbekannten Größe, die der Zielcontainer fressen wird - das wird schon schwierig, aber jetzt stell dir mal vor, das ganze liefe auf einer 64-Bit-Maschine. Außerdem, selbst wenn du genug Speicher hast, ändert sich dein Laufzeitverhalten dramatisch; anstatt O(n * log(n)) oder O(n) mit der Menge der Elemente skalierst du linear mit der Menge der möglichen Werte, bzw. exponentiell mit der Registerbreite der Maschine. Jedenfalls theoretisch; je nachdem, wie der Kernel sein Paging etc. implementiert, kann dabei im Endeffekt alles mögliche rauskommen. Nur schneller wird es nicht.

Ich kann jetzt nicht beurteilen, wie sich die Menge der eingelesenen Werte zur Registerbreite der Maschine verhält, sofern überhaupt ein Zusammenhang besteht. Aber dass dabei am Ende ein Geschwindigkeitsgewinn rauskommen soll, scheint mir unrealistisch.

Du könntest wohl vorher das Array durchlaufen, um den kleinsten und größten Wert zu ermitteln und deine Bitmaske entsprechend zu dimensionieren; damit kämst du zumindest auf eine bessere, wenn auch schwieriger auszuklamüsernde Laufzeit (abhängig sowohl von der Menge der Elemente als auch ihrer Streuung), aber eine Hashtable scheint mir doch der sinnvollere Weg.

Allerdings...bei solchen Datenmengen scheint mir eine Datenbank langsam schon sinnvoll.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 16.01.2009 um 17:20 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

014
16.01.2009, 17:22 Uhr
kronos
Quotenfisch
(Operator)

Zitat von rapso:

du hast ja gesagt, dass jede zahl nur einmal vorkommen soll, deswegen map ich anhand der zahl (also dem eintrag im urspruenglichen array) im bitarray

Das kann je nach Platform ziemlich ausarten. sizeof(int)==4 ist da die Obergrenze: Da wird Vektor über 500 MB groß.

Bearbeitung:

Verlesen...

--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Dieser Post wurde am 16.01.2009 um 17:28 Uhr von kronos editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

015
16.01.2009, 17:27 Uhr
kronos
Quotenfisch
(Operator)

Zitat von 0xdeadbeef:

Außerdem, selbst wenn du genug Speicher hast, ändert sich dein Laufzeitverhalten dramatisch;

Der Speicherverbrauch - nicht unbedingt die Laufzeit (wenn man von der Speicherverwaltung mal absieht). Der Bit-Vektor wird ja nicht durchlaufen, sondern nur zum Zahlen Testen verwendet.

Wollten wir einen Performance-Contest mit Pino als Schiedsrichter machen?
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Dieser Post wurde am 16.01.2009 um 17:29 Uhr von kronos editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

016
16.01.2009, 17:32 Uhr
0xdeadbeef
Gott
(Operator)

Hmm...ach ja, richtig. Ich war grad irgendwie auf dem Holzdampfer, dass er das erst sieben wollte, um später das Array nach gesetzten bits zu durchlaufen.

Gut, aber das ist auch nur unter sehr bestimmten Bedingungen realistisch. Und genau für sowas gibt es ja Hashtables.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

017
16.01.2009, 17:39 Uhr
kronos
Quotenfisch
(Operator)

Glaube fast, Sortieren ist schneller als die Hasherei...
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

018
16.01.2009, 17:45 Uhr
0xdeadbeef
Gott
(Operator)

Die Hasherei läuft bei vernünftigem Hash in O(n). Sortieren frisst O(n * log(n)). Bei 100 Millionen Elementen macht das schon einen großen Unterschied, davon ist auszugehen.

Die wesentliche Frage hier ist, wie gut sich die Elemente hashen lassen, also ob ein Verteilungsmuster bekannt ist.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 16.01.2009 um 17:46 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

019
19.01.2009, 14:40 Uhr
~raps
Gast

Zitat von 0xdeadbeef:

Die wesentliche Frage hier ist, wie gut sich die Elemente hashen lassen, also ob ein Verteilungsmuster bekannt ist.

fuer einen sicheren hash brauchst du n*n als bitbreite, wobei n die bitzahl der moeglichen eintraege ist, also 250 000, ergo 36bit.
ansonsten ist es eine weak-hashtable die entsprechend buckets braucht, laufzeit ist somit O(n*log(n)).

eine bit-table ist hingegen linear O(n). fuer den fall vom threadstarter ist das die schnellste loesung. wie sich das hypotetisch unter anderen bendingungen verhaellt ist fuer diesen thread glaube ich nicht so sehr relevant. ich hab lediglich eine problemorientierte loesung vorgeschlagen.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: [ 1 ] > 2 < [ 3 ] [ 4 ] [ 5 ] [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: