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

--===============0877318446081825467==
Content-Type: multipart/signed; protocol="application/pkcs7-signature";
	micalg=sha-256; boundary="------------ms050404060600080801010102"

--------------ms050404060600080801010102
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: quoted-printable

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
>=20
> 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 s=
i
> iar L1, L2 ... pana termini cu lista
> nu e cea mai eficienta metoda, dar cand lista tinde spre infinit
> statistic "galetile" ar fi echilibrate
>=20
> 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=

>=20
> 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=20
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=20
total)

dar m-a lamurit sir Wolf :) daca la liste pastrez atasat si marimea=20
totala din lista, urmatoarele aditii pot sa le fac de ex in punga cea=20
mai mica... e adevarat asta ar implica o gasire de minim pentru fiecare=20
aditie dar nu cred ca e vital.. asa ar duce la o buna aproximare, mai=20
ales ca dupa sortarea initiala, raman cantitati din ce in ce mai mici de =

distribuit intre galeti

Merci!
Adrian


> Alex
>=20
>=20
> On 02-Jul-19 1:36 PM, Adrian Sevcenco wrote:
>> Salut! Am o necesitate interesanta : mi-ar fi ff de folos sa pot
>> imparti o lista de fisiere in sub-colectii __aproximativ__ egale (sa
>> zic o colectie de la 4 la 8k de fisiere in 200 buckets).. problema e
>> ca nu am nici o idee de unde sa incep (ca si algorithm)
>> ca si implementare vad eu cum o fac in bash sau python, dar algoritmul=

>> e problema.
>>
>> Multumesc frumos!!
>> Adrian
>>


--------------ms050404060600080801010102--


--===============0877318446081825467==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
Offtopic mailing list
[email protected]
http://lists.lug.ro/mailman/listinfo/offtopic_lists.lug.ro

--===============0877318446081825467==--