Fun-Soft - Programmierforum

Autor

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

000
16.01.2009, 08:35 Uhr
~ANGs_Pino
Gast

Hey zusammen,

ich habe einen std::vector< int > mit ca. 100000000 (100*10^6) Einträgen. die bestehen jedoch aus ca. 400000 (4*10^5) verschiedenen Zahlen. Und alle doppelt vorhandenen sollen gelöscht werden (nein, der vektor ist nicht sortiert).

Ich suche keinen Code, der nur das problem löst, er soll auch extrem schnell sein

bisher habe ich zwei möglichkeiten ausprobiert

1) vektor V von anfang bis ende durchsuchen.
für jede gefundene Zahl: Vergleich mit Buffer B.
wenn Zahl in buffer, nächste Zahl.
wenn nicht in Buffer, dann hinzufügen und nächste zahl.

...dauert ewig.

2) vektor in chunks zerlegen und daraus eine liste machen.
solange liste nicht leer
erstes element in Buffer, lösche alle listeneinträge jit dem gleichen wert.
hinterher die einzelnen chunks zusammenbauen (und nach evtl. doppelten einträge suchen

)

...dauert auch laaaange

eine Idee von euch wär fett!

ANGs_Pino

Profil || Private Message || Suche

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

001
16.01.2009, 09:11 Uhr
ao

(Operator)

100 Millionen Zahlen, aber nur 400.000 verschiedene, d.h. jeder Wert kommt im Mittel 250-mal vor. Alle Wiederholungen sollen gelöscht werden, so dass am Ende ein Vektor mit 400.000 *verschiedenen* Elementen steht. Richtig verstanden?

Müssen die Wiederholungen *aus dem Originalvektor entfernt* werden? Dafür ist std::vector nicht der passende Container (vector = zusammenhängender Speicher, Element löschen bedeutet: alles, was dahinter kommt, wird ein Feld nach vorne kopiert), und darum dauert das auch so ewig. std::list wäre besser.

Oder darf auch ein neuer Ergebnisvektor angelegt werden, in den jede Zahl *genau einmal* eingefügt wird? Auch für diesen würde man besser std::list als std::vector nehmen - fürs Einfügen gilt im Prinzip dasselbe wie fürs Löschen. Und diese Liste gleich sortiert aufbauen, das beschleunigt die Prüfung, ob eine Zahl schon enthalten ist.

Es gibt auch std::set (Menge - jedes Element kann nur einfach enthalten sein) - könnte sein, dass dir das diesen Test gleich abnimmt.

Profil || Private Message || Suche

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

002
16.01.2009, 09:16 Uhr
~ANGs_Pino
Gast

Zitat von ao:

exakt!

Zitat von ao:

Müssen die Wiederholungen *aus dem Originalvektor entfernt* werden? Dafür ist std::vector nicht der passende Container (vector = zusammenhängender Speicher, Element löschen bedeutet: alles, was dahinter kommt, wird ein Feld nach vorne kopiert), und darum dauert das auch so ewig. std::list wäre besser.
Oder darf auch ein neuer Ergebnisvektor angelegt werden, in den jede Zahl *genau einmal* eingefügt wird? Auch für diesen würde man besser std::list als std::vector nehmen - fürs Einfügen gilt im Prinzip dasselbe wie fürs Löschen. Und diese Liste gleich sortiert aufbauen, das beschleunigt die Prüfung, ob eine Zahl schon enthalten ist.

Prinzipiell egal, wo sie landen oder ob gelöscht wird. Problem: eg mal ne liste mit 100 000 000 Einträgen an, da brauchst du deutlich mehr RAM als beim vektor.

Zitat von ao:

Es gibt auch std::set (Menge - jedes Element kann nur einfach enthalten sein) - könnte sein, dass dir das diesen Test gleich abnimmt.

*nachschau*.

hast du ne lösungsidee mit vektoren / listen?

Profil || Private Message || Suche

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

003
16.01.2009, 09:54 Uhr
ao

(Operator)

Zitat von ~ANGs_Pino:

Problem: eg mal ne liste mit 100 000 000 Einträgen an, da brauchst du deutlich mehr RAM als beim vektor.

Ja und? Über RAM redet man nicht, das hat man, oder man kauft es sich.

Wenn du *schnell* einfügen und löschen willst, ist eine Liste der Container der Wahl. Der Speicherverbrauch ist der Preis für die Geschwindigkeit.

Außerdem: Leg mal einen Vektor mit N Einträgen an und vergrößer den um 1 Element - das braucht auch vorübergehend die doppelte Menge, wenn der Vektor einen neuen Block holt und den Inhalt umkopiert und erst dann den alten freigibt.

Zitat:

hast du ne lösungsidee mit vektoren / listen?

Die Idee hab ich schon genannt, siehe oben. Eine fertige Lösung hab ich nicht, die machst du selber.

Profil || Private Message || Suche

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

004
16.01.2009, 10:25 Uhr
Lensflare

Vielleicht lohnt es sich den ursprungscontainer vorher zu sortieren. Zum Beispiel mit Merge-Sort in O(n*log(n)).
Und dann braucht man nur über den container zu iterieren, denn die gleichen Zahlen stehen dann ja nebeneinander. Das geht in O(n).

Wäre immer noch besser als für jede Zahl den Container nach einer gleichen Zahl zu durchsuchen. O(n^2)

Aber immer noch den Hinweis von ao beachten!
--
Wenn das Gehirn so einfach wäre, dass wir es verstehen könnten, wären wir so einfach, dass wir es nicht verstehen könnten.
(Emerson Pugh Trost)

Dieser Post wurde am 16.01.2009 um 10:28 Uhr von Lensflare editiert.

Profil || Private Message || Suche

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

005
16.01.2009, 11:27 Uhr
~jencas
Gast

Kannst Du nicht statt vector ein set benutzen, dann löst sich das Problem der Doppelten von alleine?

Profil || Private Message || Suche

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

006
16.01.2009, 12:28 Uhr
rapso

du hast also 400MB fuer den vector zZ.

wenn du noch ein wenig mehr opfern kannst, ginge das ganze recht schnell.

1.du legst einen vector an bei dem jedes bit einen moeglichen wert representiert. (also 512MB).
2. am anfang einmal alles auf 0 setzen.
3. simpler loop:
for a=0,b=0;a<vector.size;a++
if(!(BitVector[vector[a]>>3]&(1<<(vector[a]&7))))
{
vector[b++]=vector[a].
BitVector[vector[a]>>3]|=1<<(vector[a]&7);
}
in worten. du gehst jede stelle vom vector durch, pruefst das bit des wertes im BitVector ab ob die zahl schonmal vorhanden war, falls nicht, setzt du das bit und kopierst an stelle b die neue zahl und setzt b auf das naechste feld.

am ende noch ein vector.resize(b); und du bist fertig.

mit ein wenig optimierungen sollte das auf jedem pc in weit unter 5s durchlaufen schaetze ich.

einzig kritisch waeren die random zugriffe auf den 512MB bitvector

cheers

btw. das ist nur pseudocode, der muss nicht schoen sein

Profil || Private Message || Suche

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

007
16.01.2009, 14:23 Uhr
~Shade
Gast

Zitat von ao:

[quote ~ANGs_Pino]Problem: eg mal ne liste mit 100 000 000 Einträgen an, da brauchst du deutlich mehr RAM als beim vektor.

Ja und? Über RAM redet man nicht, das hat man, oder man kauft es sich.

Wenn du *schnell* einfügen und löschen willst, ist eine Liste der Container der Wahl. Der Speicherverbrauch ist der Preis für die Geschwindigkeit.
[/quote]
vector::push_back ist um dimensionen schneller als list::push_back

Hier ist vector genau das richtige.
Passendes reserve() und man hat wenn man Pech hat eine reallokation.

Idealer wäre natürlich ein Fast-Growing-Stack wie zB diese naive Implementierung hier: www.codeproject.com/KB/architecture/fast-stack.aspx

Profil || Private Message || Suche

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

008
16.01.2009, 14:58 Uhr
rapso

Zitat von ~Shade:

Idealer wäre natürlich ein Fast-Growing-Stack wie zB diese naive Implementierung hier: [url]http://www.codeproject.com/KB/architecture/fast-stack.aspx

[/url]
idealer als std::vector mit einem reserve? garantiert nicht!

Profil || Private Message || Suche

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

009
16.01.2009, 15:21 Uhr
ao

(Operator)

Zitat von ~Shade:

vector::push_back ist um dimensionen schneller als list::push_back

Wenn der Speicher schon reserviert ist. Wenn nicht, dann nicht.

Außerdem gehts hier nicht um push_back, sondern um Einfügen und Löschen an beliebigen Stellen, das heißt bei Listen nur Umhängen von Listen-Items, bei Vektoren aber Umkopieren von allem, was dahinter noch kommt. Das ist garantiert nicht "um Dimensionen schneller".

Zitat:

Passendes reserve()

Wieviel ist "passend"? Weiß man das im Voraus? Ich glaube nicht.

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: