Hallo,
@Amateurprofi:
Ich habe nur die Version, die Panthrax eingebaut hat, verwendet, villeicht hat sich dort ein kleiner Fehler eingeschlichen.
Dort ist das Ergebnis, die Anzahl der gemeinsamen Elemente in EAX, zweier gleicher Felder eben ein Element zu wenig, wie es auch bei der Pascal Version #19 der Fall ist.
Die Felder die ich erstellt habe, haben keine doppelten, wie ich auch in
http://www.delphipraxis.net/1157082-post48.html schrieb.
Das Ausgangsfeld hat die Werte 0,delta,2*delta...,(N-1)*delta
delta laut Programm
Delphi-Quellcode:
type
tData = longint;
TSampleArray = Array of tData;
tVersuch = array[0..15] of TSampleArray;
const
// MAXDATCOUNT = 1000;
MAXDATCOUNT = 10*1000*1000;
delta = High(tData) div MAXDATCOUNT-1;
also delta = 214
Bei den Versuchsfelder[i] wird das AusgangsFeld/TestFeld an zufälligen Stellen um i erhöht.
@Laser:
Zitat:
Man kann sich das so vorstellen, dass für jedes Wort in einem Buch mit mehreren Millionen Seiten eine Indexdatei vorliegt. Es werden mehrere Schlagwörter benannt und die Schnittmenge enthält die Seiten, auf denen alle Wörter vorkommen.
Zu Beginn ging es um:
Zitat:
gegeben seien n (=1 bis ca. 12) Dateien, in denen jeweils eine Anzahl a (=2 bis ca. 5.000.000) 64-bit Integer-Schlüssel s abgespeichert sind. s liegen jeweils aufsteigend sortiert vor.
Gesucht ist ein möglichst schneller Algorithmus:
Erzeuge eine Datei output der Schlüssel s, die in allen n Dateien vorkommen.
Also maximal 40 Mbyte in einer Datei.Linaer gelesen in etwa 0,5 Sekunden, bei einer nicht so aktuellen Festplatte.
Bei einer mittleren Zugriffszeit von 13 ms entsprechen 0,5 Sekunden 38..39 Schreib/Lese-Kopfpositionierungen.
Binäre Suche in 5 Mio Werten sind trunc(ln(5e6)/ln(2))+1 = 23 Schritte, Du kannst nicht mal zwei veschiedene Werte die einmal in der unterer, das andere Mal in der oberen Hälfte liegen abfragen und die 0,5 Sekunden sind um. { Bei einer SSD wäre das anders.}
Lange Rede, keinen Sinn:
Mit Furtbichlers Pascalversion aus Beitrag #39 sind bei mir 12 Felder mit 10e6 Elemeneten in 0,5 Sekunden durchgemangelt.
Wie schon festgestellt wurde, bleibt nun die Festplatte die Bremse und dort bietet sich Furtbichlers Vorschlag mit TMappedFile an, denn diese arbeiten mit einem Read-ahead den eine untypisierte Datei nicht bieten soll.
Ich halte jetzt nur noch für interessant, ob man wirklich alle 12 Dateien parallel als TMappedFile öffnen sollte oder nicht.
In ~6 Sekunden ist doch alles geschafft.
Gruß Horst