Re: programming::algo::bash - split list in buckets

On 02-Jul-19 3:32 PM, Adrian Sevcenco wrote:
> On 7/2/19 3:12 PM, Alex 'CAVE' Cernat wrote:
>> deci sa zicem ca ai niste tupli de genul nume fisier, weight (sau
>> lungime) si vrei sa generezi n liste de tupli de astia, astfel incat
>> suma acelor weight-uri sa fie cat de cat pe acolo
>>
>> cea mai simpla metoda (nu insa si cea mai eficienta) ar fi urmatoarea:
>> - ordonarea listei dupa lungime, descrescator
>> - si apoi mulinezi in lista, de genul L1, L2, ... Ln, Ln, ..., L2, L1 si
>> iar L1, L2 ... pana termini cu lista
>> nu e cea mai eficienta metoda, dar cand lista tinde spre infinit
>> statistic "galetile" ar fi echilibrate
>>
>> o alta varianta mai eficienta ar fi o varianta de problema rucsacului
>> (desi aia e alta mancare de peste pana la urma)
>> ceva de genul: faci suma weight-urilor, faci o medie per fiecare bucket,
>> si apoi incepi sa gasesti combinatii de tz elemente din lista astfel
>> incat suma weight-urilor sa fie cat mai apropiat de media calculata
>> si aici poate sa-ti dea cu virgula rau daca distributia este
>> dezechilibrata, dar are mai multe sanse de reusita decat cea de mai sus
>>
>> de obicei, cu cat dai mai multe detalii cu atat sunt mai multe sanse sa
>> gasim o solutie cat mai aproape de ce vrei tu ...
> so fisierele astea le procesez pe un cluster in batchuri si ramanea o
> long-lived tail cu joburile care aveau batchul cu fisierele cele mai mari
> in setul curent sunt 7731 fisiere cu marimi intre 357k si 931M (3.9T
> in total)
>
> dar m-a lamurit sir Wolf :) daca la liste pastrez atasat si marimea
> totala din lista, urmatoarele aditii pot sa le fac de ex in punga cea
> mai mica... e adevarat asta ar implica o gasire de minim pentru
> fiecare aditie dar nu cred ca e vital.. asa ar duce la o buna
> aproximare, mai ales ca dupa sortarea initiala, raman cantitati din ce
> in ce mai mici de distribuit intre galeti
>
> Merci!
> Adrian

ar mai fi o varianta relativ usor de implementat, pe tipul distributed
workers, si un server de mq (rabbitmq spre exemplu, ai si client in
bash), sau altceva de cozi
din procesul master iei si bagi job-uri in coada; fiecare worker (care
trebuie pre-pornit) ia un job din coada, il prelucreaza, ia urmatorul,il
prelucreaza samd
in functie de statistica job-urilor iarasi s-ar putea sa fie nu cel mai
eficient (ca e FIFO)
bine, daca e pe aceeasi masina atunci poti direct cu multiple fork si
wait direct din bash, si nu ai nevoie de cozi, tii "coada" intr-un array
in bash
insa la fel, iar nu e eficient, daca vrei sa ai toate sansele ca se
termina toate in aproximativ acelasi timp deja nu mai e simpla coada,
deja trebuie niste algoritmi mai speciali, cam ce daduse si Wolfy
poate daca totusi sortezi lista respectiva descrescator inainte de a da
drumul la job-uri obtii in cele mai multe cazuri o eficienta destul de
mare fara sa te complici cu jde algoritmi (dar intri pe taramul de
statistica pura)

Alex