Speicherproblem

freakC++

Hallo zusammmen,

ich habe hier eine "Hashfunktion", bei der ich Kollisionen entdecken soll. Meine Vorgehensweise ist wie folgt:

Ich habe eine unordered_map. Der Key ist der Hash, der "Value" ein std::vectorstd::string, der alle Strings speichert, die den Key als Hash haben.

Mittels

std::string str("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890");

  do {
    uint32_t hash_value = hash(str.c_str(), str.size());
    if(collisionCount.Add(hash_value, str)) {   
  }
  while(std::next_permutation(str.begin(), str.end()));

fülle ich meine unordered_map mit den Permutationen meines Alphabets.

Problem: Auf diese Art und Weise sind meine 4GB Ram innerhalb etwa einer Minute aufgebraucht. Klar, ich lege pro neuem Hash eine Liste an. Trotzdem wundert es mich, dass diese Herangehensweise so speicherhungrig ist....

Hat jemand ne Idee, wie man dieses Problem performanter angehen kann? Meine Idee ist ja wohl nicht umsetzbar. Ich finde etwa 11 Strings, die den gleichen Hash haben. Dann stürzt mein PC ab. Die Aufgabe fordert aber 40.000 solcher Strings zu finden....

Skym0sh0

Naja, überleg mal.

Dein String da ist 2 mal das deutsche ALphabet lang plus alle Ziffern: macht zusammen 62 Zeichen. Nach der Kombinatorik existieren dafür 62! (Fakultät) verschiedene Kombinationen. Das sind etwa 3.15 x 10⁸⁵ Werte !!!
Das Universum hat nicht viel mehr Atome...
Dass dein armer kleiner Rechner da ganz schnell den Löffel abgibt, sollte auch nicht mehr als logisch sein.

Wenn du unter Windows entwickelst, ohne entsprechende Vorkerhrungen getroffen zu haben, verabschiedet sich dein Programm schon bei 2GB RAM-Usage(Stichwort: Linkerflag EnableLargehardwareAddress oder so heist des)

freakC++

Dieser Gedankengang ist mir klar. Ich hatte die Hoffnung, dass zuvor alle Strings gefunden werden. Dann bricht nämlich die Suche automatich ab. Außerdem wundert es mich, dass so schnell der Speicher voll ist.

Habt ihr ne Idee, wie ich an das Problem anders angehen kann?

Nathan

Was genau ist die Aufgabe? ALLE Permutationen finden?
Und was meinst du "wenn alle Strings gefunden werden"?

freakC++

Also, ich habe eine Funktion gegeben, die eine Art Hash erstellt. Die Aufgabe lautet, dass ich 40.000 Strings angeben soll, die auf denselben "Hash" abbilden.

Diese "Hashfunktion" ist natürlich nicht kollisionsresistent, weswegen ich sie in Anführungsstriche schreibe.

Meine jetzige Herangehensweise ist zu speicherhungrig.

Meine neue Idee: Mit der alten Methode schaue ich, welche 10 Strings auf denselben "Hash" abbilden (10 Strings bekomme ich hin. Danach läuft der Speicher voll). Deren Hash schaue ich mir an und untersuche anschließend die Permutationen auf diesen Hash. Dieser Hash kam beim ersten Test ja am häufigsten vor.

Die Implementierung dieser Idee läuft nun seit 3 Minuten. Bis jetzt habe ich 57 Kollisionen. Ich zweifel jedoch, ob ich damit auf 40.000 komme

Mein Alphabet habe ich verkürzt auf abcdefghijklmnopq.

freakC++ schrieb:

Die Implementierung dieser Idee läuft nun seit 3 Minuten. Bis jetzt habe ich 57 Kollisionen. Ich zweifel jedoch, ob ich damit auf 40.000 komme

Manchmal hilft es, etwas zu überlegen. Ist die Funktionsweise der Hashfunktion bekannt?

Ich hätte jetzt mit einem String angesetzt und den zufällig verändert, bis wieder der gleiche Hash herauskommt (also 10 Edits, dann wieder von vorne probieren).