Nicht nachvollziehbares Verhalten von itertools.combinations

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Freitag 22. Juni 2012, 14:17

Die Fehlermeldung passt nicht zum Code!

Code: Alles auswählen

Traceback (most recent call last):
  File "./combi2.py", line 38, in <module>
    print(find_combination())
  File "./combi2.py", line 34, in find_combination
    result = map(check_combinations, give_combinations(), CHUNKSIZE)
TypeError: argument 3 to map() must support iteration
Der dritte Parameter ist doch hier sinnlos (und falsch!)

Lässt man den weg, so fehlt der Parameter `sums`. Du kannst das via `functools.partial` regeln:

Code: Alles auswählen

def check_combinations(combination, sums=None):
    ...

result = map(partial(check_combinations, sums=sums), give_combinations())
Und schreibe doch endlich mal den Code auf *eine* Python-Version um. Das kann man ja alles kaum noch lesen ;-)

Edit: Ok, die Fehlermeldungen zu Deinem Code unterscheiden sich zwischen Python2 und 3. Du verwendest also Python3, ich habe es mit Python2 getestet! Dann schreibe den Code doch auch entsprechend, damit das hier nicht zu einer Ratestunde wird :-D
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
EyDu
User
Beiträge: 4872
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Freitag 22. Juni 2012, 14:28

Hyperion hat geschrieben:Du verwendest also Python3, ich habe es mit Python2 getestet! Dann schreibe den Code doch auch entsprechend, damit das hier nicht zu einer Ratestunde wird :-D
Ich möchte ja nichts sagen, aber die erst Antwort in diesem Thread lautet:
Hyperion hat geschrieben:Das hat nichts mit Python3 zu tun, sondern liegt am Verhalten von Generatoren!
:twisted:
Das Leben ist wie ein Tennisball.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Freitag 22. Juni 2012, 14:48

@EyDu: Das war gestern und ich hatte es nicht mehr im Kopf. Durch diesen Schrunz:

Code: Alles auswählen

try:
    from functools import reduce
except ImportError:
    pass
try:
    from itertools import imap
except ImportError:
    imap = map
war ich nun irgend wie auf Python2 fixiert ;-) k.A. wieso.
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
Benutzeravatar
snafu
User
Beiträge: 5961
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Freitag 22. Juni 2012, 15:57

Irgendeine bessere Lösung als das stumpfe Ausprobieren zu finden, brennt mir auch schon die ganze Zeit unter den Nägeln. Da bin ich aber mathemäßig nict begabt genug, als dass ich da nen sinnvollen Ansatz finden würde.

Blöd ist auch, dass die Schleife zweimal in vollem Umfang durchlaufen werden muss. Aber auch das geht nicht anders, da man ja nunmal zuerst die Summen braucht. Mit Vorfilterung im ersten Durchlauf (z.B. hinsichtlich des Rausschmeißens von Kombinationen, deren Produkt weniger als 2 Mio ist) verschlechtert man erheblich die Laufzeit. Hatte da schon ein paar Dinge ausprobiert.
Benutzeravatar
snafu
User
Beiträge: 5961
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Freitag 22. Juni 2012, 16:04

Und hinsichtlich des try-import-except-Import-Error Gefrickels: Ich hatte ihm ja den Vorschlag gemacht, damit möglichst viele Leute im Forum den Code ausprobieren können, ohne Zusatztools benutzen zu müssen. Schön sieht das natürlich nicht gerade aus. In einem "echten" Projekt würde ich für sowas auch eher ein Extra-Modul anlegen, welches versionsübergreifend die passende Funktion zurückgibt. Dann hat man den Kompatibilitätskram schön abstrahiert.
heiliga horsd

Freitag 22. Juni 2012, 16:51

Jetzt bin ich verwirrt - soll ich das try-Zeug bei den Importen behalten oder nicht??

Das CHUNKSIZE hatte ich komplett vergessen, war noch ein Überbleibsel der Pool.map-Variante.

Mit dem partial hat auch alles funktioniert, jedoch ist der Code jetzt noch langsamer als die erste fertige Version bevor es ans "optimieren" ging. Das ganze nun parallel laufen lassen bringt meinen PC erstmal kurz an seine Leistungsgrenzen, lastet CPU und RAM fast komplett für mehrere Sekunden aus und spuckt mir dann nach ~35 Sekunden das Ergebnis aus - Insgesamt also "nur" 4 Sekunden schneller. Da das Ergebnis bereits eher gefunden wird, suche ich nun nach einer Möglichkeit alle Prozesse aus dem Pool abzuballern, sobald das Ergebnis gefunden wurde - würde Zeit & Strom sparen.
Hier der aktuelle Code (parallelisiert):

Code: Alles auswählen

from multiprocessing import Pool
from itertools import combinations
import operator
import collections
from functools import reduce, partial
try:
    from itertools import imap
except ImportError:
    imap = map

DIFFERENT_VALUES = 49
NUMBERS = list(range(1,DIFFERENT_VALUES + 1))
MIN_VALUE = 2*10**6
PROCESSES = 7
CHUNKSIZE = 2*10**6

def product(iterable):
    return reduce(operator.mul, iterable, 1)

def give_combinations():
    return combinations(NUMBERS, 6)

def check_combinations(combination, sums = None):
    sum_of_numbers = sum(combination)
    x = sum_of_numbers * sums[sum_of_numbers]
    if x > MIN_VALUE and product(combination) == x:
        return combination
            
def find_combination():
    pool = Pool(processes=PROCESSES)
    sums = collections.Counter(imap(sum, give_combinations()))
    result = pool.map(partial(check_combinations, sums=sums),give_combinations(),
                      chunksize=CHUNKSIZE)
    return result
        
if __name__ == "__main__":
    for element in set(find_combination()): #Set um die ~14M None's los zu werden
        print(element)
An die Vorschläge von Blackjack hab ich mich noch nicht gesetzt, hatte noch keine Zeit.

@snafu: Ich glaube genau das ist ja das Problem des Rätsels - Man kommt nur "zu Fuß" ans Ziel. Lasse mich aber gerne eines besseren belehren!

Gruß HH
BlackJack

Freitag 22. Juni 2012, 19:43

@heiliga horsd: Das ist IMHO eine unsinnige Vorgehensweise. Bei dem `Pool.map()` wird für iterierbare Objekte die keine abfragbare Länge haben erst einmal eine Liste mit allen Elementen erstellt. Ist zumindest in der Implementierung in Python 2.6 so. An der Stelle hat man im Grunde schon „verloren”. Und dann werden nicht nur ≈14 Millionen Kombinationen an die Prozesse übertragen, sondern auch ≈14 Millionen Ergebnisse, die alle bis auf *einen* Wert `None` sind. Das ist eine unglaubliche Verschwendung. Die ganzen Kombinationen werden auch nur in *einem* Prozess erzeugt, statt dass das auch Parallel passiert.

Wie gesagt: Man braucht einen eigenen Kombinations-Generator der auch mitten drin „aufsetzen” kann, wenn man das vernünftig parallelisieren möchte. Dann kann man auch den ersten Schritt mit dem Histogramm in Teilhistogramme aufteilen die im Hauptprozess zusammengeführt werden.

Parallel 35s? Solange braucht bei mir die ganz normale Version mit den beiden Schleifen über alle Kombination. Und ich dachte ich hätte hier einen lahmen Rechner. :-)

@snafu: Ich habe ja auch immer noch die Hoffnung, dass man intelligenter an die Sache heran gehen kann. Bin aber mathematisch auch zu untalentiert. Zum Beispiel müsste es auch für die Anzahl der Kombinationen die eine gegebene Summe x ausmachen eine zwar rekursive, aber letztendlich schnellere Funktion geben als alle Kombinationen zu generieren um sie zu zählen. Dann braucht man von den möglichen Summen auch nur die Hälfte berechnen, denn wenn man sich das Ergebnis mal anschaut, sieht man eine symmetrische Verteilung.

Ich hatte auch mal versucht beim zweiten Durchlauf die Kombinationen zu ignorieren wo das x schon zu klein ist. Dazu habe ich im Histogramm nicht die Kombinationen zu den Summen gezählt, sondern in Listen gesteckt. ``lotto_02.py``:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import defaultdict
from itertools import combinations
from operator import mul


def product(iterable):
    return reduce(mul, iterable, 1)


def lotto_combinations(n=49, m=6):
    return combinations(xrange(1, n + 1), m)


def main():
    sum2count = defaultdict(list)
    for combination in lotto_combinations():
        sum2count[sum(combination)].append(combination)
    
    for the_sum, combinations in sum2count.iteritems():
        x = the_sum * len(combinations)
        if x >= 2000000:
            for combination in combinations:
                if product(combination) == x:
                    print combination


if __name__ == '__main__':
    main()
Gaanz böse Falle. Es wird nicht einmal zu viel Speicher für diesen Rechner hier verbraucht, aber es dauert *eeewig*:

Code: Alles auswählen

Filename        Impl.   Runtime         Factor
==============  ======  =========  ===========
lotto_02.py     python  6m41.216s        -7.24
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_01.c                 0.267s       127.88
heiliga horsd

Samstag 23. Juni 2012, 10:34

BlackJack hat geschrieben:@heiliga horsd: Das ist IMHO eine unsinnige Vorgehensweise. Bei dem `Pool.map()` wird für iterierbare Objekte die keine abfragbare Länge haben erst einmal eine Liste mit allen Elementen erstellt. Ist zumindest in der Implementierung in Python 2.6 so. An der Stelle hat man im Grunde schon „verloren”. Und dann werden nicht nur ≈14 Millionen Kombinationen an die Prozesse übertragen, sondern auch ≈14 Millionen Ergebnisse, die alle bis auf *einen* Wert `None` sind. Das ist eine unglaubliche Verschwendung. Die ganzen Kombinationen werden auch nur in *einem* Prozess erzeugt, statt dass das auch Parallel passiert.
Naja bin ehrlich gesagt noch nicht dazu gekommen deinem Hinweis nachzugehen. Wobei ich mich frage, ob die None's nicht Referenz auf ein einziges Objekt sind - Man bräuchte ja nicht mehr als ein None-Objekt im Speicher oder? Und Referenzen auf ein Objekt machen das Ding dann ja auch nicht so fett.
BlackJack hat geschrieben: Wie gesagt: Man braucht einen eigenen Kombinations-Generator der auch mitten drin „aufsetzen” kann, wenn man das vernünftig parallelisieren möchte. Dann kann man auch den ersten Schritt mit dem Histogramm in Teilhistogramme aufteilen die im Hauptprozess zusammengeführt werden.
Wenn ich mal Zeit finde arbeite ich mich da auch mal ein - wobei hier eine Frage meinerseits wäre, wie ich so einem Generator mitteile, wann er aufhören muss und gleichzeitig schon Generator 2 mitteilen kann, wo er starten muss, bevor Generator 1 fertig ist.
BlackJack hat geschrieben: Parallel 35s? Solange braucht bei mir die ganz normale Version mit den beiden Schleifen über alle Kombination. Und ich dachte ich hätte hier einen lahmen Rechner. :-)
Ja, das bei einem AMD FX-4100 (Quad Core, 3.6GHZ). Richtig bitter die Laufzeit...
heiliga horsd

Samstag 23. Juni 2012, 11:06

Hab jetzt auch mal diese Lösung:

http://www.python-forum.de/viewtopic.ph ... 29#p223629

in PyPy rein gefüttert, war nach 4 Sekunden durch.
Benutzeravatar
snafu
User
Beiträge: 5961
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Samstag 23. Juni 2012, 11:28

heiliga horsd hat geschrieben:Hab jetzt auch mal diese Lösung:

http://www.python-forum.de/viewtopic.ph ... 29#p223629

in PyPy rein gefüttert, war nach 4 Sekunden durch.
Ich würd's jetzt einfach bei dieser Variante belassen. Ich glaub, die scheint das beste zu sein, das man Performance-mäßig mit Python hinkriegen kann...
BlackJack

Samstag 23. Juni 2012, 11:52

@heiliga horsd: 14M Objektzeiger sind bei einem 32-Bit System auch 53 MiB. Aber ich mache mir da weniger Gedanken um den Speicher als um die Laufzeit diese grossen Listen zu erzeugen und zu serialisieren, zwischen den Prozessen zu übertragen, und wieder zu deserialisieren.

Wo so ein Generator aufhören muss, kann man ja von aussen zum Beispiel mit `itertools.islice()` bestimmen. Die interessante Frage ist eher der Algoritmus die x. lexikografische Kombination direkt aus einem gegebenen x zu erzeugen kann, damit man diesen Startpunkt hat. Das geht auf jeden Fall, ich kann mich da dunkel an eine Vorlesung zu dem Thema erinnern. Muss mal in meinen Unterlagen suchen.

Bei 4 Sekunden mit PyPy lohnt sich der Aufwand das zu parallelisieren ja eigentlich kaum noch. :-)

Ich habe hier einen Athlon64 X2 (Dual Core, 2,7 Ghz) allerdings mit 32-Bit-Betriebssystem. Da dauert ein sehr ähnliches Programm 11.635s.

Meinen zweiten Ansatz — sich die Kombinationen im ersten Durchlauf zu den entsprechenden Summen zu merken um nur noch die im zweiten Durchlauf zu testen wo Summe mal Anzahl gross genug ist — habe ich auch mal in C probiert. Das hat zwar nicht so eine katastrophale Laufzeit wie der Python-Versuch, ist aber trotzdem ≈5× langsamer als der „brute force” Ansatz bei dem einfach zweimal alle Kombinationen generiert werden. Ich dachte ja es lag bei Python an den dynamisch wachsenden Listen und dass ich das Problem in C umgehen kann, in dem ich einmal ein entsprechend grosses Array mit allen Kombinationen + Listenzeiger erzeuge und im Histogram einen Zeiger auf eine Kombination zu jeder Summe speichere und die Kombinationen dann über ihre Zeiger eine verkettete Liste bilden. Das ist Konstanter Aufwand pro Kombination. Das bisschen verketten ist aber anscheinend deutlich teurer als einfach die Kombinationen noch einmal zu generieren.

lotto_02.c:

Code: Alles auswählen

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

#define N       49
#define K       6
#define MAX_SUM (279 + 1)       /* = N + N-1 + N-2 + N-3 + N-4 + N-5 + 1*/

typedef struct Combination {
    uint8_t numbers[K];
    struct Combination *next;
} Combination;

typedef struct {
    uint32_t length;
    Combination *items;
} Combinations;

typedef struct {
    uint32_t count;
    Combination *head;
} HistogramEntry;

HistogramEntry histogram[MAX_SUM];
Combinations combinations;

uint32_t number_of_combinations(uint8_t n, uint8_t k)
{
    uint32_t result = 1;
    uint8_t i, max;
    
    max = (k < n - k) ? k : n - k;
    for (i = 0; i < max; ++i) {
        result = (result * (n - i)) / (i + 1);
    }
    
    return result;
}

void Combination_init(Combination *combination)
{
    uint8_t i;
    for (i = 0; i < K; ++i) {
        combination->numbers[i] = i + 1;
    }
    combination->next = NULL;
}

_Bool Combination_next(Combination *combination)
{
    int8_t i;
    uint8_t n;
    
    for (i = K - 1, n = N - 1; i >= 0 && combination->numbers[i] > n; --i, --n);
    if (i < 0) return false;
    ++combination->numbers[i];
    for (i = ++i; i < K; ++i) {
        combination->numbers[i] = combination->numbers[i - 1] + 1;
    }
    return true;
}

uint16_t Combination_sum(Combination *combination)
{
    uint8_t i;
    uint16_t result = 0;
    
    for (i = 0; i < K; ++i) {
        result += combination->numbers[i];
    }
    
    return result;
}

uint32_t Combination_product(Combination *combination)
{
    uint8_t i;
    uint32_t result = 1;
    
    for (i = 0; i < K; ++i) {
        result *= combination->numbers[i];
    }
    
    return result;
}

void Combination_print(Combination *combination)
{
    uint8_t i;
    
    for (i = 0; i < K; ++i) {
        printf("%2d ", combination->numbers[i]);
    }
    putchar('\n');
}

void Combinations_init(void)
{
    uint32_t i;
    Combination combination;
    
    combinations.length = number_of_combinations(N, K);
    combinations.items = malloc(
        combinations.length * sizeof(*combinations.items)
    );
    i = 0;
    Combination_init(&combination);
    do {
        memcpy(&combinations.items[i++], &combination, sizeof(combination));
    } while(Combination_next(&combination));
    assert(i == combinations.length);
}

void Combinations_destroy(void)
{
    combinations.length = 0;
    free(combinations.items);
}

void calculate_histogram()
{
    Combination *combination;
    HistogramEntry *entry;
    uint32_t i;
    
    memset(histogram, 0, sizeof(histogram));
    
    for (
        i = 0, combination = combinations.items;
        i < combinations.length;
        ++i, ++combination
    ) {
        entry = &histogram[Combination_sum(combination)];
        ++entry->count;
        combination->next = entry->head;
        entry->head = combination;
    }
}

void search_combination(void)
{
    Combination *combination;
    uint16_t i;
    uint32_t x;
    
    for (i = 0; i < MAX_SUM; ++i) {
        x = i * histogram[i].count;
        if (x > 2000000) {
            combination = histogram[i].head;
            while (combination) {
                if (x == Combination_product(combination)) {
                    Combination_print(combination);
                }
                combination = combination->next;
            }
        }
    }
}

int main(void)
{
    Combinations_init();
    calculate_histogram();
    search_combination();
    Combinations_destroy();
    return 0;
}
Damit sieht der Stand meiner Versuche so aus:

Code: Alles auswählen

Filename        Impl.   Runtime         Factor
==============  ======  =========  ===========
lotto_02.py     python  6m41.216s        -7.24
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_02.c                 1.316s        25.95  (Neu)
lotto_01.c                 0.267s       127.88
@snafu: Wenn da nicht der Forscherdrang wäre. :-) Bei meiner lahmen Kiste sind es immerhin noch ≈11s. Und auf dem C64 dauert das erste Aufzählen schon mehr als eine Stunde (da habe ich abgebrochen). Wäre schon schön wenn man das besser hinbekommen würde. :-)
heiliga horsd

Samstag 23. Juni 2012, 12:56

http://www.matheforum.net/read?i=899025

http://de.wikipedia.org/wiki/Stirling-Z ... weiter_Art

Hab mich da noch nicht weiter eingelesen, sollte nur mal als Hinweis für alle dienen, dass es da anscheinend tatsächlich einen mathematischen Weg gibt.
Benutzeravatar
snafu
User
Beiträge: 5961
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Samstag 23. Juni 2012, 13:37

Man sollte vielleicht überlegen, welche Teilannahmen man treffen kann. Zum Beispiel weiß ich, dass jede Kombination, die (1, 2, 3, 4, 5) enthält und durch eine beliebige übrige Zahl (also von 6-49) ergänzt wird, als Produkt niemals größer als 2 Mio sein kann. Das Maximal mögliche Ergebnis ist 5880 für 1*2*3*4*5*49, ähnliches gilt für 2*3*4*5*6*49. Ich weiß nicht, inwiefern das erweiterbar ist, ohne "logische Fehler" einzubauen. Falls er klappt, könnte man am Ende eine Formel daraus machen. Ist aber erstmal nur ein Gedanke...
Benutzeravatar
snafu
User
Beiträge: 5961
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Samstag 23. Juni 2012, 16:01

@heiliga horsd: Vielleicht am Rande nochmal zum Generator-Verhalten, sofern dir das bisher nicht ganz klar geworden ist: So ein Generator-Objekt ist ja im Grunde nicht viel mehr als eine Zustandmaschine, die auf Anforderung den jeweils nächsten Zustand berechnet und diesen zurückgibt. Es werden in deinem Anwendungsfall also nicht irgendwo (meinetwegen in einem C-Array) alle Kombinationen gespeichert und nur einzeln ausgespuckt, sondern die nächste Kombination steht wirklich erst dann fest, wenn sie "an der Reihe" ist. Und der Generator merkt sich zuvor zurückgelieferte Kombinationen auch nicht.

Durch dieses Verhalten können Generatoren potenziell Milliarden von Elementen zurückgeben (sogar unendlich viele), ohne dass es irgendwelche negativen Effekte auf den Speicherverbrauch hat. Das Problem fängt erst dann an, wenn man selber die Ausgaben z.B. in einer Liste sammelt. Generatoren sind also grundsätzlich eher dazu gedacht, dass ihre zurückgelieferten Elemente sofort verarbeitet werden und nicht erst in irgendeinem Container abgelegt werden.

Wie du dir jetzt vielleicht schon denken kannst, bringt es durch diesen Umstand nicht sondernlich viel, wenn Generatoren am Ende wieder von selbst auf den Ausgangszustand zurückspringen würden. Das hätte letztlich den selben Effekt wie das Erstellen eines neuen Generators, da jegliche Berechnung wieder von vorn beginnen müsste und sich auch wieder Schritt für Schritt weiter "tasten" müsste. Das ist ja auch der Grund, wieso man nicht nach Belieben an eine spätere Stelle im Generator springen kann, um möglicherweise tausende von vorherigen Elementen zu überspringen. Es geht technisch einfach nicht. Was natürlich ginge, wäre eine Option, die den Generator erst für eine spätere Stelle im Ablauf initialsiert, sodass er von dort an weitermachen kann. Dies bietet `itertools.combinations()` einem aber leider nicht an.
BlackJack

Samstag 23. Juni 2012, 16:59

Ich habe jetzt `combinations_init()` und `combinations_next()` aus meinem C-Programm in einer Generator-Funktion in Python zusammengefasst. Und zusätzlich die Idee aus dem C-Programm übernommen das Histogramm in einer Liste und nicht in einem Wörterbuch zu speichern. Letzteres hat einen geringen Geschwindigkeitsvorteil weil direkt auf die Positionen zugegriffen werden kann, ohne das intern erst ein Hashwert benutzt werden muss.

Ausserdem kann die Generatorfunktion nicht nur mit der kleinsten lexikographischen Kombination beginnen, sondern an jeder beliebigen Position. Das verdanke ich dem Buch „Combinatorial Algorithms: Generation, Enumeration, and Search”, wo ich einen passenden Algorithmus gefunden habe (die `unrank()`-Funktion).

lotto_03.py:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from itertools import combinations
from operator import 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=N, k=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 main():
    histogram = [0] * (MAX_SUM + 1)
    for combination in lotto_combinations():
        histogram[sum(combination)] += 1
    
    for combination in lotto_combinations():
        the_sum = sum(combination)
        x = the_sum * histogram[the_sum]
        if x >= 2000000 and product(combination) == x:
            print combination


if __name__ == '__main__':
    main()
Das ist in CPython ausgeführt jetzt erwartungsgemäss langsamer als mit dem in C implementierten `itertools.combinations()`. Aber nur um den Faktor ≈2 — ich hätte Schlimmeres erwartet. Besonders interessant finde ich aber, dass PyPy das genau so schnell, beziehungsweise sogar ein wenig schneller, ausführt als die erste Variante die noch `itertools.combinations()` verwendet hat! Da haben wir also einen Kombinationsgenerator in reinem Python der nicht langsamer ausgeführt wird als der in C geschriebene aus dem `itertools`-Modul. Cool.

Code: Alles auswählen

Filename        Impl.   Runtime         Factor
==============  ======  =========  ===========
lotto_02.py     python  6m41.216s        -7.24
lotto_03.py     python  1m10.051s        -2.05 (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 (Neu)
lotto_02.c                 1.316s        25.95
lotto_01.c                 0.267s       127.88
Mit dem Quelltext hat man nun die Möglichkeit das Programm effizienter zu parallelisieren.
Antworten