brute force und Rechenzeitverkürzung

[tian]

Hallo.

Allem voran: ICH BIN EIN PY-NEULING! Also bitte verzeiht mir meinen Wissensstand.

Ich möchte aus einer Liste mit n Elementen alle 10-stelligen Kombinationen erstellen. Das wird also hinlänglich zeitaufwändig. Im Moment mache ich das wie folgt:

Code: Alles auswählen

for i in range(2 ** len(data)):    
        selected_indices = [j for j in range(len(data)) if (i & (1 << j)) > 0]

Jetzt werden aber auch Kombinationen mit <10 Elementen erstellt.

a) wie ergänze ich meinen code einfach um NUR 10-stellige Kombinationen zuzulassen.
b) Ich habe potente Hardware. Kann ich diese Brute-Force Methode leicht auf mehrere Cores verteilen, also mein Problem splitten um die Rechenzeit zu verkürzen? bei n=26 bin ich schon bi fast 9 Minuten Laufzeeit.

Ich würde mich tierisch über eure Hilfe freuen!

[__deets__]

Benutz itertools permutations. Und mit dem Modul multiprocessing kannst du trivial zb 9 Kombinationen ausrechnen lassen pro Worker, und eben n Worker definieren.

[narpfel]

Und PyPy ist auch einen Blick wert. Je nach Code kann das auch gerne mal 20x schneller sein als CPython.

[tian]

Ihr müsst wissen ich habe seit 10 Jahren nicht programmiert. Ist für mich gerade wie als wenn Mama den Zylinderkopf wechseln muss. Haha

Hab jetzt itertools combinations im Einsatz. Die Combis erstellen geht echt flott, aber mit diesen Indizes meine Daten prüfen ist, was dauert. Das müsste doch jetzt leicht parallelisierbar sein.

Ich tue mich aber schon schwer die Anzahl an Kombinationen in "result" anzeigen zu lassen. Jemand einen Tip?

Code: Alles auswählen

result = combinations(range(len(data)),10)

Könnte mir jemand sagen wie ich nachgelagerte Arbeit gut auf 10 Cores verteilen könnte?
So arbeite ich mich aktuell durch meine Kombinationen:

Code: Alles auswählen

for index in result:
   total_price=sum(data[j]['price'] for j in index)

Am liebsten würde ich 'result' in X gleich grosse Stücke teilen und parallel verarbeiten.

[__blackjack__]

@tian: Warum erzeugst Du Kombination von Indexwerten statt gleicht die Kombinationen von den *Werten* die Du eigentlich haben willst zu erzeugen?

Die Anzahl kann man doch ausrechnen, dazu muss man die nicht erst alle aufzählen.

Aufteilen auf Prozesse kann man mit `multiprocessing` oder `concurrent.futures`. Wobei man da auch aufpassen muss, dass das Parallelisieren und verteilen der Daten auch Zeit kostet.

[noisefloor]

Hallo,

was sind denn "deine Daten", also wie sehen die aus? Und was suchst du konkret in deinen Daten? Vielleicht gibt es noch eine besseren / effizienteren Weg ohne Brute Force, z.B. via... numpy? pandas?

Gruß, noisefloor

[tian]

@blackjack. Okay, berechnen kann ich die Anzahl der Kombinationen natürlich. Dachte ich kann einfach die Anzahl der Elemente in "results" auslesen. Das wäre natürlich einfacher.

Konkret zur Aufgabe:
ich habe eine Liste mit 50-600 Spielern. Jeder davon hat einen Preis, eine Leistung, einen Verein und eine prediction Score.

Jetzt möchte ich die besten 11 Spieler mit maximaler Leistung ermitteln, die in einem Budget X liegen. Der Rest sind weitere optionale Constraints die hier erstmal irrelevant sind.

Was die Parallelisierung angeht, hätte da vielleicht einer ein Code Snippet für mich (pls), der mich in "for index in result" leicht auf 6 cores verteilen lässt?

[noisefloor]

Hallo,

dann verstehen ich deine Ansatz erst recht nicht. Wenn du X Spieler hast und jeder Spieler hat einen identisch Satz von Daten / Attributen, dann packst du das doch viel besser in eine tabellenartige Struktur und selektierst aus der Tabelle. Das ginge z.B. mit SQLite und einer Datenbank und z.B. mit pandas. Das ist ziemlich sicher deutlich schneller als dein Brute-Force Ansatz.

Gruß, noisefloor

[__deets__]

@noisefloor nein, das ist ja ein Optimierungsproblem, wo die gebildeten Mannschaften erzeugt und bewertet werden.

[snafu]

Das scheint mir ein typisches Rucksack-Problem zu sein. Hierzu könntest du dir mal https://pypi.org/project/mknapsack/ anschauen, ob eine der dort angebotenen Funktionen dir weiterhilft. Das Backend des Pakets ist in Fortran implementiert und damit womöglich ausreichend schnell, so dass man ohne Parallelisierung auskommt.

[snafu]

Das o. g. Paket ist allerdings umständlich zu installieren. Ich hatte einige Schwierigkeiten unter Windows, da es noch kompiliert werden musste.

Einfacher fand ich die Nutzung von ``ortools`` (https://pypi.org/project/ortools/). Das sind diverse wissenschaftliche Tools, die von Google entwickelt wurden.

Ein Beispiel für das Rucksack-Problem findest du hier:

https://developers.google.com/optimizat ... sack?hl=de

[tian]

Vielen Dank für alle eure Tipps!!!! Nur nochmal um es klarzustellen: ich bin blutiger Anfänger, der viele Ressourcen über jupyter Notebook ansteuern kann. In meinen 180 Zeilen Code stecken bestimmt schon 20h Arbeit u.A. mit Hilfe von ChatGPT . Noch mehr bzw. andere Tools und Bibliotheken (Fortran...) sprengen schnell meine Möglichkeiten Ich würde also gern weitermachen wo ich gerade bin und nicht alles wieder neu erfinden. Einfach wegen meines Skill-Levels

Ich habe jetzt versucht meinen Code mit "multiprocessing" zu parallelisieren, aber irgendwie laufen meine Worker nicht?

Hier meine relevanten Code-Zeilen:

Code: Alles auswählen

import multiprocessing

def process_index(index):
   # hier werden alle Operationen auf EINER Kombination durchgeführt
   print("I am a running Worker")
   total_price = sum(data[j]['price'] for j in index)
   [...]
   
if __name__ == "__main__":
   result =  combinations(range(len(data)), 11)             # berechnet alle möglichen 11-langen-"combinations" aus der Anzahl an Daten in meinem CSV. z.B. 1,15,90,85,2,23,5,99,3,4,9
   num_processes = 4
   with multiprocessing.Pool(processes=num_processes) as pool:
        pool.map(process_index, result)

Was mache ich falsch?

PS: Danke @blackjack, ich rechne einfach meine Combinations aus. Das geht halt auch: n! / ( (n-r)! * r!
PSS: Ja, es handelt sich um das Rucksack-Problem

[__blackjack__]

@tian: „Irgendwie laufen meine Worker nicht“ ist keine gute Fehlerbeschreibung. Da kann man nur sagen, dass da irgendwas falsch gemacht wird.

Beim gezeigten Code ist sowohl `combinations()` als auch `data` undefiniert. Es macht nicht so wirklich viel Sinn Code zu zeigen der so ähnlich ist wie der, der nicht funktioniert, denn das Problem kann dann ja genau in den nicht gezeigten Unterschieden liegen.

`data` ist hier auch ein Problem, denn die zu verarbeitenden Daten müssen ja auch in die anderen Prozesse gelangen.

Ich würde da vielleicht auch erst einmal eine normale Lösung schreiben, die mit der eingebauten `map()`-Funktion arbeitet. Und das parallelisieren im nächsten Schritt machen. Dann kann man auch leichter Messen, ob das überhaupt etwas bringt.

[tian]

Ich 'lerne' mich langsam ran.

Mit multiprocessing konnte ich nun in einem Testcase tatsächlich zeit einsparen. Ich habe Child-Processe mit einem sleep=5. Führe ich alle Combinations von 2 aus 4 Elementen aus (=6), dauert mein Skript 30s. Mit 6 Child-Prozessen nur noch 5. Wahnsinn!

Wichtig: ich musste mit den print's in den Child-Prozessen experimentieren, da print mit Buffern arbeitet. Flushen hat nichts gebracht, also arbeite ich mit multiprocessing.block.
Zusätzlich werde ich die chunksize verwenden, damit bei 60.000.000 Iterationen nicht fast 60.000.000 Prozesse in memory warten müssen.

Code: Alles auswählen

from itertools import combinations
import multiprocessing
import os
import sys
import time

# timer
from datetime import datetime
start_time = datetime.now()


def process_index(index):
   # hier werden alle Operationen auf EINER Kombination durchgeführt
    
    time.sleep(5)
    with lock:
        print("I am a running Worker processing: ", list(index), "   with PID: ", os.getpid())



if __name__ == "__main__":
    
    result = combinations(range(4), 2)
    # all elemnts:  [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]     

    lock = multiprocessing.Lock()
    num_processes = 6
    with multiprocessing.Pool(processes=num_processes) as pool:
        pool.map(process_index, result, chunksize=1)
        
pool.close()
pool.join()
    
# print time taken
print("----------------\ndatetime: ", datetime.now() - start_time)

Output:

Code: Alles auswählen

I am a running Worker processing:  [0, 1]    with PID:  14485 
I am a running Worker processing:  [0, 2]    with PID:  14486 
I am a running Worker processing:  [0, 3]    with PID:  14487 
I am a running Worker processing:  [1, 2]    with PID:  14488 
I am a running Worker processing:  [2, 3]    with PID:  14491 
I am a running Worker processing:  [1, 3]    with PID:  14489 
----------------
datetime:  0:00:05.154608

Mal sehen wie das mit meinen echten Daten laufen wird....

[__blackjack__]

@tian: Das geht so nicht. Die Sachen auf Modulebene *können* in anderen Prozessen sichtbar sein, *müssen* sie aber nicht. Aber da sollte sowieso nur Code stehen der Konstanten, Funktionen, und Klassen definiert. Das Hauptprogramm gehört sauber in eine Funktion, also auch nicht einfach unter dem ``if __name__ …`` wo dann doch globale Variablen definiert werden.

Edit: Das mit `sleep()` ist nur so semi-sinnvoll, denn selbst bei nur einem Prozessor/Kern würde das so eine unglaubliche ”Beschleunigung“ bringen, denn ”schlafen” können nahezu beliebig viele Prozesse parallel, unabhängig von der Anzahl der Prozessoren/Kerne.

[tian]

sleep: Ich habe das mit meinem abgespeckten Datensatz aus einer Kombinaton 10 aus 30 laufen lassen (30 Mio Varianten). Da verringert sich die Laufzeit von 53s (1 core) auf 28s (4 cores).

Leider bleibt mein Jupyter Notebook bei Datensätzen > 30 schnell hängen. Mir ist unklar warum. Hmmm. Ich tue mich noch schwer einen Progress-Counter auszugeben. Bei single Thread ist das einfach, aber bei mehreren Thread muss ja jeder Aufruf von process_index am besten eine globale Variable erhöhen. Eigentlich bräuchte man dafür einen weiteren Thread, der die Variable ausgibt. Aber will ich das so haben?!?

@blackjack: Was deinen ersten Kommentar angeht weiß ich nicht, ob das ein Tipp für sauberes Coding ist, oder etwas funktionales, was die Ausführung betrifft. (Entschuldige meinen Skill). Du meinst das hier:

Code: Alles auswählen

result = combinations(range(4), 2)

gehört in eine eigene Funktion?

[Qubit]

Mal zum Vergleich..

Code: Alles auswählen

from concurrent import futures
from itertools import combinations
from time import monotonic

def process_index(index):
    return index[0]+index[1]


if __name__=='__main__':

    start = monotonic()

    result = combinations(range(30), 10)

    print("Start..")

    with futures.ProcessPoolExecutor(max_workers=4) as e:
        res = e.map(process_index, result, chunksize=10000)

    print(f"Summe = {sum(res)}")

    ende = monotonic()
    print(f"Ende: {ende-start:.2f}s")

Code: Alles auswählen

Start..
Summe = 193926915
Ende: 28.09s

Peak ca. 5GB Memory

[tian]

1000000x Danke @Qubit! Das sieht sehr gut aus.

Versuche gerade testweise meinen Datensatz zu integrieren, der ist aber in den Child-Prozessen ja nicht lesbar.

Code: Alles auswählen

import csv

def read_csv(file_path):
    data = []
    with open(file_path, 'r') as csvfile:
        csvreader = csv.reader(csvfile)
        for row in csvreader:
            data.append({
                'name': row[0],
                'team': row[1],
                'price': int(row[2]),        
                'value': int(row[8]),
                'oppo': int(row[7]),
            })
    return data

damit ich im Subprozess

Code: Alles auswählen

total_value = sum(data[j]['value'] for j in index)

sowas machen könnte. Kann aber "data" ja nicht an den subprozess mitgeben

[__blackjack__]

@tian: Textdateien sollte man immer explizit mit der Kodierungsangabe öffnen. Bei CSV-Dateien erwartet das `csv`-Modul, das ``newline=""` beim öffnen der Datei angegeben wurde.

Wörterbücher die immer einen festen Satz an Zeichenkettenschlüsseln haben sind eigentlich Objekte. Also mindestens mal `collections.namedtuple`.

Code: Alles auswählen

import csv
from collections import namedtuple

Player = namedtuple("Player", "name team price value oppo")


def read_csv(file_path):
    with open(file_path, "r", newline="", encoding="utf-8") as csv_file:
        return [
            Player(row[0], row[1], int(row[2]), int(row[8]), int(row[7]))
            for row in csv.reader(csv_file)
        ]

Ich stellte die Frage ja schon mal warum Du die Indexwerte für die Kombinationen generierst und nicht nicht die Kombinationen selbst. Das wäre der einfachste Weg die Daten in die anderen Prozesse zu bekommen. Und ein Weg für den man erst einmal eine nicht parallelisierte Lösung programmieren kann, die man dann einfach umstellen kann.

[Qubit]

damit ich im Subprozess

Code: Alles auswählen

total_value = sum(data[j]['value'] for j in index)

sowas machen könnte. Kann aber "data" ja nicht an den subprozess mitgeben

Das könntest du zB. mit einem Partial machen, solange du nur lesenden Zugriff auf die Daten haben willst..

Code: Alles auswählen

from time import monotonic
from concurrent import futures
from itertools import combinations
from functools import partial

def process_index(index):
    return index[0]+index[1]

def process_index2(data, index):
    return sum(data[idx]['x'] for idx in index)

if __name__=='__main__':

    start = monotonic()

    data=tuple({'x': i, 'y': str(i)} for i in range(30))

    result = combinations(range(len(data)), 10)

    process_idx = partial(process_index2, data)

    print("Start..")

    with futures.ProcessPoolExecutor(max_workers=4) as e:
        res = e.map(process_idx, result, chunksize=10000)

    print(f"Summe = {sum(res)}")

    ende = monotonic()
    print(f"Ende: {ende-start:.2f}s")

Code: Alles auswählen

Start..
Summe = 4356527175
Ende: 31.06s

Peak ca. 5GB Memory