Laufzeitverhalten verbessern

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
pixewakb
User
Beiträge: 1407
Registriert: Sonntag 24. April 2011, 19:43

Hallo zusammen,

ich habe folgendes Programm:

Code: Alles auswählen

>>> a = [[1, 1, 2, 1],
	 [2, 2, 3, 2],
	 [4, 2, 2, 1]]
>>> while any(3 in line for line in a):
	for y in range(len(a)):
		for x in range(len(a[0])):
			if a[y][x] == 3:
				a[y][x] = 1

				
>>> 
>>> a
[[1, 1, 2, 1], [2, 2, 1, 2], [4, 2, 2, 1]]
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!
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Zu Punkt 2, wobei ich lieber nicht nach dem Sinn des Ganzen fragen möchte:

Code: Alles auswählen

[[1 if n == 3 else n for n in numbers] for numbers in a]
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...
Sirius3
User
Beiträge: 17710
Registriert: Sonntag 21. Oktober 2012, 17:20

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:

Code: Alles auswählen

a = [[1 if n == 3 else n for n in numbers] for numbers in a]
Eingerückt wird übrigens immer mit 4 Leerzeichen pro Ebene, keine Tabs!
Benutzeravatar
__blackjack__
User
Beiträge: 13003
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@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:

Code: Alles auswählen

for row in a:
    for index, value in enumerate(row):
        if value == 3:
            row[index] = 1
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:

Code: Alles auswählen

a[a == 3] = 1
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.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

@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

Code: Alles auswählen

for n in range(100):
    print(n)

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

Code: Alles auswählen

for n in range(100):
    print(n)
    time.sleep(1)
    print(n)

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:

Code: Alles auswählen

counter = 0
n = 2
for x in range(n):
    for y in range(n):
        counter += 1
        print(counter)

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.
Benutzeravatar
pixewakb
User
Beiträge: 1407
Registriert: Sonntag 24. April 2011, 19:43

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.

Code: Alles auswählen

while any(3 in line for line in a):
    for y in range(len(a)):
        for x in range(len(a[0])):
            if a[y][x] == 3:
                a[y][x] = 1
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.

Code: Alles auswählen

0000  0200  0220  0222  0222  1222
0000  0003  0010  0113  1113  1113
0000  0010  0110  1110  1110  1113
Sorry für meinen missverständlichen Thread-Start.
Benutzeravatar
__blackjack__
User
Beiträge: 13003
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@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‽
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
Kebap
User
Beiträge: 686
Registriert: Dienstag 15. November 2011, 14:20
Wohnort: Dortmund

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. :mrgreen:
MorgenGrauen: 1 Welt, 8 Rassen, 13 Gilden, >250 Abenteuer, >5000 Waffen & Rüstungen,
>7000 NPC, >16000 Räume, >200 freiwillige Programmierer, nur Text, viel Spaß, seit 1992.
Antworten