Komplexitätstherorie für Rando Access Maschinen

[Tom]

Hello,

Das beantortet aber nicht die Frage, was

pemalloc()

Speicher alloziieren.

Ja. Und ist das eine statische Speicherbelegung oder eine, die während der Laufzeit stattfindet?
Kann man dem Betriebssystem vorschreiben, die angeforderten Speicherblöcke direkt hintereinander anzuorden und über EINEN einheitlichen Descriptor zugänglich zu machen?

p = p->pListNext;

denn wohl bedeuten könnten.
Ich tippe mal auf eine verkettet Liste.

*seufz* Tom, ich erklaere es dir jetzt noch einmal:

Ja, das schätze ich so an Dir. Deine Geduld und Güte...

PHP arbeitet intern nur mit Hashes

Wie ist denn so ein Hash aufgebaut?

anstelle von Arrays. Jeder Array ist ein Hash, es gibt

Was verstehst Du unter einem "Array"?
Ich verstehe darunter eine geschlossene statische Speicherstruktuer gleicher Datentypen oder oder wiederkehrender Datenmuster.

keinen Array. Da allerdings Hashes dummerweise das Problem haben,

Ach, Hashes haben ein Problem?

dass die Reihenfolge der
Keys nicht gewahrt bleibt,

Woran liegt das?
Wie liegen denn die 'Hashes' im Speicher und wie wird auf jedes einzelne ihrer Elemente gezielt zugegriffen?

wird diese Reihenfolge, ja, genau, in einer Liste gespeichert.

Also doch eine Liste? Du sagtest doch noch, PHP benutz für 'Arrays' keine Listen, sondern 'Hashes'
Das kommt mir nun langsam vor, wie Verarschung. Muss ich mal so deutsch und allgemeinverständlich, ganz ohne Frendworte, ausdrücken. ;-)

Diese Liste wird allerdings, um sie zu sortieren, in einen Array

der ja keine verkettete Struktur ist, sondern eine geschlossene Speicherstruktur?

(auf C-Ebene) umgewandelt
(das macht das kleine Code-Stueck, dass ich dir gezeigt habe). Der wird dann sortiert.

Aber das kann nicht mit einem echten Quicksort sortiert werden!

Danach wird daraus wieder eine Liste.

Ich dachte, es ist eine Liste. Qozu sonst

malloc()

und

p =  p->pListNext;

?

(Dieses Fragezeichen ist mir eine eigene Zeile wert!)

Und Du hast ja in einem der Postimngs behauptet, dass PHP sowasn nicht bemnutzt.

Nein, ich sagte, PHP benutzt fuer Arrays keine Listen. Der Zugriff auf die Elemente
geschieht ueber eine Hash-Tabelle.

Und George Busch hat den Irak nicht bombadiert. Das ist auch nicht gelogen!

(verzeih bitte den Vergleich, aber so versteht das der Enttarner vielleicht auch.

BTW: Die Genehmigung von der Staatsanwaltschaft ist inzwischen erteilt und muss nur noch mir und dem Arbeitgeber vom Enttarner rechtshändig zugestellt werden. Dann dürfen wir unsere Daten abgleichen, ohne uns strafbar zu machen. Die Ergebnsisse sind dann auch gerichtsverwertbar. Ich habe eine Menge dabei gelernt und war erstaunt, wie kooperativ die andere Firma ist.)

Und wenn Du auch noch das Stück Quellcode für ein PHP-Array bereitstellen würdest, fände
ich das fair. Wenn ich darin keine verkettete Liste oder Baumstruktur erkennen kann,
entschuldige ich mich auch bei Dir, dass ich Dir nicht vertraut habe. Versprochen!

Warum guckst du dir nicht selber den Sourcecode an? Ich sage nur soviel: der interne
Datentyp fuer einen PHP-Array ist HashTable. Die Informationen dazu findest du in
ext/standard/array.c und in Zend/zend_hash.c

Danke Christian. Das ist der Stil, den ich an Dir schätez. Into the Depth und Ruhe ist. Ich habe den Quellcode im Moment nicht in direktem Zugriff. Hatte ich aber, und ärgere mich in den letzten Tagen schon öfter darüber, dass es im Moment nicht so ist. Ich werde das aber gleich mal ändern.

Und nun nochmal: Wie funktioniert ein echter Quicksort mit einer verketteten Liste?
Müsste der nicht direct random access haben?

Quicksort braucht direkten Zugriff auf jedes Element um performant zu bleiben, ja. Deshalb
wird auch nicht mit einer Liste gearbeitet, wie ich dir ja in diesem Posting zum dritten
mal dargelegt habe.

Das werde ich nun versuchen nachzuvollziehen (da gebe ich mir gute bis sehr gute Chanchen, zur Not auch in Assembler) und dann auf mein Beispiel zu übertragen.

@Indigo: Ich empfinde es übrigens nicht als ehtenrührig, als 'Laie' bezeichnet zu werden. Die sogenannte 'Professionalität' trübt dieser Tage allzu oft den Blick für Innovation und Tatsächlichkeit, indem sie immer wieder auf 'alte Zöpfe' zurückgreift. Deren Gültigkeit wird aber immer kurzlebiger, je besser das medium 'Kommunikation für alle' wird. Das bedeutet nicht, dass ich gegen Traditionen wäre. Ich bin nur gegen die klassischen Kolonisierungsmethoden von Sklaventreibern!

Somit schließt sich der Kreis mal wider *g*

Harzliche Grüße aus http://www.annerschbarrich.de

Tom