Zahlen in einer Dict gleichmäßig auffüllen

[tobifire]

Hi zusammen! (Bin neu in dem Forum, deshalb die Frage im Allgemeinen gestellt)

Ich bin gerade an einem Projekt, wo ich als Vorgabe eine Dictionary habe die wie folgt aussieht: { "Name": Int Zahl, "Name": Int Zahl, "Name": Int Zahl } (Das Dict kann auch größer oder kleiner sein, jedoch bleibt das Muster)
dann bekomme ich einen weiteren Wert als Int geliefert. Bspw. t = int(200). Meine Aufgabe ist es diese Zahl unter dem Variabel Namen "t" gleichmäßig unter den Zahlen in der Dictionary aufzuteilen.
Kleines Beispiel:

Vorher:
t = 150
{ "Peter": 150, "Alex": 250, "Tobias": 50 }

Ergebnis soll sein:
t = 0
{ "Peter": 175, "Alex": 250, "Tobias": 175 }

Ich hoffe man sieht, anhand des Beispiels, was ich erreichen möchte..

Meine Frage ist wie ich das am Effizientesten lösen könnte.
Bisher ist mir nur eine While Schleife eingefallen t > 0 und in der Schleife sortiert das Programm nach dem kleinsten Wert des Dictionary (sort by value) und füllt ihn mit +=1 auf und beginnt von vorn.

Grüße
Tobias

[sparrow]

Dein Beispiel entspricht für mich nicht deiner Erklärung.
Du hast geschrieben "[...] Aufgabe ist es diese [...] gleichmäßig unter den Zahlen aufzuteilen".
Wenn ich etwas gleichmäßig aufteile, dann haben die Teile die gleiche Größe. Also würde jeder Wert um 50 erhöht werden.

Was genau soll denn passieren?

[__blackjack__]

@sparrow: Ich hätte das jetzt so interpretiert das immer der/die mit dem kleinsten Wert solange Gummipunkte bekommen bis alles aufgebraucht ist. Also würde erst Tobias solange was bekommen bis er mit Peter gleich auf liegt oder die Gummipunkte alle sind. Und dann bekommen Peter und Tobias solange Gummipunkte bis sie mit Alex gleichauf sind oder die Punkte alle sind. Was im Beispiel passiert wenn beide 175 erreicht haben.

[tobifire]

@sparrow
Da gebe ich dir Recht.. mein Fehler. Wie im Beispiel zu sehen müssen die Zahlen nicht "gleichmäßig" aufgefüllt werden, sondern
das geringste Value soll zunächst insoweit aufgefüllt werden, bis es gleich viel hat wie die das zweit kleinste (wenn "t" es überhaupt zulässt).
Heißt also in dem Beispiel: "Tobias": 50 werden 100 aufgefüllt bis es so viele hat wie "Peter": 150, ab dann wird der Wert so lange aufgeteilt, bis das nächst größere Value erreicht wird.
In den Beispiel wird das nächst größere Value nicht erreicht, heißt also die übrigen 50 in t werden hälfte hälfte aufgeteilt: "Peter": 175, "Tobias": 175
Ab dann sollte auch das mit in die Rechnung rein.

[tobifire]

@__blackjack__

Ganz genau! Besser hätte ich es nicht erklären können..

[narpfel]

@tobifire: Jetzt hast du ja eigentlich schon die (bzw. eine?) Lösung auf deine Frage beschrieben. Ein bisschen effizienter kann man das machen, wenn man eine passende Datenstruktur nutzt, mit der das Finden der jeweils kleinsten Elemente effizienter als linear ist. In der Standardbibliothek gibt es da zum Beispiel das `heapq`-Modul.

[tobifire]

@narpfel Ja ich habe bereits eine Lösung die auch funktioniert.. wie gesagt mit der While Schleife und dem rauspicken des kleinsten Wertes.
Dachte nur eventuell eine Effizientere Lösung vorgeschlagen zu bekommen. Ich schaue mir das mal an!

[narpfel]

@tobifire: In deiner Beschreibung hier kommt doch überhaupt keine `while`-Schleife mehr vor? (Edit: Damit meine ich die Schleife, in der jeweils der kleinste Wert inkrementiert wird.)

[tobifire]

@narpfel Das ist auch die Beschreibung explizit für das Beispiel.. Wenn ich das genau so übernehme wie beschrieben kann ich das nur bei Dictionarys verwenden, die 3 Werte haben.
Mein bisheriger Lösungsansatz war wie beschrieben:
In einer While Schleife t > 0, wird nach dem kleinsten Wert des Dictionarys gesucht. Dem Wert wird +=1 hinzugefügt und gespeichert und am Ende der While schleife wird t -=1 subtrahiert. Das wird solange gemacht, bist t = 0 ist.
Das ist meiner Meinung keine elegante Lösung, da ich aber noch nicht alle Möglichkeiten von Python kenne frage ich nach Rat.

[sparrow]

@tobifire: Zeit doch mal deine bisherige Lösung, dann schauen wir mal gemeinsam.

[tobifire]

Ich hoffe mal man kann die Funktion erkennen

Code: Alles auswählen

            
            
            t = int(150)
            daten = { "Peter": 150, "Alex": 250, "Tobias": 50 }
            sortedlist = sorted(daten.items(), key = lambda kv: kv[1])
            sortdaten = dict(sortedlist)
            
            while 0 < t:

                if len(sortdaten) >= 2:
                
                    n0 = int(list(sortdaten.values())[0])
                    n1 = int(list(sortdaten.values())[1])

                    while n0 < n1:

                        if 0 < t:
                            n0 += 1
                            t -= 1
                            name = list(sortdaten.keys())[0]
                            sortdaten[name] = int(n0)
                            pbar.update(1)
                        break
    
                    if 0 < t:

                        n0 += 1
                        t -= 1
                        name = list(sortdaten.keys())[0]
                        sortdaten[name] = int(n0)
                        pbar.update(1)
            
                    sortedlist = sorted(sortdaten.items(), key = lambda kv: kv[1])
                    sortdaten = dict(sortedlist)

                else:
                
                    n0 = int(list(sortdaten.values())[0])
                    n0 += t
                    pbar.update(t)
                    t = 0
                    name = list(sortdaten.keys())[0]
                    sortdaten[name] = int(n0)
                    sortedlist = sorted(sortdaten.items(), key = lambda kv: kv[1])
                    sortdaten = dict(sortedlist)
                    

[Thants]

@tobifire: Die nächste offensichtliche Optimierung von deinem Algorithmus wäre jetzt die Punkte nicht einzeln zu verteilen, sondern in Blöcken. Die textuelle Beschreibung von blackjack enthält ja bereits eine Idee, die musst du jetzt in Code umsetzen. Um das nochmal aufzugreifen, du könntest die Leute in dem dict in zwei Gruppen einteilen, einmal alle Teilnehmer, evtl. sogar bereits nach Punkte sortiert, und dann die Punktekandidaten. Zu Beginn wechselt derjenige mit der geringsten Punktezahl von der Teilnehmerliste in die Kandidatenliste (oder auch mehrere, falls es mehrere mit gleicher niedriger Punktezahl gäbe). In deinem Beispiel also Tobias mit seinen 50 Punkten. Die Differenz zum nächsthöheren in der Teilnehmerliste, Peter, ist 100. t ist noch >= 100, also kannst du sofort 100 Punkte an Tobias zuweisen und von t abziehen. Jetzt haben Peter und Tobias gleichviel Punkte, also wechselt Peter auch in die Kandidatenliste, da er ab jetzt auch Punkte erhält. Die Differenz zu Alex ist wieder 100, wir bräuchten also 200 Punkte, um alle Punktekandidaten auf den gleichen Punktestand wie Alex zu bringen. Soviel Punkte haben wir aber nicht mehr, also sind wir am Ende und müssen nur noch die verbliebenen Punkte gleichmäßig auf die aktuellen Punktekandidaten verteilen, jeder bekommt also 50/2 Punkte.

[Sirius3]

@tobifire: einbuchtabige Variablennamen sollte man möglichst vermeiden. Was soll denn `t` bedeuten?
Dass Wörterbücher inzwischen eine feste Reihenfolge haben, sollte man möglichst nicht brauchen. Bei Dir ist das Wörterbuch sortdaten auch gar nicht nötig, weil Du eh viel besser mit der Liste arbeitest.
Dass 150 ein int ist, sollte Dir klar sein, dem Computer ist es jedenfalls, wodurch der int-Aufruf unsinnig ist.
Eine while-Schleife, die gleich beim ersten Durchgang per break verlassen wird, ist eigentlich eine if-Abfrage.
Auch hier wieder n0 ist schon ein int, das Umzuwandeln ist überlfüssig.
Dann hast Du einen else-Block, wo garantiert ist, dass t == 0 ist. So dass der else-Block in sich zusammenfällt:

Code: Alles auswählen

    t = 150
    daten = { "Peter": 150, "Alex": 250, "Tobias": 50 }
    sorted_data = sorted(daten.items(), key = lambda kv: kv[1])
    while 0 < t:
        if len(sorted_data) >= 2:
            n0 = sorted_data[0][1]
            n1 = sorted_data[0][1]
            if n0 < n1:
                if 0 < t:
                    n0 += 1
                    t -= 1
                    sorted_data[0][1] = n0
                    pbar.update(1)
    
            if 0 < t:
                n0 += 1
                t -= 1
                sorted_data[0][1] = n0
                pbar.update(1)
                sorted_data = sorted(sorted_data, key = lambda kv: kv[1])
            else:
                pbar.update(0)

Wenn man nun den Pfad n0 < n1 anschaut und das, was nach diesem if-Block kommt, siehst Du, dass beides Mal das selbe passiert, so dass man das zusammenfassen kann:

Code: Alles auswählen

    t = 150
    daten = { "Peter": 150, "Alex": 250, "Tobias": 50 }
    sorted_data = sorted(daten.items(), key = lambda kv: kv[1])
    while 0 < t:
        if len(sorted_data) >= 2:
            if 0 < t:
                n0 = sorted_data[0][1]
                n0 += 1
                t -= 1
                sorted_data[0][1] = n0
                pbar.update(1)
                sorted_data = sorted(sorted_data, key = lambda kv: kv[1])
            else:
                pbar.update(0)

Die Abfrage 0 < t wird aber schon durch die while-Schleife garantiert:

Code: Alles auswählen

    t = 150
    daten = { "Peter": 150, "Alex": 250, "Tobias": 50 }
    sorted_data = sorted(daten.items(), key = lambda kv: kv[1])
    while 0 < t:
        if len(sorted_data) >= 2:
            t -= 1
            sorted_data[0][1] += 1
            pbar.update(1)
            sorted_data = sorted(sorted_data, key = lambda kv: kv[1])
    pbar.update(0)

Der selbe Code, viel einfacher, und man sieht gleich ein Problem. Was passiert wenn es nur einen Eintrag gibt?

[tobifire]

@Sirius3 Das ist schlichtweg Genial. Durch die Erklärung fallen mir erst die unnötigen Wiederholungen sowie unnötige Zwischenschritte auf!

Jedoch ist es nicht möglich mit sorted_data[0][1] += 1 den Werten eine Zahl zu addieren Fehlercode: can only concatenate tuple (not "int") to tuple

Somit habe ich den Code ein wenig verändert, was dann im Endeffekt für mich funktioniert hat!
Vielen Dank!

Code: Alles auswählen

        
        t = 150
   	daten = { "Peter": 150, "Alex": 250, "Tobias": 50 }
        with tqdm(total=t, desc='Berechne..') as pbar:

            sorted_data = dict(sorted(daten.items(), key = lambda kv: kv[1]))
            save_daten = dict(sorted_data)

            while 0 < t:
                sorted_data_values = list(sorted_data.values())
                sorted_data_keys = list(sorted_data.keys())
                if len(sorted_data) >= 2:
                    t -= 1
                    sorted_data_values[0] += 1
                    pbar.update(1)
                    sorted_data = dict(zip(sorted_data_keys, sorted_data_values))
                    sorted_data = dict(sorted(sorted_data.items(), key = lambda kv: kv[1]))
                else:
                    sorted_data_values[0] += t
                    pbar.update(t)
                    t = 0
                    sorted_data = dict(zip(sorted_data_keys, sorted_data_values))
                    sorted_data = dict(sorted(sorted_data.items(), key = lambda kv: kv[1]))
                    
	print(sorted_data)
                    
>>> {'Peter': 175, 'Tobias': 175, 'Alex': 250}

[sparrow]

Ich wusste doch, dass ich so etwas mal unter den Fingern hatte. Ich weiß nur nicht mehr, welche Aufgabe es war, aber es muss etwas mit dem Advent of Code zu tun gehabt haben.
Umgemünzt auf das Problem hier, sieht meine Lösung so aus - ich hab es aber noch nicht ausführlich getestet:

Code: Alles auswählen

def divide_points(points, receiver_count, maximum):
    """Divides points for receiver_counts, but not more than maximum for each

    returns a tuple, which first element is a list of the points for the receiver
    and the secodn is the remainder.
    """
    spreadable = min(points, receiver_count * maximum)
    points_receiver = spreadable // receiver_count
    if points_receiver > 0:
        spreads = [points_receiver] * receiver_count
    else:
        spreads = [1] * points + [0] * (receiver_count - points)
    remainder = points - sum(spreads)
    return spreads, remainder

def spread_points_to_players(player_to_points, points_to_give):
    if len(player_to_points) == 1:
        player_to_points[list(player_to_points.keys())[0]] += points_to_give
        return player_to_points
    player_to_points = {
        k: v for k, v in sorted(player_to_points.items(),
        key=lambda item: item[1])
    }
    receivers = set()
    minimum_points = list(player_to_points.values())[0]
    for name, points in player_to_points.items():
        if points == minimum_points:
            receivers.add(name)
        else:
            points_to_spread = points - minimum_points
            spreads, remainder = divide_points(
                points_to_give, len(receivers), points_to_spread
            )
            for receiver, spread in zip(receivers, spreads):
                player_to_points[receiver] += spread
            receivers.add(name)
            minimum_points += spread
            points_to_give = remainder
    return player_to_points

def main():
    t = 150
    daten = {"Peter": 150, "Alex": 250, "Tobias": 50}
    daten = spread_points_to_players(daten, t)
    print(daten)


if __name__ == "__main__":
    main()

[LeSchakal]

Eine eher plumpe Lösung:

Code: Alles auswählen

def give_to_the_poor(people):
    poor = people.index(min(people))
    people[poor] += 1
    return "Thank You, Sir!"

def main():
    people = [150, 250, 50]
    coins = 150

    while coins:
        give_to_the_poor(people)
        coins -= 1

    print(people)

if __name__ == "__main__":
    main()