Příspěvky

4621

Server / Re:Třídicí algoritmus pro disková pole

« kdy: 13. 12. 2014, 13:31:38 »

Decision problem (vejde se to do X binů) je NP-complete.
Optimální řešení je strongly NP-hard (tzn. není NP)

Mne porad neni uplne jasny rozdil mezi temihle dvema problemy. Nemel jsem cas se na to poradne podivat kvuli pareni XComu se synem Muzete mi to nekdo nejak polopaticky, ale presne vysvetlit?

Ten prvni problem je predpokladam otazka "Mam mnozinu bucketu a mnozinu predmetu, vejdou se predmety do bucketu?" s odpovedi ano/ne.

A ten druhy problem je teda presne jak? Protoze jestli to je "Jak naskladat predmety do nejmensiho poctu bucketu", tak pak nerozumim tomu, proc bych nemohl pouzit ten decision problem k tomu, abych se ptal "Vejde se to do jednoho? Vejde se to do dvou? atd." - coz by bylo jenom polynomialni rozsireni, takze mi porad neni jasne, jak muze ten problem skocit do jine slozitosti.

4622

Server / Re:Třídicí algoritmus pro disková pole

« kdy: 13. 12. 2014, 01:46:18 »

Tohle je ale problém, kterej tu autor řeší a verdikt zní: "Bin packing is strongly NP-HARD": http://link.springer.com/chapter/10.1007/3-540-29297-7_18

K placenemu Springeru uz nemam pristup a v nahledu to nevidim, ale budu ti verit

ale už vůbec neřeší druhou část zadání:

a pritom zbylo co nejvic volneho mista na konci

Ok, tak to mi asi teda uniklo. Diky za upresneni.

4623

Server / Re:Třídicí algoritmus pro disková pole

« kdy: 12. 12. 2014, 23:07:56 »

To je přeci něco úplně jiného než o čem píšete!

Nevim, asi je nejaka pozdni hodina a neco mi nedochazi, ale je pak teda tohle spatne?

http://www2.informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/bin_packing.pdf - "The Bin Packing problem is NP-complete."

A tohle?

https://people.cs.umass.edu/~barring/cs311/disc/11.html - ukol 1)

Nebo se tady bavime o nejakem jinem problemu, ktery na ty popsane neni redukovatelny?

4624

Studium a uplatnění / Re:Je PHP nutné k uplatnění?

« kdy: 12. 12. 2014, 22:16:23 »

můj názor je, že dnes dělá weby téměř každý. Opravdu bych rád znal názor veřejnosti.

Spatne weby dela kazdy. Dobreho webare je problem sehnat.

4625

Server / Re:Třídicí algoritmus pro disková pole

« kdy: 12. 12. 2014, 22:11:09 »

A jak víte že neexisuje polynomiální algoritmus který ověří správnost řešení?

Ja nevim, skoly nemam, ale overit, ze v kazdem bucketu je soucet velikosti mensi nez velikost bucketu a ze v bucketech jsou fakt vsechny prvky, ktere jsem na zacatku mel, mi neprijde jako polynomialne neresitelny

4626

Server / Re:Třídicí algoritmus pro disková pole

« kdy: 12. 12. 2014, 21:51:21 »

Že se nějaká permutace zdá býti dobrá na začátku, ještě neznamená, že bude dobrá na konci.

Rezani se ale pouziva k tomu, aby se neprohledavala *spatna* reseni, o dobrych to nic nerika. Ja jsem rikal rezat vetve, ktere zarucene *nemuzou* vest k *lepsimu* reseni, nez jake uz mam. Napr. pokud uz jsem nasel reseni s peti buckety a soucasne prochazena vetev jich uz ted potrebuje pet a jeste jsem neumistil vsechno, tak dal proste pokracovat nemusim, protoze vsechna reseni v danem podstromu uz budou zarucene HORSI nez to uz nalezene. Takze zadne dalsi permutace v danem podstromu uz proste neprochazim.

Nakolik je prorezavani efektivni je dany typem tech dat - pro kazdy set bude jinak uspesne.

4627

Server / Re:Třídicí algoritmus pro disková pole

« kdy: 12. 12. 2014, 15:23:53 »

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.

4628

Server / Re:Třídicí algoritmus pro disková pole

« kdy: 12. 12. 2014, 10:06:42 »

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

4629

Server / Re:Třídicí algoritmus pro disková pole

« kdy: 12. 12. 2014, 10:04:29 »

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í.

4630

Server / Re:Raid5 - OS crash

« kdy: 12. 12. 2014, 09:53:49 »

Ciste teoreticky ... prakticky muze to pole byt v haji trebas proto, ze se systemu v poslednim tazeni povedlo ho sejmout.

Jasne. Chtel jsem jenom rict, ze "prvni linux" se nelisi od "druheho linuxu" - u obojiho je potreba (ne)udelat to same. Tim se to lisi treba od bootovani, kde je u spousty distribuci zadratovany UUID, takze jeden linux z disku nabootuje a jiny nenabootuje.

4631

Server / Re:Tridici algoritmus

« kdy: 12. 12. 2014, 09:38:15 »

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ě.

4632

Server / Re:Tridici algoritmus

« kdy: 12. 12. 2014, 09:26:50 »

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

4633

Hardware / Re:Spotřeba elektřiny PC vs. notebook

« kdy: 11. 12. 2014, 18:02:13 »

Pořád máme vysokou spotřebu a musím zjistit, kde je ten "únik" Jde to dost to peněz.

Trochu do měření spotřeby dělám a můžu myslím celkem zodpovědně říct, že zjistit, který spotřebič člověku žere v celku nejvíc peněz, rozumně nejde jinak, než spotřebu trvale měřit - nerozhoduje totiž jenom kolik jednotlivé spotřebiče žerou, ale hlavně jak často běží. A to většinou od stolu neodhadneš.

Nejjednodušší příklad je lednička - má třeba půl hodiny spotřebu 80W a pak hodinu 0. Kolik ti to udělá na celkovém účtu fakt nezjistíš jinak než že si tyhle čísla změříš. Můžeš kouknout na náš produkt: https://app.energomonitor.cz/login?username=demoEN

(Roote, sorry za neplacenou reklamu, ale je to odpověď přesně na dotaz, tak to snad neva)

4634

Server / Re:Raid5 - OS crash

« kdy: 11. 12. 2014, 17:47:05 »

a raid je pak mozne znovu obnovit a data sosnout?

Nic není potřeba obnovovat. RAID prostě používáš na druhém Linuxu úplně stejně jako jsi ho používal na prvním.

4635

Odkladiště / Re:Geekovský dárek k letošním Vánocům

« kdy: 11. 12. 2014, 15:00:41 »

Hm, tak co sehnat další ženu?

Myslíš jako RAID-0?