Nicht nachvollziehbares Verhalten von itertools.combinations

[heiliga horsd]

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?

[Hyperion]

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?

[heiliga horsd]

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?

[Hyperion]

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

[heiliga horsd]

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())

[Hyperion]

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.

[Hyperion]

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

[BlackJack]

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

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]

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

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)

[Hyperion]

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

[EyDu]

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:

Das hat nichts mit Python3 zu tun, sondern liegt am Verhalten von Generatoren!

[Hyperion]

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

[snafu]

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.

[snafu]

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]

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]

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

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

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.

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]

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.

[snafu]

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