Komplexitätstherorie für Rando Access Maschinen

[Christian Kruse]

Hallo Tom,

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?

man malloc():
MALLOC(3)                  Linux Programmer's Manual                 MALLOC(3)

NAME
       calloc, malloc, free, realloc - Allocate and free dynamic memory

Kann man dem Betriebssystem vorschreiben, die angeforderten Speicherblöcke direkt
hintereinander anzuorden und über EINEN einheitlichen Descriptor zugänglich zu machen?

So ist es definiert, Tom. Wenn du Speicher mit *alloc() anforderst, bekommst du den
entweder in einem zusammenhaengenden Block oder gar nicht. Im Falle von gar nicht wird
nicht genug Speicher vorhanden gewesen sein.

PHP arbeitet intern nur mit Hashes
Wie ist denn so ein Hash aufgebaut?

http://de.wikipedia.org/wiki/Hashtabelle

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

Was verstehst Du unter einem "Array"?

In diesem Kontext: http://www.php.net/manual/en/language.types.array.php

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?

Hashes bzw. Hashtables stellen Tabellen dar. Die Position des Wertes in dieser Tabelle wird
anhand einer Hash-Funktion aus dem Schluessel erstellt. Aber das steht ja auch in dem
Link, den ich dir gegeben habe...

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

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

“geschlossene Speicherstruktur”? Ein Array auf C-Ebene ist ein zusammenhaengender Block im
Speicher. Ein Array auf PHP-Ebene ist eine Hash-Tabelle.

(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!

Selbstverstaendlich kann er. Das ist doch der “Trick” bei der PHP-Variante. Ein Array auf
C-Ebene ist ein zusammenhaengender Speicherblock, ein Array auf PHP-Ebene ist eine
Hash-Tabelle.

Danach wird daraus wieder eine Liste.

Ich dachte, es ist eine Liste.

Ein Array auf C-Ebene ist ein zusammenhaengender Speicherblock, ein Array auf PHP-Ebene ist
eine Hash-Tabelle.

Grüße,
 CK