NTFS Dateianzahl pro Verzeichnis und Performance

Wie wàre es anstelle Millionen von Dateien mit einer einzigen, als Hashtabelle?

volkard

frag0r schrieb:

Wie wàre es anstelle Millionen von Dateien mit einer einzigen, als Hashtabelle?

Nö, besser nicht.
Wenn eine Datei gelesen wird, werden die drin stehenden Zahlen (zum Beispiel 600 Stück) nach aufsteigender Größe gelesen und verarbeitet. Wenn eine neue Zahl zu einer Datei hinzukommt, ist sie größer als alle bisherigen Zahlen der Datei, also kann einfach hinten drangehängt werden. Das macht Dateien schonmal recht praktisch.

DEvent

Wie waere es mit einer Datenbank? Muss ja nicht gleich mysql sein, nimmt halt sqlite.

Mit python und alchemy ist sowas in 5min gemacht. Oder besser in elixir

volkard

DEvent schrieb:

Wie waere es mit einer Datenbank? Muss ja nicht gleich mysql sein, nimmt halt sqlite.

Dateien sind für mich optimal, solange das Dateisystem nicht völlig überlastet ist. Es sieht nicht danach aus, daß NTFS schnell in die Knie ginge.

volkard schrieb:

Dateien sind für mich optimal, solange das Dateisystem nicht völlig überlastet ist.

was hast du eigentlich vor, beschreib doch mal? es ist keine seltenheit, dass ein DBMS (wie schon DEvent vorgeschlagen hat), wesentlich effektiver mit grossen datenmengen umgehen kann, als wenn man alles selber in dateien schreiben würde. ich habe z.b. letztens erst recht positive erfahrungen mit HSQLDB (ein DBMS komplett in Java geschrieben, spottet jeder aussage, dass Java langsam sei) gemacht und früher auch schon (mit DB2, mySQL).

volkard

;fricky schrieb:

was hast du eigentlich vor, beschreib doch mal?

Ich mache das da (mußt Du nicht ganz lesen, ich fasse gleich zusammen)
http://www.gpgpgpu.com/gecco2009/6.pdf
Allerdings ohne GPU und ohne genetische Algorithmen. Darüberhinaus auf einem alten Rechner und single threaded.

Die Funktion isPrime(x) sagt, ob x eine Primzahl ist.
Die Funktion isSPRP(x,a) sagt, ob x eine stark wahrscheinliche Primzahl zur Basis a ist. http://en.wikipedia.org/wiki/Probable_prime
Die isSPRP() verbläst praktisch die gesamte Rechentzeit.
Sie verbläst für einmal isSPRP(x,a) leider log(x) Integer-Divisionen.
isSPRP(x,irgendwas) liefert sehr oft das gleiche wie isPrime(x). Leider nicht immer. Aber zum Beispiel liefert isSPRP(x,2) das gleiche wie isPrime(x), solange x<2047. Wenn man alle Basen bis 2^32 ausprobiert, kommt man zu der am weitesten tragenden Basis:
isSPRP(x,42162995) liefert das gleiche Ergebnis wie isPrime(x), solange x<97921.
Damit kann man eine isPrime() deutlich beschleunigen, indem man ein leckeres

//vorher ein wenig trial division durch 2,3,5,7
if(x<97921)
  return !isSPRP(x,42162995);
//nachher der test für große zahlen

baut.
Man braucht dann in diesem Bereich nur noch log(x) Divisionen statt der normalen sqrt(x) Divisionen. Das rockt die Bude.
Ist aber auch nicht neu http://www.groupsrv.com/science/post-3260091.html

Im Wesentlichen ist mein Programm nur ein

for a=2 to maxint (bin jetzt bei ca 70000)
  for b=3 to a-1 (bin dauernd zwischen 3 und ca 70000)
//also laufe über alle paare (a;b) mit a,b<=maxint
    for x=2 to inf (sehr oft bis ein paar milliönchen)
       if isSPRP(x,a) and isSPRP(x,b) and (not isPrime(x))
//also finde den ersten Aussetzer für dieses Basenpaar
          if x>bestesXBisher
             print a,b,x,teilerVon(x)
             break, also exit for, also beim nächsten b weitermachen

Aber das braucht EWIG. Und dann kommen halt die Optimierungen. Die allerstärkste Optimierung von mir ist die, daß ich "die üblichen Verdächtigen" in einem Move-To-Front-Cache halte und vor der x-Schleife erstmal "die üblichen Verdächtigen" gegen die beiden Basen prüfe. Ein x wird zum "üblichen Verdächtigen", wenn es den Vergleich x>bestesXBisher auslösen kann.

Wenn a so um 30k ist, sorgt diese Optimierung dafür, daß während b von 2 bis 30k läuft, alle b bis auf ungefähr eins bereits einen Treffer in "den üblichen Verdächtigen" haben und nicht die x-Schleife bis ein paar Milliönchen betreten muß.
Bei a=30k ist die Anzahl "der üblichen Verdächtigen" gerde mal 2042. Also Hammer-Beschleunigung. Mit Move-To-Front in "den üblichen Verdächtigen" habe ich sogar meistens nur weniger als 10 isSPRP() pro neuem b zu zahlen.

Manchmal aber muß die x-Schleife laufen. Und hier kommt die Optimierung mit den Dateien. Dann habe ich für a und für b, falls ich jemals a oder b in einer x-Schleife schon laufen ließ, die kleinen SPRPs für a und b schon auf der Platte und kann einfach die beiden Dateien laden und die erste Gleichheit suchen. Ist keine Gleichheit da, wird die x-Schleife genommen, die aber zusätzlich alle SPRPs, die anfallen, in die beiden Dateien ablegt für's nächste mal.

Für die Suche bis a=75k sind lustigerweise nur 3000 Dateien entstanden mit zusammen 5MB (weil die erste Optimierung so sagenhaft gut greift).
Die letzen beiden Dateien sind
0000074616.txt

und
0000000659.txt

Entsprechen war 4932841 das kleinste x, das zu den Basen 74616 und 659 ein Aussetzer war.
Meine 49Mio sind noch weit weg von den 177Mio von David McAllister.
Aber ich mache ja auch eine erschöpfende Suche und lasse keinen Kandidaten aus, um irgendwann ich wenigen hundert Prozessorjahren das optimale Paar zu haben.

Die Dateien-Optimierung soll dafür sorgen und sorgt dafür, daß die x-Schleife immer jene milliönchen SPRP-Tests nicht machen muß, die bereits auf einer der beiden Basen schon passiert sind. Ich muß also manchmal (ca einmal pro Sekunde) so zwei kleine Datein lesen und die werden dann auch sequentiell gelesen. Ich denke, Dateien sind da optimal.

Übrigens habe ich festgestellt, daß statt 543756235327412.txt eine 5437/5623/5327/412.txt nicht so schlau ist. Besser ist es, mit den Verzeichnissen nur einen Suchweg zu machen und zu zerlegen in 5437/5623/5327/543756235327412.txt. Da kann ich mit normalen tools oder mit freaktools und weniger Nachdenken leichter umstrukturieren. 5437/5623/5327/412.txt nur nehmen, wenn nur automatisch drauf zugegriffen wird wie in ccache oder so.

Die Dateien, die entstehen, sind als soche von Bestand und können unmittelbar für den komplett wahnwitzigen Versuch genommen werden, auch das perfekte Basentripel zu finden. Aber dazu brächte es bis zum Ende Milliarden von Rechnern, die hunderte von Jahren laufen. Mal schauen, eine (fremderfundene) vielleicht tausendstarke mathematische Optimierung gärt in mir. Vielleicht gilt Moore's Gesetz weiter und in 15 Jahren haben wir wider 1000-mal mehr Rechenpower als jetzt.

volkard schrieb:

;fricky schrieb:

was hast du eigentlich vor, beschreib doch mal?

Ich mache das da (mußt Du nicht ganz lesen, ich fasse gleich zusammen)
http://www.gpgpgpu.com/gecco2009/6.pdf

ein primzahlen-sucher? vielleicht interessiert dich das: http://www.alpertron.com.ar/ECM.HTM
kann relativ schnell relativ grosse zahlen faktorisieren, source code ist auch auf der seite, der code sieht zwar furchtbar aus, aber vielleicht kannstes irgendwie für deine zwecke verwerten.

volkard

;fricky schrieb:

?

Ach, übrigens, ich benutze C++ mit Objektorientierung.
Die teure x-Schleife ist derzeit:

{
				sa.start(a);
				sb.start(b);
				while(sa.peek()!=sb.peek()){
					cout<<a<<' '<<b<<' '<<sa.peek()<<' '<<sb.peek()<<"           \r";
					if(sa.peek()<sb.peek()){
						sa.pop();
					}
					else{
						sb.pop();
					}
				}

sa und sb sind dabei vom Typ SPRPGenerator. Und der erledigt die ganzen Geschichten um Laden und Speichern und ums Dazuberechnen, wenn noch nicht genug Daten da sind.

volkard

;fricky schrieb:

volkard schrieb:

;fricky schrieb:

was hast du eigentlich vor, beschreib doch mal?

Ich mache das da (mußt Du nicht ganz lesen, ich fasse gleich zusammen)
http://www.gpgpgpu.com/gecco2009/6.pdf

ein primzahlen-sucher? vielleicht interessiert dich das: http://www.alpertron.com.ar/ECM.HTM
kann relativ schnell relativ grosse zahlen faktorisieren, source code ist auch auf der seite, der code sieht zwar furchtbar aus, aber vielleicht kannstes irgendwie für deine zwecke verwerten.

Denke nicht. Bis 2^64 nehme ich zum Faktorisieren Pollard's Rho mit Brent. Aber was treibt Dich dazu, so unpassende Links zu posten? Google-Größenwahn, daß Du meinst, mit zwei Minuten Googlen was Tolles beitragen zu können?

volkard

;fricky schrieb:

volkard schrieb:

;fricky schrieb:

was hast du eigentlich vor, beschreib doch mal?

Ich mache das da (mußt Du nicht ganz lesen, ich fasse gleich zusammen)
http://www.gpgpgpu.com/gecco2009/6.pdf

ein primzahlen-sucher?

Nee, ein Primzahlen-Sucher-Sucher.

volkard schrieb:

Aber was treibt Dich dazu, so unpassende Links zu posten?

ich hatte das applet noch in erinnerung, finde es ganz schick.

volkard schrieb:

Google-Größenwahn, daß Du meinst, mit zwei Minuten Googlen was Tolles beitragen zu können

google ist einfach toll. kennste schon diese seite: http://primes.utm.edu/prove/index.html

volkard

;fricky schrieb:

volkard schrieb:

Aber was treibt Dich dazu, so unpassende Links zu posten?

ich hatte das applet noch in erinnerung, finde es ganz schick.

volkard schrieb:

Google-Größenwahn, daß Du meinst, mit zwei Minuten Googlen was Tolles beitragen zu können

google ist einfach toll. kennste schon diese seite: http://primes.utm.edu/prove/index.html

Vor 5 Jahren kannte ich sie noch, wie
http://www.c-plusplus.net/forum/viewtopic-var-t-is-67513-and-start-is-10.html
beweist.

volkard schrieb:

Vor 5 Jahren kannte ich sie noch, wie
http://www.c-plusplus.net/forum/viewtopic-var-t-is-67513-and-start-is-10.html
beweist.

wow, du beschäftigst dich wohl schon ziemlich lange mit dem thema, bist wohl ein echter zahlentheorie-freak? schon mal dran gedacht, eine eigene webseite mit deinen forschungsergebnissen aufzumachen?

volkard

;fricky schrieb:

wow, du beschäftigst dich wohl schon ziemlich lange mit dem thema,

Ja. 1997 oder so spendierte ich ein halbes Jahr Freizeit darein und seitdem gelegentlich vielleicht mal eine Woche im Jahr. Heuer ein wenig mehr, und ursprünglich gar nicht dessentwegen, sondern weil ich eine Spielwiese für das Range-Konzept brauchte. Uih, das Konzept ist stark!

;fricky schrieb:

bist wohl ein echter zahlentheorie-freak?

Nur Hobby-Mathematiker. Mir fehlt der Unterbau.

;fricky schrieb:

schon mal dran gedacht, eine eigene webseite mit deinen forschungsergebnissen aufzumachen?

Ja, langsam wird es dringend. Inzwischen kriege ich ca. eine Milliarde mal mehr Tests pro Stunde unter als am Anfang. Immernoch ohne jeden mathematischen Trick. Im Endeffekt nur ein paar Beobachtungen, die erlauben, Rechenzeit zu sparen und C++-Code ohne abstraction overhead. Primzahlen sind kacke, die fliehen immer und jeder beobachtete Trick ist dann doch nur für ein paar Tausend oder Millionen gültig. Die Geschichte meines Suchers ist aber schreibenswert, weil da der Reihe nach hunderte von geilen Programmiertricks vorkommen, allein in den letzten Tagen eine move-to-front-list als intrusive ring, ein verzögertes bubble-sort, ein update-log und sentinel-ranges. Aber meine Klassen sind obzwar minimalistisch noch ziemlich hingekotzt. Und das alles zum Aufschreiben nachzuvollziehen wird voll lange dauern, in der Zeit könnte ich ja soo viel sinnvolles machen...