Das deutsche Python-Forum

Hallo zusammen,

ich habe folgendes Programm: Ich habe zwei Fragen:

(1) Wie ist das Laufzeitverhalten? Ich denke while-Schleife * erste * zweite for-Schleife, also x³? Kann ich die Kompexität O(n³) genauer angeben? Habe ich überhaupt recht und das Konzept verstanden?

(2) Mein Anliegen bei obigem Programm dürfte verständlich sein. Kann ich so etwas besser machen ohne so viele verschachtelte Schleifen?

Danke!

Zu Punkt 2, wobei ich lieber nicht nach dem Sinn des Ganzen fragen möchte: Auch verstehe ich nicht wirklich, wie jemand nach mehr als 1.300 Beiträgen hier im Forum scheinbar noch immer nicht das Konzept von for-Schleifen in Python (nämlich *kein* ``range(len(items))``) verinnerlicht hat. Aber sich darüber zu beschweren, bringt ja eh nicht viel...

Die while-Schleife ist keine, weil sie maximal einmal durchlaufen wird. Statt while solltest Du also if schreiben. Oder gleich gar keinen Test, weil es keinen Unterschied macht.
Bleibt also: Eingerückt wird übrigens immer mit 4 Leerzeichen pro Ebene, keine Tabs!

@pixewakb: Laufzeitverhalten in O-Notation ist O(n) mit n der Anzahl der Elemente und das wird man auch nicht besser hinbekommen, denn man muss ja jedes Element einmal betrachten, ob es den Wert 3 hat oder nicht.

Das ``while`` ist das falsche Mittel weil, wie Sirius3 ja auch schon sagte, die Schleife je nach dem was die Bedingung ergibt, entweder gar nicht oder genau einmal durchlaufen wird, was ein ``if`` ist und keine Schleife in der etwas wiederholt wird. Und das ``if`` ist überflüssig, weil es ein zusätzlicher Schritt ist, der keine Auswirkung auf das Ergebnis hat.

Beide bisherigen Lösungen bauen eine neue Datenstruktur auf, mit den gewünschten Werten, was die Vorlage ja nicht tut. Darum der Vollständigkeit halber noch eine Lösung, welche die vorhandene Datenstruktur verändert, mit weniger Indexzugriffen: Verändern von der Struktur kann effizienter sein als eine neue Datenstruktur aufzubauen, das kommt aber sehr auf die Umstände wie grösse der Struktur, die Anzahl der zu ersetzenden Werte, die Python-Implementierung, und so weiter an. Am Laufzeitverhalten in O-Notation ändert das aber nichts! „Pythonischer“ wäre IMHO eine neue Struktur zu erzeugen. Keine Seiteneffekte zu haben macht Code in der Regel einfacher nachvollziehbar, weil man sich keine Gedanken machen muss, ob noch irgendwelcher anderer Code auf die Struktur Zugriff hat, den eine Änderung vielleicht ”überraschen” könnte.

Wo man Veränderung eher erwarten würde, währen Numpy-Arrays. Da sähe der Code dann aber komplett ”schleifenfrei” einfach so aus: Dort laufen natürlich dann intern Schleifen, und auch das hat eine Laufzeitverhalten von O(n). Was die Komplextitätsklasse angeht, sind all diese Varianten also gleichwertig.

@pixewakb: Eine Komplexität von O(n) hast Du, wenn Du alle n Elemente x-mal betrachten musst, wobei x konstant ist. Musst Du n Elemente n-mal betrachten, also bei 4 Elementen jedes 4 mal, bei 5 Elementen dann jedes Element 5 mal usw., dann hast Du ein quadratisches Verhalten, also eine Komplexität von O(n^2).

Du fasst in Deinem Beispiel jedes Element zwar (ungefähr) 3 mal an, Deine Lösung ist aber dennoch O(n) und nicht O(n^3). Die vorgestellten List-Comprehension fassen jedes Element 1 mal an und sind schneller, aber auch O(n). Zwei Varianten (oder Algorithmen) mit O(n) müssen jedoch nicht die gleiche Laufzeit aufweisen. Nimm zum Beispiel

das hat eine Komplexität von O(n). Die folgende Variante

fasst jedes n zweimal an und läuft deutlich langsamer, ist aber auch O(n).

In dem nächsten Beispiel dagegen wächst die Zahl der Schleifendurchläufe mit steigendem n quadratisch an:

daher hat dieser Code eine Komplexität von O(n^2).

Geht das Beispiel einmmal im Geiste mit den Werten 2, 3 und 4 für n durch und lass es dann anschließend mit diesen Werten laufen.

Momentan komme ich nur langsam dazu das Feedback zu verarbeiten, weshalb ich jetzt erst antworte.

Mein Einstiegsbeispiel war nicht gut gewählt. Tatsächlich geht es um etwas wie ein Game of Life, wobei ich von den Koordinaten in einem zweidimensionalen Array ausgehend benachbarte Felder mit Zahlen versehen muss.
Ich prüfe dann zunächst, ob ich schon alle Felder besetzt habe und dann hole ich mir mit den zwei for-Schleifen die Koordinaten für x und y. Die letzten beiden Codezeilen sind Platzhalter, tatsächlich muss ich dort vielmehr machen und benachbarte Felder (dafür brauche ich 'x' und 'y') auch mit Zahlen versehen. Es ist letztlich eine Spielerei.

Ausgehend von der Überlegung vermute ich, dass ich dann, weil ich das Feld schrittweise durchlaufen muss, um es schrittweise zu befüllen, schon bei O(n³) auskomme???
Es kommt nämlich - schrittweise - in etwa so etwas heraus, links Anfangszustand, rechts Endzustand.
Sorry für meinen missverständlichen Thread-Start.

@pixewakb: Also das *in* der ``while``-Schleife hat weiterhin O(n) Laufzeitverhalten mit dem gezeigten innersten Code, mit `n` der Anzahl Elemente in der 2D-Datenstruktur. Wie oft die ``while``-Schleife durchlaufen wird, und wie sich der tatsächliche Code in der innersten Schleife auf die Laufzeitkomplexität auswirkt, kann man nicht sagen solange man nicht weiss, was da passiert.

Es macht nicht so wirklich Sinn kryptischen Teilcode zu zeigen, denn da lässt sich nicht wirklich dran ablesen ob man da etwas deutlich besser/schneller machen kann, weil das in der Regel ein alternativer oder zumindest ein abgewandelter Algorithmus ist. Dazu muss man den aber komplett kennen, und meistens auch wissen, welche Randbedingugen gelten müssen, oder was man vielleicht auch ignorieren kann. Und oft auch welche Eigenschaften die Daten haben.

Falls es keine algorithmische Veränderung gibt, gibt es auch nichts was die O-Laufzeit ändert. Dann kann noch an den konstanten Faktoren, die bei der O-Notation keine Rolle spielen, versuchen zu optimieren. Da wäre der erste Schritt aber zu messen wo überhaupt am meisten Zeit, bei typischen Eingabedaten verbraucht wird, damit nicht unnötig Zeit in Codeteile steckt, bei denen man man gar nicht wirklich nennenswert Zeit einsparen kann.

Ein wesentlicher Unterschied zu so etwas wie „Game of Life“ scheint hier zu sein, dass es nichts ausmacht, das Änderungen an Zellen innerhalb einer Generation schon andere Zellen beeinflussen‽ Es also nicht egal ist in welcher Reihenfolge man die Zellen besucht‽

Wenn man wie bei Game of Life in jedem Schritt quasi eine komplett neue Generation auf dem Spielbrett zeigen will, dann würde ich den Vorschlag aufgreifen und einfach eine neue Liste-von-Listen erstellen, anstatt die bestehende zu verändern.

Und nein, dein (bisheriger) Pseudo-Code hat kein O(n^3) Verhalten.

weil ich das Feld schrittweise durchlaufen muss, um es schrittweise zu befüllen

Dann ist es O(n) Verhalten. Oder meinetwegen O(2*n) oder O(3*n) aber diese konstanten Faktoren werden bei großen n eben irrelevant.

Du scheinst dich selbst zu verwirren, weil du zwei Schleifen hast für die X- und Y-Koordinaten. Du schaust dir aber jedes Feld nur einmal an. Und die Prüfung pro Feld scheint immer genau das gleiche zu tun, unabhängig von der Anzahl der Felder, richtig? Also O(n). Du könntest die zwei Schleifen übrigens jetzt auch theoretisch zusammenfassen und statt bspw. 10x10 in x und y zu durchlaufen, einmal bis 100 laufen und die Felder so ebenfalls einzeln prüfen.

Wenn du dir hingegen jedes einzelne Feld anschauen würdest, und dann für jedes einzelne Feld nochmal ALLE anderen Felder anschauen müsstest, dann wärst du bei O(n^2) weil es plötzlich einen Unterschied macht, wie viele andere Felder es da jeweils für jedes einzelne Feld noch zu prüfen gibt.

Bei Game of Life guckt man sich pro Feld aber auch immer nur genau 4 Nachbarfelder an, unabhängig davon wie groß das Spielfeld ist. Es bleibt also O(n) Verhalten.

Es wurde zwar schon erklärt, aber noch nicht von jedem.