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?
Beitrag #6222305 wurde vom Autor gelöscht.
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?
Sieht auch ein bisschen aus wie das Multiple Knapsack Problem, nur die Constraints sind anders
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
Da hilft der kleine Gauss: 1x 80 kg, Dann 1+79, 2+78, 3+77, 4+76 ... und 40 solo.
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.
:
Bearbeitet durch User
> 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.
von: https://www.tutorialspoint.com/bin-packing-problem-minimize-number-of-used-bins-in-cplusplus die Implementierung genommen und die volumen-einschränkung per bin + liste der Gewichte die in bin sind eingebaut sieht mal nicht so schlecht aus
cppbert schrieb: > von: > https://www.tutorialspoint.com/bin-packing-problem-minimize-number-of-used-bins-in-cplusplus > > die Implementierung genommen und die volumen-einschränkung per bin + > liste der Gewichte die in bin sind eingebaut > > sieht mal nicht so schlecht aus ist nicht die schönste Implementierung aber ein guter Start Beispiel-Ausgabe:
1 | weight1: |
2 | 42 39 80 74 45 47 31 59 3 17 |
3 | bin_rem[0]: 0, adds: 1 |
4 | weight[0]: 80 |
5 | bin_rem[1]: 3, adds: 2 |
6 | weight[1]: 74 |
7 | weight[9]: 3 |
8 | bin_rem[2]: 4, adds: 2 |
9 | weight[2]: 59 |
10 | weight[8]: 17 |
11 | bin_rem[3]: 2, adds: 2 |
12 | weight[3]: 47 |
13 | weight[7]: 31 |
14 | bin_rem[4]: 35, adds: 1 |
15 | weight[4]: 45 |
16 | bin_rem[5]: 38, adds: 1 |
17 | weight[5]: 42 |
18 | bin_rem[6]: 41, adds: 1 |
19 | weight[6]: 39 |
20 | Number of bins required in First Fit Decreasing : 7 |
Jetzt würde ich noch das Solver (https://stackoverflow.com/questions/48866506/binpacking-multiple-constraints-weightvolume) basierte Beispiel in ein paar hundert Randomszenarien dagegen kämpfen lassen, mal schauen was da so raus kommt
noch ein Beispiel wo die Packdichte nicht ganz perfekt ist: Beispiel von hier: http://www.youtube.com/watch?v=7QBwgI7h-zw&t=9m29s zum Online-Spielen: cpp.sh/57zkx Ausgabe:
1 | weight1: |
2 | 200 140 120 120 110 100 100 90 80 75 75 70 65 60 60 50 40 25 |
3 | bin_rem[0]: 0 (added: 3) |
4 | weight1 |
5 | [0]: 200 |
6 | [1]: 140 |
7 | [13]: 60 |
8 | complete: 400 |
9 | bin_rem[1]: 0 (added: 4) |
10 | weight1 |
11 | [2]: 120 |
12 | [3]: 120 |
13 | [4]: 110 |
14 | [15]: 50 |
15 | complete: 400 |
16 | bin_rem[2]: 5 (added: 5) |
17 | weight1 |
18 | [5]: 100 |
19 | [6]: 100 |
20 | [7]: 90 |
21 | [8]: 80 |
22 | [17]: 25 |
23 | complete: 395 |
24 | bin_rem[3]: 15 (added: 6) |
25 | weight1 |
26 | [9]: 75 |
27 | [10]: 75 |
28 | [11]: 70 |
29 | [12]: 65 |
30 | [14]: 60 |
31 | [16]: 40 |
32 | complete: 385 |
33 | 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
cppbert schrieb: > vielleicht nocht mit "Best Fit Decreasing" optimierbar Best Fit ändert nichts an der Packdichte - gleiches Ergebnis
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.