Jedes n T Element in einer Liste ändern

[xfire]

Hallo,
ich bin ein python Newbie. Ich möchte in einer Liste (isList) mit der Länge length ab dem Wert i+1 jedes kte Element von True in False ändern. Allerdings möchte ich dies ohne eine Schleife lösen. Die Liste sieht von Beginn so aus: isList=length*[True]

Ich stelle mir das etwa so vor: isList = isList[0:i]+(length-i)*[ jedes kt-Element False, sonst True]
Also, wenn k=2 ist, sollen allen Vielfachen von 2 auf False gesetzt werden.
wenn k=3 ist, alle Vielfachen von 3 auf False
danach geht es mit 5 weiter usw.
(Das Betreffende k und i, werden zuvor schon ermittelt)
Kann ich das in dieser Form überhaupt ausdrücken? Wenn ja wäre ich über Hilfe sehr dankbar.
Oder kann ich das über eine Listenmethode erreichen?
Geht das überhaupt ohne Schleife? wenn Nein, muss ich weiter grübeln.....

[__blackjack__]

@xfire: Warum willst Du das ohne Schleife machen?

Grunddatentypen sollten nicht in Namen vorkommen, weil man die im Laufe der Programmentwicklung nicht selten mal ändert und dann hat muss man alle betroffenen Namen anpassen, oder man hat falsche, irreführende Namen im Programm.

Namen schreibt man in Python klein_mit_unterstrichen. Ausnahmen sind Konstanten (KOMPLETT_GROSS) und Klassen (MixedCase).

Bleibt also `is` übrig, was aber als Name nicht geht, weil es ein Schlüsselwort von Python ist, aber auch weil das als Name nicht aussagekräftig genug ist. Namen sollten dem Leser verraten wofür der Wert dahinter steht, nicht zum Rätselraten zwingen.

Klingt übrigens so ein bisschen nach dem Sieb des Eratosthenes.

[xfire]

Also, danke für fen Hinweis zur Nomenklatur, habe diese aus meinem Tutorial,werde ich beherzigen
Also ja genau darum handelt es sich. Bei dieser Aufgabe geht es um Effizienz. Es war kein größeres Problem für einzelne Zahlen zu ermitteln, ob es eine Primzahl ist. In dieser Aufgabe soll eine Liste ereugt werden,ab 0, die jeweils True für Primzahl und False für teilbar ausgibt. Die Länge der Liste soll 100001 betragen. ( zu Testzwecken arbeite ich mit 101).
Außerdem wurde die Laufzeit des Programms verlängert. Ich möchte also so wenig Schleifen wie möglich.
Meine Überlegung ist folgende.
1. Schleife (for)geht den Index der Liste mit durch und springt in eine while Schleife die testet wenn prim == True and k*k<=i
Dies funktioniert auch im Einzellfall.
Wenn es keine Primzahl ist: prim=False und danach soll die Liste mit dem Faktor i geändert werden. (Ev. würde ich dann die Überprüfung des Wertes prim noch in die 1. Schleife nehmen.

Mein Sohn(13) mit dem ich parallell am Tutorial arbeite hat übrigens den Ansatz in der while Schleife nur jedes kte Element zu überprüfen.
Aber dann erwischt das Programm die Primzahlen nicht.

Ich hoffe das war verständlich.

[__blackjack__]

@xfire: Nicht so wirklich. Ich sehe da irgendwie keine ``while``-Schleife. Die innere Schleife ist auch eine ``for``-Schleife. Ein ``== True`` hast Du hoffentlich nicht im Programm stehen, denn da kommt ja nur wieder `True` oder `False` heraus. Da kann man auch gleich den Wert nehmen mit dem man vergleicht.

[xfire]

Ja, das ist einleuchtend. Ich werde wohl noch an den Schleifen feilen und ein wenig mit meinem Sohn diskutieren. Mit dem richtigen Ansatz findet er manchmal recht schlicht Lösungen. Jetzt sollte ich aber schlafen und werde mal die nächsten Tage mich melden. Danke vorerst.

[xfire]

Jetzt habe ich die Schleifen noch einmal überarbeitet und schließlich die Änderung in der Liste doch mit einer 3.-for Schleife gelöst und Tadaaa! Es läuft! Sicherlich geht es noch eleganter und schneller, aber das Ergebnis stimmt. Manchmal braucht es einfach einen kleinen Schubser von außen um auf die Lösung zu kommen. Danke für die Hilfe!

[__blackjack__]

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

[__blackjack__]

Um das dann doch noch mal in Python zu zeigen:

Code: Alles auswählen

def sieve(upper_limit):
    prime_flags = [True] * (upper_limit + 1)
    prime_flags[0] = prime_flags[1] = False
    for i in range(len(prime_flags)):
        if prime_flags[i]:
            for j in range(i + i, len(prime_flags), i):
                prime_flags[j] = False
    return prime_flags

An der Lauflänge der äusseren Schleife kann man noch ein bisschen optimieren.

[Sirius3]

Die innere Schleife könnte man noch zur Effizienzsteigerung internalisieren:

Code: Alles auswählen

def sieve(upper_limit):
    prime_flags = [True] * (upper_limit + 1)
    prime_flags[0] = prime_flags[1] = False
    for i in range(len(prime_flags)):
        if prime_flags[i]:
            prime_flags[i+i::i] = [False] * ((len(prime_flags)-i-1)//i)
    return prime_flags

[__blackjack__]

@Sirius3: Vom Speicherverbrauch her eher nicht, und ob das nun eine bessere Laufzeit hat und wenn ja wieviel das bringt, dürfte implementierungsabhängig sein. Bevor ich so etwas mache, würde ich eher Numpy verwenden.