Fair distribution problem - T-SQL

perich · 24.04.2015., 20:08

Problem bih ja trebao rijesiti kroz T-SQL, ali bitnija mi je logika, pa bi ja oko nje mogao graditi query.

Radi se o slijedecem, koristit cu izmisljen scenarij.

Imam jednu veliku tablicu u kojoj se nalazi 1000 redova, sa dva stupca, ID i vrijednost.

Cilj je distribuirati ID-jeve u 5 skupina, na način da se u svakoj skupini nalazi podjednak broj ID-jeva, i da je ukupna vrijednost svake grupe opet podjednaka. Tolerancija je moguća, od nule pa do recimo 10%. Radi jednostavnosti, uzmimo da nema ekstrema u vrijednostima nego da su svi u range-u od recimo 100-500.

Ideje?

rodney · 27.04.2015., 22:27

Hm, za*ebano

Mislim da je to prije "k-way (ili multiway) number partitioning problem" nego
"fair division".

Mislim da će ti tu t-sql biti veći problem od samog algoritma. Naime algoritmi postoje, treba ih samo implementirati, ali iterativni algoritmi, rekurzije ili pretraživanje stabla rješenja u sqlu mi ne zvuče primamljivo.
par linkova:
https://www.aaai.org/ocs/index.php/I...ewFile/625/705
https://www.aaai.org/ocs/index.php/I...File/3364/3574
http://www.mysmu.edu/faculty/kyriakos/IJCAI11.pdf
http://www.cs.uic.edu/pub/Isaim2014/..._Korf_etal.pdf

Dalje, za odabir algoritma je vrlo bitno koliko je tvoj izmišljeni scenarij izmišljen, a koliko stvaran. Tu prvenstveno mislim na broj particija. Da li će u praksi taj broj biti fiksan? Isto tako, toleranciju je teško garantirati. Eventualno sa nekim iterativnim algoritmom, da ne staje dok nije u tih 10%, ali i tu moraš često izmišljati nešto da ne zapneš u lokalnim ekstremima.

Evo našao sam i neki tekst o "bin packing" problemu u sql-u:
https://www.simple-talk.com/sql/t-sq...blems-the-sql/
koji bi mogao poslužiti.

"par minuta kasnije" ...

http://aprogrammerwrites.eu/?p=896
http://aprogrammerwrites.eu/?p=878
http://aprogrammerwrites.eu/?p=803

Ne odustaj, zadnji link je najbliže onom što ti treba. Idući koji nađeš će bit još bolji.

Bubba · 27.04.2015., 22:35

@OP, ne kuzim zasto bi se patio s necim ovakvim ako imas 1.000.000 redova, a kamo li 1.000...

To bi stvarno trebala biti bezobrazno ogromna i kompleksna tabela da se ubijas s necim ovakvim, barem IME na PgSQL.

rodney · 27.04.2015., 22:50

Bubba ti si jedan od onih prodavača..
Ja kažem: "Imaš m6 maticu?"
On kaže: "Za šta ti treba?"

Bubba · 27.04.2015., 23:49

Malo ti je lose usporedba.

Moja percepcija je ta da ako je dosao na forum pitati za ovakvu nekakvu abominaciju, gotovo sigurno mu ili ne treba ili se moze odigrati jednostavnije. Nista vise.

A kao sto rekoh, primjer koji je dao je daleko od necega sto bi se povecano za redove velicine isplatilo zajebavati ovako.

rodney · 28.04.2015., 07:24

https://rohitrohan09.files.wordpress...on-cartoon.jpg

perich · 06.05.2015., 08:42

Evo za pocetak, hvala na predlozenim linkovima, proucit cu to malo pa da vidim sto i kako.

Inace, ne radi se o "nepotrebnoj" stvari. Naime, na poslu imamo potrebu angažirati određene vanjske suradnike, no kako bi mogli procijeniti efikasnost svakog pojedinog, a bez da se bilo koji od njih "osjeća oštećen" radi toga što je dobio manje taskova, ili taskove manje vrijednosti, potrebno je te taskove "fairly" distribuirati.

Radi se o financijskom sektoru, tako da su i "fairly" i "taskovi" izraženi u nekoj valuti i iznosu koji je apsolutno usporediv s drugima (znaci termin koji sam koristio, "task manje vrijednosti" nije relativan i podlozan subjektivnoj procjeni).

24.04.2015., 20:08	#1
perich I hate mondays.......... Datum registracije: Nov 2002 Lokacija: Zagreb - Zaprešić Postovi: 1,524	Fair distribution problem - T-SQL Problem bih ja trebao rijesiti kroz T-SQL, ali bitnija mi je logika, pa bi ja oko nje mogao graditi query. Radi se o slijedecem, koristit cu izmisljen scenarij. Imam jednu veliku tablicu u kojoj se nalazi 1000 redova, sa dva stupca, ID i vrijednost. Cilj je distribuirati ID-jeve u 5 skupina, na način da se u svakoj skupini nalazi podjednak broj ID-jeva, i da je ukupna vrijednost svake grupe opet podjednaka. Tolerancija je moguća, od nule pa do recimo 10%. Radi jednostavnosti, uzmimo da nema ekstrema u vrijednostima nego da su svi u range-u od recimo 100-500. Ideje?

27.04.2015., 22:27	#2
rodney only fool, not a horse Moj komp Datum registracije: Apr 2008 Lokacija: near zgb Postovi: 1,276	Hm, za*ebano Mislim da je to prije "k-way (ili multiway) number partitioning problem" nego "fair division". Mislim da će ti tu t-sql biti veći problem od samog algoritma. Naime algoritmi postoje, treba ih samo implementirati, ali iterativni algoritmi, rekurzije ili pretraživanje stabla rješenja u sqlu mi ne zvuče primamljivo. par linkova: https://www.aaai.org/ocs/index.php/I...ewFile/625/705 https://www.aaai.org/ocs/index.php/I...File/3364/3574 http://www.mysmu.edu/faculty/kyriakos/IJCAI11.pdf http://www.cs.uic.edu/pub/Isaim2014/..._Korf_etal.pdf Dalje, za odabir algoritma je vrlo bitno koliko je tvoj izmišljeni scenarij izmišljen, a koliko stvaran. Tu prvenstveno mislim na broj particija. Da li će u praksi taj broj biti fiksan? Isto tako, toleranciju je teško garantirati. Eventualno sa nekim iterativnim algoritmom, da ne staje dok nije u tih 10%, ali i tu moraš često izmišljati nešto da ne zapneš u lokalnim ekstremima. Evo našao sam i neki tekst o "bin packing" problemu u sql-u: https://www.simple-talk.com/sql/t-sq...blems-the-sql/ koji bi mogao poslužiti. "par minuta kasnije" ... http://aprogrammerwrites.eu/?p=896 http://aprogrammerwrites.eu/?p=878 http://aprogrammerwrites.eu/?p=803 Ne odustaj, zadnji link je najbliže onom što ti treba. Idući koji nađeš će bit još bolji. __________________ "I intend to live forever. So far, so good." job security - example

27.04.2015., 22:35	#3
Bubba E Pluribus UNIX Moj komp Datum registracije: Oct 2002 Lokacija: M82 Postovi: 6,543	@OP, ne kuzim zasto bi se patio s necim ovakvim ako imas 1.000.000 redova, a kamo li 1.000... To bi stvarno trebala biti bezobrazno ogromna i kompleksna tabela da se ubijas s necim ovakvim, barem IME na PgSQL. __________________ Programer Rok od dva mjeseca u stvari znači četiri, ali nikako ispod šest.

27.04.2015., 22:50	#4
rodney only fool, not a horse Moj komp Datum registracije: Apr 2008 Lokacija: near zgb Postovi: 1,276	Bubba ti si jedan od onih prodavača.. Ja kažem: "Imaš m6 maticu?" On kaže: "Za šta ti treba?" __________________ "I intend to live forever. So far, so good." job security - example

27.04.2015., 23:49	#5
Bubba E Pluribus UNIX Moj komp Datum registracije: Oct 2002 Lokacija: M82 Postovi: 6,543	Malo ti je lose usporedba. Moja percepcija je ta da ako je dosao na forum pitati za ovakvu nekakvu abominaciju, gotovo sigurno mu ili ne treba ili se moze odigrati jednostavnije. Nista vise. A kao sto rekoh, primjer koji je dao je daleko od necega sto bi se povecano za redove velicine isplatilo zajebavati ovako. __________________ Programer Rok od dva mjeseca u stvari znači četiri, ali nikako ispod šest.

28.04.2015., 07:24	#6
rodney only fool, not a horse Moj komp Datum registracije: Apr 2008 Lokacija: near zgb Postovi: 1,276	https://rohitrohan09.files.wordpress...on-cartoon.jpg __________________ "I intend to live forever. So far, so good." job security - example

06.05.2015., 08:42	#7
perich I hate mondays.......... Datum registracije: Nov 2002 Lokacija: Zagreb - Zaprešić Postovi: 1,524	Evo za pocetak, hvala na predlozenim linkovima, proucit cu to malo pa da vidim sto i kako. Inace, ne radi se o "nepotrebnoj" stvari. Naime, na poslu imamo potrebu angažirati određene vanjske suradnike, no kako bi mogli procijeniti efikasnost svakog pojedinog, a bez da se bilo koji od njih "osjeća oštećen" radi toga što je dobio manje taskova, ili taskove manje vrijednosti, potrebno je te taskove "fairly" distribuirati. Radi se o financijskom sektoru, tako da su i "fairly" i "taskovi" izraženi u nekoj valuti i iznosu koji je apsolutno usporediv s drugima (znaci termin koji sam koristio, "task manje vrijednosti" nije relativan i podlozan subjektivnoj procjeni).

Oglasni prostor
PC Ekspert Forum Oglas

Oglasni prostor
PC Ekspert Forum Oglas