>>49436

>mit verarbeitetem Fleisch aufgewachsen.

Wie wir alle. Eine stark gewürzte, erhitzte oder gebratene Eiweiß-Fett-Masse (Sachen, nach denen der Körper giert) in Form von Wurst, Käse, auf Pizza, in Lasagnen auf Brötchen, Süßigkeiten, Kuchen und so weiter. Schmeckt gerade Kindern super. Heute dann noch drölfzig Zusatzstoffe.

Früher waren Schlachtfeste auch in Deutschland normal, da wurden bereits kleine Kinder an das Töten von Tieren herangeführt. Das ist wenigstens nicht so heuchlerisch, wie seine Kinder zu belügen und mit dem niedlichen Ferdi Fuchs zu füttern. Aber egal wie sehr du von klein auf an das Töten von Tieren und die Art der Verarbeitung gewöhnt wurdest, so bleibt doch immer ein Rest Mitleid oder zumindest Ekel zurück.

Mein Vater hat das Töten von Karnickeln und Hühnern irgendwann sein gelassen, weil er es nicht mehr ertrug. Ein Metzger kommt, anders als mein Vater, nicht so einfach von der Realität weg, aber ich bin mir sicher, dass keiner von ihnen, wie sehr er auch noch hinter seiner Lebensweise steht, nicht hin und wieder – beispielsweise, wenn ein Schwein besonders panisch wird oder ein Bolzenschuss daneben geht und das Schwein vor Qual durchdreht – Mitleid empfindet. Und diese Leute sind sicherlich auch froh, wenn sie abends endlich unter der Dusche stehen, um sich den beißenden Gestank vom Körper abzuwaschen.

Und ich sehe es genau wie du, mich geht deine Lebensweise nichts an. Es ist ja auch so, wenn man Menschen eine Lebensweise aufzwingt, über Sanktionen, Verbote und Strafen, dann werden sie trotzig und sich früher oder später dagegen wehren. So eine Entscheidung muss schon ganz von allein getroffen werden.

Das Zitat bezieht sich auf eine alte umgewandelte Paste.

>Hallo, jetzt kann ich endlich mit der Sprache rausrücken: ich bin bernd!

>nein, nicht ein bernd, der bernd…es gibt nur einen!

>du hast dich tatsächlich die ganze zeit nur mit einer person unterhalten, mit mir bilder ausgetauscht und sonst noch was gemacht. naja, meine scripte und bots haben etwas geholfen, aber so eine querschnittslähmung gibt einem viel zeit und antriebskraft.

>wenn du willst, kannst du geren weiterposten, vielleicht werde ich irgendwann eine dritt person ins board lassen.

>mfg Bernd

Da >>52285 den Pfostierer von >>52284 gefragt hat, warum dieser den Faden gestoßen hat (was er nicht getan hat) habe ich ihn unterstellt zu denken es würde nur einen Ernst geben.

Um die Frage in >>52285 zu beantworten: Katalog

>>51436
Ich sehe schon. Mein Ansatz ist aber genau andersherum. Ich habe ja gleich zu Anfang nur pandigitale Zahlen und ich muss die zusammengesetzten darunter ausschließen.

>>50492
Du musst nicht die ganze Zahl in eine Zeile quetschen. Lass das doch Püthon übernehmen:

N = '''
731...
...450
'''.replace('\n','')

Meine Lösung ist zuerst mal genauso wie deine.

def v1(n, l):
    m = 0

    for i in range(len(n)-l+1):
        r = 1
        for x in n[i:i+l]:
            r *= int(x)
        if r > m:
            m = r
            p = i

    return p, int(n[p:p+l]), m

print('Position: %d, Ziffernfolge: %d, Produkt: %d' % v1(N, 13))

Schau dir mal die innere Schleife an. Die ist für die Optimierung besonders interessant, weil sie in deinem Kode am häufigsten ausgeführt wird. Hier solltest du nicht in jeder Iteration i + j berechnen, sondern dir ein Scheibchen von n geben lassen. Damit läuft das Ganze immerhin nochmal doppelt so schnell.

Eine andere Lösung aus dem Zwischennetz. Also nicht meine, nur angepasst.

def _querprod(n):
    e = 1

    while n:
        e *= n % 10
        n //= 10

    return e

def v2(n, l):
    m = 0

    a = map(int, re.findall(re.compile(f'(?=([1-9]{{{l}}}))'), n))
    for i in a:
        r = _querprod(i)
        if r > m:
            m = r
            z = i

    return n.find(str(z)), z, m

Bei der Zeichenfolge {{{l}}} denkt man mit Bilderbretterfahrung natürlich unwillkürlich an

> De Joodn

Hier geht es allerdings um die sogenannten f-Strings. Mit dem f vor dem String wird das {l} durch den Wert von l ersetzt (z. B. 4 oder 13). Die doppelten geschweiften Klammern werden durch einfache ersetzt. Nach den Ersetzungen bleibt ein gültiger regulärer Ausdruck. Wenn du wissen willst, wie das genau funktioniert, such mal in der Python-Doku für das re-Modul nach lookahead assertion. Jedenfalls hält a danach alle möglichen 13-stelligen Zahlen ohne eine Null, für die man dann das größte Querprodukt sucht.

Das hat mich dann auf die Idee gebracht, die große Zahl an den Nullen zu zerteilen und die Berechnungen nur für Teile durchzuführen, die lang genug sind. Gerade wenn man 13 aufeinanderfolgende Ziffern untersucht, fällt da ja einiges weg. Das brachte mir die bisher schnellste Lösung.

Für 10000 Wiederholungen
Dauer(v1(13)) =  18.012172414993984
Dauer(v2(13)) =  5.416081340998062
Dauer(v3(13)) =  5.063234209999791

Die Lösung mit den regulären Ausdrücken (v2) ist also überraschenderweise mehr als doppelt so schnell und meine Lösung ohne regA (v3) bringt nur noch einen geringen Gewinn. Das gibt einen zu denken, wie mächtig Pythons (kompilierte) reguläre Ausdrücke sind! Die Zeiten sind hier höher, als in >>50492, weil ich hier wieder timeit benutze, das den Versuch zehntausendmal wiederholt. Bei einer durchschnittlichen Ausführungsdauer von ursprünglich 0,008 Sekunden jetzt eher 0,0001 :3 wird der Unterschied zwischen den Algorithmen dadurch deutlicher.

Nebenbei habe ich noch gelernt, dass JS viele Eigenschaften mit Püthon teilt (also auch so Dinge wie Generatoren und map() usw). Der kühle Einzeiler hier

f = n => [...n.matchAll(/(?=([1-9]{13}))/g)].reduce((a,c)=>(p=eval(c[1].split``.join`*`),p>a?p:a),0)

zeigt aber leider auch die ganze Beschissenheit der Sprache. Weil es ohne externe Bibos kein prod() gibt, wird da ein String zusammengefriemelt und mit dem pöhsen eval() interpretiert. Will man das in seiner JS-Konsole ausführen, fliegt einem mitunter ein blocked by CSP um die Ohren, weil der Kode im Webseiten-Kontext läuft m(

Der Kode im ZIP ist noch ein bisschen mehr ausgearbeitet mit den drei verschiedenen Formatierungsmöchlichkeiten, die Püthon bietet, mit Zeichenkettenarithmetik und gibt eine hübsche ASCII-Tabelle aus. Bei Fragen, hier im Faden die Fragen fragen :3

N = '''
731...
...450
'''.replace('\n','')

>>50602
Protipp, wenn Ernst die Lösung selbst erarbeiten möchte: Beim „kleinen“ Triplett (3, 4, 5), das als Beispiel gegeben ist, ist 3 + 4 + 5 = 12. Stell dich doof! Wenn du nur die 12 hast, wie würdest du auf die 3, 4 und 5 kommen?

Es ist jedenfalls eine geniale Aufgabe und ohne muh Primzahlen. Kann man so weit optimieren, dass eine Million Lösungen in unter einer Sekunden gefunden werden (sagt timeit). Das geht auch für andere Zahlen als die 1000 (allerdings findet man dann nicht immer eine gültige Lösung). Dabei wird keine höhere Mathematik eingesetzt! Es läuft alles nach dem Schema „Einsetzen, ausmultiplizieren und nach xy umstellen“.

Du kannst einen Trick direkt in deinem Kode ausprobieren. Du iterierst ja über a und b. Das c ergibt sich dann aus den anderen Größen, ist also abhängig von a und b. Wenn du jetzt eine von den ersten beiden Variablen von der jeweils anderen abhängig machst, brauchst du nur über die eine iterieren und kannst dir die andere Schleife sparen. Dafür nimmst du die zwei Gleichungen aus der Aufgabe. Ich nenne Sie mal Ⅰ und Ⅱ:

Ⅰ: a² + b² = c² (Pythagoras)
Ⅱ: a + b + c = u (Umfang)

Du musst also nur z.B. Ⅱ nach c = u - a - b umstellen und in Ⅰ einsetzen, dann ausmultiplizieren und nach b umstellen. Dann solltest du auf b(a) = u ÷ 2 ⋅ (u-2a) ÷ (u-a) kommen (oder auf pythonisch b = u / 2 * (u - 2 * a) / (u - a)). Das packst du in deine innere Schleife, löschst die äußere. Schon bist du schneller.

Okeh, wenn ich dir jetzt meine Lösung zeige, werde ich ein bisschen erklären müssen. Die Anforderungen sind aber dennoch eher mäßig. Wie gesagt: „Einsetzen, ausmultiplizieren, umstellen“. Mehr nicht.

from math import isqrt

def p9(u):
    uh = u >> 1
    p = isqrt(uh); q = 0
    while p > q:
        q = uh / p - p
        if q.is_integer():
            return 2 * p * q * (p*p*p*p - q*q*q*q)
    p -= 1

print(p9(12), p9(1000))#;print(p9(randint(1,8192))

Die ersten beiden Zeilen sind etwas magere Optimierungen, die ich trotzdem mal gezeigt haben möchte:

- 1) Mit u >> 1 teile ich durch zwei, was zumindest früher(tm) schneller war als einfach zu teilen.
- 2) Bei Compilern kann man angeblich auch nicht mehr optimieren, indem man Zwischenergebnisse speichert, wie hier mit uh geschehen. Bei Python scheint sich das zu lohnen, allerdings nicht so sehr.
- 3) Wie mir scheint, ist isqrt nix anderes als int(sqrt(x)), zumindest wenn ich auf die Ausführungszeiten gucke.
- 4) Der Wert von q ist hier noch egal. Die Variable muss nur für das while darunter schon definiert sein.


Jetzt brauchen wir die Formeln von Euklid, mit denen man aus zwei ganzen Zahlen p und q pythagoräische Zahlentripletten erzeugt.

a = p² - q²
b = 2pq
c = p² + q²

Mit der richtigen Kombination aus p und q erzeugen wir ein Triplett, das genau den Umfang von u = 1000 hat (Gleichung Ⅱ).

Wie bei deinem Kode haben wir dasselbe Problem: Zwei scheinbar voneinander unabhängige Variablen (p und q) müssen durchprobieren werden. Verändere ich jetzt p oder q? Wie muss ich vorgehen, um möglichst schnell zu kommen? Zum Glück können wir mit den beiden Gleichungen Ⅰ und Ⅱ und den Euklidischen Formeln wieder eine Variable als abhängig von der anderen definieren. Euklidische Formeln in Ⅱ einsetzen, ausmultiplizieren und nach q umgestellen: q(p) = u ÷ 2p - p. Damit haben wir nebenbei q auch abhängig von u gemacht. Alle q, die wir mit dieser Formel finden, sind bereits so gewählt, dass Ⅱ erfüllt ist. Jetzt brauchen wir nur noch ein ganzzahliges q(p) zu finden, für das der Euklid nämlich nur definiert ist.

Wir brauchen also nur noch eine Schleife (für p). Aber auch hier können wir Iterationen sparen. Schau nochmal auf die gefundene Formel für q(p). Bei sehr großen p wird q(p) negativ. Spätestens dann sollte unsere Schleife enden. Um herauszufinden, bei welchen p das q(p) negativ wird, setzen wir einfach q(p) = 0 und stellen diese neue Formel nach p um. Also 0 = u ÷ (2p) - p nach p umstellen. Dann solltest du auf p = √(u/2) kommen.


Wenn wir auf den ersten Euklid (a = p² - q²) schauen, sieht man, dass a negativ wird, wenn q > p ist. Also fangen wir am besten nicht „unten“ (mit p = 2) an, sondern arbeiten uns von „oben“ herab. Deswegen steht p in der ersten Iteration auf der Nullstelle von q(p), die wir uns gerade errechnet haben. Von da aus wird er dann immer weiter dekrementiert.

Wir wissen dann aber auch, dass p > q für unsere ganze Schleife gelten sollte und wir aufhören können, wenn das nicht mehr stimmt. Wenn du dir p und q in der Schleife ausgeben lässt, wirst du sehen, dass sie aufaneinder zu wachsen (weil q über u an p gebunden ist).

Der letzte Trick ist beim Rückgabewert und auch hier muss man wieder einsetzen und ausmultiplizieren (nicht mal umstellen): Euklidische Formeln in a ⋅ b ⋅ c eingesetzt ((p²-q²)² ⋅ (2pq)² ⋅ (p²+q²)²) und gekürzt (2pq(p⁴-q⁴)).

Ⅰ: a² + b² = c² (Pythagoras)
Ⅱ: a + b + c = u (Umfang)

>>50604
Wir haben schon in >>51361 für Problem 7 Primzahlen bis 200'000 gesiebt. Jetzt einfach denselben Generator für 2 Mio. erzeugen und dann print(sum(P)) und fertig!

Das ist also auch noch nicht die Aufgabe, für die wir Bitvektoren brauchen werden. Nur, wann ist es soweit, dass unser Programm nicht mehr in den Speicher passt?

Mit sys.getsizeof können wir schon einzelne Variablen untersuchen. Um das Programm insgesamt einzuschätzen, suchen wir den maximalen Speicherverbrauch. Leider unterscheiden sich die Befehle da nach Betriebssystem:

# Linux
from resource import getrusage, RUSAGE_SELF
# hier Algorithmus einfügen
print(getrusage(RUSAGE_SELF).ru_maxrss)

# Windows
import psutil
# Arbeit, Arbeit...
print(psutil.Process().memory_info().peak_wset)

Gegebenfalls muss man erstmal pip install psutil bemühen. Dann hat man aber auch ein Modul, dessen Funktionsumfang weit über das hinausgeht, was wir hier brauchen.

Wenn man schon dabei ist, kann man sich auch den memory_profile dazu installieren. Dann schreibst du from memory_profiler import profile zu deinen Importen, packst deinen Algorithmus in eine Funktion und schreibst @profile in die Zeile über das def. Nach dem Ausführen bekommst du dann eine zeilenweise Übersicht über den Speicherbedarf.

Line #    Mem usage    Increment   Line Contents
================================================
     2     13.8 MiB     13.8 MiB   @profile
     3                             def SumOfPrimes(MaxNum):
     4     13.8 MiB      0.0 MiB       Sieb = []
     5                             
     6     91.3 MiB      0.0 MiB       for i in range(0, MaxNum+1):
     7     91.3 MiB     77.5 MiB           Sieb.append(i)
     8                             
     9     91.3 MiB      0.0 MiB       Removers = [0, 1]
    10    580.6 MiB      0.0 MiB       for Prime in Sieb:
    11    580.6 MiB      0.0 MiB           if Prime!=0 and Prime!=1:
    12    580.6 MiB      0.0 MiB               Maex = int(MaxNum/Prime)
    13    580.6 MiB    394.6 MiB               for i in range(Prime, Maex+1):
    14    580.6 MiB     94.6 MiB                   Removers.append(i*Prime)
    15                                             
    16    291.6 MiB   -289.0 MiB       Removers = list(set(Removers))
    17    305.5 MiB -7707477.4 MiB       for i in sorted(Removers, reverse=True):
    18    305.5 MiB -7707491.3 MiB           del Sieb[i]
    19    292.1 MiB    -13.4 MiB       return sum(Sieb)

Die Ausführung wird dadurch natürlich verlangsamt, also musst du die Laufzeit separat testen.

Dein Programm ist hierfür ein sehr dankbares Beispiel, weil du Listen dynamisch anfragst und andernorts Einträge wieder löschst. Damit wächst und schrumpft der Speicher, den dein Programm braucht, immer wieder.

Beim del gibt es allerdings ein Problem, denn die angezeigte Speicherfreigabe (rund 7,7 TiB) in Zeile 17 und 18 ist Unsinn. Dein Programm war während der Ausführung tatsächlich nie größer als die angegeben 580 MiB.

Leistungsmessung ist anscheinend nicht immer einfach. Die 13,8 MiB vom Anfang sind übrigens der Grundbedarf, den Python und die Module haben. Ich habe dasselbe mal mit print('Krtek') versucht und es waren auch 13,8 MiB.

Mit dem Paket memory_profiler kommt außerdem ein Programm namens mprof (oder python3-mprof, je nachdem, wer das paketiert hat). Damit sagt man dann

mprof run SumOfPrimes.py
mprof plot
# `pip install matplotlib`, falls plot "No module named 'pylab'" sagt

Dann bekombt man seinen Speicherbedarf grafisch aufbereitet (so wie bsp.png).

Kühlerweise hat man dann Speicher und Ausführungszeit gegenübergestellt. Auch wenn die Programme insgesamt langsamer laufen, sieht das nach einem guten Anhaltspunkt aus, um die Komplexität seines Algorithmus überwachen.

Das nützt uns freilich nicht viel, wenn wir tatsächlich zu C oder einer anderen Sprache wechseln sollten. Zumindest unter Linux kann man versuchen, in der Sprache auf die getrusage-API zuzugreifen oder man nutzt einfach GNU time (ggf. installieren).

\time -f '%M' python SumOfPrimes.py

Das \ vor dem time ist wichtig, weil du sonst die eingebaute Funktion deiner Muschel aufrufst und die ist bei weitem nicht so mächtig. Interessant ist auch, \time -v, das dir allerhand weitere Informationen gibt.

Unter Windows bekommt man die Information vermutlich mit resmon.exe oder perfmon.exe, aber damit habe ich mich noch nicht anfreunden können. Ich fand immer den Prozesserforscher (procexp.exe) von Sysinternals kühler. Bei dem klickt man auf einen Prozess doppelt, wählt den Reiter "Performance", bei "Physical Memory" schaut man nach "Peak Working Set".

Wieder etwas dazugelernt. Dann kann Problem 41 bald kommen :^)

# Linux
from resource import getrusage, RUSAGE_SELF
# hier Algorithmus einfügen
print(getrusage(RUSAGE_SELF).ru_maxrss)

>>50863

>weil man viele Zigaretten rauchen muss, bis es durchgelaufen ist

Mit anderen Worten: Je schlechter der Kot, desto häufiger sind die Raucherpausen. Wozu will man da noch guten Kode schreiben ;)

>>50660
Dieses Problem bringt einfach keinen Gewinn. Die größte Einsparung, die du in deinem Programm machen kannst, ist es, die Berechnungen zu halbieren, indem du nicht nach links und rechts usw. prüfst, sondern nur nach rechts, weil du ohnehin über die gesamte Matrix läufst und Multiplikation assoziativ ist. Das wurde ja von >>50666 schon angesprochen und mehr scheint dieses Problem nicht zu bieten.

from time import time

t0 = time()
D20 = """
08 02..
...
..67 48
"""

def p11(M, n):
    'Suche in Datenmatrix M nach dem größten Produkt aus n Faktoren'

    M = M.strip().split('\n')
    d = len(M) # Dimension der Matrix, Annahme: quadratische Matrix 
    e = 0 # Endergebnis

    # (1): Eingabe nach Ganzzahlmatrix umwandeln
    for i in range(d):
        M[i] = M[i].split(' ')
        for j in range(d):
            M[i][j] = int(M[i][j])

    # (2): solange wir den Rand nicht berühren in alle Richtungen suchen
    for i in range(d - n + 1):
        for j in range(d - n + 1):
            w0 = M[i][j]
            # Jedes Tupel steht für eine Suchrichtung, wobei wir uns die Suche
            # nach links, oben usw. sparen, um Doppelberechnungen zu meiden.
            for di, dj in [(0, 1), (1, 0), (1, 1)]:
                w = w0
                for k in range(1, n):
                    w *= M[i + k*di][j + k*dj]
                if w > e:
                    e = w
            # Speziell für die zweite Diagonale muss die Startposition 
            # um (n - 1) nach unten verlegt werden
            w = 1
            for k in range(n):
                w *= M[i + n - 1 - k][j + k]
            if w > e:
                e = w
        # in den letzten n - 1 Spalten nur noch senkrecht prüfen
        for j in range(n - 1):
            w = 1
            for k in range(n):
                w *= M[i + k][j + d - n + 1]
            if w > e:
                e = w
    # in den letzten n - 1 Zeilen nur noch waagerecht prüfen
    for i in range(n - 1):
        for j in range(d - n + 1):
            w = 1
            for k in range(n):
                w *= M[i + d - n + 1][j + k]
            if w > e:
                e = w

    return e

print(p11(D20, 4), time() - t0)

Im Kode wurden Schleifen abgerollt und Dereferenzierungen sollten gespart werden. Aber das ist Kleinkram.

>>50863

>Ich versuche mal, meine Idee zu Problem 11 auszuformulieren.

Das war auch meine Überlegung, die Daten erst in eine für die Berechnung günstige Form zu bringen, so dass beim Berechnen höchstens ein Zähler hochgezählt werden muss und die Index-Berechnungen alle entfallen. Für die 3x3-Matrix wäre das:

gerade		transponiert	diagonal	gegendiagonal
08 02 22	08 49 81	       22	   08
49 49 99	02 49 49	     02 99	  02 49
81 49 31	22 99 31	    08 49 31	22 49 81
				      49 49	  99 49
			               81	   31

Dann läuft man da nur noch zeilenweise drüber (für Zeilen, die lang genug sind). Habe ich sein lassen, weil es letztlich die Index-Berechnungen nur verschiebt.

from time import time

t0 = time()
D20 = """

>>52040
Gespräch war okay, denke ich. Arbeitsaufgabe war "Hier ist ein Quelltext, was macht der, was ist der Fehler, und wie korrigiert man den Fehler?" und "Sie wollen zwischen zwei Dateiformaten, die spezifisch für diese Stelle sind, umwandeln, wie machen sie das?"

Konnte beides nicht wirklich lösen. Ich kannte die Formate nicht, also war die Frage hinfällig, und den Quelltext konnte ich zwar entschlüsseln, habe aber keinen Fehler gesehen. Dann das Gespräch selbst: Habe erstmal meine "Lösungen" vorgestellt. Das Formatumwandeln war einfacher als gedacht, als ich ein wenig Hilfe von den Interviewern bekommen habe (das sind effektiv beides json-Dateien, lassen sich also einfach ineinander umwandeln), habe die Aufgabe also so lösen können, denke ich. Den Quelltext habe ich korrekt identifiziert (obwohl ich die Sprache nicht gut konnte), und den Fehler dann auch gesehen, als ich darauf hingewiesen wurde - Lösung natürlich auch direkt parat, war eigentlich sehr simpel.

Dann das Gespräch selbst: Einige fachliche Fragen, die aber im großen und ganzen auch beantwortbar waren. Nur bei einer Frage wusste habe ich garnichts gewusst, weil ich nicht wusste, wie das genau funktioniert. Habe gesagt, dass ich nicht gerne vor Leuten spreche, wenn ich nicht gut vorbereitet bin, aber wenn ich weiß, was auf mich zu kommt, ist es kein Problem etwas gelogen, aber gut :3. Am Ende wurde ich dann noch gefragt, was ich in der Abteilung gerne machen würde, habe im Prinzip gesagt, dass mich alle angebotenen Bereiche interessieren würden.

Sie melden sich diese Woche, ob ich in Erwägung gezogen werde, wollte dann erst den Pfosten machen, aber Ernst ist einfach zu neugierig :3