C++ mit welchem Prozessor

Hi, vieleicht kann euch das mein problem verdeutlichen:

ich habe zwei vektoren. der eine hat 14 milionen zeilen, der andere 18 tausend.

jetzt muss ich jede einzelne zeile des ersten vektor mit jeder zeile des zweiten vektors vergleichen. dann das ergebnis auswerten. halt die zeile die am meisten gemeinsamkeiten mit der anderen hat, wird auf null gesetzt. (nein ich lösche sie nicht, da ja das zu viel umkopieren des vektors verursachen würde)

so sieht meine 2d schleife aus. kann man da was machen? im threads oder sonst was

Bashar

Hast du mal dran gedacht, einen Suchbaum zur Hilfe zu nehmen? Den 18000er Vektor muesste man da auf jeden Fall unterbringen koennen. Vielleicht auch den anderen.

ich weiß nicht ob mir ein suchbaum helfen kann. ich muss ja folgendes ausrechnen. ich habe 14 milionen zeilen. diese werden jeweils mit den 18 tausen zeilen verglichen. komplett einmal durch. dann wird diese zeile die in den 14milionen drin ist aus dem spiel genommen. das ist die zeile, die am meisten deckung mit den zeilen aus der 18tausen schleife hatte. automatisch sind alle zeilen die mit der ersten schleife gemeinsamkeit haben auch weg. das geht so weiter bis alle 18 tausend zeilen verbraucht wurden. ich mache es halt noch so, dass ich die zeile die ich rausschmeiße auf null setze. ich will sie nicht löschen,da der vektor sonst umkopiert wird und ich noch mehr zeit verlieren würde. also wird dann noch mit einer if anweisung geschaut ob nicht bereits diese zeile auf null ist. wenn ja dann wird sie übersprungen.

kann mir da ein suchbaum helfen. ich glaube nicht. das ist zu komplex. kann ich diese schleifen teilen so dass ich mehrere threads bekomme?

7H3 N4C3R

Das kannst du nicht so einfach aufteilen, da das ein iterativer Prozess ist (das Ergebnis der zweiten Schleife hängt vom Ergebnis der ersten Schleife ab). Du kannst die Suche an mehrere Threads delegieren. Allerdings stellt sich da die Frage, ob das Thread-Management inklusive Erzeugen, Synchonisation etc. nicht genauso teuer oder sogar teurer wird als deine 18000 Vergleiche.

Hängt natürlich auch von der Beschaffenheit der Daten ab (im Wesentlichen Sortierung).

Chris++ 0

Durchsucht dein Algorithmuss auch die Zeilen die du auf 0 gesetzt hast? Da könntest du nochwas rausholen. Wenn z.B. zu jeder Zeile ein Flag existiert ob die Spalte auf 0 gesetzt wurde oder nicht. Den kannst du prüfen und eventl. diese Zeile überspringen.

Da kannst Du soviel CPU-Power nehmen wie Du willst... Das wird es nicht wirklich bringen. Der Algorithmus klingt sehr nach Brute-Force. Ich bin mir sicher, dass sich die Laufzeit, unter Verwendung entsprechender Bäume und (möglicherweise) Hashtabellen auf wenige Sekunden reduzieren läßt...

Artchi

Wenn ich es richtig verstehe, machst du aber immer einen kompletten Durchlauf durch den 2. Vector und erst dann wird eines dieser Vector-Elemente gelöscht?

Weiterhin gehst du, da dein 2. Vector IMMER 18000 Elemente groß bleibt, komplett durch, obwohl nach einer Stunde vielleicht nur 9000 Elemente gültig sind???

Wenn das so ist, würde ich mal sagen ist hier Optimierungspotential. Die unnötigen if's durch mit der Zeit immer ungültigen Elemente sind kostspieliger, als wenn der Vector immer umkopiert werden würde. Da mit der Zeit immer weniger umkopiert werden würde.

Ich würde also erstmal das eine if raushauen, anstatt das Element auf Null zu setzen, richtig löschen. Dann mal einen Testlauf machen.

Als zweite Variante würde ich dann mal eine std::list ausprobieren. Der Index-Operator-Zugriff ist zwar suboptimal, aber mit dem Iterator durch iterieren in Kombination mit den weniger werdenden Elementen, könnte auch was bringen.

So wie du es aber bisher hast, ist es völlig unoptimal. Auch wenn die ersten Schleifendurchläufe einen großen Block umkopieren würden. Aber wahrscheinlich optimieren auch das mittlerweile die CPUs (der alte 16bit Amiga konnte per Customchip jedenfalls ganze Speicherblöcke nebenbei kopieren, hi hi).

Artchi

Joe_M. schrieb:

Ich bin mir sicher, dass sich die Laufzeit, unter Verwendung entsprechender Bäume und (möglicherweise) Hashtabellen auf wenige Sekunden reduzieren läßt...

Das würde mich ernsthaft interessieren.

Joe_M hat recht. Das ist nichts anderes als ein Brute_Force. Ich werde es auf jeden fall mit dem löschen des vektors versuchen. vieleicht ist das besser als die if schleifen.

wie es aussieht werde ich da wohl kaum was dran machen könne. die paar sekunden hin oder her.

ich versuche es noch heute abend beim kollegen auf einem p4 mit hyperthreading.

Noch eine kurze frage. Glaubt ihr dann dass sich eine investition in einen dicken intel prozi nicht lohnen würde. ich dachte vieleicht würde mit ein xeon 3,4 schon ne menge bringen. oder lohnt sich der aufwand nicht.

Würde mir vieleicht ein 64Bit Betrieb was bringen. natürlich müßte ich meinen code auf 64bit erstmal bringen

7H3 N4C3R

MrTempo schrieb:

Würde mir vieleicht ein 64Bit Betrieb was bringen. natürlich müßte ich meinen code auf 64bit erstmal bringen

Vermutlich doppelten Speicherverbrauch. Viel mehr nicht.

@Artchi: Unter dem folgenden Link wurde ein ähnliches gelagertes Problem von einer mehrstündigen Laufzeit auf ca. 3 Sek. gedrückt (allerdings in Delphi, was für die Herangehensweise an das Problem jedoch keinen Unterschied macht):
http://www.entwickler-forum.de/WebX?128@102.4Thda6vxi6t.3@.2cb7d1a5

Artchi

64bit ist ja nur der Adressraum der größer wird. Um Speicherausbau geht es dir ja nicht. Eine Frage fällt mir da aber noch ein: hast du genug RAM? Weil ein paar Mio. Elemente im Vector ist schon nicht wenig! Nicht das dein PC die ganze Zeit am Swappen von virtuellen Speicher ist und die Festplatte am Ende der Schuldige ist.

Die Athlon64-CPUs haben einen 1 GHz Frontsidebus, das geht wahrscheinlich auch noch mal Speed gegenüber den Intel64-CPUs.

Ob sich die Investition in einen xeon lohnt mußt du entscheiden. Verdienst du dann mehr Geld durch den Xeon bzw. sparst du mehr Geld? (nach der Investition in den Xeon meine ich) Natürlich ist Zeit = Geld. Für eine kommerzielle Nutzung wo nicht nur einmal gerechnet wird, wird sich das wohl lohnen. Aber dann kann man auch gleich Dualcores oder gar Multicores kaufen und versuchen Threads zu benutzen. Dann lohnt sich das auf jeden Fall.

Und wenn du einen Rechendurchlauf nicht in Threads umsetzen kannst, kannst du vielleicht die zweite Berechnung (die du vielleicht später starten würdest) parallel laufen lassen. Würden zwar die Ergebnisse nicht schneller als 2 Std. da sein, aber du hättest nach 2 Std. zwei Ergebnisse! Ist auch eine Lösung.