Das deutsche Python-Forum

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

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

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

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

def check_combinations(combinations_to_check):
    for combination in combinations_to_check():
        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(check_combinations, give_combinations(), CHUNKSIZE)
    return result
        
if __name__ == "__main__":
   print(find_combination())

Leider kann ich mit der Fehlermeldung nicht viel anfangen, da ich keine Ahnung habe, welches Tupel da gemeint ist.

Code: Alles auswählen

Traceback (most recent call last):
  File "C:\Users\XX\Desktop\Lotto.py", line 41, in <module>
    print(find_combination())
  File "C:\Users\XX\Desktop\Lotto.py", line 37, in find_combination
    result = pool.map(check_combinations, give_combinations(), CHUNKSIZE)
  File "C:\Python32\lib\multiprocessing\pool.py", line 251, in map
    return self.map_async(func, iterable, chunksize).get()
  File "C:\Python32\lib\multiprocessing\pool.py", line 556, in get
    raise self._value
TypeError: 'tuple' object is not callable

Ansonsten hoffe ich, dass mein Ansatz nicht allzu verkehrt ist.

Gruß HH

@heiliga horsd: `map()` wendet die Funktion in Argument 1 auf die *Elemente* von Argument 2 an, also auf jedes einzelne Tupel das ``give_combinations()`` liefert. Und das erste was Dein `check_combinations()` macht ist das Argument aufrufen. Das geht bei Tupeln nicht.

Ich habe mal bei folgender Python-Implementierung (für 2.6 — darum kein `collections.Counter`) mit CPython und PyPy die Zeit gemessen:

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(int)
    for combination in lotto_combinations():
        sum2count[sum(combination)] += 1
    
    for combination in lotto_combinations():
        the_sum = sum(combination)
        x = the_sum * sum2count[the_sum]
        if x >= 2000000 and product(combination) == x:
            print combination


if __name__ == '__main__':
    main()

Und dazu noch die C-Lösung mit folgender, etwas aufgeräumterer `combination_next()`:

Code: Alles auswählen

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

Ergebnis:

Code: Alles auswählen

Filename        Impl.   Runtime         Factor
==============  ======  =========  ===========
lotto_01.py     python    34.144s         1.00
lotto_01.py     pypy      11.635s         2.93
lotto_01.c                 0.267s       127.88

Ohne etwas am Python-Quelltext zu ändern ist PyPy fast 3× schneller. Und wenn man sich die Mühe macht es in C nach zu implementieren ist der Faktor 127.

Für algorithmische Verbesserungen stellt sich die Frage ob es möglich ist die Anzahl der Kombinationen, welche eine vorgegebene Summe ergeben, effizienter zu Zählen als tatsächlich all die Kombinationen zu generieren (für die erste Schleife); und ob es dann einen effizienten Weg gibt all die Kombinationen für eine Summe zu generieren, ohne *alle* Kombinationen zu generieren (für die zweite Schleife).

@heiliga horsd: Ich denke die `Pool.map()`-Varianten bringen nicht viel solange der Hauptprozess weiterhin alle ≈14M Kombinationen generiert und diese serialisiert an die Prozesse übermittelt um für jede Kombination ein Ergebnis zurück geschickt zu bekommen. Das dürften mehrere hundert Megabyte an Daten werden, die (de)serialisiert und zwischen den Prozessen hin und her übermittelt werden.

Wenn man das parallelisieren möchte, müssten man auch die Generierung der Kombinationen verteilen können, also beim Generieren der Kombinationen auch bei der x. Kombination beginnen können. Dann könnte man sowohl das Berechnen der Summenhäufigkeit, als auch das Testen aller Kombinationen verteilen. Bei zwei Prozessen könnte einer dann zum Beispiel die ersten ≈7M Kombinationen testen und der andere die zweiten ≈7M Kombinationen. `itertools.combinations()` kann aber nur von vorne aufzählen. Man müsste sich also einen eigenen Kombinations-Iterator schreiben und neben der Funktion, welche die lexikografisch nächste Kombination aus einer gegebenen Kombination erzeugt, auch eine welche die x. lexikographische Kombination aus einem gegebenen x erzeugt. Sollte beides machbar sein. Vorlage für das generieren könnten die Funktionen `combination_init()` und `combination_next()` aus meinem C-Programm sein. Fehlt also nur noch die Funktion um aus x die zugehörige Startkombination zu berechnen. Und dann muss das in Python-Code parallel ausgeführt nur noch schneller sein als der C-Code hinter `itertools.combinations()` sequentiell ausgeführt.

Komme dir bei deinem ersten Post nicht ganz hinterher - wieso kann ich Tupel nicht aufrufen?

Code: Alles auswählen

>>> a = (1,2,3)
>>> sum(a)
6

bzw.

Code: Alles auswählen

>>> a = ((2,3,4),(3,4,5),(4,5,6))
>>> map(sum, a)
<map object at 0x0000000003123A58>
>>> for b in map(sum,a):
	print(b)

	
9
12
15
>>>

Funktioniert doch auch, ich übergebe einer Funktion doch da ein Tupel? Oder wie meinst du das?

Für algorithmische Verbesserungen stellt sich die Frage ob es möglich ist die Anzahl der Kombinationen, welche eine vorgegebene Summe ergeben, effizienter zu Zählen als tatsächlich all die Kombinationen zu generieren (für die erste Schleife); und ob es dann einen effizienten Weg gibt all die Kombinationen für eine Summe zu generieren, ohne *alle* Kombinationen zu generieren (für die zweite Schleife).

Ich bin kein Mathematiker, d.h. die Antwort kann ich dir nicht geben.

Wenn man das parallelisieren möchte, müssten man auch die Generierung der Kombinationen verteilen können, also beim Generieren der Kombinationen auch bei der x. Kombination beginnen können. Dann könnte man sowohl das Berechnen der Summenhäufigkeit, als auch das Testen aller Kombinationen verteilen. Bei zwei Prozessen könnte einer dann zum Beispiel die ersten ≈7M Kombinationen testen und der andere die zweiten ≈7M Kombinationen. `itertools.combinations()` kann aber nur von vorne aufzählen. Man müsste sich also einen eigenen Kombinations-Iterator schreiben und neben der Funktion, welche die lexikografisch nächste Kombination aus einer gegebenen Kombination erzeugt, auch eine welche die x. lexikographische Kombination aus einem gegebenen x erzeugt. Sollte beides machbar sein. Vorlage für das generieren könnten die Funktionen `combination_init()` und `combination_next()` aus meinem C-Programm sein. Fehlt also nur noch die Funktion um aus x die zugehörige Startkombination zu berechnen. Und dann muss das in Python-Code parallel ausgeführt nur noch schneller sein als der C-Code hinter `itertools.combinations()` sequentiell ausgeführt.

Stellt sich mir natürlich die Frage, ob es der Aufwand Wert ist und wie ich der Funktion sage, wann sie aufhören die Kombinationen zu erzeugen.

heiliga horsd hat geschrieben: - wieso kann ich Tupel nicht aufrufen?
Code: Alles auswählen
>>> a = (1,2,3)
>>> sum(a)
6
Funktioniert doch auch, ich übergebe einer Funktion doch da ein Tupel? Oder wie meinst du das?

Hier rufst Du aber eine Funktion `sum` auf und nicht den Tupel; das wäre `a()` - und das geht nicht

Code: Alles auswählen

>>> a = ((2,3,4),(3,4,5),(4,5,6))
>>> map(sum, a)
<map object at 0x0000000003123A58>
>>> for b in map(sum,a):
        print(b)

       
9
12
15
>>>

Da hab ich ja auch eine Funktion und ein Tupel das ich übergebe und es funktioniert?

heiliga horsd hat geschrieben: Da hab ich ja auch eine Funktion und ein Tupel das ich übergebe und es funktioniert?

Ja und? Hier rufst Du ja auch eine Funktion auf und nicht das Tupel! Ich kapiere den Einwand jetzt irgend wie nicht...

BlackJack bezog sich doch auf diese Zeilen:

Code: Alles auswählen

def check_combinations(combinations_to_check):
    for combination in combinations_to_check():
        ...

`combinations_to_check` ist (wohl) ein Tupel und dieses rufst Du via `()` am Ende des `for`-Ausdrucks auf! Und das kracht dann eben... wo ist da jetzt genau das Verständnisproblem?

Achso, das habe ich gar nicht bemerkt

dachte er bezieht sich auf

Code: Alles auswählen

result = pool.map(check_combinations, give_combinations(), CHUNKSIZE)

Edit:

Code: Alles auswählen

Traceback (most recent call last):
  File "C:\Users\XX\Desktop\Lotto.py", line 43, in <module>
    print(find_combination())
  File "C:\Users\XX\Desktop\Lotto.py", line 38, in find_combination
    result = pool.map(check_combinations, give_combinations(), CHUNKSIZE)
  File "C:\Python32\lib\multiprocessing\pool.py", line 251, in map
    return self.map_async(func, iterable, chunksize).get()
  File "C:\Python32\lib\multiprocessing\pool.py", line 556, in get
    raise self._value
TypeError: 'int' object is not iterable

Ich iteriere doch gar nicht über einen Integer?

Wie sieht denn der aktuelle Code aus? Ohne den kann man die Meldung ja nicht interpretieren!

Sorry, hatte ich ganz vergessen.

Code: Alles auswählen

from itertools import combinations
import operator
import collections
try:
    from functools import reduce
except ImportError:
    pass 
try:
    from itertools import imap
except ImportError:
    imap = map

DIFFERENT_VALUES = 49
NUMBERS = list(range(1,DIFFERENT_VALUES + 1))
MIN_VALUE = 2*10**6
VALUES_TO_COMBINE = 6
PROCESSES = 14
CHUNKSIZE = 10**6
sums = None  # Um 'global' herumgemogelt

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

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

def check_combinations(combinations_to_check):
    for combination in combinations_to_check:
        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(check_combinations, give_combinations(), CHUNKSIZE)
    return result
        
if __name__ == "__main__":
    print(find_combination())

Das kann schon mal nicht stimmen - bei dem Code kommt ein `NameError`

Code: Alles auswählen

Traceback (most recent call last):
  File "./combi.py", line 44, in <module>
    print(find_combination())
  File "./combi.py", line 38, in find_combination
    pool = Pool(processes=PROCESSES)
NameError: global name 'Pool' is not defined

Da fehlt also

Code: Alles auswählen

from multiprocessing import Pool

Was sollen diese schaurigen bedingten import-Konstrukte? Entweder Du schreibst Code für Python2 oder für Python3! Vor allem ist das wirklich unnötig, da das Tool `2to3` die benötigte Umformung der imports wirklich selber regeln kann

Aus diesem Script für Python2:

Code: Alles auswählen

#!/usr/bin/env python

from operator import add
from itertools import imap

reduce(add, [1, 2, 3])

imap(lambda x: x+1, [1, 2, 3])

erstellt `2to3` eine wunderschöne "diff"-Ausgabe:

Code: Alles auswählen

1 nelson@destiny ~/src/Python/forum/combinations % 2to3 test.py
RefactoringTool: Skipping implicit fixer: buffer
RefactoringTool: Skipping implicit fixer: idioms
RefactoringTool: Skipping implicit fixer: set_literal
RefactoringTool: Skipping implicit fixer: ws_comma
RefactoringTool: Refactored test.py
--- test.py     (original)
+++ test.py     (refactored)
@@ -1,8 +1,9 @@
 #!/usr/bin/env python
 
 from operator import add
-from itertools import imap
+from functools import reduce
+
 
 reduce(add, [1, 2, 3])
 
-imap(lambda x: x+1, [1, 2, 3])
+map(lambda x: x+1, [1, 2, 3])
RefactoringTool: Files that need to be modified:
RefactoringTool: test.py

Wie man sieht, erkennt das Tool genau, was an den imports geändert werden muss und dass der Aufruf von `imap` in `map` geändert werden muss

Dein `sums` ist übrigens immer noch *global*, da ändert der Kommentar nichts dran:

Code: Alles auswählen

sums = None  # Um 'global' herumgemogelt

Und `VALUES_TO_COMBINE` ist unbenutzt.

Zum Problem fällt mir leider spontan nichts ein; mir hat das Tool in seiner aktuellen Form meinen Rechner lahmgelegt - da muss ich erst noch ein wenig an den Parametern fummeln.

Narf... manchmal sieht man den Wald vor lauter Bäumen nicht.

`pool.map` gibt doch einzelne *Items* des Iterable an die Funktion weiter! Insofern bekommt Deine `check_combinations`-Funktion bereits das Tupel mit den Kombinationen und nicht eine Liste von Tupeln! Ergo ist die `for`-Schleife nun überflüssig.

Edit: `return` ist ein Statement und keine Funktion; Klammern um den Rückgabewert sind also semantisch unnötig und verwirren eher, als dass sie nützen

@heiliga horsd: Ersetze das `Pool.map()` zu Testzwecken mal durch das normale `map()` (für Python 3.x wahlweise mit einem `list()`- oder `next()`-Aufruf kombiniert), damit der Fehler ohne die ganze Prozess-Zwischenschicht untersucht werden kann.

Wobei das so auch ohne dieses Problem nicht funktionieren wird, wenn Dein `sums` auf Modulebene ist immer `None` weil dem nie etwas zugewiesen wird. Das Problem wird sich nicht ganz so einfach lösen lassen, denn alle Prozesse auf gemeinsame Daten zugreifen müssen. Ich bin mir auch nicht so ganz sicher ob Du `map()` verstanden hast. Das Ergebnis ist eine Liste mit ≈14M Elementen weil Du als Argument ein `iterable()` mit so vielen Elementen übergibst. Die Funktion `check_combinations()` wird für *jede* Kombination aufgerufen und *nicht* für eine Sequenz mit Kombinationen! So kommt auch der Fehler zustande: `check_combinations()` wird zum Beispiel mit ``(1, 2, 3, 4, 5, 6)`` aufgerufen, dann geht die Schleife über die Elemente und bindet die einzelnen Zahlen an den Namen `combination` und dann versuchst Du auf einer einzelnen Zahl `sum()` aufzurufen:

Code: Alles auswählen

In [146]: sum(42)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/bj/<ipython console> in <module>()

TypeError: 'int' object is not iterable

Code: Alles auswählen

from multiprocessing import Pool
from itertools import combinations
import operator
import collections
from functools import reduce
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 = 14
CHUNKSIZE = 10**6

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

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

def check_combinations(combination, sums):
    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 = map(check_combinations, give_combinations(), CHUNKSIZE)
    return result
        
if __name__ == "__main__":
    print(find_combination())

Ich blicke echt nichtmehr durch...

Code: Alles auswählen

Traceback (most recent call last):
  File "C:\Users\XX\Desktop\Lotto.py", line 39, in <module>
    print(find_combination())
  File "C:\Users\XX\Desktop\Lotto.py", line 35, in find_combination
    result = map(check_combinations, give_combinations(), CHUNKSIZE)
TypeError: 'int' object is not iterable

Jetzt iteriere ich doch nichtmehr über einen Integer, oder? Map übergibt die einzelnen Elemente des Kombination-Aufrufs an check_combinations - und das sind Tupel und keine Integer?
Und wie bekomme ich - wenn nicht irgendwie über eine globale Variable - sums in den Namensraum von check_combinations?

heiliga horsd hat geschrieben:Jetzt iteriere ich doch nichtmehr über einen Integer, oder? Map übergibt die einzelnen Elemente des Kombination-Aufrufs an check_combinations - und das sind Tupel und keine Integer?

Dann überlege doch noch einmal, was CHUNKSIZE genau ist

heiliga horsd hat geschrieben:Und wie bekomme ich - wenn nicht irgendwie über eine globale Variable - sums in den Namensraum von check_combinations?

Mittels ``functools.partial``

Code: Alles auswählen

functools.partial(check_combinations, sums=sums)

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

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

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!

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

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.

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.

Das deutsche Python-Forum

Nicht nachvollziehbares Verhalten von itertools.combinations

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat