Grundsätzliche frage zum @Array

Computer: Software & Programmierung Perl & CGI
#1

Hu Leute!

Also ich bin gerade ein bischen verwirrt. Ich bin z.Zt. Informtikstudent an der FH in Trier und hätt da mal eine Frage:

Uns wurde erzählt, das ein Array nur eine feste Größe haben kann. Bsp: Java. Man muss im vorhinein sagen, dass es z.B. 100 Werte werden. Vergrössern oder verkleinern geht danach nicht mehr.
Lösung: einfach- oder doppeltverkettete Liste. Die passt sich dynamisch an. Nachteil: Bei einer einfach- oder doppelverketteten Liste ist kein direkter Zugriff auf ein Element in O(1) möglich. Lauftzeitbedingung ist dort O(n)

Nun meine Frage: Ist in Perl das Array eine Implementierung von einer einfach verketteten Liste? Und somit Laufzeitbedingung O(n) oder funktioniert das anders?

Gibt es im Internet vielleicht eine Seite, wo man genau solche Dinge über verschiedene Programmiersprachen erfahren kann?

Gruß,
Martin

#2

Uns wurde erzählt, das ein Array nur eine feste Größe haben
kann. Bsp: Java. Man muss im vorhinein sagen, dass es z.B. 100
Werte werden. Vergrössern oder verkleinern geht danach nicht
mehr.

Hallo,

unter Perl muss man ein Array nicht deklarieren - und somit auch keine feste Größe zuweisen. Wie das intern gelöst wird von Perl, weiss ich nicht - möglicherweise tut sich Perl da leichter als andere Sprachen, weil es ja interpretiert wird. Ich als Praktiker und Nicht-Informatiker habe mir Perl-Arrays immer wie einen Stack vorgestellt - schließlich kann man da auch pushen und poppen…

Vielleicht kann das noch jemand mit besserem Verständnis für die Perl-Interna konkretisieren…

Marian

#3

unter Perl muss man ein Array nicht deklarieren

… im prinzip schon. Zumindest wenn Du es „sauber“ tust, solltest Du alle Variablen mit „my“ deklarieren.

Wie das intern gelöst wird
von Perl, weiss ich nicht

Gerade das interessiert mich :smile:

Ich als Praktiker und Nicht-Informatiker habe mir Perl-Arrays
immer wie einen Stack vorgestellt - schließlich kann man da
auch pushen und poppen…

In diesem Zusammenhang aber etwas anderes :smile:
Ein Stack ist ein FILO (first in last out) und bedeutet sowas wie:
Ich stecke nach und nach etwas in mein Stack hinein (mit push) und hol es mir bei Bedarf in umgekehrter Reihenfolge wieder heraus (mit pop).
Ein Stack kann man sich wie die Milchtüten in einem Kaufhaus vorstellen. Es werden die neuen Milchtüten immer oben drauf gelegt und der Kunde nimmt sich die Milchtüten von oben wieder herunter. Bis man unten angekommen ist, ist die Milch vergammelt :smile:

Ein Queue ist das Gegenstück zum Stack. Es funktioniert „genau umgekehrt“ wie ein Stack und ist somit ein FIFO (first in first out). Ein praktisches Beispiel wäre da die Warteschlange an der Kasse in einem Kaufhaus. Wenn ich mich anstelle, komme ich nach einer gewissen Zeit an die Reiehe. Neu hinzugekommene Käufer stehen hinter mir und kommen auch nach mir drann.

Bei Stacks und Queues ist es allerdings (im Normalfall) nicht möglich (oder nicht sinnvoll) auf zwischenliegende Elemente zuzugreifen. Deswegen kann man sich Arrays nicht unbedingt wie Stacks/Queues vorstellen

Sorry für die Abschweifung… aber das war mal ganz gut :smile: Ich hab in 2 Wochen Klausuren und hab mein Gedächnis etwas aufgefrischt :wink:

Gruß,
Martin

#4

Hallo Martin!

Nun meine Frage: Ist in Perl das Array eine Implementierung
von einer einfach verketteten Liste? Und somit
Laufzeitbedingung O(n) oder funktioniert das anders?

Arrays in Perl sind komplizierter aufgebaut als beispielsweise in C. Während in C direkt auf den Speicher zugegriffen werden kann (array_start+index_number*sizeof(element_type)), läuft der Zugriff in Perl indirekt ab:

In Perl besteht ein Array aus einem Speicherbereich, in dem ein Array von Pointern auf die enthaltenen Werte gespeichert ist. Zusätzlich beschrieben wird ein Array durch einen Pointer auf den Anfang dieses Speicherbereichs und einen Pointer auf den tatsächlichen Anfang der Pointerliste.

Wird am Ende des Array ein Element angefügt, so muss nur ein weiterer Pointer abgelegt werden, der auf einen beliebigen Speicherbereich zeigen kann. Ggf. muss die Verwaltungsstruktur in einen neuen Speicherbereich umkopiert werden, um wieder Platz für neue Pointer zu schaffen. Der zu allozierende Speicher ist so bemessen, dass er einen Kompromiss zwischen Platzersparniss und Performance (seltenem Umkopieren) darstellt.

Wird am Anfang des Arrays ein Element entfernt, so wird lediglich der Pointer auf den tatsächlichen Beginn der Verwaltungsstruktur angepasst, während der Pointer auf den Beginn des gesamten Speicherbereichs stets erhalten bleibt. Ein Umkopieren findet in diesem Fall nicht statt.

Gibt es im Internet vielleicht eine Seite, wo man genau solche
Dinge über verschiedene Programmiersprachen erfahren kann?

http://groups.google.de/groups?hl=de&lr=&ie=UTF-8&oe…

CU
Markus

#5

Hi Markus!

Vielen Dank für Deine Antwort. Der Artikel ist sehr interessant!
Also ist ein Perl Array eine art verbesserte Art von „herkömmlichen“ Arrays in der Form, dass einfach das Array vergrössert wird, wenn es sein muss.
Dabei wird anscheinend im Vornerein gleich ein wenig mehr platz hinter dem Array im Speicher gelassen, damit sich die Liste noch vergrössern kann, bevor sie umkopiert werde muss. Und das es eine Liste von Pointern auf den tatsächlichen Wert ist, ist mit Sicherheit ebenfalls eine Art der Performance. So ist ein Array von einfechen Pointern wahrscheinlich schneller kopiert als ein ein Array mit den tatsächlichen Werten.
Hab ich das jetzt so richtig verstanden?

Somit ist also der Zugriff auf ein Element immer O(1), wobei ein anfügen nur solange O(1) sein kann, bis das Array umkopiert werden muss. Das wäre dann der einzige Fall, wo man ein O(n) als Laufzeitfaktor hätte … mhh… interessant … warum wird dass dann nicht gleich überall so gemacht :smile:

Gruß,
Martin

#6

Also ist ein Perl Array eine art verbesserte Art von
„herkömmlichen“ Arrays in der Form, dass einfach das Array
vergrössert wird, wenn es sein muss.
Dabei wird anscheinend im Vornerein gleich ein wenig mehr
platz hinter dem Array im Speicher gelassen, damit sich die
Liste noch vergrössern kann, bevor sie umkopiert werde muss.
Und das es eine Liste von Pointern auf den tatsächlichen Wert
ist, ist mit Sicherheit ebenfalls eine Art der Performance. So
ist ein Array von einfechen Pointern wahrscheinlich schneller
kopiert als ein ein Array mit den tatsächlichen Werten.
Hab ich das jetzt so richtig verstanden?

Ja.

Somit ist also der Zugriff auf ein Element immer O(1), wobei
ein anfügen nur solange O(1) sein kann, bis das Array
umkopiert werden muss. Das wäre dann der einzige Fall, wo man
ein O(n) als Laufzeitfaktor hätte … mhh… interessant …
warum wird dass dann nicht gleich überall so gemacht :smile:

Es ist nicht ganz so performant wie der direkte Speicherzugriff, da Du noch eine Indirektion über den Pointer verarbeiten musst.

Wenn Du beispielsweise mit großen Matrizen bekannter Dimension und Größe rechnest, ohne sie vergrößern zu wollen, dann ist diese Indirektion überflüssig.

Sie ist auch nicht realisierbar bei Sprachen wie C, bei denen Pointerarithmetik möglich ist.

CU
Markus

#7

Hallo,

Uns wurde erzählt, das ein Array nur eine feste Größe haben
kann. Bsp: Java. Man muss im vorhinein sagen, dass es z.B. 100
Werte werden. Vergrössern oder verkleinern geht danach nicht
mehr.

Mal wieder ein Grund, Perl zu nutzen, und nicht Java :smile:

unter Perl muss man ein Array nicht deklarieren

Man muss nicht, man sollte aber (nahezu) ausschliesslich Variablen benutzen, die lexikalisch deklariert wurden, um diesen den kleinstsinnvollsten Gültigkeitsbereich zu geben.
Globale Variablen sind fast immer ein Zeichen für einen schlechten Stil.

  • und somit
    auch keine feste Größe zuweisen. Wie das intern gelöst wird
    von Perl, weiss ich nicht

Bei Bedarf reserviert Perl für ein Array neuen Speicher. Deshalb ist push auch schneller als unshift (Obwohl Perl bei einer unshift Operation NICHT das ganze Array verschiebt): push reserviert automatisch sehr viel Speicher, um bei wiederholtem push-en Zeit zu sparen.

  • möglicherweise tut sich Perl da
    leichter als andere Sprachen,

Nein, ganz bestimmt nicht. Perl tut eine Menge Arbeit hinter den Kulissen. Deswegen ist Perl auch nicht so schnell wie C.

weil es ja interpretiert wird.

Falsch. Perl ist eine kompilierte Sprache. Wenn man ein Perl Programm ausführt, wird es erst in einen Parse-Tree kompiliert und *dann* erst ausgeführt.

Ich als Praktiker und Nicht-Informatiker habe mir Perl-Arrays
immer wie einen Stack vorgestellt - schließlich kann man da
auch pushen und poppen…

Perl Arrays sind kein Stack. Sie können beispielsweise auch wie eine Queue eingesetzt werden:

perldoc -f shift

MfG
Steffen