Třídicí algoritmus pro disková pole

[Karel.hu]

Zdravim mistni matematiky.

Mam hromadu virtualnich serveru, kazdy jinak velky, o velikostech X₁, X₂, X₃, X₄... az X_n a datova uloziste, vsechna stejne velka, o velikosti Y. Chci virtualni stroje poskladat vedle sebe tak, aby idealne vyplnily vsechna uloziste (zbylo co nejmin volneho mista na kazdem ulozisti) a pritom zbylo co nejvic volneho mista na konci, idealne aby se mi nejake uloziste uplne uvolnilo.

Seradim X podle velikosti. Vezmu nejvetsi X, zkusim k nemu pricist druhe nejvetsi X a zkusim se vejit do Y. Kdyz se mi tam druhe nevejde, zkusim treti nejvetsi X, ctvrte nejvetsi X a tak postupne pricitam mensi a mensi az k nejmensimu a porad zkousim, jestli se jeste vejdu do Y. Pak vezmu zbyla X a zkusim to znova od nejvetsiho k nejmensimu a postupne tak vyplnit dalsi Y a tak dal, az mi dojdou X.

Metoda jednoducha, ale idealni? Ja jsem nematematik. Potrebuju za pochodu prekopat rozlozeni diskovych poli a premyslim, jak to k sobe kratkodobe nahnacat, aby se mohlo ve zbyvajici casti pracovat. Pak dal uz budu s obsahem poli hrat hanojske veze.

Diky predem.

[Reklama]

[Jenda]

https://en.wikipedia.org/wiki/Knapsack_problem

[Bla]

Snad ne sám Mr.Uloz to? 

Pokud ano, tak tohle by zajímalo asi 100+1 člověda!

[Jimm]

Lol, jako že uloz.to jede na virtuálech? 
Sry ale sedí tam pár kluků a kdyby si chodili pro rady na root, těžko by pořád vydělávali a dostali se tak daleko. 

[Mirek Prýmek]

https://en.wikipedia.org/wiki/Knapsack_problem

Klasickej baťoh to není. Pokud by postupoval postupně po jednotlivých batozích, tak imho nutně nedostane optimální řešení.

Pro OP: ne že bych chtěl snižovat snahu o optimalizaci, ale pokud těch virtuálů nemáš milion a nepočítáš rekonfiguraci každých sto milisekund, tak si úplně v klidu vystačíš s bruteforce řešením - prostě si z těch virtuálů udělej všechny permutace a v tomhle pořadí je (virtuálně) naláduj do úložišť uspořádaných v jakémkoli neměnném pořadí - pokud se už virtuál do úložiště nevejde, dáš ho už do následujícího. K mírné optimalizaci pak můžeš použít nějaký stupidní prořezávání - např. pokud přetečeš do baťohu s číslem větším než na kolik batohů už jsi našel řešení, nepokračuješ. Tímhle způsobem musíš být schopnej to spočítat pro tisíce strojů během zlomku sekundy.

Vzhledem k tomu, že ten problém je (odhaduju) určitě NP-úplný, bude rozdíl mezi tímhle stupidním řešením a optimálním algoritmem prakticky stejně zanedbatelný, takže bych si s tím vůbec hlavu nelámal

[Reklama]

[Mirek Prýmek]

Tímhle způsobem musíš být schopnej to spočítat pro tisíce strojů během zlomku sekundy.

Pardon, tisíce určitě ne, faktoriál je svině ale pro nějaké rozumné množství určitě.

[mr_x]

Prymek: nevim nevim - faktorial roste o dost rychleji nez exponencialni funkce

zajimavy by mohlo byt vyzkouset nejaky evolucni algoritmus.

[Mirek Prýmek]

Prymek: nevim nevim - faktorial roste o dost rychleji nez exponencialni funkce

Jasně. Ale rozhodující je, jakou část prostoru vážně projdeš a jaká se odřízne. Pokud budeš permutace generovat postupně, budeš tímpádem procházet strom a můžeš jedním krokem odříznout obrouvskou část prostoru.

Taky si můžeš pomoct nějakou další stupidní heuristikou - jako např. že si předem spočítáš, pod jaký číslo se zaručeně nedostaneš a jakmile najdeš řešení jenom o x horší, skončíš, protože takhle ti to prostě stačí. "Inženýrských" možností je spousta

zajimavy by mohlo byt vyzkouset nejaky evolucni algoritmus.

Buď, anebo simulované žíhání. Tyhle metody se AFAIK na tyhle typy problémů používají.

[Mirek Prýmek]

Ale rozhodující je, jakou část prostoru vážně projdeš a jaká se odřízne.

...a samozřejmě hlavně jde o to, o jakých číslech se bavíme. Jestli je těch virtuálů deset, tak není co řešit že jo

[Karel.hu]

Prakticky to bude vyreseno, jak jsem psal na zacatku - asi stupidni, ale rychle a snadne reseni. Jde jen o uklid pred rekonfiguraci pole a jedna se o pouhych 105 stroju. Jen me zajimalo (ciste teoreticky), jak se podobna uloha resi "spravne", protoze, jak rikam, nejsem matematik.

V kazdem pripade diky.

[randolf]

Jedna se o tzv. Bin-packing problem (viz wiki).
Jedine mne zname algoritmy pro exaktni optimalni reseni jsou:
- MTP (napr. strana 237/17/ zde http://www.or.deis.unibo.it/kp/Chapter8.pdf)
- Exhaustive search (brute force) - pro pocet VM < 1000 je to asi to nejrychlejsi, co muzes udelat - zkusit si vsechny kombinace. Sice to nejakou dobu pobezi, ale neni to tak hrozne.

Randolf

[randolf]

https://en.wikipedia.org/wiki/Knapsack_problem

Klasickej baťoh to není. Pokud by postupoval postupně po jednotlivých batozích, tak imho nutně nedostane optimální řešení.

Pro OP: ne že bych chtěl snižovat snahu o optimalizaci, ale pokud těch virtuálů nemáš milion a nepočítáš rekonfiguraci každých sto milisekund, tak si úplně v klidu vystačíš s bruteforce řešením - prostě si z těch virtuálů udělej všechny permutace a v tomhle pořadí je (virtuálně) naláduj do úložišť uspořádaných v jakémkoli neměnném pořadí - pokud se už virtuál do úložiště nevejde, dáš ho už do následujícího. K mírné optimalizaci pak můžeš použít nějaký stupidní prořezávání - např. pokud přetečeš do baťohu s číslem větším než na kolik batohů už jsi našel řešení, nepokračuješ. Tímhle způsobem musíš být schopnej to spočítat pro tisíce strojů během zlomku sekundy.

Vzhledem k tomu, že ten problém je (odhaduju) určitě NP-úplný, bude rozdíl mezi tímhle stupidním řešením a optimálním algoritmem prakticky stejně zanedbatelný, takže bych si s tím vůbec hlavu nelámal

+1

[e3k]

ano bin packing problem:
http://en.wikipedia.org/wiki/Bin_packing_problem

pozry do software nieco najdes.

[randolf]

zajimavy by mohlo byt vyzkouset nejaky evolucni algoritmus.

Buď, anebo simulované žíhání. Tyhle metody se AFAIK na tyhle typy problémů používají.

Ani jedno bych nedoporucil.
- Pobezi to v tomto pripade zbytecne dlouho (velky overhead navstivenim mnohokrat stejneho reseni
- Nezarucena optimalita reseni... a pokud to optimalni byt nemusi, pak opravdu bude fungovat ten jednoduchy algoritmus ktery autor naznacil v prvnim prispevku
- Dost pracne na implementaci
- V pripade simulovaneho zihani to nejspis skonverguje do nejakeho lokalne optimalniho reseni, ktere ale bude daleko od globalniho optima (ale to je jen intuitivni hodnoceni, mozna by to slo nejak vyresit)

[Mirek Prýmek]

Ani jedno bych nedoporucil.
- Pobezi to v tomto pripade zbytecne dlouho (velky overhead navstivenim mnohokrat stejneho reseni
- Nezarucena optimalita reseni... a pokud to optimalni byt nemusi, pak opravdu bude fungovat ten jednoduchy algoritmus ktery autor naznacil v prvnim prispevku
- Dost pracne na implementaci

Myslel jsem to jako metodu druhe volby - pokud by tech virtualu bylo tolik, ze brute-force by byl neumerne narocny a timpadem by se clovek smiril se suboptimalnim resenim...

Ten Karlem zmineny postup by myslim pro nektera data mohl davat docela slabe vysledky. Mozna by bylo lepsi udelat neco na tenhle zpusob: 1) odhadnu, kolik budu zhruba potrebovat bucketu 2) virtualy seradim podle velikosti 3) postupne davam jednotlive virtualy do bucketu *poporade* - nejvetsi do prvniho, druhy nejvetsi do druheho atd. 3) jestli se mi takhle nepodari virtualy rozprostrit, zvysim pocet bucketu o jeden a jedu cely znovu

Tohle by myslim mohlo davat docela dobre vysledky zvlast pokud jsou buckety stejne velke.

- V pripade simulovaneho zihani to nejspis skonverguje do nejakeho lokalne optimalniho reseni, ktere ale bude daleko od globalniho optima (ale to je jen intuitivni hodnoceni, mozna by to slo nejak vyresit)

AFAIK se tam da pridat nahoda, ktera resenim obcas "zatrese" - stejne jako u GA.