Doppelt verkettete Liste sortieren

[Mr.P-Funk]

Was ist der beste Weg eine doppelt verkettete Liste zu sortieren?
Das Problem ist nicht der Sortieralgorythmus selbst [zb: Quicksort, Shellsort,...], sondern der Zugriff auf ein Element in der Liste?

Wenn man ein Array sortiert, hat man ja einen Index und somit einen direkten Zugriff.


Ein paar Lösungen die mir eigefallen sind:

1. Ein weiteres Feld für eine eindeutige ID in den record mitaufnehmen.
Funktion die sequentiell sucht und das Element zurückliefert.

Denke aber das es bei einer großen Liste wohl sehr lange dauert immer sequentiell zu suchen.


2. Einen Record mit 2 Feldern hinzufügen.

Delphi-Quellcode:

type
  TDAddress = record
  Value : string;
  PADR   : Pointer;
  end;

Ein DynArray von TDAddress anlegen. Dann in einer Schleife die Liste durchlaufen und den Wert nachdem sortiert werden soll in Value schreiben. In PADR kommt dann die Adresse von dem Element.
Das Array sortieren und anschließend die Liste anpassen.
Liste in das Array schreiben:

Delphi-Quellcode:

var 
    AoTDA : array of TDAddress;
    Runner: Pzeiger;
    i     : integer;
begin
  Runner := Root;
  i      := 0;
  while Runner <> NIL do
  begin
     inc(i);
     Setlength(AoTDA, Length(AoTDA)+1);
     AoTDA[i-1].PADR   := Pointer(Runner);
     AoTDA[i-1].Value  := Runner^.IRGENDWAS;  //Irgendwas ist der Wert nachdem sortiert werden soll 
     Runner := Runner^.next;
  end;
end;

Liste anpassen:

Delphi-Quellcode:

var i : integer;
    Runner : PZeiger;
begin
   Root       := AoTDA[low(AoTDA)].PADR;
   Root^.next := AoTDA[low(AoTDA)+1].PADR;
   Root^.prev := NIL;

   FOR i := low(AoTDA)+1 TO high(AoTDA)-1 DO begin
      Runner        := AoTDA[i].PADR;
      Runner^.prev  := AoTDA[i-1].PADR;
      Runner^.next  := AoTDA[i+1].PADR;
   end;

   Runner       := AoTDA[high(AoTDA)].PADR;
   Runner^.next := NIL;
   Runner^.prev := AoTDA[high(AoTDA)-1].PADR;
end;

Die 2 Variante benutze ich im moment, allerdings habe ich gehört das man das so nicht machen darf.
Hatte jemand mit sowas schonmal Erfahrungen gemacht? Gibt es eine Muster-, Standartlösung?

[DelphiDeveloper]

Ich sehe an deinem Code noch nicht die doppelverkettung aber mit PREV und NEXT kann ich schon erahnen wie
es gemacht ist.

Schau dir in Delphi doch mal die TList an, hier ein kleines Beispiel wie man darin records/objekte einhaengen kann:
Die Sortiertung ist dann ein Kinderspiel für dich:

Hier die Sourceb die ich gerade auf die schnelle zusammengeklickt habe:

Delphi-Quellcode:

{-----------------------------------------------------------------------------
 Author:    DelphiDeveloper  05.02.22
 Purpose:   Sort with TList
-----------------------------------------------------------------------------}
unit Unit1;
interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, ExtCtrls;

type

  TDAddress = class
    SValue: string;
    IValue: integer;
    PADR: Pointer;
  end;

  TForm1 = class(TForm)
    BtnCreateTheList: TButton;
    BtnShowList: TButton;
    ListBox1: TListBox;
    RGrpSort: TRadioGroup;
    BtnSort: TButton;
    procedure BtnCreateTheListClick(Sender: TObject);
    procedure BtnShowListClick(Sender: TObject);
    procedure BtnSortClick(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
    myList: Tlist;
    procedure ClearList;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.BtnCreateTheListClick(Sender: TObject);
var aAdrObj: TDAddress;
  I: integer;
begin
  myList := TList.create;
  // fuelle Liste mit beispielwerten
  for i := 1 to 5 do
  begin
    aAdrObj := TDAddress.Create;
    aAdrObj.SValue := chr(random(20) + 65);
    aAdrObj.IValue := random(10);
    MyList.Add(aAdrObj);
  end;
end;

procedure TForm1.ClearList;
var I: integer;
begin
   // erst die Objekte freigeben
  if assigned(MyList) then
  begin
    for i := 0 to myList.Count - 1 do
      if MyList.Items[i] <> nil then
        TDAddress(myList.Items[i]).Free;
    //und jetzt die Liste
    MyList.Clear;
  end;
end;

procedure TForm1.BtnShowListClick(Sender: TObject);
var i: integer;
begin
  // nur um anzuzeigen was in der Liste steht
  ListBox1.Clear;
  for i := 0 to myList.Count - 1 do
  begin
    ListBox1.Items.Add(Inttostr(TDAddress(myList[i]).IValue) +
      ' ' + TDAddress(myList[i]).SValue);
  end;
end;

function SortierenString(item1,item2:pointer):integer;
begin
  // intern wird quicksort algo verwendet siehe OH
  // sortierung von strings
  result:=CompareText( TDAddress(Item1).SValue, (TDAddress(Item2).SValue));
end;

function SortierenInteger(item1,item2:pointer):integer;
begin
   // intern wird quicksort algo verwendet siehe OH
  // sortierung von integerwerten
  result:=( TDAddress(Item1).iValue - (TDAddress(Item2).iValue));
end;

procedure TForm1.BtnSortClick(Sender: TObject);
begin
   case  RGrpSort.ItemIndex of
     0: MyList.Sort( SortierenInteger);
     1: MyList.Sort( SortierenString);
   end;
   // neu anzeigen
   BtnShowList.OnClick(sender);
end;

end.

[Chewie]

Zum wasweißichwievielten Mal:
TList ist keine(!!!) verkettete Liste, sondern ein Array!

[IngoD7]

Zitat:

Zitat von Chewie

Zum wasweißichwievielten Mal:
TList ist keine(!!!) verkettete Liste, sondern ein Array!

Stimmt. Wo wurde denn was anderes behauptet?

[Chewie]

Naja, das Thema sind doppelt verkettete Listen, und der Vorredner brachte heri TList ins Spiel.

[IngoD7]

Zitat:

Zitat von Chewie

und der Vorredner brachte heri TList ins Spiel.

Ja schon, aber (wenn ich es richtig verstanden habe) als Alternative zur verketteten Liste. ;)

[Chewie]

Hm, wie auch immer. Man kanns auf jeden Fall nie oft genug sagen ;)

[Niko]

Hi

Zitat:

Zitat von Mr.P-Funk

Was ist der beste Weg eine doppelt verkettete Liste zu sortieren?
Das Problem ist nicht der Sortieralgorythmus selbst [zb: Quicksort, Shellsort,...], sondern der Zugriff auf ein Element in der Liste?

Wenn man ein Array sortiert, hat man ja einen Index und somit einen direkten Zugriff.

Genau deshalb ist Quicksort für eine verkettete Liste nicht besonders gut geeignet. Das schnellste Sortierverfahren für Listen dürfte Mergesort sein (benötigt keinen direkten Zugriff auf die Elemente).

[shmia]

Zitat:

Zitat von Mr.P-Funk

Was ist der beste Weg eine doppelt verkettete Liste zu sortieren?
Das Problem ist nicht der Sortieralgorythmus selbst [zb: Quicksort, Shellsort,...], sondern der Zugriff auf ein Element in der Liste?

Wenn man ein Array sortiert, hat man ja einen Index und somit einen direkten Zugriff.


Ein paar Lösungen die mir eigefallen sind:

1. Ein weiteres Feld für eine eindeutige ID in den record mitaufnehmen.
Funktion die sequentiell sucht und das Element zurückliefert.

Denke aber das es bei einer großen Liste wohl sehr lange dauert immer sequentiell zu suchen.


2. Einen Record mit 2 Feldern hinzufügen.

Mit einem zusätzlichen Speicheraufwand von 1 Zeiger pro Element kann man ein indirektes Sortieren durchführen:

Delphi-Quellcode:

type
   PSortItem =  ^TSortItem;
   // die Grundstruktur deiner doppelt verketteten Liste
   TSortItem = Record
      data:string;
      Prev : PSortItem;
      Next : PSortItem;
   end;

var 
   // Hilfsarray zum Sortieren
   SortArray : array of PSortItem;

Ich gehe jetzt davon aus, dass deine doppelt verkettete Liste komplett aufgebaut ist.
Der nächste Schritt ist nun das Hilfsarray zu dimensionieren.
Dazu wird die Anzahl der Elemente benötigt (entweder schon bekannt oder man muss die Liste durchzählen):

Delphi-Quellcode:

   SetLength(SortArray, AnzahlElemente);

Jetzt wird das Array bestückt:

Delphi-Quellcode:

runner := FirstElement
for i:=0 to AnzahlElemente-1 do
begin
   SortArray[i] := runner;
   runner := runner.Next;
end;

Jetzt ist der double-linked List ein Array übergestülpt.
Beim Sortieren wird nun über das Array SortArray gearbeitet und innerhalb des Arrays werden Zeiger vertauscht.
Die Verkettungen innerhalb der double linked List bleiben völlig unberücksichtigt.
Nach dem Sortieren enhält das Array die Zeiger auf die Elemente in sortierter Form.
Jetzt werden alle Verkettungen der double-linked List quasi weggeschmissen und mit Hilfe
des SortArray neu aufgebaut:

Delphi-Quellcode:

Head := SortArray[0]; // Kopf der Liste
// gesonderte Behandlung für Anfangselement
SortArray[0]^.Prev := nil;
SortArray[0]^.Next := SortArray[1];
for i := 1 to AnzahlElemente-2 do
begin
   SortArray[i]^.Prev := SortArray[i-1];
   SortArray[i]^.Next := SortArray[i+1];
end;
// gesonderte Behandlung für letztes element
SortArray[AnzahlElemente-1]^.Prev := SortArray[AnzahlElemente-2];
SortArray[AnzahlElemente-1]^.Next := nil;
Tail := SortArray[AnzahlElemente-1];

[Robert Marquardt]

Der einfachste Weg ist es ein Array von Zeigern auf die Daten zu erzeugen und dann dieses Array mit QuickSort oder HeapSort zu sortieren.
Das funktioniert wenn die Daten selbst als Zeiger im Verkettungsknoten gespeichert sind.
Danach spielt man die Zeiger einfach wieder in die Liste ein.

Natuerlich hat dieses Verfahren eine limitation, naemlich der zusaetzliche Platzaufwand fuer das Array.

[Mr.P-Funk]

@ DelphiDeveloper
Der Vorschlag mit TList zu arbeiten, erspart sicher viel Zeit, ist aber nicht ganz das was ich wollte.
Trotzdem THX für die Idee.

@ Niko
MergeSort kenne ich noch nicht... leider :(
Werde mir das aber mal ansehen.

@ Shima
Ungefähr so hatte ich mir das in meine 2 Variante auch vorgestellt.
Aber warum brauchst du so viele Informationen in dem Array (SortArray : array of TSortItem) ?
Ich glaube es reicht ein Array mit einem untypisiertem Pointer, in dem die Adresse des Elementes steht, und ein Feld wo der Wert drinn steht nachdem sortiert werden soll.
Das Array lässt man dann sortieren und "verbiegt" seine Liste neu (Die Daten davon liegen ja noch im Speicher).

Wenn ich das richtig verstanden habe, würdest du alle Infos die in der Kette stehen auch in das DynArray schreiben. Aber dann würde ein Dreickstausch doch sehr lange dauern, wenn das record aus mehr Feldern bestehen würde...
Oder habe ich das jetzt falsch verstanden? :gruebel:


Ich habe mal ein kleines Beispielprogramm erstellt.
Allerdings raten mir viele Leute davon ab, das so zu machen. Es wäre zu unsicher...
Könnt ja mal reinschauen.

Großes THX an alle! :hello:

cya
MR.P-Funk

[negaH]

Der schnellste und effizientes Weg ist die unsortierten Einträge der Liste A in eine neue Liste B sortiert einzufügen. Man kann dies noch beschleunigen indem man zur ListB ein Array mit Ln2(ListA.Count) Pointern benutzt. In diesem Array wird ein Zeiger auf das jeweils ListB.Count/Ln2(ListA.Count) Element/Node gespeichert. Beim Enfügen einer Neuen Node wird nun dieses Array per QuickFind durchsucht um die Anfangsnode ab der die Liste itertiert werden muß zu finden. Dies beschleunigt ungemein das sortierte Einfügen in deine ListeB.
Das Zusatzarray wird von Anfang an auf ListA.Count Elemente initialisiert und dann deren enthaltene Pointer nur succesive nach dem Einfügen/Umkopieren der Node geupdatet. Bei diesem Update kann man sich weiter beschränken indem man nur die beiden "Rand" Nodes in diesem Array korregiert.

Hm, ich glaube nicht das ich das verständlich rübergebracht habe :)

Gruß Hagen

[shmia]

Zitat:

Zitat von Mr.P-Funk

@ Shima
Ungefähr so hatte ich mir das in meine 2 Variante auch vorgestellt.
Aber warum brauchst du so viele Informationen in dem Array (SortArray : array of TSortItem) ?
Ich glaube es reicht ein Array mit einem untypisiertem Pointer, in dem die Adresse des Elementes steht, und ein Feld wo der Wert drinn steht nachdem sortiert werden soll.

Da hast du nicht genau hingeschaut. :hi:
Das Array aus meinem Vorschlag enthält nur Zeiger (Datentyp PSortItem)
Der typisierte Pointer vereinfacht das Programmieren...

[Hansa]

Zitat:

Zitat von negaH

Der schnellste und effizientes Weg ist die unsortierten Einträge der Liste A in eine neue Liste B sortiert einzufügen....Hm, ich glaube nicht das ich das verständlich rübergebracht habe :) Gruß Hagen

Hehe, ich verstehe das auch nicht. 8) Ich vermute mal, er will das sagen, was man machen sollte : die Liste direkt sortiert aufzubauen und basta. Dann entfällt der Rest sowieso. Muß die Liste unbedingt komplett anders umsortiert werden, tja dann eben wirklich unter dem neuen Sortierkriterium neu aufbauen.

[negaH]

@Hansa, stop mal, will er die Liste umsortieren oder will er einen sortierten Index für die Liste aufbauen ohne die Liste physikalsich umzusortieren ?

Ich war der Meinung das er die Liste umsortieren will. Da er eh schon mit Verketteten Nodes/Elementen arbeitet ist es auch kein Problem sehr schnelle Nodes aus einer Liste zu erntfernen und in eine andere Liste sortiert einzufügen. Dies kostest erstmal keinen zusätzlichen Speicher. Allerdings muß er beim Einfügen einer Node in die neue und sortierte Liste im ungünstigen Falle immer diese Node mit allen Nodes in der Zielliste vergleichen. Dies ist sehr ineffizient. Man könnte nun ein komplettes Array[] of PNode aufbauen das so viele Zeiger wie Nodes in der Liste enthält. Dies kostet Speicher, lässt sich aber per QuickSort einfach und schnell sortieren, wäre vergleichbar mit einem externen Index und kostet im Grunde sehr viele Speicherkopieroperation während der Sortierei.

Ein Kompromiss ist nun eine Lösung die beide primären Varianten vereint, sprich Umsortieren in neue List und dabei ein sehr kurzes Indexarray für die Suche der Einsortierposition der Node.

Speicherbedarf: Ln2(List.Count) statt (List.Count * SizeOf(Pointer)) bei der arary[] Methode
Suchkomplexität: Ln2(List.Count) + List.Count / Ln2(List.Count) statt Ln2(List.Count) bei Quicksort
Kopieroperation: (List.Count) Zeiger verbiegen == linear

Somit wäre mein Vorschlag leicht langsammer beim Suchen der richtigen Einfügeposition, allerdings wird dies durch die wesentlich erhöhten Speicheroperationen bei den anderen Methoden weitestgehend kompensiert. Denn Speicherkopierungen sind wesentlich langsammer auf modernen CPU's also nur readonly durch eine verkettete Liste durchzuiterieren.

Falls das Sortieren der Liste wirklich enorm schnell gehen muß dann kann man das durch eine Erweiterung der Nodes erreichen. Die Nodes selber sind als verkettete Liste linear untereinander verknüpft. Aber gleichzeitig sind sie auch als Binärer Baum, zb. ein AVL oder Red Black Tree aufgebaut. Die Nodes müssten dann nicht mehr doppelverlinkt werden, aber zusätlich benötigen sie mindesten zwei weitere Zeiger -> Left,Right.
Beschränkt sich das Sortieren aber nur auf das Einfügen in einen solchen Tree dann kann man die Left,Right Zeiger später als Prev,Next Pointer für die verlinkte Liste benutzen. Während des Aufbauens des Baumes entsteht also ein ausbalancierter binärer Baum (RB, AVL). Nachdem man alle Nodes so eingefügt hat, kann man mit einer Rekursiven Funktion die den Baum sequetiell alphabethisch abarbeitet, neu zu einer normalen doppeltverlinkten Liste ummodscheln :) Klar, einmal in eine Liste umgemodschelt kann man keine neuen Nodes mehr sortiert als Baum einfügen.
D.h. temporär beim Umsortieren werden die Nodes statt in einer linearen Liste in einen binären Baum eingearbeitet, aus den Prev,Next Zeigern werden die Left,Right Zeiger für den AVL/RB Tree. Nachdem man alle Nodes so binär umkopiert hat wird der Baum neu verlinkt so das eine Liste entsteht.

Dieses Verfahren ist Ln2(List.Count) schnell, asymptotisch schneller als QuickSort !! benötigt keinen zusätzlichen Speicher und keine Kopieroperationen ausser dem Umbiegen der Zeiger. Allerdings ist es komplex und nicht einfach zu coden.

Gruß Hagen

[Mr.P-Funk]

@ Shima
Upps zu schnell gelesen... ;)
Aber die einen typisierten Zeiger zu nehmen ist gut, warum bin ich da nicht selber drauf gekommen ...:wall:
Damit ist der Aufwand wohl echt geringer.

@ negaH
Das hört sich ja interessant an, aber ich hatte schon Probs das überhaupt zu verstehen, nen Code kann ich mir nur schwer vorstellen... :gruebel:
Hast du sowas mal geschrieben? Wenn ja kannst du es mal posten oder direkt Email??

Ich erkläre den Thread als geschlossen; meine Fragen wurden beantwortet
THX @ all

[negaH]

Zitat:

Hast du sowas mal geschrieben? Wenn ja kannst du es mal posten oder direkt Email??

Ja, ich habe irgendwie schon alles mal programmiert :) AVL und RB Trees und verlinkte Listen auf jeden Fall, allerdings noch nie eine solche Kombination wie ich sie oben beschrieben habe. Gehen tut das auf alle Fälle, davon bin ich überzeugt, und die Abschätzung der Komplexität eines solchen Mischalgos. kann man auch trocken auf rein theoretischer Basis machen.

Hier im Forum, meine ich mich erinnern zu können, muß es auch ein Source von mir für einen AVL Tree geben. Kann mich halt nicht erinnern im welchen Zusammenhang, eventuell war das der Thread mit dem DoubleChecker/Doppelte Dateienfinder oder sä.

Zum Verständnis nochmal:

Du hast eine doppelt verlinkte Liste. Jedes Element dieser Liste nenne ich mal Node. Eine Node hat zwei Felder/Member mit Namen Prev: PNode und Next: PNode. Über diese beiden Zeiger wird das Element mit seinem Vorgänger und Nachfolger verlinkt. Die doppelte Verlinkung macht es möglich diese Node sehr schnell aus der Liste zu entfernen, oder die List vorwärts und rückwärts zu iterieren.

Ein binärer Baum hat auch Elemente, nenn sie mal Node. Jede Node in einem binären Baum hat auch zwei Zeiger vom Typ PNode, allerdings benennt man sie meisten Right und Left. Zusätzlich enthält sie noch die Daten. Das die Node nur zwei untergeordnete Nodes enthalten kann kann nur ein binärer Baum entstehen. Die Art und Weise wie nun der Baum ausbalanciert wird, sprich ob die Anzahl der untergeordneten Node in Right und Left immer nur um +-1 differieren kann bestimmt den Typ des Baumes. Können sich diese Anzahlen stark unterscheiden dann ist der Baum nicht ausbalanciert, er wäre ein stinknormaler binärer Baum. Solche Bäume haben keinen Suchvorteil, d.h. deren Komplexität ist im schlechtesten Falle genauso schlecht wie eine lineare Liste. Ist die Anzahl der Linke und Rechten Hälten der Node aber immer fast identisch dann ist der Baum ausbalanciert. Die Art und Weise wie man nun effizient erreicht WIE dieses ausbalancieren funktioniert bestimmt den "Namen" des Trees. Die meistbekannten Vertreter sind die AVL und Red Black Trees. (frag mich jetzt nicht was AVL genau bedeutet, müsste ich erst nachschlagen). Gut, beide Trees balancieren ihre Nodes direkt beim Einfügen und auch Löschen einer Node in den Baum aus.

So, nun muß man noch eine Frage beantworten: Gibt es in deiner Liste Duplikate ? Das ist wichtig da es in einem normalen binären Baum niemals direkt die Möglichkeit gibt Duplikate zu speichern. In jedem Falle müsste man entweder zu einer Node eine weitere verlinkte Liste einführen in die dann alle Duplikate verwaltet werden, oder aber die Ausbalancierung würde nicht mehr korrekt funktionieren.

Ich gehe mal von Listen ohne Duplikate aus. Was passiert nun beim Umsortieren ?
Man entfernt die erste Node aus der Liste und fügt sie in die Rootnode des Tree sortiert ein. Dabei wird sie vorerst einfach Left in Root. Nun nimmt man die zweite Node aus der Liste und macht sie zu Right der Root. Anschliesend vergleicht man Left mit Right und eventuell müssen sie die Plätze tauschen, weil Left größer Right ist. Das geht nun so lange weiter bis die Liste leer ist. Auf der anderen Seite entsteht ein binärer Baum der ansich sortiert ist. Ganz ganz unten Links in diesem Baum steht die Node mit dem kleinsten Wert, ganz unten Rechts diemit dem größten Wertund gleich unterhalb der Root stehen die zwei Nodes die exakt in der Mitte aller Wertigkeiten stehen. Man kann nun sehr leicht rekursiv diesen Baum von Links nach Rechts auflösen und alle Nodes wie eine normale Liste doppelt verlinken. Schwups wurde die Liste mit der bestmöglichen Komplexität und geringstmöglichen Overhead und fast 0 Bytes zusätzlichen Speicher umsortiert.

Auf Grund der direkten binären Suche im Baum benötigt man bei zb. 1024 Nodes maximal 10 Vergleiche um deren Einfügeposition zu finden. Pro Node fällt immer nur das Umsetzen der Zeiger als Speicheroperation an, es müssen also keine großen Speicherbereich umkopiert werden. Die Neuverlinkung hat nur lineare Komplexität.

Gruß Hagen

[Hansa]

Bin mir fast sicher, daß es das hier ist. Aber wie gesagt : so was ist nicht gerade trivial.

http://www.delphipraxis.net/internal...t=doublekiller

[mleyen]

Zitat:

Zitat von negaH (Beitrag 277592)

Speicherbedarf: Ln2(List.Count) statt (List.Count * SizeOf(Pointer)) bei der arary[] Methode
Suchkomplexität: Ln2(List.Count) + List.Count / Ln2(List.Count) statt Ln2(List.Count) bei Quicksort
Kopieroperation: (List.Count) Zeiger verbiegen == linear

Ich weiß der Thread ist schon uralt, aber für mich gerade aktuell da ich auch eine eigene spezielle Liste bastle.
Ziemlich interessant wie du den Ramverbrauch der CPUlast gegenüberstellst. (Ich war immer der Meinung, dass das bei Such/Sortierverfahren, aufgrund des dynamischen Inhalts, nahezu nicht geht)
Aber was tut bitte "Ln2()"?

[Sherlock]

Ins blaue geraten ist das der Logarithmus mit Basis 2.

Sherlock

[Gollum]

Hallo,

wenn ich den Link aus dem Thread von Hansa anklicke komme ich auf eine Seite, die vBulletin-Systemmitteilung heißt und mir etwas von mangelden Rechten erzählt.
Ist dieser Link so geheim, dass ich ihn nicht anklicken darf oder ist dies ein Bug?

[xZise]

Moin,
wobei Ln2() auch irgendein anderer Logarithmus sein kann. O(LnX()) = O(LnY()) ;)

Und wegen Hansas Post: Entweder er liegt irgendwo, wo der Otto Normal Benutzer nicht hin darf, oder bei der Umstellung auf die DP20XX ist was schief gelaufen.

MfG
Fabian