Types sortieren .... Optimierung... geht das schneller??

Übersicht

BlitzBasic

Allgemein

Gehe zu Seite 1, 2 Weiter

	Rallimen Sieger des 30-EUR-Wettbewerbs Betreff: Types sortieren .... Optimierung... geht das schneller??	Do, Apr 01, 2004 1:15 Antworten mit Zitat
Mein erster TypesortierAlgo:Code: [AUSKLAPPEN] [EINKLAPPEN] Type Test Field X End Type For t= 0 To 5000 ralf.Test = New Test ralf\x = Rand (0,9999) Next time = MilliSecs () SortTypefield () Print MilliSecs ()-time Print "Taste >>> Weiter" WaitKey For Ralf.test = Each test Print Ralf\X Next Print "Taste >>> Beenden" WaitKey End ;######################################################################## Function SortTypefield () Repeat ralf.Test = First test Repeat wert_1 = ralf\x ; 1. wert sichern ralf.Test = After (ralf) ; zur nächsten schalten If ralf = Null Then Exit ; wenn letzte erreicht dann schleife verlassen If wert_1 > ralf\x Then ; prüfen und ggf tauschen Insert Ralf Before Before Ralf x=x+1 ; dummy Var >wenn = 0 dann fertig sortiert ;DebugLog ralf\x End If Forever If x = 0 Then Exit ;>wenn = 0 dann fertig sortiert x= 0 Forever End Function läßt sich da noch was an Speed rausholen? Oder gibt es da noch andere Möglichkeiten speziell für Types? dauert bei mir 1420 Millisekunden
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Betreff: Types sortieren .... Optimierung... geht das schneller??

Do, Apr 01, 2004 1:15
Antworten mit Zitat

Mein erster TypesortierAlgo:Code: [AUSKLAPPEN]

Type Test
Field X
End Type

For t= 0 To 5000
ralf.Test = New Test
ralf\x = Rand (0,9999)
Next

   time = MilliSecs ()
SortTypefield ()
   Print MilliSecs ()-time
Print "Taste >>> Weiter"
WaitKey
For Ralf.test = Each test
   Print Ralf\X
Next
Print "Taste >>> Beenden"
WaitKey
End
;########################################################################
Function SortTypefield ()
Repeat
   ralf.Test = First test
   Repeat
      wert_1 = ralf\x ; 1. wert sichern
      ralf.Test = After (ralf) ; zur nächsten schalten
      If ralf = Null Then Exit ; wenn letzte erreicht dann schleife verlassen
      If wert_1 > ralf\x Then ; prüfen und ggf tauschen
            Insert Ralf Before Before Ralf
            x=x+1 ; dummy Var >wenn = 0 dann fertig sortiert
            ;DebugLog ralf\x
      End If
   Forever
   If x = 0 Then Exit ;>wenn = 0 dann fertig sortiert
   x= 0
Forever
End Function

läßt sich da noch was an Speed rausholen?
Oder gibt es da noch andere Möglichkeiten speziell für Types?
dauert bei mir 1420 Millisekunden

[BB2D | BB3D | BB+]

	MasterK	Do, Apr 01, 2004 1:52 Antworten mit Zitat
das ist ein (leicht optimierter) bubble-sort algorithmus, damit wirst du nicht viel reissen. suche mal nach quicksort. ist etwas schwerer zu verstehen, aber sehr viel schneller. wenn du ein array verwenden würdest, könnte man auch bucketsort verwenden, schneller gehts dann kaum noch. aber da types in BB scheinbar etwas merkwürdig sind, fällt das wohl flach

MasterK

Do, Apr 01, 2004 1:52
Antworten mit Zitat

das ist ein (leicht optimierter) bubble-sort algorithmus, damit wirst du nicht viel reissen. suche mal nach quicksort. ist etwas schwerer zu verstehen, aber sehr viel schneller.
wenn du ein array verwenden würdest, könnte man auch bucketsort verwenden, schneller gehts dann kaum noch. aber da types in BB scheinbar etwas merkwürdig sind, fällt das wohl flach

	Suco-X Betreff: ......	Do, Apr 01, 2004 4:38 Antworten mit Zitat
@MasterK : Warum du dir bemerkungen über BB erlaubst obwohl du damit nicht arbeitest und nie gearbeitet hast, wird mir wohl immer ein Rätsel bleiben. Aber jeder hat so seine Hobbys. Zwischen arrays und types gibt es bis auf speed unterschiede und Komfort keine unterschiede beim Thema Sortieren der Einträge. @Ralli : Habe auch mal eine Version gemacht, Doppelt bis 3 fach so schnell wie deine : Code: [AUSKLAPPEN] [EINKLAPPEN] Type test Field x End Type SeedRnd(MilliSecs()) startzeit = MilliSecs() For i = 0 To 5000 t.test = New test t\x = Rand(0,9999) Next For a.test = Each test For b.test = Each test If a\x<b\x t_a = a\x t_b = b\x a\x = t_b b\x = t_a EndIf Next Next endzeit = MilliSecs()-startzeit Print "Fertig" Print endzeit WaitKey() Wie man diese Version nennen würde weiß ich nicht, ich kenne mich mit den ganzen Namen wirr warr nicht aus und nenne es einfach mal Sortierung von Types... Ist jedenfalls schneller als deine Version, vielleicht hilft es dir ja. bye
Intel Core 2 Quad Q8300, 4× 2500 MHz, 4096 MB DDR2-Ram, GeForce 9600GT 512 MB

Suco-X

Betreff: ......

Do, Apr 01, 2004 4:38
Antworten mit Zitat

@MasterK : Warum du dir bemerkungen über BB erlaubst obwohl du damit nicht arbeitest und nie gearbeitet hast, wird mir wohl immer ein Rätsel bleiben. Aber jeder hat so seine Hobbys. Zwischen arrays und types gibt es bis auf speed unterschiede und Komfort keine unterschiede beim Thema Sortieren der Einträge.
@Ralli : Habe auch mal eine Version gemacht, Doppelt bis 3 fach so schnell wie deine :

Code: [AUSKLAPPEN]

Type test
Field x
End Type

SeedRnd(MilliSecs())

startzeit = MilliSecs()

For i = 0 To 5000
t.test = New test
t\x = Rand(0,9999)
Next

For a.test = Each test
For b.test = Each test

If a\x<b\x
   t_a = a\x
   t_b = b\x
   a\x = t_b
   b\x = t_a
EndIf

Next
Next

endzeit = MilliSecs()-startzeit

Print "Fertig"
Print endzeit

WaitKey()

Wie man diese Version nennen würde weiß ich nicht, ich kenne mich mit den ganzen Namen wirr warr nicht aus und nenne es einfach mal Sortierung von Types... Wink

Ist jedenfalls schneller als deine Version, vielleicht hilft es dir ja.
bye

Intel Core 2 Quad Q8300, 4× 2500 MHz, 4096 MB DDR2-Ram, GeForce 9600GT 512 MB

	Firstdeathmaker	Do, Apr 01, 2004 10:10 Antworten mit Zitat
Ich sitze gerade auch an diesem Problem und komme nicht weiter. Ich habe Suco-X´s Version mal getestet und sie funktioniert. Nur möchte ich auch gerne verstehen warum sie so funktioniert, damit ich das Prinzip verstehe. Also, ich versuch mal zu schildern was ich bis jetzt wie verstanden habe und wo sich mir ein Räzel auftut: Code: [AUSKLAPPEN] [EINKLAPPEN] Type test Field x End Type ;[Typefeld generiert] SeedRnd(MilliSecs()) startzeit = MilliSecs() For i = 0 To 5000 ;[5000 Typeinträge t.test gefüllt] t.test = New test t\x = Rand(0,9999) Next For a.test = Each test ;[Ab hier verstehe ich das nicht mehr. a.test For b.test = Each test ;[gibt es doch noch garnicht, oder? If a\x<b\x ;[Wenn die Zahl a<b ist, dann: Zahlen tauschen t_a = a\x t_b = b\x a\x = t_b b\x = t_a EndIf Next Next endzeit = MilliSecs()-startzeit Print "Fertig" Print endzeit WaitKey() Ich wäre echt dankbar wenn mir das jmd erklären könnte.
www.illusion-games.de Space War 3 \| Space Race \| Galaxy on Fire \| Razoon Gewinner des BCC #57 User posted image

Firstdeathmaker

Do, Apr 01, 2004 10:10
Antworten mit Zitat

Ich sitze gerade auch an diesem Problem und komme nicht weiter. Ich habe Suco-X´s Version mal getestet und sie funktioniert. Nur möchte ich auch gerne verstehen warum sie so funktioniert, damit ich das Prinzip verstehe. Also, ich versuch mal zu schildern was ich bis jetzt wie verstanden habe und wo sich mir ein Räzel auftut:

Code: [AUSKLAPPEN]

Type test
Field x
End Type ;[Typefeld generiert]

SeedRnd(MilliSecs())

startzeit = MilliSecs()

For i = 0 To 5000 ;[5000 Typeinträge t.test gefüllt]
t.test = New test
t\x = Rand(0,9999)
Next

For a.test = Each test ;[Ab hier verstehe ich das nicht mehr. a.test
For b.test = Each test ;[gibt es doch noch garnicht, oder?

If a\x<b\x ;[Wenn die Zahl a<b ist, dann: Zahlen tauschen
t_a = a\x
t_b = b\x
a\x = t_b
b\x = t_a
EndIf

Next
Next

endzeit = MilliSecs()-startzeit

Print "Fertig"
Print endzeit

WaitKey()

Ich wäre echt dankbar wenn mir das jmd erklären könnte.

www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

	MasterK Betreff: Re: ......	Do, Apr 01, 2004 11:04 Antworten mit Zitat
Suco-X hat Folgendes geschrieben: @MasterK : Warum du dir bemerkungen über BB erlaubst obwohl du damit nicht arbeitest und nie gearbeitet hast, wird mir wohl immer ein Rätsel bleiben. Aber jeder hat so seine Hobbys. Zwischen arrays und types gibt es bis auf speed unterschiede und Komfort keine unterschiede beim Thema Sortieren der Einträge. nach dem was ich bisher aa code gesehen hab, kann man types scheinbar nicht per index ansprechen, daher meine aussage. für bucketsort braucht man das nämlich fürs ansprechen (damits sinn macht). allerdings muss dann auch jeder wert einmalig sein, was in diesem fall ja nicht gegeben ist, wie mir auffällt.

MasterK

Betreff: Re: ......

Do, Apr 01, 2004 11:04
Antworten mit Zitat

Suco-X hat Folgendes geschrieben:

nach dem was ich bisher aa code gesehen hab, kann man types scheinbar nicht per index ansprechen, daher meine aussage. für bucketsort braucht man das nämlich fürs ansprechen (damits sinn macht). allerdings muss dann auch jeder wert einmalig sein, was in diesem fall ja nicht gegeben ist, wie mir auffällt.

	Dreamora	Do, Apr 01, 2004 11:43 Antworten mit Zitat
Suco: Ist ein Insertion Sort, eigentlich der schlechteste aller Sortieralgos, wenn man grosse Mengen an Einträgen hat, allerdings sehr schnell bei derart kleinen Mengen Und was den Vergleich von Speed Array - Types betrifft: Das hängt immer von der Sprache ab! Normalerweise macht man das mit Types ( Pointer ), weil das eine konstante umhängezeit von 1 hat, während ein Array meistens zig mal so lange haben kann ( Arrays sind ja nix anderes als LinkedLists und wenn du nen grossen Array hast und etwas ziemlich genau in die Mitte setzen willst, wird er da ziemlich lange suchen im Vergleich zu ner einfachen "Umhängeoperation" bei Types )

Dreamora

Do, Apr 01, 2004 11:43
Antworten mit Zitat

Suco: Ist ein Insertion Sort, eigentlich der schlechteste aller Sortieralgos, wenn man grosse Mengen an Einträgen hat, allerdings sehr schnell bei derart kleinen Mengen Smile

Und was den Vergleich von Speed Array - Types betrifft: Das hängt immer von der Sprache ab! Normalerweise macht man das mit Types ( Pointer ), weil das eine konstante umhängezeit von 1 hat, während ein Array meistens zig mal so lange haben kann ( Arrays sind ja nix anderes als LinkedLists und wenn du nen grossen Array hast und etwas ziemlich genau in die Mitte setzen willst, wird er da ziemlich lange suchen im Vergleich zu ner einfachen "Umhängeoperation" bei Types )

	Rallimen Sieger des 30-EUR-Wettbewerbs	Do, Apr 01, 2004 23:53 Antworten mit Zitat
Suco-X: Das mit einem wert zu sortieren ist schon wesentlich schneller , aber wenn ich Types habe mit vielen Fields dann wird das immer langsamer, da deine Version ja die Werte tauscht, meine tauscht das komplette type!, MasterK: wenn ich Quicksort richtig verstehe sollte das auch auf Types umsetzbar sein, die schwierigkeit besteht allerdings darin das ich nicht direckt auf die einzelnen Types zugreifen kann! dreamora: ich glaube eher das Suco´s Routine auf bubblesort aufbaut! Hier hab ich etwas gefunden, was den Speedvergleich der verschiedenen Sortiermethoden angeht, einfach mal auf start klicken http://www.inf.fh-flensburg.de...ontest.htm
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Do, Apr 01, 2004 23:53
Antworten mit Zitat

Suco-X:

Das mit einem wert zu sortieren ist schon wesentlich schneller , aber wenn ich Types habe mit vielen Fields dann wird das immer langsamer, da deine Version ja die Werte tauscht, meine tauscht das komplette type!,

MasterK:
wenn ich Quicksort richtig verstehe sollte das auch auf Types umsetzbar sein, die schwierigkeit besteht allerdings darin das ich nicht direckt auf die einzelnen Types zugreifen kann!

dreamora:
ich glaube eher das Suco´s Routine auf bubblesort aufbaut!

Hier hab ich etwas gefunden, was den Speedvergleich der verschiedenen Sortiermethoden angeht, einfach mal auf start klicken
http://www.inf.fh-flensburg.de...ontest.htm

[BB2D | BB3D | BB+]

	Dreamora	Fr, Apr 02, 2004 0:05 Antworten mit Zitat
Sorry hast recht, is bubblesort. Insertion sort würde im Endeffekt zu leicht besseren Resultaten führen weil der Algo da definitiv N * N schleifendurchläufe macht. Zum optimieren: Immer das letzte Element der Typeliste nehmen und an den Start setzen und solange es kleiner/grösser als das nächste ist, es mit dem nächsten vertauschen ( den Type bzw. seine Instanz. nicht den wert! ). Danach wieder das letzte und wiederholen. Das is im schlimmsten Fall so langsam wieder Algo da, wird aber tendenziel beträchtlich schneller sein Bei der Menge an Types muss Quicksort net ma schneller sein, da die zu sortierende Menge extrem klein is und Quicksort & Shellsort ihre Stärken erst in beträchtlichen grösseren Mengen haben Bubblesort und einige andere Lowlevel sortieralgorithmen sind da um einiges effizienter im normalfall da sie nicht soviel "überarbeit" leisten wie Quicksort. Und was die sortierung betrifft: am einfachsten sortierst du beim erstellen schon indem du einfach jedes neue element schon richtig einsortierst (Insertion Sort) indem du einfach die typelist durchgehst ( am besten gleich von hinten nach vorne ) und jeweils vertauscht wenn es grösser/kleiner is

Dreamora

Fr, Apr 02, 2004 0:05
Antworten mit Zitat

Sorry hast recht, is bubblesort. Insertion sort würde im Endeffekt zu leicht besseren Resultaten führen weil der Algo da definitiv N * N schleifendurchläufe macht.
Zum optimieren: Immer das letzte Element der Typeliste nehmen und an den Start setzen und solange es kleiner/grösser als das nächste ist, es mit dem nächsten vertauschen ( den Type bzw. seine Instanz. nicht den wert! ). Danach wieder das letzte und wiederholen.

Das is im schlimmsten Fall so langsam wieder Algo da, wird aber tendenziel beträchtlich schneller sein

Bei der Menge an Types muss Quicksort net ma schneller sein, da die zu sortierende Menge extrem klein is und Quicksort & Shellsort ihre Stärken erst in beträchtlichen grösseren Mengen haben

Bubblesort und einige andere Lowlevel sortieralgorithmen sind da um einiges effizienter im normalfall da sie nicht soviel "überarbeit" leisten wie Quicksort.

Und was die sortierung betrifft: am einfachsten sortierst du beim erstellen schon indem du einfach jedes neue element schon richtig einsortierst (Insertion Sort) indem du einfach die typelist durchgehst ( am besten gleich von hinten nach vorne ) und jeweils vertauscht wenn es grösser/kleiner is

	MasterK	Fr, Apr 02, 2004 2:01 Antworten mit Zitat
Rallimen hat Folgendes geschrieben: MasterK: wenn ich Quicksort richtig verstehe sollte das auch auf Types umsetzbar sein, die schwierigkeit besteht allerdings darin das ich nicht direckt auf die einzelnen Types zugreifen kann! quicksort ist machbar, ich meinte aber bucketsort. hat sich aber erledigt, da ja durchaus mehrere types (oder wie auch immer ne variable von dem typ heisst) den gleichen wert haben können

MasterK

Fr, Apr 02, 2004 2:01
Antworten mit Zitat

Rallimen hat Folgendes geschrieben:

MasterK:
wenn ich Quicksort richtig verstehe sollte das auch auf Types umsetzbar sein, die schwierigkeit besteht allerdings darin das ich nicht direckt auf die einzelnen Types zugreifen kann!

quicksort ist machbar, ich meinte aber bucketsort. hat sich aber erledigt, da ja durchaus mehrere types (oder wie auch immer ne variable von dem typ heisst) den gleichen wert haben können

	Dreamora	Fr, Apr 02, 2004 9:24 Antworten mit Zitat
Naja aber selbst wenn mehrere den gleichen Wert haben können, macht eine Sortierung ( sofern häufig Abfragen nach Wert vorkommen ) Sinn, da damit die durchschnittliche Suchzeit minimiert wird. Es sagt ja niemand, das es in einer zu sortierenden Menge nicht mehrmals den gleichen Wert haben kann, weil am Algorithmus ändert das ja dann nichts. Was allerdings dann auch eine Variante ist, ist dass jeder Type nen zusätzlichen Wert "Häufigkeit" bekommt der um 1 erhöht wird, jedes ma wenn der Type erfragt wird, und dann nach diesem Wert sortieren. Das macht zum einen den Sortieralgorithmus konstant, da normalerweise nur um 1 Stelle nach vorne gerutsch wird, zum anderen findest du so häufig benötigte Types erheblich schneller weil For Type each type ja auch von vorne nach hinten durch die liste geht.

Dreamora

Fr, Apr 02, 2004 9:24
Antworten mit Zitat

Naja aber selbst wenn mehrere den gleichen Wert haben können, macht eine Sortierung ( sofern häufig Abfragen nach Wert vorkommen ) Sinn, da damit die durchschnittliche Suchzeit minimiert wird.
Es sagt ja niemand, das es in einer zu sortierenden Menge nicht mehrmals den gleichen Wert haben kann, weil am Algorithmus ändert das ja dann nichts.
Was allerdings dann auch eine Variante ist, ist dass jeder Type nen zusätzlichen Wert "Häufigkeit" bekommt der um 1 erhöht wird, jedes ma wenn der Type erfragt wird, und dann nach diesem Wert sortieren.
Das macht zum einen den Sortieralgorithmus konstant, da normalerweise nur um 1 Stelle nach vorne gerutsch wird, zum anderen findest du so häufig benötigte Types erheblich schneller weil For Type each type ja auch von vorne nach hinten durch die liste geht.

	Rallimen Sieger des 30-EUR-Wettbewerbs	Fr, Apr 02, 2004 9:32 Antworten mit Zitat
werde mich da mal mit auseinander setzen, und mal eine insetion proggen, denn diese bubblesort geht mit zahlen ja noch schnell genug, aber bei Strings schiessen die millisecs voll in die höhe!
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Fr, Apr 02, 2004 9:32
Antworten mit Zitat

werde mich da mal mit auseinander setzen, und mal eine insetion proggen, denn diese bubblesort geht mit zahlen ja noch schnell genug, aber bei Strings schiessen die millisecs voll in die höhe!

[BB2D | BB3D | BB+]

	Dreamora	Fr, Apr 02, 2004 9:40 Antworten mit Zitat
Ja, strings sind immer ein wenig umständlich beim sortieren, da sie innerhalb des SortierAlgos eine weitere Loop erfordern um die buchstaben im string selbst zu vergleichen

Dreamora

Fr, Apr 02, 2004 9:40
Antworten mit Zitat

Ja, strings sind immer ein wenig umständlich beim sortieren, da sie innerhalb des SortierAlgos eine weitere Loop erfordern um die buchstaben im string selbst zu vergleichen

	Hubsi	Fr, Apr 02, 2004 10:47 Antworten mit Zitat
Firstdeathmaker hat Folgendes geschrieben: Ich sitze gerade auch an diesem Problem und komme nicht weiter. Ich habe Suco-X´s Version mal getestet und sie funktioniert. Nur möchte ich auch gerne verstehen warum sie so funktioniert, damit ich das Prinzip verstehe. Also, ich versuch mal zu schildern was ich bis jetzt wie verstanden habe und wo sich mir ein Räzel auftut: Die Variablen a und b sind nur das Handle des Eintrags. Man könnte es auch mit einem Dim-Feld vergleichen: Code: [AUSKLAPPEN] [EINKLAPPEN] For a=0 To 5000 For b=0 To 5000 If test(a)=test(b) Then lustige Sachen Next Next Ich denke der Knoten sollte gelöst sein
Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

Hubsi

Fr, Apr 02, 2004 10:47
Antworten mit Zitat

Firstdeathmaker hat Folgendes geschrieben:

Die Variablen a und b sind nur das Handle des Eintrags. Man könnte es auch mit einem Dim-Feld vergleichen:
Code: [AUSKLAPPEN]

For a=0 To 5000
For b=0 To 5000
If test(a)=test(b) Then lustige Sachen
Next
Next

Ich denke der Knoten sollte gelöst sein Smile

Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

	MasterK	Fr, Apr 02, 2004 11:12 Antworten mit Zitat
Dreamora hat Folgendes geschrieben: Naja aber selbst wenn mehrere den gleichen Wert haben können, macht eine Sortierung ( sofern häufig Abfragen nach Wert vorkommen ) Sinn, da damit die durchschnittliche Suchzeit minimiert wird. Es sagt ja niemand, das es in einer zu sortierenden Menge nicht mehrmals den gleichen Wert haben kann, weil am Algorithmus ändert das ja dann nichts. nochmal: ich sprach von bucketsort, das ist ein schubladenprinzip. man hat dabei 2 felder, das quellfeld und das zielfeld. man geht das quellfeld von vorn bis hinten durch, nimmt sich den wert und packt ihn in das zielfeld, welches diesem wert entspricht. ist also etwas schwerer, das zu realiseren, wenn mehrere einträge den gleichen wert haben. es geht, aber das steigert natürlich den aufwand. sonst würde der aufwand bei N liegen.

MasterK

Fr, Apr 02, 2004 11:12
Antworten mit Zitat

Dreamora hat Folgendes geschrieben:

nochmal: ich sprach von bucketsort, das ist ein schubladenprinzip. man hat dabei 2 felder, das quellfeld und das zielfeld. man geht das quellfeld von vorn bis hinten durch, nimmt sich den wert und packt ihn in das zielfeld, welches diesem wert entspricht. ist also etwas schwerer, das zu realiseren, wenn mehrere einträge den gleichen wert haben. es geht, aber das steigert natürlich den aufwand. sonst würde der aufwand bei N liegen.

	Dreamora	Fr, Apr 02, 2004 12:09 Antworten mit Zitat
keine Ahnung, wir lernen hier nur effiziente Sortieralgorithmen die in ihrem Array operieren können, weil alle anderen Sortieralgos lediglich 2ter Klasse sind. Kann mich von daher net an nen Bucketsort erinnern.

Dreamora

Fr, Apr 02, 2004 12:09
Antworten mit Zitat

keine Ahnung, wir lernen hier nur effiziente Sortieralgorithmen die in ihrem Array operieren können, weil alle anderen Sortieralgos lediglich 2ter Klasse sind. Kann mich von daher net an nen Bucketsort erinnern.

	MasterK	Fr, Apr 02, 2004 12:13 Antworten mit Zitat
aha... 2ter klasse... nur dass bucketsort bei geeigneten daten das schnellste wäre. übrigens: quicksort wird nicht langsamer sein als bubblesort, auch nicht bei kleinen datenmengen (man wird höchstens nur keinen unterschied feststellen). und bei 5000 elementen könnte sich quicksort schon positiv bemerkbar machen

MasterK

Fr, Apr 02, 2004 12:13
Antworten mit Zitat

aha... 2ter klasse...
nur dass bucketsort bei geeigneten daten das schnellste wäre.
übrigens: quicksort wird nicht langsamer sein als bubblesort, auch nicht bei kleinen datenmengen (man wird höchstens nur keinen unterschied feststellen). und bei 5000 elementen könnte sich quicksort schon positiv bemerkbar machen

	Dreamora	Fr, Apr 02, 2004 12:51 Antworten mit Zitat
Bei Sortieralgos geht man aber nicht von geeigneten Daten aus sondern vom Worst Case ausser man hat eine verhältnismässig sichere Angabe darüber, wie die Daten im Grossteil der Fälle strukturiert sein werden. Und was den Quicksoft vs Bubblesort betrifft: Du vergisst, dass der Quicksort rekursiv ist und Funktionsaufrufe zeit brauchen. Drum wird sich erst ab einer geeigneten Menge der Nachteil der dort eingefahren wird, wieder ausgeglichen. ( Wirste in verschiedenen Programmierhandbüchern so finden, die sich mit Algorithmen und Effizienzanalysen beschäftigen ) Ein SortierAlgo der von einem Array in ein zweites Array sortiert wird nie so schnell sein, wie einer der auf sich selbst operiert. Hinzu kommt, dass dein Bucketsort, so wie du ihn beschreibst, O( N^2 ) Laufzeit hat, da er zuerst durch den Quellarray durch muss -> O( N ) und dann muss er noch einen Insertion Sort auf den ZielArray ausführen -> O( N ) und da er das für jedes Element machen muss gibt das O( N ) * O( N ) = O( N^2 ). Dies is nebenher auch ihre Mindestestzeit, da er durch jeden Array min. 1 durch muss zum auslesen und auffüllen, da du ja nicht wissen kannst, wohin das Element kommt ohne suchen oder hashen. Letzteres würd das ganze allerdings noch ineffizienter machen.

Dreamora

Fr, Apr 02, 2004 12:51
Antworten mit Zitat

Bei Sortieralgos geht man aber nicht von geeigneten Daten aus sondern vom Worst Case ausser man hat eine verhältnismässig sichere Angabe darüber, wie die Daten im Grossteil der Fälle strukturiert sein werden.
Und was den Quicksoft vs Bubblesort betrifft: Du vergisst, dass der Quicksort rekursiv ist und Funktionsaufrufe zeit brauchen. Drum wird sich erst ab einer geeigneten Menge der Nachteil der dort eingefahren wird, wieder ausgeglichen. ( Wirste in verschiedenen Programmierhandbüchern so finden, die sich mit Algorithmen und Effizienzanalysen beschäftigen )

Ein SortierAlgo der von einem Array in ein zweites Array sortiert wird nie so schnell sein, wie einer der auf sich selbst operiert. Hinzu kommt, dass dein Bucketsort, so wie du ihn beschreibst, O( N^2 ) Laufzeit hat, da er zuerst durch den Quellarray durch muss -> O( N ) und dann muss er noch einen Insertion Sort auf den ZielArray ausführen -> O( N ) und da er das für jedes Element machen muss gibt das O( N ) * O( N ) = O( N^2 ). Dies is nebenher auch ihre Mindestestzeit, da er durch jeden Array min. 1 durch muss zum auslesen und auffüllen, da du ja nicht wissen kannst, wohin das Element kommt ohne suchen oder hashen. Letzteres würd das ganze allerdings noch ineffizienter machen.

	MasterK	Fr, Apr 02, 2004 17:00 Antworten mit Zitat
Dreamora hat Folgendes geschrieben: Bei Sortieralgos geht man aber nicht von geeigneten Daten aus sondern vom Worst Case... man entscheidet anhand der daten (bzw ihrer speicherart), welches algorithmus man verwendet. sind die daten zB in einem baum gespeichert, dann ist es doch optimal, ein heapsort auf genau diesen baum anzuwenden? dann erspart man sich das aufbauen des baums. heap bauen, letztes element raus, heap bauen, nächstes usw. hast du ein array von 1 bis 5000 mit den werten 1 bis 5000 und kommt jeder wert nur einmal vor, ist bucketsort das schnellste (auch schon gesehen als radix-sort). Dreamora hat Folgendes geschrieben: Und was den Quicksoft vs Bubblesort betrifft: Du vergisst, dass der Quicksort rekursiv ist und Funktionsaufrufe zeit brauchen. Drum wird sich erst ab einer geeigneten Menge der Nachteil der dort eingefahren wird, wieder ausgeglichen. willkommen im 21ten jahrhundert. meinst du wirklich, dass die paar nanosekunden irgendjemand merkt? die daten müssten da schon sehr ungünstig sein. man geht übrigens auch nicht vom worst-case (zitat davor)aus, das ist blödsinn. dann würde nach deiner logik niemand zu quicksort greifen? der aufwand ist abhängig von der konstellation der eingabedaten, und da unterscheidet man worst case, best case sowie average case (der erwartete fall). und wenn ich weiss, wie meine daten im beschaffen sind, dann entscheide ich. das gilt natürlich immer dafür, dass man das optimale für die aktuelle situation sucht und sich keine allgemeingültige sortierroutine bauen will. habe ich keine so klare situation wie zB im oben genannten beispiel für bucketsort, entscheide ich mir für den average case Dreamora hat Folgendes geschrieben: ( Wirste in verschiedenen Programmierhandbüchern so finden, die sich mit Algorithmen und Effizienzanalysen beschäftigen ) (das ist gut, ich hab in den vorlesungen scheinbar nicht aufgepasst) Dreamora hat Folgendes geschrieben: Ein SortierAlgo der von einem Array in ein zweites Array sortiert wird nie so schnell sein, wie einer der auf sich selbst operiert. Hinzu kommt, dass dein Bucketsort, so wie du ihn beschreibst, O( N^2 ) Laufzeit hat, da er zuerst durch den Quellarray durch muss -> O( N ) und dann muss er noch einen Insertion Sort auf den ZielArray ausführen -> O( N ) und da er das für jedes Element machen muss gibt das O( N ) * O( N ) = O( N^2 ). Dies is nebenher auch ihre Mindestestzeit, da er durch jeden Array min. 1 durch muss zum auslesen und auffüllen, da du ja nicht wissen kannst, wohin das Element kommt ohne suchen oder hashen. Letzteres würd das ganze allerdings noch ineffizienter machen. ok, nochmal ganz langsam für dich zum mitmeißeln: ich hab ein array quell von 1 bis 5000 wo die zahlen von 1 bis 5000 gespeichert sind. ausserdem hab ich ein array ziel mit 1 bis 5000. dann lautet der ablauf: Code: [AUSKLAPPEN] [EINKLAPPEN] for x = 1 to 5000 zielarray(quellarray(x)) = quellarray(x) next x aufwand: N für den hier aufgeführten fall aber nicht wirklich anwendbar wie von mir schon mehrmals gesagt, da durchaus 5000 mal die gleiche zahl vorkommen kann. aber ich denke mal man sieht, dass ich von meinen daten ausgehen sollte, wenn ich mich für einen algorithmus entscheide. es wäre mehr als dumm vom worst case auszugehen, wenn der in der praxis nicht auftreten kann (wie gesagt, es sei denn man will sich eine allgemeine sortierroutine schreiben). übrigens: das hashen (das von dir angesprochene) würde den mathematischen aufwand nicht erhöhen, da es teil eines durchlauf ist.

MasterK

Fr, Apr 02, 2004 17:00
Antworten mit Zitat

Dreamora hat Folgendes geschrieben:

Bei Sortieralgos geht man aber nicht von geeigneten Daten aus sondern vom Worst Case...

man entscheidet anhand der daten (bzw ihrer speicherart), welches algorithmus man verwendet. sind die daten zB in einem baum gespeichert, dann ist es doch optimal, ein heapsort auf genau diesen baum anzuwenden? dann erspart man sich das aufbauen des baums. heap bauen, letztes element raus, heap bauen, nächstes usw. hast du ein array von 1 bis 5000 mit den werten 1 bis 5000 und kommt jeder wert nur einmal vor, ist bucketsort das schnellste (auch schon gesehen als radix-sort).

Dreamora hat Folgendes geschrieben:

Und was den Quicksoft vs Bubblesort betrifft: Du vergisst, dass der Quicksort rekursiv ist und Funktionsaufrufe zeit brauchen. Drum wird sich erst ab einer geeigneten Menge der Nachteil der dort eingefahren wird, wieder ausgeglichen.

willkommen im 21ten jahrhundert. meinst du wirklich, dass die paar nanosekunden irgendjemand merkt? die daten müssten da schon sehr ungünstig sein.

man geht übrigens auch nicht vom worst-case (zitat davor)aus, das ist blödsinn. dann würde nach deiner logik niemand zu quicksort greifen? der aufwand ist abhängig von der konstellation der eingabedaten, und da unterscheidet man worst case, best case sowie average case (der erwartete fall). und wenn ich weiss, wie meine daten im beschaffen sind, dann entscheide ich. das gilt natürlich immer dafür, dass man das optimale für die aktuelle situation sucht und sich keine allgemeingültige sortierroutine bauen will. habe ich keine so klare situation wie zB im oben genannten beispiel für bucketsort, entscheide ich mir für den average case

Dreamora hat Folgendes geschrieben:

( Wirste in verschiedenen Programmierhandbüchern so finden, die sich mit Algorithmen und Effizienzanalysen beschäftigen )

(das ist gut, ich hab in den vorlesungen scheinbar nicht aufgepasst)

Dreamora hat Folgendes geschrieben:

Ein SortierAlgo der von einem Array in ein zweites Array sortiert wird nie so schnell sein, wie einer der auf sich selbst operiert. Hinzu kommt, dass dein Bucketsort, so wie du ihn beschreibst, O( N^2 ) Laufzeit hat, da er zuerst durch den Quellarray durch muss -> O( N ) und dann muss er noch einen Insertion Sort auf den ZielArray ausführen -> O( N ) und da er das für jedes Element machen muss gibt das O( N ) * O( N ) = O( N^2 ). Dies is nebenher auch ihre Mindestestzeit, da er durch jeden Array min. 1 durch muss zum auslesen und auffüllen, da du ja nicht wissen kannst, wohin das Element kommt ohne suchen oder hashen. Letzteres würd das ganze allerdings noch ineffizienter machen.

ok, nochmal ganz langsam für dich zum mitmeißeln:
ich hab ein array quell von 1 bis 5000 wo die zahlen von 1 bis 5000 gespeichert sind. ausserdem hab ich ein array ziel mit 1 bis 5000. dann lautet der ablauf:
Code: [AUSKLAPPEN]

for x = 1 to 5000
zielarray(quellarray(x)) = quellarray(x)
next x

aufwand: N
für den hier aufgeführten fall aber nicht wirklich anwendbar wie von mir schon mehrmals gesagt, da durchaus 5000 mal die gleiche zahl vorkommen kann. aber ich denke mal man sieht, dass ich von meinen daten ausgehen sollte, wenn ich mich für einen algorithmus entscheide. es wäre mehr als dumm vom worst case auszugehen, wenn der in der praxis nicht auftreten kann (wie gesagt, es sei denn man will sich eine allgemeine sortierroutine schreiben).
übrigens: das hashen (das von dir angesprochene) würde den mathematischen aufwand nicht erhöhen, da es teil eines durchlauf ist.

	Rallimen Sieger des 30-EUR-Wettbewerbs	Fr, Apr 02, 2004 21:18 Antworten mit Zitat
hier die neue....mal mit strings und vielen Fields komplett zum testen der Speed einfach die functionen tauschenCode: [AUSKLAPPEN] [EINKLAPPEN] SeedRnd (MilliSecs ()) Type Test Field X$,y,z,s,d,f,g$,h$ End Type For t= 0 To 1000 ralf.Test = New Test ralf\x$ = Rand (0,99999); <<<<dieser wird sortiert ralf\y = Rand (0,99999) ralf\z = Rand (0,99999) ralf\s = Rand (0,99999) ralf\d = Rand (0,99999) ralf\f = Rand (0,99999) ralf\g$ = Rand (10000,99999) ralf\h$ = Rand (10000,99999) Next time = MilliSecs () Global wert_1$ ;---------------------------------------------- ;SortTypefield () ; <<< die alte Routine insSortTypefield () ; <<< die neue Routine ;---------------------------------------------- Print MilliSecs ()-time Print "Taste >>> Weiter" WaitKey ;Anzeigen ;For Ralf.test = Each test ;Print Ralf\x ;Next ;WaitKey End ;######################################################################## ;Function SortTypefield () ; Repeat ; ralf.Test = First test ; wert_1 = ralf\x ; Repeat ; ralf.Test = After (ralf) ; zur nächsten schalten ; If ralf = Null Then Exit ; wenn letzte erreicht dann schleife verlassen ; If wert_1 > ralf\x Then ; prüfen und ggf tauschen ; Insert Ralf Before Before Ralf ; x=x+1 ; dummy Var >wenn = 0 dann fertig sortiert ; Else ; wert_1 = ralf\x ; 1. wert sichern ; End If ; Forever ; If x = 0 Then Exit ;>wenn = 0 dann fertig sortiert ; x= 0 ; Forever ; Return ;End Function Function SortTypefield () Repeat ralf.Test = First test Repeat wert_1 = ralf\x ; 1. wert sichern ralf.Test = After (ralf) ; zur nächsten schalten If ralf = Null Then Exit ; wenn letzte erreicht dann schleife verlassen If wert_1 > ralf\x Then ; prüfen und ggf tauschen Insert Ralf Before Before Ralf x=x+1 ; dummy Var >wenn = 0 dann fertig sortiert ;DebugLog ralf\x End If Forever If x = 0 Then Exit ;>wenn = 0 dann fertig sortiert x= 0 Forever End Function Function insSortTypefield () Repeat ralf.Test = First test feld = 0 Repeat ralf.Test = After (ralf) feld = feld + 1 Until feld > bis_sort If ralf = Null Then Return bis_sort = bis_sort +1 Repeat wert_1 = ralf\x ralf.Test = Before (ralf) If ralf = Null Then Exit If wert_1 < ralf\x Then Insert Ralf After After Ralf ralf.Test = Before (ralf) If ralf = Null Then Exit Else Exit End If Forever Forever End Function bei mir bis 5x schneller
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Fr, Apr 02, 2004 21:18
Antworten mit Zitat

hier die neue....mal mit strings und vielen Fields
komplett
zum testen der Speed einfach die functionen tauschenCode: [AUSKLAPPEN]

SeedRnd (MilliSecs ())
Type Test
Field X$,y,z,s,d,f,g$,h$
End Type

   For t= 0 To 1000
      ralf.Test = New Test
      ralf\x$ = Rand (0,99999); <<<<dieser wird sortiert
      ralf\y = Rand (0,99999)
      ralf\z = Rand (0,99999)
      ralf\s = Rand (0,99999)
      ralf\d = Rand (0,99999)
      ralf\f = Rand (0,99999)
      ralf\g$ = Rand (10000,99999)
      ralf\h$ = Rand (10000,99999)
   Next

time = MilliSecs ()
Global wert_1$
;----------------------------------------------
;SortTypefield () ; <<< die alte Routine
insSortTypefield () ; <<< die neue Routine
;----------------------------------------------

Print MilliSecs ()-time
Print "Taste >>> Weiter"
WaitKey

;Anzeigen
;For Ralf.test = Each test
;Print Ralf\x
;Next
;WaitKey
   End

   ;########################################################################
;Function SortTypefield ()
; Repeat
;    ralf.Test = First test
;       wert_1 = ralf\x
; Repeat
; ralf.Test = After (ralf) ; zur nächsten schalten
; If ralf = Null Then Exit ; wenn letzte erreicht dann schleife verlassen
; If wert_1 > ralf\x Then ; prüfen und ggf tauschen
; Insert Ralf Before Before Ralf
; x=x+1 ; dummy Var >wenn = 0 dann fertig sortiert
;                   Else
;                   wert_1 = ralf\x ; 1. wert sichern
; End If
; Forever
; If x = 0 Then Exit ;>wenn = 0 dann fertig sortiert
; x= 0
; Forever
; Return
;End Function
Function SortTypefield ()
Repeat
ralf.Test = First test
Repeat
wert_1 = ralf\x ; 1. wert sichern
ralf.Test = After (ralf) ; zur nächsten schalten
If ralf = Null Then Exit ; wenn letzte erreicht dann schleife verlassen
If wert_1 > ralf\x Then ; prüfen und ggf tauschen
Insert Ralf Before Before Ralf
x=x+1 ; dummy Var >wenn = 0 dann fertig sortiert
;DebugLog ralf\x
End If
Forever
If x = 0 Then Exit ;>wenn = 0 dann fertig sortiert
x= 0
Forever
End Function

Function insSortTypefield ()
Repeat
   ralf.Test = First test
   feld = 0
   Repeat
      ralf.Test = After (ralf)
      feld = feld + 1
   Until feld > bis_sort
   If ralf = Null Then Return
   bis_sort = bis_sort +1
   Repeat
      wert_1 = ralf\x
      ralf.Test = Before (ralf)
      If ralf = Null Then Exit
If wert_1 < ralf\x Then
Insert Ralf After After Ralf
         ralf.Test = Before (ralf)
         If ralf = Null Then Exit
      Else
         Exit
End If
Forever
Forever
End Function

bei mir bis 5x schneller

[BB2D | BB3D | BB+]

	Dreamora	Mo, Apr 05, 2004 9:05 Antworten mit Zitat
MasterK: ich studiere Computer Science an der ETH Zürich und ich glaube kaum das unser Departementsvorsteher nicht weiss wovon er spricht. Hinzu kommt dass nicht du die Frage gestellt hast, dich also nicht als Gott aufzuspielen brauchst was die voraussetzungen für die Daten betrifft. ( wenn 1-5000 schon richtig sortiert sind brauchste keinen Sortalgo ) Es wird versucht hier nen effizienten Algo aufzustellen. Wenn ihr schon die Vorlesung habt, solltet ihr vielleicht gewisse technische Einschränkungen auch ma angucken und dergleichen anstatt nur die Algo theoretisch anzugucken. Aber lassen wir die Diskussion, die endet auf nix.

Dreamora

Mo, Apr 05, 2004 9:05
Antworten mit Zitat

MasterK: ich studiere Computer Science an der ETH Zürich und ich glaube kaum das unser Departementsvorsteher nicht weiss wovon er spricht. Hinzu kommt dass nicht du die Frage gestellt hast, dich also nicht als Gott aufzuspielen brauchst was die voraussetzungen für die Daten betrifft. ( wenn 1-5000 schon richtig sortiert sind brauchste keinen Sortalgo )
Es wird versucht hier nen effizienten Algo aufzustellen.
Wenn ihr schon die Vorlesung habt, solltet ihr vielleicht gewisse technische Einschränkungen auch ma angucken und dergleichen anstatt nur die Algo theoretisch anzugucken.

Aber lassen wir die Diskussion, die endet auf nix.

Gehe zu Seite 1, 2 Weiter

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Types sortieren .... Optimierung... geht das schneller??

Betreff: Types sortieren .... Optimierung... geht das schneller??

Betreff: ......

Betreff: Re: ......