Autor |
Beitrag |
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 14.04.06 13:36
Hallo,
dem Wahnsinn eine Chance, eine kleine Optimierung  .
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:
| procedure Sortiere(var aNumbers : array of double); var AbsDiff,Summ : double; pAi,pAj : ^double; pInt32 :^Cardinal; i,j : integer; begin pInt32 := @AbsDiff; inc(pInt32); pAi := @aNumbers[High(aNumbers)-1]; for i:= High(aNumbers)-1 downto 0 do begin pAj := @aNumbers[High(aNumbers)]; for j:=High(aNumbers) downto 1 do begin AbsDiff := pAi^-pAj^; pInt32^:=pInt32^ AND $7FFFFFFF; Summ :=pAi^+pAj^; pAi^ := (Summ-AbsDiff)*0.5; pAj^ := (Summ+AbsDiff)*0.5; dec(pAj); end; dec(pAi); end; end; |
Gruss Horst
|
|
zemy
      
Beiträge: 207
Win XP Prof.
D7
|
Verfasst: Fr 14.04.06 14:07
Spaceguide hat folgendes geschrieben: | 1) Das sortiert ni
2) Procedures geben keine Werte zurück
3) Den Datentyp int gibt es in Delphi nicht
4) Bei der Deklaration einer Variablen wird der Datentyp nachgestellt und durch einen Doppelpkt. vom Variablennamen getrennt
5) Nach der Angabe des Rückgabewerts einer Funktion muss ein Strichpkt. folgen |
Schon ein Problem, wenn man Stundenlang C/C++ schreibt und dann sich Delphi-Code ausm Ärmel Schütteln soll... Aber es sortiert trotzdem;) Ein einzelner Wert ist sortiert ^^
_________________ LifeIsToShortToThinkAboutTheShortness
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Fr 14.04.06 15:11
Bucketsort macht keine Vergleiche. Bucketsort funktioniert vereinfacht ungefähr so:
Sortiere die Buchstaben im Wort "elephant". Dabei wird einfach gezählt welcher Buchstabe wie häufig vorkommt. Das heisst:
1x"a", 2x"e", 1x"h", 1x"l", 1x"n", 1x"p", 1x"t"
Das kannst du ungefähr so machen:
Delphi-Quelltext 1: 2:
| for I := 1 to length(S) do inc(Haeuffigkeit[S[I]]); | Danach gibst du einfach das Resultat aus...
Das ganze Spielchen kann man dann auch in mehrere Schritte unterteilen. Verglichen hast du die Zahlen bzw. Buchstaben untereinander jedoch nie.
Bei Wikipedia gibt's ein Codeschnipsel in Pascal. Im Code kommt nirgends ein "if", ein "=", "<" oder ">" vor. Auch keine while oder repeat Schleifen. Nur fest vorgegebene for-Schleifen.
|
|
nullplan001
      
Beiträge: 212
Win 2000 Professional, Debian Linux 4.0 (Etch,Stable)
Pascal (FreePascal 2.0.2, TurboPascal 7.0), C(++) (G++/GCC 3.4.2 + MinGW), Java (JDK 1.5.0_07), PHP (PHP 5.1.4)
|
Verfasst: Fr 14.04.06 15:39
Es war ja nur gefragt, ob man denn "if" rauslassen könne. Klar, das geht:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:
| procedure sortarray(var a:array of word); assembler; label loop1, endloop; asm lea cx,a loop1: mov ax,[cx] add cx,2 mov bx,[cx] cmp ax,bx jz endloop jns endloop sub cx,2 mov bx,[cx] add cx,2 mov ax,[cx] endloop: push offset a call sizeof cmp cx,ax jnz loop1 end; |
_________________ Ich fahr' nicht selber, weil ich festgestellt habe: ich fahre zu emotional. Bin 180 gefahren wo 30 erlaubt war... -- Jürgen von der Lippe
|
|
Spaceguide
      
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: Fr 14.04.06 15:48
Das "IF" ist nicht wörtlich gemeint. Das Problem ist eine Sortierung ohne Verzweigungen.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 14.04.06 15:59
Hallo,
bei Bucketsort muss aber noch etwas hinzukommen, das Du naemlich einen sehr eingeschraenkten Wertebereich.
Siehe [url=www.linux-related.de...radix.htm]Hier[/url] bei linstraightradix.
Dies gilt fuer Fliesskommazahln nun meist garnicht.
Aber auch da kann man erst nach Mantissenbytes und dann nach Exponent sortieren.
Dazu muss aber die Anordnung im Speicher genau kennen und es erschliesst sich nicht so leicht.
Hast Du soetwas schon umgesetzt.
Gruss Horst
|
|
F34r0fTh3D4rk
      
Beiträge: 5284
Erhaltene Danke: 27
Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
|
Verfasst: Fr 14.04.06 16:31
|
|
delfiphan
      
Beiträge: 2684
Erhaltene Danke: 32
|
Verfasst: Fr 14.04.06 21:34
Spaceguide hat folgendes geschrieben: | Das Problem ist eine Sortierung ohne Verzweigungen. |
Das Problem ist nicht eine Sortierung ohne Verzweigungen. Er hat ein Array und möchte die möglichst ohne eine komplizierte Sortierroutine sortieren. Dabei geht es nicht darum, ob man ein min(a,b) mathematisch zu einem Audruck mit abs() bzw sqrt(sqr()) umformulieren kann.
Es ist nicht meine Aufgabe, die Threads sauber zu halten. Aber: Er hat lediglich gefragt, ob man 6 Integer-Zahlen möglichst ohne grosse IF-Entscheidungen sortieren kann. Alles andere ist dazugedichtet. DarkCell hat seit dem ersten Post nie mehr was von sich gegeben. Die vielen Hacks hier beantworten imho weder seine Frage noch sind die meisten Codeschnipsel ihm in irgend einer Weise dienlich.
Meine Antwort auf seine Frage: Ja, es ist unter Umständen möglich, aber nicht so, wie du es dir wohl vorstellst. Wenn du ein Array sortieren willst hast du zwingend eine For-Schleife und bei allen klassischen Sortieralgorithmen musst du Zahlen vergleichen (eine Ausnahme ist Bucketsort). Bucketsort hat zwar eine lineare Sortierzeit, ist aber bei einer so kleinen Datenmenge (6 Integers) überhaupt nicht zu empfehlen.
|
|
Jan11
      
Beiträge: 62
|
Verfasst: Mo 17.04.06 17:20
Man kann sie auch einfach in eine Tstringlist schreiben, und da gibt es den befehl Mystringlist.sort; ... dann kannst du sie einfach wieder einlesen
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
| procedure ordnen var(i : integer, mystringlist : Tstringlist, werte : array[1..6] of integer);
begin mystringlist:=Tstringlist.create;
for i := 1 to 6 do begin Mystringlist.add(inttostr(werte[i])); end;
mystringlist.sort;
for i := 1 to 6 do begin werte[i]:=strtoint(mystringlist.strings[i-1]); end;
Mystringlist.free;
end; |
und kann mir mal jemand sagen, wie ich das in sonen coolen delphi-quelltext schreiben kann?
Zuletzt bearbeitet von Jan11 am Di 18.04.06 13:07, insgesamt 1-mal bearbeitet
|
|
F34r0fTh3D4rk
      
Beiträge: 5284
Erhaltene Danke: 27
Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
|
Verfasst: Mo 17.04.06 17:31
Benutzen auch du die Delphi Tags du sollst junger Padawan.
[delphi][/delphi]
|
|
Spaceguide
      
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: Mi 19.04.06 08:19
Jan11, da hast du aber überhaupt nicht nachgedacht. Zahlen als Werte zu sortieren ist gänzlich anders als Zahlen als Strings:
1
2
3
100
200
300
wird bei dir zu
1
100
2
200
3
300
sortiert.
|
|
TSittly
Hält's aus hier
Beiträge: 9
AmigaOS3.5
|
Verfasst: Di 25.04.06 16:38
Ich versteh euch nicht...als Assemblercode wird immer ein Compare verwendet... aber wen es dennoch interessiert: Hier ein Beispiel mit und eines ohne if.
In Delphi gibt es anscheinend keinen Bedingungsoperator wie in C:
#define Min(x,y) (x<y) ? x:y
Deshalb habe ich es so gemacht, hier mit if (einfaches BubbleSort)
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| procedure TForm1.Sort(var a:array of integer); var t:integer; i,j:integer; begin t:=0; for i:=0 to 8 do begin for j:=0 to 7 do begin if (a[j]>a[j+1]) then begin t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t; end; end; end; end; |
Und hier das gleiche ohne if
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| procedure TForm1.Sort2(var a:array of integer); var t:integer; i,j:integer; begin t:=0; for i:=0 to 8 do begin for j:=0 to 7 do begin case (a[j]>a[j+1]) of True: begin t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t; end; end; end; end; end; |
Wer kommt auf die Idee, so rechenintensive Sqrt dem if vorzuziehen?
Die Wahl des Algorithmus hängt mit von der Datenmenge ab, Bubblesort kann man gut für relativ kurze Listen verwenden, Quicksort ist zwar im schlechtesten Fall genauso lahm, aber im besten Fall dafür schneller 
|
|
alzaimar
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: Di 25.04.06 17:32
Dreht es, wie ihr wollt: Spaceguide hat gewonnen (zu recht)!
_________________ Na denn, dann. Bis dann, denn.
|
|
Spaceguide
      
Beiträge: 552
(D3/D7/D8) Prof.
|
Verfasst: Fr 28.04.06 15:59
Hehe, thx. Die ganzen anderen "Lösungen" sind wie einfach das Fremdwort beim Spiel Tabu zu sagen.
|
|