Fiktives Szenario damit mir vielleicht jemand sagen kann wie solche
Algorithmen genannt werden - für eine ausschweifende google-Suche
ich habe eine Datenquelle aus der ich per int32 id einen Text
unterschiedlicher Länge bekommen kann
z.B.
zu 1 bekomme ich "hallo wie geht es dir"
zu 2 bekomme ich "du du"
zu 3 bekomme ich "tralala"
usw.
viele tausend ids sind vorhanden, zu jeder id ist vorher klar wie viele
Bytes der Text im Ergebnis enthält
der Query-Block hat eine feste länge in den ich 20 ids stellen kann
(d.h. 20*sizeof(int32) = 80 bytes)
der Result-Block hat eine feste Länge die dem Query Block entspricht
und in dem die Texte serialisiert geliefert werden
der Query oder Result-Block darf durch die angebenen ids nicht zu gross
werden, müssen also beide im 80 byte Bereich bleiben (es gibt keine
Texte die größer sind als 80 Bytes)
die Anzahl an Query(aka Result)-Blöcken ist entscheident für die
Performanz d.h. wenig Queries = hohe Geschwindigkeit, was mein Ziel wäre
jetzt möchte ich hunderte von ids möglichst schnell Abfragen:
einfache(langsamste) Lösung:
jede id einzeln Abfragen
bessere(bisschen schneller) Lösung:
die Query-Blöcke so lange mit ids auffüllen
bis der Query oder Result-Block voll ist, dann den nächsten Query
erzeugen
bist die id Liste durch ist
optimale Lösung:
die ids werden so auf Query-Blöcke verteilt das eine möglichst kleine
Menge an Queries ensteht (vergleichbar mit Schnittmuster platzsparend
verteilen)
Wie nennt man solche Algorithmen, Suchbegriffe für google?
https://de.wikipedia.org/wiki/Beh%C3%A4lterproblem
mit Approximationsalgorithmus First Fit Decreasing:
"
Sortiere die Objekte nach absteigendem Gewicht
Füge die Objekte der Reihe nach ein,
sodass jedes in den ersten Behälter gegeben wird, in dem noch genug
Platz ist.
Falls in keinem der bereits geöffneten Behälter genügend Platz ist,
öffne einen neuen.
"
Rucksack und Transport Problem ist schon mal eine gute Richtung
Meine Texte sind dann die Güter die mit möglichst wenig Transportern
geliefert werden sollen, oder?
Kleinere Beschreibung des Szenarios:
n Gewichte (1-80Kg) sollen auf so wenig Rucksäcke wie möglich verteilt
werden
Einschränkung: Jeder Rucksack kann maximal 20 Gewichte aufnehmen und
eine Maximallast von 80Kg tragen
Peter M. schrieb:> Da hilft der kleine Gauss:>> 1x 80 kg,>> Dann 1+79, 2+78, 3+77, 4+76 ... und 40 solo.
Kapier ich nicht:
z.B. habe ich diese Gewichte(kg): 5,80,34,2,2,7,8,9,40
Wuerde bei mir diese Rucksäcke ergeben
5+34+40
80
2+2+7+8+9
Hallo cppbert,
cppbert schrieb:> Peter M. schrieb:>> Da hilft der kleine Gauss:>>>> 1x 80 kg,>>>> Dann 1+79, 2+78, 3+77, 4+76 ... und 40 solo.>> Kapier ich nicht:
Ich habe Deine Beschreibung nicht so verstanden, wie Du sie verstanden
hast.
:)
>> z.B. habe ich diese Gewichte(kg): 5,80,34,2,2,7,8,9,40>> Wuerde bei mir diese Rucksäcke ergeben>> 5+34+40> 80> 2+2+7+8+9
Du meinst in Wirklichkeit n ganzzahlige Zufallszahlen aus dem Intervall
[1;80] (mit oder ohne zurücklegen?, das heißt ob sich Zufallszahlen
wiederholen können).
Jetzt brauchst Du nur noch ein Kostengewichte, die Dir sagen, was ein
Behälter kostet (z.B. ein Hin- und Rückflug nach Wuhan) und was ein
Probiervorgang kostet. Dann siehst Du ja, wie groß die Kosten (und
Ersparnisse!) werden, wenn es darum geht, Helmuts triviale Heuristik zu
schlagen.
> Ich habe Deine Beschreibung nicht so verstanden, wie Du sie verstanden> hast.> :)
Weil die Erklärung schlecht war? :(
> Du meinst in Wirklichkeit n ganzzahlige Zufallszahlen aus dem Intervall> [1;80] (mit oder ohne zurücklegen?, das heißt ob sich Zufallszahlen> wiederholen können).
Mit wiederholung von den Zufallszahlen: 5,6,5,7,7 ist also Ok
> Jetzt brauchst Du nur noch ein Kostengewichte, die Dir sagen, was ein> Behälter kostet (z.B. ein Hin- und Rückflug nach Wuhan) und was ein> Probiervorgang kostet. Dann siehst Du ja, wie groß die Kosten werden,> wenn es darum geht, Helmuts triviale Heuristik zu schlagen.
Mehr Informationen gibt es in meinem Szenario nicht - es geht wirklich
nur um die optimale Verteilung der Gewichte (aka Hanteln)
Peter M. schrieb:> Helmuts triviale Heuristik
Das war ein Zitat aus dem Wikipedia-Artikel, sorry falls das nicht
ersichtlich war. Noch ein Zitat: "Johnsons Approximationsalgorithmus
First Fit Decreasing löst das Problem in polynomieller Zeit mit einer
scharfen asymptotischen Gütegarantie von 11/9"
Helmut H. schrieb:> Peter M. schrieb:>> Helmuts triviale Heuristik>> Das war ein Zitat aus dem Wikipedia-Artikel, sorry falls das nicht> ersichtlich war.
Doch, das war ersichtlich, aber von mir faul und unpräzise abgekürzt.
cppbert schrieb:> Kapier ich nicht:>> z.B. habe ich diese Gewichte(kg): 5,80,34,2,2,7,8,9,40>> Wuerde bei mir diese Rucksäcke ergeben>> 5+34+40> 80> 2+2+7+8+9
kommt auf die Wertung an..
eventuell ist 2+2+34+40, 80 und 5+7+8+9
weil so kein Rucksack 5 Gewichte hat besser..
Warum ist das Wichtig?
Weil TO nach query strings fragt
und strings haben im concatenate häufig einen node count penalty von
plus eins
(wir sagen auch gerne Leerzeichen dazu ;))
man kann also eben eventuell NICHT
16 5 kg Gewichte in einen 80kg Rucksack packen
da 15 von ihnen einen +1 Längenmodifikator haben (Leerzeichen)
der Algorithmus sollte (sofern Leerzeichen benötigt werden)
diese auch zählen.
cppbert schrieb:> zu 1 bekomme ich "hallo wie geht es dir"> zu 2 bekomme ich "du du"> zu 3 bekomme ich "tralala"
es macht also einen Unterscheid ob man bei 1+2
"hallo wie geht es dirdu du" oder
"hallo wie geht es dir du du" als query braucht
(oder weil es vielleicht wahrscheinlicher ist.."|" ;))
'sid
sid schrieb:> Warum ist das Wichtig?> Weil TO nach query strings fragt
ich hab das ganze auf Hantel-Gewichte und Rucksäcke reduziert - damit
solche Details wirklich nicht relevant sind
Hantel-Gewicht = alle Daten (mit Leerzeichen) :)
naja dasselbe glt aber für Hantelscheiben in Rücksäcken,
die sind ja nunmal unterschiedlich gross bei unterschiedlichem Gewicht,
und in den äusseren Abmessungen ist eine 10kg Scheibe kleiner als zwei
5kg Scheiben (um's überzählige Mittelloch mindestens.. ein Leerzeichen
quasi ;))
Aber gut, wenn Du keine Trennzeichen mit concatenieren musst,
dann klar.. alles gut .. weitermachen
falls doch, denk an deren anzahl und falls Du C-strings benutzt den
string terminator ;)
Quasi als Merksatz:
"ich habe hier ganz schnell achtzig byte vollgeschrieben und dabei
zweiundneunzig verbraucht\0"
ich weiss.. man verbraucht keine aber ich musste ja auf 80 und
zweiundneunzig kommen, da kann man schonmal freier formulieren müssen ;)
Mahlzeit
'sid
sid schrieb:> naja dasselbe glt aber für Hantelscheiben in Rücksäcken,> die sind ja nunmal unterschiedlich gross bei unterschiedlichem Gewicht,
Das Volumen(Größe) kann man in meinem Beispiel ignorieren - vergessen
hin zu schreiben :|
Ich hab ein Beispiel gefunden das passt
https://stackoverflow.com/questions/48866506/binpacking-multiple-constraints-weightvolume
Ich brauche eine Lösung ohne Solver aber als Testgrundlage um dann die
Qualität meiner eigenen Implementierung zu beurteilen ist das denke ich
schon mal sehr wertvoll
cppbert schrieb:> Ich brauche eine Lösung ... als Testgrundlage
Hänge doch mal deine Testdaten als Textdatei (nur die Stringlängen
inklusive Terminator) an, vielleicht finden wir eine gute Lösung...
Mit deinen Daten oben
[40, 34, 5]
[80]
[9, 8, 7, 2, 2]
Anzahl 3 Free 53
hm A* (A star) könnte klappen.. wenn man die value und penalties
sinnvoll setzt
zB indem Du alle text-bausteine der Datenquelle
in Knoten ihrer Stringlänge setzt,
dem Knoten dann die Gesamtzahl als Wert gibst.
die Stringlänge ist deine "Distanz zum Ziel"
verlässt man einen Knoten, wird der Wert um eins verringert (man hat ja
einen string benutzt)
man kann sich sogar den Pfad (die strings) ausspucken lassen.
Hat nun ein Pfadsucher sein Ziel erreicht
(also 80 byte länge ud möglichst viele Punkte)
sind seine Worte schon aus den knoten gelöscht und man speichert den
Pfad
der nächste Pfadsucher hat dann etwas weniger Auswahl...
und irgendwann hat man nurnoch wenige Knoten mit Inhalt, leere knoten
erzeugen keine Stringverlängerung und haben den Wert null.
der letzte pfadsucher hat dann ggf nur 8 oder neun punkte generiert weil
nurnoch ein oder zwei strings übrig blieben...
aber viel effizienter wirst Du es kaum hinbekommen
'sid
Helmut H. schrieb:> cppbert schrieb:>> Ich brauche eine Lösung ... als Testgrundlage> Hänge doch mal deine Testdaten als Textdatei (nur die Stringlängen> inklusive Terminator) an, vielleicht finden wir eine gute Lösung...
wie ich schon geschrieben habe, es ist ein...
> Fiktives Szenario damit mir vielleicht jemand sagen kann wie solche> Algorithmen genannt werden
es gibt keine Terminatoren :)
und auch die Hanteln und Rucksäcke sind nur ein Beispiel - die Zahlen
damit man was handfesteres hat
Ich denke das Hantel/Rucksack-Beispiel ist einfacher:
-Es gibt n Hanteln (Mit Zufallsgewicht zwischen 1-80Kg)
-Ein Rucksack kann maximal 80Kg aufnehmen
-Ein Rucksack kann maximal 20 Hanteln aufnehmen (Volumen/Größe
unrelevant)
-Hantel-Gewichte können mehrfach in einem Rucksack vorkommen - also z.B.
3 x 2Kg
Ziel: für eine Menge aus Hanteln z.B. 200 Stück herausbekommen wie man
die verteilen muss damit die geringste Anzahl an Rucksäcken gebraucht
wird
cppbert schrieb:> Ziel: für eine Menge aus Hanteln z.B. 200 Stück> herausbekommen wie man die verteilen muss damit> die geringste Anzahl an Rucksäcken gebraucht> wird
???
Was an "bin packing problem" ist Dir unklar?
Egon D. schrieb:> cppbert schrieb:>>> Ziel: für eine Menge aus Hanteln z.B. 200 Stück>> herausbekommen wie man die verteilen muss damit>> die geringste Anzahl an Rucksäcken gebraucht>> wird>> ???>> Was an "bin packing problem" ist Dir unklar?
Das würde ich ausprobieren - eben mit Erweiterung auf die 20 Hanteln
maximal
cppbert schrieb:>> Was an "bin packing problem" ist Dir unklar?>> Das würde ich ausprobieren - eben mit Erweiterung> auf die 20 Hanteln maximal
Ach so... mea culpa.
Diese Beschränkung ist im originalen "bin packing
problem" nicht enthalten; Du hast Recht.
Man müsste sich mal überlegen, ob diese Beschränkung
überhaupt wesentlichen Einfluss hat. Wenn das Gros
Deiner nachrichten länger als 4 Zeichen ist (was ich
annehme), wird die Beschränkung der Anzahl der
Nachrichten je Bin selten zum Tragen kommen. Wenn es
keine Nachrichten gibt, die kürzer als 4 Zeichen sind,
sogar überhaupt nie.
Number of bins required in First Fit Decreasing : 4
(aus dem Video)
um eine "optimiale" Packdichte zu bekommen könnte man noch
bin[2] 100 in bin[3] verschieben
und von bin[3] 65+40 in bin[2] schieben
damit wäre dann auch der bin[2] auf 400
und bin[3] wäre dann auf 380
vielleicht nocht mit "Best Fit Decreasing" optimierbar aber vielleicht
geht es auch nicht besser und ist eh sehr stark von den Gewichten
abhängig wie gut man verdichten kann
