|
Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
|
Re: Hashing Problem
17. Aug 2003, 11:52
Erstmal kannste dein A: array[0..63] of Boolean optimieren auf 1/8 der jetzigen Größe wenn du A: Int64 nutzt. Jedes Bit in A wäre dann ein Boolean aus A[]. Nun sortierst du diese A's binär in eine Liste ein. Die Suche nach einem A wäre dann die Suche in dieser Liste von Int64 Werten. Angenommen 1024 solcher A's sind in der Liste, dann benötigst du nur maximal 10 Vergleiche per Binärer Suche um das richtige A zu finden. Somit benötigst du überhaupt keinen Hashalgortihmus, er wäre in deinem alle sinnlos und wesentlich langsammer. Die Suche nach der richtigen Einfügeposition in der Liste für ein neues A wäre bei 1024 Einträge ebenfalls nur 10 Vergleiche maximal. Beim Einfügen selber müsste man aber ca. 512 Einträge durchschnittlich im Speicher kopieren.
Gruß Hagen
|