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.
heiliga horsd

Donnerstag 21. Juni 2012, 20:28

Code: Alles auswählen

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
BlackJack

Donnerstag 21. Juni 2012, 20:50

@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. ;-)
BlackJack

Freitag 22. Juni 2012, 10:35

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. :-)
heiliga horsd

Freitag 22. Juni 2012, 12:22

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.
Zuletzt geändert von heiliga horsd am Freitag 22. Juni 2012, 12:25, insgesamt 1-mal geändert.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Freitag 22. Juni 2012, 12:24

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 ;-)
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
heiliga horsd

Freitag 22. Juni 2012, 12:43

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?
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Freitag 22. Juni 2012, 12:55

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?
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
heiliga horsd

Freitag 22. Juni 2012, 12:56

Achso, das habe ich gar nicht bemerkt :oops:

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?
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Freitag 22. Juni 2012, 13:04

Wie sieht denn der aktuelle Code aus? Ohne den kann man die Meldung ja nicht interpretieren!
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
heiliga horsd

Freitag 22. Juni 2012, 13:09

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())
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Freitag 22. Juni 2012, 13:40

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.
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Freitag 22. Juni 2012, 13:47

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 ;-)
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
BlackJack

Freitag 22. Juni 2012, 13:47

@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
heiliga horsd

Freitag 22. Juni 2012, 14:07

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?
EyDu
User
Beiträge: 4872
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Freitag 22. Juni 2012, 14:14

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)
Das Leben ist wie ein Tennisball.
Antworten