Autor Beitrag
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Fr 14.04.06 13:36 
Hallo,

dem Wahnsinn eine Chance, eine kleine Optimierung ;-).

ausblenden 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);//wegen double und little endian
 pAi := @aNumbers[High(aNumbers)-1];
 // High(aNumbers) wird nur einmal abgefragt statt jedesmal
 for i:= High(aNumbers)-1 downto 0 do
   begin
   pAj := @aNumbers[High(aNumbers)];
   for j:=High(aNumbers) downto 1 do
     begin
     AbsDiff := pAi^-pAj^;
     // Vorzeichen auf + setzen
     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
ontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 207

Win XP Prof.
D7
BeitragVerfasst: Fr 14.04.06 14:07 
user profile iconSpaceguide 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: 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:
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
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)
BeitragVerfasst: Fr 14.04.06 15:39 
Es war ja nur gefragt, ob man denn "if" rauslassen könne. Klar, das geht:
ausblenden 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 {beide gleich -> nix zu tun}
    jns endloop { a größer b -> nix zu tun}
    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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: Fr 14.04.06 15:48 
Das "IF" ist nicht wörtlich gemeint. Das Problem ist eine Sortierung ohne Verzweigungen.
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Fr 14.04.06 16:31 
user profile iconSpaceguide hat folgendes geschrieben:
Von was redet ihr hier eigentlich? Kuchen?!?!

Hier der Beweis:

ausblenden 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:
procedure Sortiere(var aNumbers : array of double);
 var temp : double;
     i,j : integer;
begin
 for i:=Low(aNumbers) to High(aNumbers)-1 do
  for j:=i+1 to High(aNumbers) do
  begin
   temp := aNumbers[i];
   aNumbers[i] := (-Sqrt(Sqr(aNumbers[i]-aNumbers[j]))+
                           (aNumbers[i]+aNumbers[j]))*0.5;
   aNumbers[j] := (Sqrt(Sqr(temp-aNumbers[j]))+
                           (temp+aNumbers[j]))*0.5;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
 var zahlen : array of double;
     i : integer;
begin
 setlength(zahlen,100);
 for i:=Low(zahlen) to High(zahlen) do zahlen[i]:=Random*100;
 Sortiere(zahlen);
 for i:=Low(zahlen) to High(zahlen) do
  memo1.lines.add(floattostr(zahlen[i]));
end;


wo er recht hat... ;) ihm geht es auch wohl nur darum nicht jede zahl mit jeder vergleichen zu müssen, ihm wurden genug wege genannt, es wurden genug wege genannt, dann sollte auch irgendwann mal gut sein ;)
delfiphan
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2684
Erhaltene Danke: 32



BeitragVerfasst: Fr 14.04.06 21:34 
user profile iconSpaceguide 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 62



BeitragVerfasst: 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

ausblenden 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..6of 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Mo 17.04.06 17:31 
Benutzen auch du die Delphi Tags du sollst junger Padawan.

[delphi][/delphi]
Spaceguide
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: 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

BeitragVerfasst: 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)

ausblenden 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;
  //Sortiere array
  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

ausblenden 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;
  //Sortiere array
  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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Di 25.04.06 17:32 
Dreht es, wie ihr wollt: Spaceguide hat gewonnen (zu recht)!

_________________
Na denn, dann. Bis dann, denn.
Spaceguide
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 552


(D3/D7/D8) Prof.
BeitragVerfasst: Fr 28.04.06 15:59 
Hehe, thx. Die ganzen anderen "Lösungen" sind wie einfach das Fremdwort beim Spiel Tabu zu sagen.