Restklassen/Kongruenzen ausdünnen

L I V E Stammtisch ab 20:30 Uhr im Chat
  • Hallo zusammen,

    ich muss für eine Statistik folgendes machen:

    Ich habe ein Skript, dass liefert mir eine Liste von Restklassen. Beispielsweise [[1,4], [2,4], [1,3]]

    Das bedeutet, dass alle Elemente k abgedeckt sind, für die gilt: k lässt bei Division durch 4 den Rest 1 oder 2. Oder k lässt bei Division durch 3 den Rest 1.

    Nun möchte ich gerne ein Skript schreiben dass mir sagt, wieviele Restklassen noch übrig sind.

    Mathematisch geht das folgendermaßen:
    Bilde das kleinste gemeinsame Vielfache der Module (hier 3 und 4) und streiche alle abgedeckten Elemente.

    Im obigen Beispiel also kgv = 12, und streiche nun

    1,5,9

    2,6,10

    1 (bereits weg), 4,7, 10 (bereits weg)

    Nun möchte ich in erster Linie wissen, wieviele Elemente übrig bleiben.

    In meiner Statistik kommen teilweise kgv > eine Milliarde vor.

    Trotzdem hatte ich gehofft, zumindest die gefragte Anzahl relativ schnell herauszubekommen.

    Leider habe ich nun gar keine Ahnung, wie ich das mal angehen sollte.

    Meine Idee war, über die Liste zu iterieren und in jedem Schritt das kgv zu bilden. Dann die Elemente streichen. Wenn dann im nächsten Schritt das kgv größer wird, würde ich die Liste mit dem >>Streichmuster<< einfach entsprechend oft hintereinanderhängen und dann bei den nicht-gestrichenen Elementen schauen, ob sie gestrichen werden müssen.

    Ich bin nun absoluter Neuling und wollte euch daher um Hilfe bitten, in welche Richtung das geht. Auch wenn es fortgeschrittene Methoden wären (Bitvektor? Ich weiß nur dass es sowas gibt :D ), wäre ich sehr froh über Hilfestellung.

    Vielen Dank an dieser Stelle für's Lesen :)

  • Hallo,

    für das kgV könntest du math.lcm nutzen.

    Die weiteren Schritte mit dem wegstreichen habe ich ehrlich gesagt nicht verstanden.

    Grüße

    Dennis

    Edit: Ich glaube mein Beispiel ging an der Fragestellung vorbei :conf: Ich lasse es trotzdem mal so stehen.

    🎧 Strahlend soll die Zukunft sein, gut wir werden seh'n, ob wir wie ein Strahlemann lächelnd untergeh'n.  🎧

  • Wenn ich das Element 1 entferne, prüft er danach direkt das Element 3.

    Liegt das am remove?

    Was mache ich falsch?

    Edit:

    Habe es nun so gemacht und das funktioniert. Aber wenn es bei schon klappt bin ich sicher, es geht viel schneller :D

    Edited 2 times, last by neuernutzer (February 24, 2023 at 7:53 PM).

  • Wenn du nur zaehlen willst kannst du mal das probieren:

    Wahrscheinlich kannst du die Geschwindigkeit noch optimieren wenn du das el in zwei einzelne Variablen zerlegst.

    Vermutlich ist auch die Initialisierung von Numbers ineffizient. Probier mal ein groessere Liste als [1] fuer den Anfang.

    Und checke mal wie schnell der Algorithmus mit numpy laeuft.

  • Damit man erst ein bisschen besser erkennt, was da eigentlich passiert, könnte man den ursprünglichen Code etwas kürzen:

    Unabhängig von der Geschwindigkeit solltest du dir aber gleich sprechende Namen angewöhnen und Funktionen schreiben, die immer nur eine Sache macht.

    Zur Geschwindigkeitsoptimierung kann ich nichts beitragen, aber da hast du ja schon Tipps von Tell bekommen :thumbup:


    Grüße

    Dennis

    🎧 Strahlend soll die Zukunft sein, gut wir werden seh'n, ob wir wie ein Strahlemann lächelnd untergeh'n.  🎧

  • Die schnellste Variante die ich gefunden habe:

    Interessanterweise war die numpy-Version langsamer als diese?!

    numpy koennte aber totzdem interessant werden wenn kgv noch viel groesser wird. numpy.int8 braucht dann nur ein Byte pro Wert.

  • Hallo,

    ja genau, wobei Element auch recht allgemein ist. Es geht darum, das die die den Code nicht kennen, verstehen was da passiert. Dann solltest auch die in zwei Monaten nicht darüber rätseln was du da eigentlich gemacht hast und wenn ein Programm/Problem komplexer wird, ist es wesentlich einfacher, wenn da Namen stehen, die sagen was sie sind, bzw. was sie machen. Und wenn einem kein Name einfällt, ist das ein Zeichen dafür, dass da irgendwas nicht stimmt.

    Genau genommen berechnet deine Funktion das kleinste gemeinsame Vielfaches, sucht dann nach denn Werten die gelöscht werden können und vergleicht dann noch zwei Datenmengen. Da Funktionen nach ihrer Tätigkeit benannt werden müsste deine Funktion nicht 'ausduennen' heißen, sondern 'berechne_kgv_finde_zu_loeschende_elemente_und_gebe_eine_bereinigte_liste_zurueck'.

    Wenn du zum Beispiel Probleme mit einem dieser Aufgaben hast, die da in der Funktion gemacht werden, dann ist das auch einfacher die zu testen, wenn die extra steht. Dann kann man das drum herum mal "vergessen" und sich auf ein Problem konzentrieren.

    Ich würde das in die RIchtung machen (Mit den Namen/Beschreibungen hoffe ich das ich einigermaßen richtig liege):

    Grüße

    Dennis

    🎧 Strahlend soll die Zukunft sein, gut wir werden seh'n, ob wir wie ein Strahlemann lächelnd untergeh'n.  🎧

  • Bei der Lösung von Tell könnte man noch `el` als Namen überflüssig machen, in dem man die Unterlisten (die eigentlich eher Tupel sein sollten) gleich in der ``for``-Schleife schon auf Namen aufteilt.

    Aus der ``while``-Schleife würde ich eine ``for``-Schleife machen.

    “For every complex problem, there is a solution that is simple, neat, and wrong.” — H. L. Mencken

  • Hallo zusammen!

    Vielen Dank für eure Hinweise. Die habe ich mir zu Herzen genommen und habe nun die Version von Tell umgesetzt (auch weil die Antwort von __blackjack__ erst jetzt gesehen habe :D ).

    Nun ist es mir allerdings auch passiert, dass ich einen "Memory Error" hatte. Ich weiß jetzt die Zahl nicht genau, aber das kgv kann halt prinzipiell astronomisch werden.

    Wie könnte ich das angehen?

    Vielleicht bin ich völlig auf dem falschen Dampfer, aber ich habe immernoch dieses Wörtchen "Bitvektor" im Kopf. Ich weiß, dass wir an der Uni mal damit ein Primzahlsieb programmiert haben.

    Edit: Ich habe mich jetzt mal mit Bitvektoren beschäftigt und das Sieb des Eratosthenes erfolgreich programmiert.

    Edited once, last by neuernutzer (February 27, 2023 at 1:03 AM).

  • Da bin ich wieder :)

    Ich habe die Methode mit dem Bitvektor einfach mal auf den Code übertragen:

    Siehe da, bei einer Liste die mit der alten Methode 29 Sekunden dauerte, braucht es jetzt nur noch 10 :-O

  • Der `BitVector` hat eine Methode zum zählen von Bits, diese Schleife braucht man also nicht selbst schreiben (ungetestet):

    Python
    def ausduennen_mit_bitvector(liste):
        kgv = functools.reduce(math.lcm, (step for _, step in liste), 1)
        vektor = BitVector.BitVector(size=kgv)
        for index, step in liste:
            for index in range(index, len(vektor), step):
                vektor[index] = 1
    
        return len(vektor) - vektor.bit_count()

    “For every complex problem, there is a solution that is simple, neat, and wrong.” — H. L. Mencken

  • Der `BitVector` hat eine Methode zum zählen von Bits, diese Schleife braucht man also nicht selbst schreiben (ungetestet):

    Python
    def ausduennen_mit_bitvector(liste):
        kgv = functools.reduce(math.lcm, (step for _, step in liste), 1)
        vektor = BitVector.BitVector(size=kgv)
        for index, step in liste:
            for index in range(index, len(vektor), step):
                vektor[index] = 1
    
        return len(vektor) - vektor.bit_count()

    Ich erhalte

    Quote

    AttributeError: 'BitVector' object has no attribute 'bit_count'

  • Nach was bemessen dich denn die beiden Teiler und die relvanten Reste? Können die jeden beliebigen Wert annehmen oder gibt es da Einschränkungen/Regeln?

    Ich würde einen Zählansatz versuchen, in dem die beiden vielfachen der Teiler zzgl. der Reste parallel hochgezählt werden, beginnend bei einem der rausfallenden Werte. Bei jedem Wert wird ein Element gezählt, das rausfällt. Treffen sich die beiden Vielfachen, wird nicht zweimal gezählt, sondern nur einmal. Bei k mod 4 = 1 und k mod 4 = 2 wäre das die Zählweise +1, +3 beginnend bei 1 (also 1-2-5-6-9-10-...) für k mod 3 = 1 wäre es +3 beginnend bei 1 (also 1-4-7-10-...). Wenn ein Wert größer ist als der andere, wird der jeweils andere hochgezählt.

    1 1 -> 1 fällt raus

    2 1 -> 2 fällt raus

    2 4 -> 4 fällt raus

    5 4 -> 5 fällt raus

    5 7 -> 7 fällt raus

    6 7 -> 6 fällt raus

    9 7 -> 9 fällt raus

    9 10 -> 10 fällt raus

    10 10 -> 10=10, hatten wir schon, wird nicht berücksichtigt

    10 13 -> ist über 12, wird nicht berücksichtigt
    13 13 -> dito

    8 Stück fallen raus, 4 von 12 bleiben übrig.

    Wenn ein Teiler deutlich kleiner als der andere ist, kann man vielleicht noch abkürzen, indem man die Anzahl der entfallenden Zahlen bis zum Erreichen des nächsten Gleichstandes berechnet und somit das langwierige Hochzählen umgehen. Das dürfte die Sache bei großen Zahlen deutlich beschleunigen. Bei den Zahlendimensionen, die du angibst, vermute ich aber, dass man trotzdem bei mehreren 100000 Zählschritten noch in erhebliche Rechenzeiten kommt.

    Bei der Zählerei ergibt sich frühr oder später wahrscheinlich ein gewisses Muster. Womöglich kann man einen Zählalgorithmus auf diese Muster hin optimieren.

    Was du hier berechnest ist ja im Grunde eine Art Interferenz. Du hast zwei Zahlenmuster, die in festen Abständen also mit konstanten Frequenzen auftreten. Kann einem da sowas wie Fourier Transformation oder was Ähnliches weiter helfen? Da kann dir ein Mathematiker sicher mehr sagen.

    Bei großen Zahlen kann man vielleicht auch statistisch an die Sache rangehen. Das hat aber sicher ne Menge Tücken.

    Oh, man kann hier unliebsame Nutzer blockieren. Wie praktisch!

  • Hallo Gnom,

    dazu

    ... Da kann dir ein Mathematiker sicher mehr sagen.

    ...

    fällt mir sogar eine Geschichte ein.

    Es gab mal in der Zeit, in der aktiver als heute zum Thema Fullerene geforscht wurde ein Wissenschaftler, der sich über die Strukturen (Anordnung der C-Atome im Raum) Gedanken gemacht hatte. Und er wolle verstehen, wie man sich diese Strukturen (ein sog. Polyeder) besser vorstellen könnte.

    Er ersann auf Basis seiner neuen Messwerte die Idee, dass die neue Struktur aus 12 5-Ecken und 20-Sechsecken bestehen könnte. Er fragte dann in seinem Wissenschaftsnetzwerk, ob jemand jemals zuvor mit einer solchen Struktur zu tun gehabt haben könnte. Das war wohl nicht so. Es handelte sich ja auch um ein sehr neues Forschungsgebiet.

    Ein Kind erfuhr von diesem wissenschaftlichen Austausch. Das Kind ließ sich erklären, worin der Unterschied von einem 5-Eck zu einem 6-Eck besteht. Beim Kicken auf der Straße wurde das Kind stutzig. Der Ball hatte sechseckige und auch fünfeckige Lederstücke. Das Kind zählte 12 Fünfecke und 20 Sechsecke. Sollte die neue Struktur des Fullerens so aussehen wie ein ordinärer Fußball?

    Nach einer weiteren Zeit des Forschens hat sich das das dann tatsächlich so bestätigt.


    Die andere Version der Geschichte geht so, dass ein Mathematiker diverse Anordnungen berechnet hatte. Der "Fußball" war auch darunter. Ein Kontakt zwischen dem Fulleren-Forscher und ihm wurde hergestellt. Der Fulleren-.Forscher hatte die Antwort auf seine Frage. Der Mathematiker hat dadurch gelernt, dass er die Struktur eines Fußballs aufgebaut hatte.

    Da der Fußball aus 32 Flächen besteht spricht man in dem Zusammenhang auch von einem Triantadoeder (32-Flächner). Bekannter sind da Tetraeder, Oktaeder, Ikosaeder...


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

    Edited once, last by Andreas (February 28, 2023 at 2:19 PM).

Participate now!

Don’t have an account yet? Register yourself now and be a part of our community!