@xfire: Wenn es um Effizienz geht ist eine Lösung mit weniger Code nicht zwingend die effizienteste und nur weil im Code an der Stelle keine ``for``-Schleife steht, bedeutet das nicht, das nicht eine oder mehrere Schleifen ausgeführt werden.
Nehmen wir mal das ``length * [True]`` – da wird im Hintergrund natürlich eine Schleife ausgeführt werden, die `length`-mal ausgeführt wird, um alle Elemente der Liste, die als Ergebnis von dem Ausdruck heraus kommt, auf den Wert `True` zu setzen. Es ist aufgrund Implementierungsdetails bei CPython schneller als ``[True for _ in range(length)]`` weil die in C implementierte Multiplikation einer Liste mit einer ganzen Zahl Dinge tun kann, die man auf Python-Ebene aus Sicherheitsgründen nicht kann. Zum Beispiel eine Liste mit einer angegebenen Länge erstellen, bei denen die Elemente nicht initialisiert sind. In Python-Code kann man Listen ansonsten nur elementweise aufbauen. Mit dem Effekt, dass ab und zu neuer Speicher für zusätzliche Elemente angefordert werden muss, und möglicherweise der bisherige Inhalt in den neuen Speicherbereich kopiert werden muss, wenn man ein Element anhängt.
Dein Pseudocode-Ansatz war ja:
Code: Alles auswählen
isList = isList[0:i]+(length-i)*[ jedes kt-Element False, sonst True]
Das funktioniert so zwar nicht, aber man sieht schon das hier eine neue Liste erstellt wird, das heisst es wird Speicher angefordert und alle Elemente müssen kopiert werden, weil man ja hinterher wieder eine Liste mit `length` Elementen haben muss. Da ist ein ``+`` mit Listen in dem Ausdruck. Auch das bedeutet wieder neuen Speicher anfordern, der die Elemente beider Listen aufnehmen kann, dann das kopieren aller Elemente in diese neue Liste, und wenn eine oder beide beteiligten Listen nur Zwischenergebnisse waren auf die ansonsten keine Referenz mehr besteht, muss auch noch Speicher wieder freigegeben werden.
Eine ``for``-Schleife in der ab 2·i jedes i-te Element einer Liste auf `False` gesetzt wird, verändert nur eine vorhandene Liste und es müssen keine Elemente kopiert oder neuer Speicher angefordert werden, was diese Liste angeht.
Man wird das mit Listen und „slicing“ und ``*`` mit ``[False]`` mit einer Zuweisung anstelle der inneren ``for``-Schleife lösen können wenn man unbedingt will. Da werden intern dann aber weiterhin Schleifen beteiligt sein. Nur eben als Folge des „sclicings“ und des ``*`` mit einer Liste und nicht mehr als ``for`` im selbstgeschriebenen Code.
Das könnte vielleicht innerhalb bestimmter Grenzen in CPython sogar effizienter sein, weil der C-Code der da intern abläuft trotz mehr Schleifendurchläufen und Speichersauereien schneller sein könnte. Das ist aber nichts auf das man sich verlassen sollte, und es geht auf die Verständlichkeit des Quelltextes.
Was legitim wäre in Hinblick auf die Lesbarkeit wäre ein `numpy`-Array anstelle einer Liste zu verwenden, weil man bei denen auch skalare Werte einem „sclice“ zuweisen kann, was intern in einer in C geschriebenen Schleife umgesetzt wird. Würde natürlich bedeuten, dass man sich Numpy als Abhängigkeit an Bord holt.
Mal als Vergleich die im Grunde gleiche, einfache Implementierung des Siebs einmal in Icon:
Code: Alles auswählen
link lists
procedure main(args)
n := \args[1] | 101
P := lrepl([1], n) ; P[1] := 0
every P[i := 1 to *P] = 1 & P[i+i to *P by i] := 0
write(limage(P))
end
Hier stecken die beiden Schleifen in einer Zeile (``every …``), in einem Ausdruck. Und der gleiche Algorithmus in einer der „geschwätzigsten“ Programmiersprachen die ich kenne – COBOL:
Code: Alles auswählen
IDENTIFICATION DIVISION.
PROGRAM-ID. sieve.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 n CONSTANT AS 101.
01 i BINARY-LONG.
01 j BINARY-LONG.
01 is-prime-table.
02 is-prime PIC 9 VALUE 1 OCCURS n TIMES.
PROCEDURE DIVISION.
MOVE 0 TO is-prime(1).
PERFORM VARYING i FROM 2 BY 1 UNTIL i EQUALS n
IF is-prime(i) EQUALS 1 THEN
ADD i TO i GIVING j
PERFORM VARYING j FROM j BY i
UNTIL j IS GREATER THAN OR EQUAL TO n
MOVE 0 TO is-prime(j)
END-PERFORM
END-IF
END-PERFORM
DISPLAY is-prime-table.
GOBACK.
END PROGRAM sieve.
Vom Vorgehen her sind beide gleichwertig, also auch gleich effizient. COBOL wird ziemlich wahrscheinlich in der Praxis hier schneller sein, weil das statisch typisiert ist und üblicherweise in ein natives Binärprogramm übersetzt wird, während Icon ähnlich wie Python Bytecode einsetzt. Es gibt die Option Icon auch in ein natives Binärprogramm zu übersetzen, da spart man sich aber im Grunde nur die Interpreterschleife die durch direkte Aufrufe der jeweiligen Funktionen von den Bytecode-Anweisungen ersetzt wird. Ähnlich wie bei Python wenn man normales Python mit Cython nach C übersetzt.
Beide Implementierungen weichen geringfügig von der Aufgabenstellung ab, weil sowohl bei Icon als auch bei COBOL Listen bzw. Tabellenindices bei 1 anfangen. Und bei beiden gibt es keinen Datentyp für Wahrheitswerte, darum habe ich 0 und 1 genommen.
Ich sehe übrigens nicht wofür man für's sieben drei Schleifen braucht. Es sei denn Du hast da nach dem sieben noch eine, die eine Liste mit den Primzahlen aus den Siebdaten erstellt.