Bubblesort seeehr langsam

Übersicht

BlitzBasic

Allgemein

	Iguan Betreff: Bubblesort seeehr langsam	Do, Aug 17, 2006 13:37 Antworten mit Zitat
Tachwohl! ich möchte gerne alle Einträge in einem Type der X koordinate nach sortiert. ich verwende dazu das Bubblesort verfahren, siehe folgender code: Code: [AUSKLAPPEN] [EINKLAPPEN] Type CWerte Field X# End Type Global C.CWerte ...... ...... CPX1# = 0 Anzahl = 0 For C = Each CWerte Anzahl = Anzahl + 1 Next For ii = 1 To Anzahl iii = 0 For C = Each CWerte iii = iii + 1 If CPX1# > C\X# And iii > 1 Then Insert C Before Before C CPX1# = C\X# Next Next das funktioniert ja auch, aber bereits nach 10 Einträgen benötigt mein PC ca 5 sekunden!!!! Das kann doch nicht sein... das währen dann ja lediglich ca. 110 schleifendurchläufe... das sollte doch kein problem sein... seht ihr da einen Fehler im code? Oder gibt es sonst was schnelleres/einfacheres?? Greez Iguan

Iguan

Betreff: Bubblesort seeehr langsam

Do, Aug 17, 2006 13:37
Antworten mit Zitat

Tachwohl!

ich möchte gerne alle Einträge in einem Type der X koordinate nach sortiert.
ich verwende dazu das Bubblesort verfahren, siehe folgender code:

Code: [AUSKLAPPEN]

Type CWerte
Field X#
End Type

Global C.CWerte

......
......

CPX1# = 0
Anzahl = 0

For C = Each CWerte
Anzahl = Anzahl + 1
Next

For ii = 1 To Anzahl
iii = 0
For C = Each CWerte
iii = iii + 1
If CPX1# > C\X# And iii > 1 Then Insert C Before Before C
CPX1# = C\X#
Next
Next

das funktioniert ja auch, aber bereits nach 10 Einträgen benötigt mein PC
ca 5 sekunden!!!! Das kann doch nicht sein... das währen dann ja lediglich ca. 110 schleifendurchläufe... das sollte doch kein problem sein...

seht ihr da einen Fehler im code? Oder gibt es sonst was schnelleres/einfacheres??

Greez

Iguan

	Mr.Keks	Do, Aug 17, 2006 13:47 Antworten mit Zitat
lol? ich habe gerade deinen code bei mir getestet und mein rechner braucht erst ab etwas über 10 000 einträgen fünf sekunden ^^. es muss an etwas anderem liegen xD
MrKeks.net

Mr.Keks

Do, Aug 17, 2006 13:47
Antworten mit Zitat

lol?

ich habe gerade deinen code bei mir getestet und mein rechner braucht erst ab etwas über 10 000 einträgen fünf sekunden ^^. es muss an etwas anderem liegen xD

MrKeks.net

	Iguan	Do, Aug 17, 2006 14:13 Antworten mit Zitat
seltsam!! es kann ja nur an diesem code liegen! ich führe ihn in der Hauptschleife aus.. Code: [AUSKLAPPEN] [EINKLAPPEN] repeat if MouseHit(1) then ....neuen eintrag erstellen ....sortieren end if until keyhit(1)

Iguan

Do, Aug 17, 2006 14:13
Antworten mit Zitat

seltsam!! es kann ja nur an diesem code liegen!
ich führe ihn in der Hauptschleife aus..

Code: [AUSKLAPPEN]

repeat

if MouseHit(1) then

....neuen eintrag erstellen

....sortieren

end if

until keyhit(1)

	Dreamora	Do, Aug 17, 2006 14:16 Antworten mit Zitat
Gibt es einen Grund das du in der Mainloop versuchst zu sortieren? Normalerweise sortiert man nur, wenn sich etwas geändert hat (oder ausreichend geändert hat um den Aufwand zu rechtfertigen ...)
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Do, Aug 17, 2006 14:16
Antworten mit Zitat

Gibt es einen Grund das du in der Mainloop versuchst zu sortieren?
Normalerweise sortiert man nur, wenn sich etwas geändert hat (oder ausreichend geändert hat um den Aufwand zu rechtfertigen ...)

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Iguan	Do, Aug 17, 2006 14:18 Antworten mit Zitat
sieh den code oben an! ich sortiere nur, nachdem ein neuer eintrag erstellt wurde... das ist grund genug finde ich

Iguan

Do, Aug 17, 2006 14:18
Antworten mit Zitat

sieh den code oben an! ich sortiere nur, nachdem ein neuer eintrag erstellt wurde... das ist grund genug finde ich Wink

	Dreamora	Do, Aug 17, 2006 14:26 Antworten mit Zitat
Find ich supi dein Kommentar, speziell da du den Teil mit "neues Element einfügen" erst danach reineditiert hast ... Theoretisch ja, macht es sinn nach jedem eingefügten Element zu sortieren. Praktisch nein, wenn du in schneller Folge Elemente einfügst ist das eine ziemlich tödlich Idee. Wenn du nach jedem einfügen Sortieren willst, empfehle ich dir Insertion Sort zu nehmen. Sprich sortier das Element direkt korrekt rein anstatt alles nochma zu sortieren Übrigens dein Code ist kein BubbleSort. Sondern ein Insitu InsertionSort.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Do, Aug 17, 2006 14:26
Antworten mit Zitat

Find ich supi dein Kommentar, speziell da du den Teil mit "neues Element einfügen" erst danach reineditiert hast ...

Theoretisch ja, macht es sinn nach jedem eingefügten Element zu sortieren.
Praktisch nein, wenn du in schneller Folge Elemente einfügst ist das eine ziemlich tödlich Idee. Wenn du nach jedem einfügen Sortieren willst, empfehle ich dir Insertion Sort zu nehmen. Sprich sortier das Element direkt korrekt rein anstatt alles nochma zu sortieren

Übrigens dein Code ist kein BubbleSort. Sondern ein Insitu InsertionSort.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Iguan	Do, Aug 17, 2006 14:32 Antworten mit Zitat
ok, ich versuchs mal so! PS: stimmt, ich habe nachträglich den Beitrag editiert... warst wohl schneller als ich..

Iguan

Do, Aug 17, 2006 14:32
Antworten mit Zitat

ok, ich versuchs mal so!

PS: stimmt, ich habe nachträglich den Beitrag editiert... warst wohl schneller als ich.. Laughing

	Iguan	Do, Aug 17, 2006 14:49 Antworten mit Zitat
ich habs jetzt mal so versucht: Code: [AUSKLAPPEN] [EINKLAPPEN] If MouseHit1 = 1 Then i = 0 For C= Each CWerte i = i + 1 If MouseX() < C\X# Then Exit Next C = Before C C = New CWerte C\X# = MouseX() End if geht aber auch nicht, da mit NEW automatisch ein Eintrag am Ende der Liste eingefügt wird. und... Code: [AUSKLAPPEN] [EINKLAPPEN] insert new c before c ...geht ja auch nicht... wie macht man das dann?

Iguan

Do, Aug 17, 2006 14:49
Antworten mit Zitat

ich habs jetzt mal so versucht:

Code: [AUSKLAPPEN]

If MouseHit1 = 1 Then
i = 0
For C= Each CWerte
i = i + 1
If MouseX() < C\X# Then Exit
Next
C = Before C

C = New CWerte
C\X# = MouseX()
End if

geht aber auch nicht, da mit NEW automatisch ein Eintrag am Ende der Liste
eingefügt wird.

und...
Code: [AUSKLAPPEN]

insert new c before c

...geht ja auch nicht...

wie macht man das dann?

	Mr.Keks	Do, Aug 17, 2006 14:58 Antworten mit Zitat
erst new und dann insert anwenden . is doch eigentlich recht logisch.
MrKeks.net

Mr.Keks

Do, Aug 17, 2006 14:58
Antworten mit Zitat

erst new und dann insert anwenden Wink

. is doch eigentlich recht logisch.

MrKeks.net

	Iguan	Do, Aug 17, 2006 15:15 Antworten mit Zitat
Das ist mir schon klar, aber wie mache ich dass in folgendem code der neue Eintrag VOR der Stelle an der ich die Schleife mit EXIT verlasse, eingefügt wird? Code (diesmal kein Pseudocode): Code: [AUSKLAPPEN] [EINKLAPPEN] Type CWerte Field X Field Y End Type Global C.CWerte SetBuffer BackBuffer() Repeat Cls Color 255,0,0 Oval MouseX()-2,MouseY()-2,4,4 If MouseHit(1) Then i = 0 For C = Each CWerte i = i + 1 If MouseX() < C\X Then Exit Next C = New CWerte C\X = MouseX() C\Y = MouseY() EndIf ;Linien zeichnen CX = 0 CY = 0 For C = Each CWerte If CX > 0 Or CY > 0 Then Line C\X, C\Y,CX,CY CX = C\X CY = C\Y Next Flip Until KeyHit(1) schlussendlich möchte ich gerne, dass es nicht möglich ist, dass eine Linie zurück (nach links) geht.

Iguan

Do, Aug 17, 2006 15:15
Antworten mit Zitat

Das ist mir schon klar, aber wie mache ich dass in folgendem code
der neue Eintrag VOR der Stelle an der ich die Schleife mit EXIT verlasse, eingefügt wird?

Code (diesmal kein Pseudocode):

Code: [AUSKLAPPEN]

Type CWerte
Field X
Field Y
End Type

Global C.CWerte

SetBuffer BackBuffer()

Repeat
Cls

Color 255,0,0
Oval MouseX()-2,MouseY()-2,4,4

If MouseHit(1) Then
i = 0
For C = Each CWerte
   i = i + 1
   If MouseX() < C\X Then Exit
Next

C = New CWerte
C\X = MouseX()
C\Y = MouseY()

EndIf

;Linien zeichnen
CX = 0
CY = 0
For C = Each CWerte
If CX > 0 Or CY > 0 Then Line C\X, C\Y,CX,CY
CX = C\X
CY = C\Y
Next

Flip
Until KeyHit(1)

schlussendlich möchte ich gerne, dass es nicht möglich ist, dass eine Linie zurück (nach links) geht.

	Dreamora	Do, Aug 17, 2006 15:27 Antworten mit Zitat
- i habe ich rausgeworfen. Da nix gezählt werden muss, machts net viel Sinn, zu zählen Code: [AUSKLAPPEN] [EINKLAPPEN] If MouseHit(1) Then local D.CWerte = New CWerte D\X = MouseX() D\Y = MouseY() For C = Each CWerte If MouseX() < C\X Then insert D before C Exit EndIf Next EndIf Code ist net getestet, sollte aber eigentlich funktionieren. Nur mit einer einzigen Variable für CWerte gehts nicht, da du ja eine haben musst die deine Daten drin hat und einen temporären Zeiger auf das aktuell zu überprüfende Objekt
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Do, Aug 17, 2006 15:27
Antworten mit Zitat

- i habe ich rausgeworfen. Da nix gezählt werden muss, machts net viel Sinn, zu zählen

Code: [AUSKLAPPEN]

If MouseHit(1) Then
local D.CWerte = New CWerte

D\X = MouseX()
D\Y = MouseY()

For C = Each CWerte
If MouseX() < C\X Then
insert D before C
Exit
EndIf
Next

EndIf

Code ist net getestet, sollte aber eigentlich funktionieren.
Nur mit einer einzigen Variable für CWerte gehts nicht, da du ja eine haben musst die deine Daten drin hat und einen temporären Zeiger auf das aktuell zu überprüfende Objekt

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Iguan	Do, Aug 17, 2006 15:35 Antworten mit Zitat
Cool! Vielen dank, so klappt es!!!!

Iguan

Do, Aug 17, 2006 15:35
Antworten mit Zitat

Cool! Vielen dank, so klappt es!!!!

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Bubblesort seeehr langsam

Betreff: Bubblesort seeehr langsam