aSort() Geschwindigkeit

Zugriff, Engines, Konvertierung. Von ADS über DBF bis zu SQL.

Moderator: Moderatoren

Antworten
saul
Rekursionen-Architekt
Rekursionen-Architekt
Beiträge: 284
Registriert: So, 26. Mär 2006 12:23

aSort() Geschwindigkeit

Beitrag von saul »

Hallo,
ich muss ein zweidimensionales Array sortieren und habe das mit

Code: Alles auswählen

 ASort( aArray,,, {|aX,aY| aX[Spalte] < aY[Spalte] } )   
durchgeführt. Bei 100000 Einträge in dem Array dauert das ein wenig. Gibt es da eine schnellere Möglichkeit?
mfg
Wolfgang
Benutzeravatar
brandelh
Foren-Moderator
Foren-Moderator
Beiträge: 15688
Registriert: Mo, 23. Jan 2006 20:54
Wohnort: Germersheim
Hat sich bedankt: 65 Mal
Danksagung erhalten: 33 Mal
Kontaktdaten:

Re: aSort() Geschwindigkeit

Beitrag von brandelh »

Sind das Stringvergleiche und was ist "etwas" ?

Du kannst mal ein Beispiel posten (mit Spieldaten die von Typ und Länge mit den originalen übereinstimmen, sowie Infos über deinen Rechner: Ram, Windows Version etc.) und wir prüfen gegen ob es an deinem Rechner liegt.
Es könnte sein, dass der Rechner bei wenig RAM auslagern muss, das würde stark aufhalten.
Bisher ist es mir nicht gelungen eine Sortierung zu programmieren, die schneller als aSort war ;-)
Gruß
Hubert
Benutzeravatar
Herbert
Der Entwickler von "Deep Thought"
Der Entwickler von "Deep Thought"
Beiträge: 1991
Registriert: Do, 14. Aug 2008 0:22
Wohnort: Gmunden am Traunsee, Österreich
Danksagung erhalten: 3 Mal
Kontaktdaten:

Re: aSort() Geschwindigkeit

Beitrag von Herbert »

Sortieren grosser Datenmengen ist nicht einfach.
Die Frage ist, wie füllst du zu diesen Arrray? Falls aus Werten einer Tabelle gelesen wird, könntest du überlegen, einen Index darüber zu legen, damit die Daten bereits sortiert erscheinen.
Grüsse Herbert
Immer in Bewegung...
georg
Der Entwickler von "Deep Thought"
Der Entwickler von "Deep Thought"
Beiträge: 2823
Registriert: Fr, 08. Feb 2008 21:29
Hat sich bedankt: 95 Mal
Danksagung erhalten: 13 Mal

Re: aSort() Geschwindigkeit

Beitrag von georg »

Hallo, Wolfgang -


derart grosse Arrays brauchen (auch abhängig von ihrer Grösse) sehr viel Platz im Speicher.

Du kannst ja parallel mal die Daten in eine temporäre Datei schreiben, deren Index entsprechend definiert ist und die Laufzeiten vergleichen.

Wenn Deine Daten z.B. "auf dem Kopf stehen", d.h. das erste Element am Ende das letzte sein wird und umgekehrt, kann das Verschieben der Array-Elemente im Speicher elend lange dauern. Das Erstellen des Index über eine temporäre Datei ist da deutlich weniger aufwändig.

So lautet zumindest meine Einschätzung.
Liebe Grüsse aus der Eifel,

Georg S. Lorrig
Redakteur der Wiki des Deutschprachigen Xbase-Entwickler e.V.
saul
Rekursionen-Architekt
Rekursionen-Architekt
Beiträge: 284
Registriert: So, 26. Mär 2006 12:23

Re: aSort() Geschwindigkeit

Beitrag von saul »

Hallo,
das sind Strings mit einer Länge von 30 Stellen, 6 Spalten. Rechner Windows 7, 4 GB RAM, AMD Phenom(tm)II/X4 Stepping:RB-C3 (Sockel-Typ AM3) 3400Mhz. Sortierung dauert ca. 1 Sekunde. Wenn es aber nichts schnelleres bekannt ist werde ich damit leben müssen.

Danke
mfg
Wolfgang
Benutzeravatar
brandelh
Foren-Moderator
Foren-Moderator
Beiträge: 15688
Registriert: Mo, 23. Jan 2006 20:54
Wohnort: Germersheim
Hat sich bedankt: 65 Mal
Danksagung erhalten: 33 Mal
Kontaktdaten:

Re: aSort() Geschwindigkeit

Beitrag von brandelh »

100.000 Zeilen, 30 Zeichen (eventuell 6 Spalten a 30 Zeichen ?) um eine Sekunde, ich halte das für schnell ;-)

Beispiel: for next Schleife mit 100000 Durchläufen ohne irgendetwas zu tun, wird kaum schneller sein ;-)
Gruß
Hubert
Benutzeravatar
Jan
Marvin
Marvin
Beiträge: 14641
Registriert: Fr, 23. Sep 2005 18:23
Wohnort: 49328 Melle
Hat sich bedankt: 21 Mal
Danksagung erhalten: 87 Mal
Kontaktdaten:

Re: aSort() Geschwindigkeit

Beitrag von Jan »

... naja, bei so einem alten Prozessor... Der Phenom wurde immerhin 2007-2009 verkauft.

Aber Spaß beiseite: ASort() Funktioniert auch auf langsameren Prozessoren relativ flott. Arbeitsspeicher ist ja auch ausreichend dafür vorhanden. Ich halte wie Hubert 1 Sekunde für recht annehmbar bei dieser umfangreicheren Sortiergrundlage.

Jan
Mitglied der XUG Osnabrück
Mitglied der XUG Berlin/Brandenburg
Mitglied des Deutschsprachige Xbase-Entwickler e. V.
Benutzeravatar
Tom
Der Entwickler von "Deep Thought"
Der Entwickler von "Deep Thought"
Beiträge: 9345
Registriert: Do, 22. Sep 2005 23:11
Wohnort: Berlin
Hat sich bedankt: 100 Mal
Danksagung erhalten: 359 Mal
Kontaktdaten:

Re: aSort() Geschwindigkeit

Beitrag von Tom »

Dieser Code erzeugt ein zweidimensionales Array mit 6 Spalten, die jeweils eine zufällige, 30 Zeichen lange Zeichenfolge (Wertebereich ASCII 65 bis 122) enthalten. Die mehr oder weniger zufällige Erzeugung des Arrays dauert auf einer halbwegs aktuellen 64-Bit-Maschine 7 Sekunden, die Sortierung eine knappe Sekunde. Für mich ist das in Ordnung.

Code: Alles auswählen

FUNCTION Main()
LOCAL a := {}, i, j, x, n
CLEAR
? Seconds()
FOR i := 1 to 100000
  aAdd(a,{'','','','','',''})
  n := Len(a)
  FOR j := 1 to 6
    FOR x := 1 to 30
      a[n,j] += Chr(RandomInt(65,122))
    NEXT
  NEXT
NEXT
? Seconds()
ASort( a ,,,{|aY1,aY2| aY1[1] < aY2[1]})
? Seconds()
RETURN nil
Herzlich,
Tom
Benutzeravatar
brandelh
Foren-Moderator
Foren-Moderator
Beiträge: 15688
Registriert: Mo, 23. Jan 2006 20:54
Wohnort: Germersheim
Hat sich bedankt: 65 Mal
Danksagung erhalten: 33 Mal
Kontaktdaten:

Re: aSort() Geschwindigkeit

Beitrag von brandelh »

Ich habe mal einen Versuch mit PowerBasic und einem ein dimensionalen Stringarray gemacht.
Dieses wird in 0,2 Sekunden sortiert.
Ein zwei dimensionales konnte ich zwar anlegen, allerdings nicht richtig sortieren ... und schon gar nicht nach einer Spalte ...

Arrays in Xbase++ sind sehr viel komplexer, da verschiedene Typen vorkommen können.
Die Sortierung mit ASort() auf eine Spalte ist ohne Probleme möglich, da muss man halt etwas länger warten ...

Auf meinem I5-2500 3,4 Ghz auch etwa 1 Sekunde.
Gruß
Hubert
Benutzeravatar
Tom
Der Entwickler von "Deep Thought"
Der Entwickler von "Deep Thought"
Beiträge: 9345
Registriert: Do, 22. Sep 2005 23:11
Wohnort: Berlin
Hat sich bedankt: 100 Mal
Danksagung erhalten: 359 Mal
Kontaktdaten:

Re: aSort() Geschwindigkeit

Beitrag von Tom »

Ich hab's übrigens auch mit einem eindimensionalen Array ausprobiert, ohne großartige Unterschiede (Zehntelsekunde).
Herzlich,
Tom
Antworten