@snafu: Danke für die Generator-Erläuterung, mir hats schon ein bisschen gedämmert, jetzt hab ich das Schwarz auf Weiß
Wie man das mit den Produkten machen kann weiß ich so auch nicht. Frage mich auch gerade, ob es effizienter ist, paar Millionen Größenvergleiche anzustellen um sich das multiplizieren zu sparen oder eben gleich zu multiplizieren
@BlackJack: Ich hab das Gefühl du hast Gefallen an dem Problem gefunden
Da ich v.a. jetzt am WE Klausur- & Wetterbedingt wenig Zeit habe muss ich schauen wann ich zum testen und weiter probieren komme. Das mit dem unrank hört sich aber relativ cool an.
@all: Hat sich jemand das mit den Stirling-Zahlen angeschaut bzw. kennt sich damit aus? Bin da mit meinem 'begrenzten' Oberstufenwissen noch nicht auf dem mathematischen Level um da viel raus holen zu können... :K
Nicht nachvollziehbares Verhalten von itertools.combinations
@BlackJack: Kann ich bestätigen. Der in Python implementierte Kombinationsgenerator ist hier ein paar Zehntel Sekunden schneller als `itertools.combinations()`. Auch die Verwendung der Liste anstelle des Wörterbuchs ist schneller. PyPy ist echt der Hammer.
//edit: Wobei ja auch der verwendete Algorithmus aus deinem Buch recht effizient zu sein scheint, wenn man sich mal den Performance-Schub allein in CPython anguckt.
//edit2: Achso, jetzt schnall ich das. Nur `unrank()` ist aus dem Buch. Den Rest hattest du ja schon vorher. Und `unrank()` kommt erst dann wirklich ins Spiel, wenn ein wahlweiser Zugriff benötigt wird, d.h. Verändern des `start`-Parameters für den Kombinationsgenerator.
//edit: Wobei ja auch der verwendete Algorithmus aus deinem Buch recht effizient zu sein scheint, wenn man sich mal den Performance-Schub allein in CPython anguckt.
//edit2: Achso, jetzt schnall ich das. Nur `unrank()` ist aus dem Buch. Den Rest hattest du ja schon vorher. Und `unrank()` kommt erst dann wirklich ins Spiel, wenn ein wahlweiser Zugriff benötigt wird, d.h. Verändern des `start`-Parameters für den Kombinationsgenerator.
Zuletzt geändert von snafu am Samstag 23. Juni 2012, 18:30, insgesamt 1-mal geändert.
Um ehrlich zu sein, ist mir bisher nicht klar geworden, wie der Stirling-Ansatz da überhaupt sinnvoll zu beitragen kann. Soweit ich weiß, hilft das eher bei Wahrscheinlichkeitsberechnungen. Evtl hat dich der Antwortende auch einfach nicht richtig verstanden...heiliga horsd hat geschrieben:@all: Hat sich jemand das mit den Stirling-Zahlen angeschaut bzw. kennt sich damit aus? Bin da mit meinem 'begrenzten' Oberstufenwissen noch nicht auf dem mathematischen Level um da viel raus holen zu können... :K
@snafu: Bei Lotto geht es doch auch um Wahrscheinlichkeiten.
Bei Wahrscheinlichkeitsrechnung geht es oft um das Zählen von möglichen Ergebnissen mit bestimmten Eigenschaften. Wenn Du beantworten kannst wie gross die Wahrscheinlichkeit ist, dass bei einer Ziehung eine Kombination mit einer festen aber beliebigen Summe x kommt, dann weisst Du auch wie viele Kombinationen es für diese Summe gibt. Und umgekehrt.
Bei Wahrscheinlichkeitsrechnung geht es oft um das Zählen von möglichen Ergebnissen mit bestimmten Eigenschaften. Wenn Du beantworten kannst wie gross die Wahrscheinlichkeit ist, dass bei einer Ziehung eine Kombination mit einer festen aber beliebigen Summe x kommt, dann weisst Du auch wie viele Kombinationen es für diese Summe gibt. Und umgekehrt.
Nun ja, aber die konkrete Zahlenfolge finde ich damit ja trotzdem nicht heraus.BlackJack hat geschrieben:Wenn Du beantworten kannst wie gross die Wahrscheinlichkeit ist, dass bei einer Ziehung eine Kombination mit einer festen aber beliebigen Summe x kommt, dann weisst Du auch wie viele Kombinationen es für diese Summe gibt. Und umgekehrt.
Übrigens hab ich die Idee, möglichst viele Zahlenfolgen vorab überspringen zu können, wieder aufgegriffen. Die Fee sagt ja: "[...] dann erhältst du eine sehr große Zahl von einigen Millionen, und diese Zahl kommt auch raus, wenn man alle sechs Lottozahlen miteinander malnimmt." Das heißt ja mit anderen Worten, alle Kombinationen, deren Produkt nicht mindestens 2 Mio ergibt, kommen gar nicht erst infrage.
So, jetzt verläuft die Erzeugung der Kombinationen ja nach einem bestimmten Muster. Man kann sich quasi einen Tacho denken, bei dem man mit dem Kilometerstand 123456 losfährt, wobei die Tachoeinheiten nicht von 0-9, sondern von 1-49 gehen. Wenn die am weitesten rechts stehende Einheit bei dem Maximalwert 49 angekommen ist, dann erhöht sich die links daneben stehende Einheit um eins. Im Gegensatz zu einer gewöhnlichen Tachoanzeige springt die rechte Einheit jedoch auf den Wert `linker_nachbar + 1`. Soll heißen: (1, 2, 3, 4, 5, 49) -> (1, 2, 3, 4, 6, 7) -> (1, 2, 3, 4, 6, 8) -> usw.
Da es dank `unrank()` nun wesentlich einfacher geworden ist, die Ergebnisse zu untersuchen, hab ich mal versucht, eine bestimmte "Tachozähler-Konstellation" zu bestimmen. Sieht noch etwas komisch aus, weil es keine Formel ist, aber vielleicht ein guter Anfang:
Code: Alles auswählen
>>>> unrank((49-6)+(49-6)+(48-6)+(47-6)+(46-6)+(45-6))
[1, 2, 3, 4, 10, 49]
>>>> unrank((49-6)+(49-6)+(48-6)+(47-6)+(46-6))
[1, 2, 3, 4, 9, 49]
>>>> unrank((49-6)+(49-6)+(48-6)+(47-6))
[1, 2, 3, 4, 8, 49]
Code: Alles auswählen
>>>> 1*2*3*4*5*49
5880
>>>> 1*2*3*4*49*49
57624
>>>> 1*2*3*49*49*49
705894
>>>> 1*2*49*49*49*49
11529602
Wie gesagt, da muss noch ein bißchen Form rein (ich will natürlich keinen endlos langen Term da stehen haben, sondern etwas hübsches mit Variablen) und so ganz zu Ende gedacht ist die Idee auch noch nicht. Aber an sich wage ich mal zu behaupten, dass man damit dem Ziel der reinen Berechnung des Ergebnisses schon ein Stück näher gekommen ist. Zumindest dürfte es schonmal die Zeit zum Durchprobieren merklich vermindern (also natürlich erst dann, wenn die Formel zum Erhalten des ersten Kandidaten komplett definiert ist).
//edit: Ups. Die 49 geht natürlich nur einmal pro Kombination. But you get the idea - perhaps. :D
Vorerst wohl die letzte Variante von mir — jetzt parallelisiert.
lotto_04.py:
Ist damit die schnellste Python-Version von mir, wenn man es mit PyPy ausführt. Noch einmal ≈19% schneller als die bisher schnellste sequentielle Variante mit PyPy.
lotto_04.py:
Code: Alles auswählen
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from functools import partial
from itertools import combinations, islice
from multiprocessing import cpu_count, Pool
from operator import add, mul
N, K = 49, 6
MAX_SUM = sum(N - i for i in xrange(K))
def product(iterable):
return reduce(mul, iterable, 1)
def number_of_combinations(n, k):
if k > n or n < 0 or k < 0:
return 0
result = 1
for i in xrange(min(k, n - k)):
result = (result * (n - i)) / (i + 1)
return result
def unrank(r, n, k):
result = list()
x = 1
for i in xrange(1, k + 1):
y = number_of_combinations(n - x, k - i)
while y <= r:
r -= y
x += 1
y = number_of_combinations(n - x, k - i)
result.append(x)
x += 1
return result
def lotto_combinations(start=0, n=N, k=K):
combination = unrank(start, n, k)
while True:
yield combination
i = k - 1
j = n - 1
while i >= 0 and combination[i] > j:
i -= 1
j -= 1
if i < 0:
break
combination[i] += 1
for i in xrange(i + 1, k):
combination[i] = combination[i - 1] + 1
def count_sums(length, start):
histogram = [0] * (MAX_SUM + 1)
for combination in islice(lotto_combinations(start), length):
histogram[sum(combination)] += 1
return histogram
def search_combination(sum_histogram, length, start):
result = list()
for combination in islice(lotto_combinations(start), length):
the_sum = sum(combination)
x = the_sum * sum_histogram[the_sum]
if x >= 2000000 and product(combination) == x:
result.append(tuple(combination))
return result
def main():
combinatio_count = number_of_combinations(N, K)
chunksize = (combinatio_count // cpu_count()) + 1
offsets = range(0, combinatio_count, chunksize)
pool = Pool()
sum_histogram = [0] * (MAX_SUM + 1)
for histogram in pool.map(partial(count_sums, chunksize), offsets, 1):
sum_histogram = map(add, sum_histogram, histogram)
for combinations in pool.map(
partial(search_combination, sum_histogram, chunksize), offsets, 1
):
for combination in combinations:
print combination
if __name__ == '__main__':
main()
Code: Alles auswählen
Filename Impl. Runtime Factor
============== ====== ========= ===========
lotto_02.py python 6m41.216s -7.24
lotto_03.py python 1m10.051s -2.05
lotto_04.py python 39.093s -1.14 (Neu)
lotto_01.py python 34.144s 1.00
lotto_02.py pypy 21.054s 1.62
lotto_01.py pypy 11.635s 2.93
lotto_03.py pypy 10.099s 3.38
lotto_04.py pypy 8.219s 4.15 (Neu)
lotto_02.c 1.316s 25.95
lotto_01.c 0.267s 127.88
Hallo,
entschuldigung für die späte Antwort, habe grade wenig Zeit...
Hab die Lösung mal durch PyPy gejagt, ist jetzt nach 2 Sekunden durch.... aber ich schätze mal wirklich noch schneller schafft mans mit Python wohl wirklich nicht.
Gruß heiliga horsd
entschuldigung für die späte Antwort, habe grade wenig Zeit...
Hab die Lösung mal durch PyPy gejagt, ist jetzt nach 2 Sekunden durch.... aber ich schätze mal wirklich noch schneller schafft mans mit Python wohl wirklich nicht.
Gruß heiliga horsd
So, hab mir jetzt den Code nochmal angeschaut und mir die Messergebnisse mal durch den Kopf gehen lassen. Ich frage mich gerade, warum Lotto04.py (Parallelisiert) mit CPython langsamer ist als Lotto01.py (Sequentiell), mit PyPy der Sachverhalt jedoch genau anders herum ist?
@heiliga horsd: Weil in der 4er Variante der Kombinationsgenerator in Python geschieben ist und das ist selbst parallelisiert langsamer als `itertools.combinations()` was in CPython in C implementiert ist. Bei PyPy macht es keinen Unterschied ob man `itertools.combinations()` oder die in Python geschriebene Generatorfunktion verwendet. Das war bei mir die 3er Variante. Da ist PyPy bei der 1er und der 3er ungefähr gleich schnell, aber CPython bei der 3er *deutlich* langsamer.
Noch mal zwei Datenpunkte für einen Raspberry Pi (mit Raspbian als Betriebssystem): ``lotto_01.py`` hat 11 Minuten und 16 Sekunden gebraucht und ``lotto_01.c`` war in knapp unter 2s fertig.