Hallo,
wie definiert man ein Array von einer bestimmten Länge?
Viele Grüße
Array defenieren
- Defnull
- User
- Beiträge: 778
- Registriert: Donnerstag 18. Juni 2009, 22:09
- Wohnort: Göttingen
- Kontaktdaten:
Arrays gibt es nicht, aber listen. Listen haben eine dynamische Länge, du kannst jederzeit Objekte hinzu fügen oder daraus entfernen. Daher macht es keinen Sinn, eine liste mit einer bestimmten Länge zu definieren.
Bottle: Micro Web Framework + Development Blog
Mich würde immer noch interessieren, wozu du das konkret brauchst, weil man dir dann sicher einen guten Vorschlag machen könnte.
Das hat jetzt eine bestimmte Länge wo erstmal nichts drinsteht. Ich weiß aber nicht, was das bringen soll. Möglicherweise suchst du eigentlich ein Dictionary.
Code: Alles auswählen
In [2]: [None for dummy in xrange(10)]
Out[2]: [None, None, None, None, None, None, None, None, None, None]
Zuletzt geändert von snafu am Mittwoch 7. Oktober 2009, 07:11, insgesamt 1-mal geändert.
Du könntest zum Beispiel den folgenden Code verwenden:
None wäre durch einen geeigneten Leerwert zu ersetzen.
ABER: Es fast immer unnötig, Listen mit einer bestimmten Länge vorzuinitialisieren. Vermutlich hast du etwas vor, was eher schlechter Programmierstil wäre. Wenn du ein bisschen mehr über dein Problem und deinen Lösungsansatz erzählen würdest, könnten wir da mal drüberschauen.
Code: Alles auswählen
my_list = 5 * [None]
ABER: Es fast immer unnötig, Listen mit einer bestimmten Länge vorzuinitialisieren. Vermutlich hast du etwas vor, was eher schlechter Programmierstil wäre. Wenn du ein bisschen mehr über dein Problem und deinen Lösungsansatz erzählen würdest, könnten wir da mal drüberschauen.
z.B. soLeonidas hat geschrieben:Man kann auch so eine Klasse erstellen, indem man von ``list`` ableitet...
Code: Alles auswählen
class SpecialArray(list):
def __init__(self, length, default_value=None):
list.__init__(self)
self.extend([default_value] * length)
s_array = SpecialArray(3)
print s_array
s_array = SpecialArray(8, 'default')
print s_array
-
- User
- Beiträge: 456
- Registriert: Mittwoch 15. April 2009, 14:11
Wie sieht es denn mit der Zugriffszeit aus. Listen zu durchwandern liegt schließlich in O(n). Eine Array an einer bestimmten Stelle anzusprechen hingegen nur konstante Laufzeit O(1). Falls die der Zugriff auf Python Listen in O(n) liegt, bringt das Ableiten eines Arrays aus einer Liste überhaupt nichts.
Kann das jemand mal aufklären?
Kann das jemand mal aufklären?
- Defnull
- User
- Beiträge: 778
- Registriert: Donnerstag 18. Juni 2009, 22:09
- Wohnort: Göttingen
- Kontaktdaten:
Der Satz ist richtig. Allerdings kannst du die Worte "Liste" und "Array" auch beliebig tauschen. Ein Index-Zugriff dauert immer O(1), ein scan immer O(n).anogayales hat geschrieben:Listen zu durchwandern liegt schließlich in O(n). Eine Array an einer bestimmten Stelle anzusprechen hingegen nur konstante Laufzeit O(1).
Für C Versteher: Pythons Listen sind Pointer-Arrays mit variabler Länge.
Bottle: Micro Web Framework + Development Blog
Ich hab das schon öfter gesehen aber wofür steht das? Ist O quasi die Zeit für einen Lookup und der Vergleich drückt aus, dass bei bekannter Position des Elements die Zeit nur einmal gebraucht wird, während bei einem Durchlaufen aller Elemente die Lookup-Zeit mal Anzahl der Elemente nötig ist?anogayales hat geschrieben:O(n)
O(1)
Die O-Notation ist hier eine Abschätzung der maximalen Laufzeit eines Algorithmus.
Wenn man g(n) = O(f(n)) schreibt, wobei f(n) eine Funktion ist, meint man, dass die max. Laufzeit g in Abhängigkeit der Eingabelänge n höchstens so schnell wächst, wie die Funktion f.
Häufig sieht man O(n), O(1), O(log(n)) u.a. Das sind abkürzende Schreibweisen für O(f(n)) mit f(n) = n, f(n) = 1, f(n) = log(n).
Genauer bedeutet es, dass eine feste konstante c existiert, sodass für jedes beliebige n, g(n) <= c * f(n) gilt.
Das Durchwandern einer Liste von vorne nach hinten, ist damit O(n).
Wenn ich eine doppelt so lange Liste habe, muss ich doppelt soviele Elemente angucken, die Laufzeit ist doppelt so lange. Also steigt die Laufzeit in Abhängigkeit der Eingabelänge (= Länge der Liste) linear.
Ob ich jetzt 5 oder 10 Operationen brauche, um von einem Element zum anderen zu kommen, ist mir dabei wurscht. Daher die Konstante c, die man frei wählen kann. Ist halt eine gröbere Einteilung.
Wenn man g(n) = O(f(n)) schreibt, wobei f(n) eine Funktion ist, meint man, dass die max. Laufzeit g in Abhängigkeit der Eingabelänge n höchstens so schnell wächst, wie die Funktion f.
Häufig sieht man O(n), O(1), O(log(n)) u.a. Das sind abkürzende Schreibweisen für O(f(n)) mit f(n) = n, f(n) = 1, f(n) = log(n).
Genauer bedeutet es, dass eine feste konstante c existiert, sodass für jedes beliebige n, g(n) <= c * f(n) gilt.
Das Durchwandern einer Liste von vorne nach hinten, ist damit O(n).
Wenn ich eine doppelt so lange Liste habe, muss ich doppelt soviele Elemente angucken, die Laufzeit ist doppelt so lange. Also steigt die Laufzeit in Abhängigkeit der Eingabelänge (= Länge der Liste) linear.
Ob ich jetzt 5 oder 10 Operationen brauche, um von einem Element zum anderen zu kommen, ist mir dabei wurscht. Daher die Konstante c, die man frei wählen kann. Ist halt eine gröbere Einteilung.
Um das Haar mal vollends zu spalten: Ob ein Index-Zugriff in O(1) (also in konstanter Zeit) möglich ist, hängt von der Implementierung ab. Nimm eine verkettete Liste auf die du nur über das erste Element zugreifen kannst. Dann mußt du dich, um auf die i-te Stelle zugreifen zu können, die ganze Kette entlanghangeln. Damit hast du dann ein Worst-Case-Verhalten von O(n) und im Durchschnitt etwas wie O(log n).Defnull hat geschrieben: Ein Index-Zugriff dauert immer O(1), ein scan immer O(n).
Merke: Der Wahl der richtigen Datenstruktur kommt eine gewisse Bedeutung zu. Man sollte aber davon ausgehen, daß alle Programmiersprachen, die eine gewisse Reife erreicht haben, die jeweils bestmögliche Implementierung für die "einfachen" Datenstrukturen gewählt haben. Spannend wird es, wenn man kompliziertere Strukturen wie Graphen oder Bäume nutzen will. Da hängt es dann schon sehr von der Natur des Programms ab, welche man wählt.
Ich verstehe den Zusammenhang glaube ich trotzdem nicht. Wenn die Größe des Array/der Liste bekannt ist, warum soll der Zugriff auf ein Element dann schneller sein? Oder war die Zeit zur Bestimmung der Länge gemeint? Dann ist mir natürlich klar, dass man die schneller gekommt, wenn man einen gemerkten Wert abruft anstatt bei einer variablen Länge erstmal alle Elemente durchlaufen zu müssen, um an die derzeitige Länge zu kommen. Aber macht man das in der Praxis überhaupt? Wäre es nicht effizienter eine Art Zähler einzubauen, der bei neuen Elementen hochgezählt wird, damit dadurch auch einfach der Stand des Zählers beim Aufruf von `len()` abgefragt werden kann?
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
@snafu: Die Kenntniss der Größe ist ja auch nicht entscheidend, sondern die Implementierung. Sprich: Kann ich direkt über einen Index (und somit indirekt auf eine bestimmte Speicheradresse) auf ein Element zugreifen oder muss ich erst die Liste bis zu diesem Element durchlaufen.
Was ich nicht begreife: Wieso möchte man das überhaupt so in Python definieren? In C gibt es ja keine komfortable Implementierung von dynamischen Datenstrukturen im ANSI Sprachumfang (oder irre ich hier?). Daher ist es dort bei angenommener bekannter maximaler Größe oft einfacher, ein statisches Array anzulegen. Aber im Grunde genommen wird das ja eigentlich obsolet durch eine solche komfortbale Struktur, die einem die eigene Speicherverwaltung abnimmt, oder nicht?
Was ich nicht begreife: Wieso möchte man das überhaupt so in Python definieren? In C gibt es ja keine komfortable Implementierung von dynamischen Datenstrukturen im ANSI Sprachumfang (oder irre ich hier?). Daher ist es dort bei angenommener bekannter maximaler Größe oft einfacher, ein statisches Array anzulegen. Aber im Grunde genommen wird das ja eigentlich obsolet durch eine solche komfortbale Struktur, die einem die eigene Speicherverwaltung abnimmt, oder nicht?
Zuletzt geändert von Hyperion am Donnerstag 8. Oktober 2009, 06:45, insgesamt 1-mal geändert.
Ein Array wird in der Regel als eine feste Speicheradresse und eine Feldgröße definiert. Um ein bestimmtes Feld anzusprechen muß man also nur Speicheradresse + index * Feldgröße rechnen und kann die Daten auslesen. Das ist in konstanter Zeit möglich. Da man nicht den ganzen verbleibenden Speicher für mögliche weitere Elemente reservieren kann, muß man irgendwo eine Grenze ziehen. Aus diesem Grund werden Arrays mit einer bestimmten Anzahl von Elementen initialisiert. Dynamische Arrays setzen auf klassischen Arrays auf, in dem sie bei Überschreiten der ursprünglichen Anzahl Felder einen neuen, größeren Array anlegen und die Daten rüberkopieren.
Listen können auf verschiedene Arten implementiert werden. U.a. mit Zeigern oder halt in Arrays. Beide Formen haben ihre Vor- und Nachteile bezügllich der Laufzeit von Operationen wie Auslesen, Hinzufügen oder Löschen von Elementen.
Listen können auf verschiedene Arten implementiert werden. U.a. mit Zeigern oder halt in Arrays. Beide Formen haben ihre Vor- und Nachteile bezügllich der Laufzeit von Operationen wie Auslesen, Hinzufügen oder Löschen von Elementen.
Ich greife einfach auf den Index des darunter liegenden Pointer-Arrays zu und lasse C sich um diesen Schwachsinn kümmern. Nein, ich denke ich habe verstanden: Es käme im Fall von Python eben darauf an, wie C das implementiert oder ob man das möglicherweise selbst implementieren möchte, wenn man denkt, dass es für die eigenen Sprache sinnvoll ist.Hyperion hat geschrieben:Kann ich direkt über einen Index (und somit indirekt auf eine bestimmte Speicheradresse) auf ein Element zugreifen oder muss ich erst die Liste bis zu diesem Element durchlaufen.
@Pekh:
Aha. Das heißt also, wenn ich das Maximum auf 50 Elemente der gleichen Größe (z.B. Zeiger auf die tatsächliche Datenstruktur) festlege, hätte ich den Zugriff auf Element 48 im Grunde so schnell wie auf Element 2, da ich die Speicheradresse des Elements jeweils auf dem gleichen Weg berechne und mich daher im Grunde nicht interessiert, wieviele Elemente davor kommen, richtig? Wenn ich dann das Maximum überschreite, müsste ich ein neues Array für 50 Elemente anlegen. Diese Arrays könnte ich meinetwegen verbinden, indem das letzte Element von Array1 ein Zeiger auf Array2 ist oder indem ich irgendwo abspeicher, dass alle Elemente > 50 in Array2 liegen. Dann müsste ich halt den Zusatzschritt gehen, erstmal abzufragen, welches Array ich benutzen soll und von dieser Speicheradresse aus das Spielchen mit der Multiplikation machen. Hab ich das so einigermaßen richtig wiedergegeben?
Aha. Das heißt also, wenn ich das Maximum auf 50 Elemente der gleichen Größe (z.B. Zeiger auf die tatsächliche Datenstruktur) festlege, hätte ich den Zugriff auf Element 48 im Grunde so schnell wie auf Element 2, da ich die Speicheradresse des Elements jeweils auf dem gleichen Weg berechne und mich daher im Grunde nicht interessiert, wieviele Elemente davor kommen, richtig? Wenn ich dann das Maximum überschreite, müsste ich ein neues Array für 50 Elemente anlegen. Diese Arrays könnte ich meinetwegen verbinden, indem das letzte Element von Array1 ein Zeiger auf Array2 ist oder indem ich irgendwo abspeicher, dass alle Elemente > 50 in Array2 liegen. Dann müsste ich halt den Zusatzschritt gehen, erstmal abzufragen, welches Array ich benutzen soll und von dieser Speicheradresse aus das Spielchen mit der Multiplikation machen. Hab ich das so einigermaßen richtig wiedergegeben?
Der erste Teil ist richtig. Aber wenn ich ein 51. Element hinzufügen will, muß ich ein neues Array anlegen (oder anlegen lassen), mit z.B. 100 Elementen, und dann die Daten aus dem alten Array hinüberkopieren. Das macht das Hinzufügen von neuen Elementen zu einem Array recht teuer. Lösche ich ein Element, muß ich alle folgenden Elemente verschieben.
Bei einer Liste mit Zeigern enthält jedes Element einen Zeiger auf seinen Nachfolger und evtl. auch auf seinen Vorgänger. Die Elemente können so faktisch bunt über den Speicher gestreut sein. Das Hinzufügen und Löschen ist hier in konstanter Zeit möglich, da ich "nur" ein paar Zeiger umbiegen muß. Will ich aber auf das i-te Element zugreifen, muß ich mich vom ersten Element durchhangeln und bei jedem Element nachfragen, wo denn nun sein Nachfolger steckt. Solche Strukturen verwendet man, wenn sich oft Änderungen ergeben, oder wenn man eigentlich nur sequentiell darauf zugreifen will. Arrays (oder mit Arrays implementierte Listen) bieten schnelleren Zugriff, sind aber eher für statische Datenmengen geeignet.
Bei einer Liste mit Zeigern enthält jedes Element einen Zeiger auf seinen Nachfolger und evtl. auch auf seinen Vorgänger. Die Elemente können so faktisch bunt über den Speicher gestreut sein. Das Hinzufügen und Löschen ist hier in konstanter Zeit möglich, da ich "nur" ein paar Zeiger umbiegen muß. Will ich aber auf das i-te Element zugreifen, muß ich mich vom ersten Element durchhangeln und bei jedem Element nachfragen, wo denn nun sein Nachfolger steckt. Solche Strukturen verwendet man, wenn sich oft Änderungen ergeben, oder wenn man eigentlich nur sequentiell darauf zugreifen will. Arrays (oder mit Arrays implementierte Listen) bieten schnelleren Zugriff, sind aber eher für statische Datenmengen geeignet.
Okay, jetzt ist mir auch klar, was mit dem Durchlaufen der Elemente gemeint war.
Aber meines Wissens hat man über all das in Python keine Kontrolle, da Python eben nur die Liste anbietet. Von daher dürfte es, wie schon gesagt wurde, relativ sinnfrei sein, eine Liste mit vorbestimmter Länge zu initialisieren.
Aber meines Wissens hat man über all das in Python keine Kontrolle, da Python eben nur die Liste anbietet. Von daher dürfte es, wie schon gesagt wurde, relativ sinnfrei sein, eine Liste mit vorbestimmter Länge zu initialisieren.