Dva random broja čija kombinacija ne postoji u tabeli

[ vujkev @ 27.05.2008. 12:47 ] @

U jednoj tabeli postoje kolone:

ID....
LocationX INT
LocationY INT
...

Treba da nađem jednu kombinaciju LocationX i LocationY koja ne postoji u bazi. LocationX i LocationY su ograničene vrednosti (npr 0 - 100) i bilo bi poželjno da nova kombinacija bude blizu starih :)

primera radi ako u bazi postoje
LocationX LocationY
----------------------
10 10
8 12
12 1

bilo bi poželjno da nova kombinacija bude npr 8-10 pre nego 100 - 100. Znao bih kako to da napravim sa jednom petljom koja će proveravati da li zadata kombinacija postoji u bazi, pa ako je postoji da zada novu i ponovi postupak, ali me interesuje da li postoji bolje rešenje

Pozdrav

[ Fedya @ 27.05.2008. 13:22 ] @

Code:

declare @x int
declare @y int

while 1=1
begin
    select @x = rand()*100+1
    select @y = rand()*100+1
    if not exists(select * from loc where x=@x and y=@y)
    begin
        insert into loc values(@x, @y)
        return
    end
end

Naravno, ovo je brzo resenje nije bas optimalno (rand je poprilicno losa funkcija - ali ovde radi posao posto ponavljanja nisu moguca).
Takodje ako hoces bliske vrednosti, mozes za osnovu rand-a da uzmes max vrednost iz trenutne tabele i dodas jos neki mali broj (time bi izbegao beskonacnu petlju kada ispucas sve kombinacije ali bi polako pomerao limit mogucih vrednosti)...

_{[Ovu poruku je menjao Fedya dana 27.05.2008. u 14:36 GMT+1]}

[ deerbeer @ 27.05.2008. 14:42 ] @

Citat:

Znao bih kako to da napravim sa jednom petljom koja će proveravati da li zadata kombinacija postoji u bazi, pa ako je postoji da zada novu i ponovi postupak, ali me interesuje da li postoji bolje rešenje

A sto ne probas da postavis Index-e na ta 2 polja i das im UNIQUE CONSTRAINT ..
Kad neko bude ubacivao nove vrednosti SQL baca exception na osnovu tog Unique index-a
ako kombinacija vec postoji .....

Code:

CREATE TABLE Tabela (
   [ID] int ....
   [LOCATIONX] int ...
   [LOCATIONY] int ....

   CONSTRAINT [IX_LOCATION] UNIQUE NONCLUSTERED
   (
      [LOCATIONX],
      [LOCATIONY]

   ) ON [PRIMARY]

)

i dodas posle tvoj check constrain za doticna polja da mogu biti u rasponu od (0 -100)

Code:

ALTER TABLE Tabela
ADD CONSTRAINT checkLocationX CHECK (Tabela.LOCATIONX >= 0 AND Tabela.LOCATIONX < 100 );
ADD CONSTRAINT checkLocationY CHECK (Tabela.LOCATIONY >= 0 AND Tabela.LOCATIONY < 100 );

[ jablan @ 27.05.2008. 15:02 ] @

Napravi temp tabelu sa vrednostima 1-100 i uradi join na samu sebe, kako bi dobio sve moguće parove (x, y) (doduše, možeš i da pripremiš takvu tabelu, 10000 nije mnogo slogova). Onda uradiš SELECT TOP 1 sa WHERE uslovom da se par ne nalazi u tvojoj tabeli. Dodatnim dobro smišljenim ORDER BY možeš da ispuniš i svoj, loše definisan uslov da vrednosti budu "bliže" postojećim.

Code:

select top 1 p1.x, p2.x from temp_tab p1
inner join temp_tab p2 on 1=1
left outer join tabela t on (p1.x = t.x and p2.x = t.y)
where t.x is null;

_{edit: dodao kod}

_{[Ovu poruku je menjao jablan dana 27.05.2008. u 16:28 GMT+1]}

[ Fedya @ 27.05.2008. 15:02 ] @

@deerbeer: he he, nisam skontao poslednju liniju :P

Nego, ovo sto si naveo i dalje nije resenje posto je pitanje kako dobiti random kombinaciju.
Trenutno sam malo zauzet, razmislicu o ovome malo kasnije (ako neko ne uskoci sa resenjem).

[ deerbeer @ 27.05.2008. 15:12 ] @

Citat:

@Fedya
@deerbeer: he he, nisam skontao poslednju liniju :P

Na koju mislis ??

Citat:

@Fedya
Nego, ovo sto si naveo i dalje nije resenje posto je pitanje kako dobiti random kombinaciju.

U pravu si ....e sad ne znam sta je postavka zadatka tj. nisam bas shvatio iz vujketovog posta
generisanje random brojeva programski ili "korisnicki" ?
Ako korisnici unose te brojeve (sto se isto moze smatrati random unosom) onda je check constraint sasvim logicno resenje ....

Citat:

vujkev
....bilo bi poželjno da nova kombinacija bude npr 8-10 pre nego 100 - 100.

Sa ovim mojim primerom nikako ne moze :)

_{[Ovu poruku je menjao deerbeer dana 27.05.2008. u 16:30 GMT+1]}

[ vujkev @ 27.05.2008. 15:45 ] @

Citat:

deerbeer:
A sto ne probas da postavis Index-e na ta 2 polja i das im UNIQUE CONSTRAINT ..

Kreiranje novog para je programski bez intervencije korisnika

Citat:

jablan:
... Dodatnim dobro smišljenim ORDER BY možeš da ispuniš i svoj, loše definisan uslov da vrednosti budu "bliže" postojećim.

Ne razumem "loše definisan uslov". Nisi razumeo koji je problem ili misliš da ovo može bolje da se napravi u bazi?

Ovako sam ja za sad napravio, a ako neko zna bolje nek se javi. U svakom slučaju postupak je da prvo nađemo min i max lokacije iz baze, povećamo taj okvir za npr 4 i iz tog okvira nađemo novi par koji ne postoji u bazi

Code:

declare @MinX int
declare @MinY int
declare @MaxX int
declare @MaxY int
declare @x int
declare @y int
declare @Delta int

set @Delta = 4

while 1=1
begin

    select @MinX=min(LocationX), @MinY=Min(locationY), @MaxX=max(LocationX), @MaxY=Max(LocationY)
        from tblVillages

    if @MinX >= @Delta
        set @MinX = @MinX - @Delta
    else
        set @MinX = 0

    if @MaxX <= 100 - @Delta
        set @MaxX = @MaxX + @Delta
    else
        set @MaxX = 100

    if @MinY >= @Delta
        select  @MinY = @MinY - @Delta
    else
        set @MinY = 0

    if @MaxY <= 100 - @Delta
        select  @MaxY = @MaxY + @Delta
    else
        set @MaxY = 100

    select @x = ROUND(((@MaxX - @MinX -1) * RAND() + @MinX), 0)
    select @y = ROUND(((@MaxY - @MinY -1) * RAND() + @MinY), 0)

    if not exists(select * from tblVillages where LocationX=@x and LocationY=@y)
    begin
        select @x, @y
        --insert into loc values(@x, @y)
        return
    end
end

[ jablan @ 27.05.2008. 15:51 ] @

Citat:

vujkev: Ne razumem "loše definisan uslov". Nisi razumeo koji je problem ili misliš da ovo može bolje da se napravi u bazi?

Napisao si:

Citat:

vujkev: bilo bi poželjno da nova kombinacija bude blizu starih

A nisi napisao šta znači "blizu starih". Kompjuteri nažalost još uvek ne mogu da čitaju misli, a bogami ni mi na forumu.

Dakle, "blizu starih" između ostalog može da znači:
1) Novi x i y uzimaju vrednosti koje se najčešće pojavljuju među starim (postojećim) vrednostima.
2) x i y uzimaju vrednosti najbliže prosečnoj vrednosti starih vrednosti x i y
3) x i y uzimaju vrednosti najbliže prosečnim vrednostima starih vrednosti x i y (posebno x, posebno y)

itd itd.

BTW, u slučaju da ti treba taj dodatni uslov "blizine", ne može se više govoriti o random vrednostima. I inače, mislim da je random loše izabran pojam i da problem uopšte ne treba rešavati upotrebom random funkcija. Čini mi se da se previše trudite da prenesete logiku iz struktuiranog programiranja u SQL. To što stored procedure to omogućavaju ne znači da je to dobar put.

_{[Ovu poruku je menjao jablan dana 27.05.2008. u 17:06 GMT+1]}

[ deerbeer @ 27.05.2008. 16:00 ] @

Hmmm.. zanimljiv kod ... voleo bih da znam cemu sluzi
tj. svrha generisanja brojeva sa RAND() funkcijom u tvom primeru
(Slucajno rasporedjivanje lokacije sela unutar neke opstine ? :)

Da li ti ovaj kod daje raspodelu brojeva kao sto si hteo
(od 0 do 100 ali sa gustom raspodelom do 10) ?

Probacu kasnije da li moze da se uprosti ovakav primer ...

[ vujkev @ 27.05.2008. 17:01 ] @

Citat:

jablan: A nisi napisao šta znači "blizu starih". Kompjuteri nažalost još uvek ne mogu da čitaju misli, a bogami ni mi na forumu.

Ok moj previd. Već dosta radim na ovom programu tako da sam predpostavio da je i vama jasno da LocationX i LocationY predstavljaju koordinate u xy ravni. Kad kažem blizu mislim da rastojanje između nove tačke i starih tačaka bude "manje". Ne znam kako bolje da objasnim

Citat:

deerbeer:
Da li ti ovaj kod daje raspodelu brojeva kao sto si hteo
(od 0 do 100 ali sa gustom raspodelom do 10) ?

pa ne baš :( Ovaj kod mi daje tačke koje su za max. @Delta udaljene od krajnjih tačaka koje postoje u tabeli.

[ jablan @ 27.05.2008. 17:13 ] @

Citat:

vujkev: Kad kažem blizu mislim da rastojanje između nove tačke i starih tačaka bude "manje". Ne znam kako bolje da objasnim

Možda ovako: "Suma razdaljina nove tačke od postojećih tačaka treba da bude minimalna.".

I da, ovaj uslov definitivno isključuje svaku upotrebu slučajnih brojeva, pošto se tačno zna koje ga kordinate zadovoljavaju.

Evo ti rešenje u PostgreSQL-u, ti ga prevedi u MSSQL ako hoćeš:

Code:

reports=# select * from sve_koord ;
x
---
1
2
3
4
5
(5 rows)

reports=# select * from tabela ;
x | y
---+---
2 | 5
3 | 1
4 | 4
(3 rows)

reports=# select p1.x as nx, p2.x as ny, sum((p1.x - r.x)^2 + (p2.x-r.y)^2) as d
from sve_koord p1
inner join sve_koord p2 on 1=1
left outer join tabela t on (p1.x = t.x and p2.x = t.y)
inner join tabela r on 1=1
where t.x is null
group by nx, ny
order by d;
nx | ny | d
----+----+----
  3 |  3 | 11
  3 |  4 | 12
  2 |  3 | 14
  4 |  3 | 14
  2 |  4 | 15
  3 |  2 | 16
  2 |  2 | 19
  4 |  2 | 19
  3 |  5 | 19
  4 |  5 | 22
  5 |  3 | 23
  1 |  3 | 23
  5 |  4 | 24
  1 |  4 | 24
  1 |  2 | 28
  5 |  2 | 28
  4 |  1 | 30
  2 |  1 | 30
  5 |  5 | 31
  1 |  5 | 31
  5 |  1 | 39
  1 |  1 | 39
(22 rows)

Tačka koju tražiš je TOP 1 u poslednjem queryju, ostavio sam ga celog da bi se videla treća kolona, odnosno suma kvadrata rastojanja između nove tačke i svih postojećih.

_{[Ovu poruku je menjao jablan dana 27.05.2008. u 18:25 GMT+1]}

[ vujkev @ 27.05.2008. 18:37 ] @

Pa ne treba mi baš to. Po ovom kodu, ako sam dobro razumeo, ukoliko imam tačku 0,0 i 4,4, nova tačka će biti 2,2. Meni ipak treba random tačka koji će biti blizu dve postojeće tačke.

[ jablan @ 27.05.2008. 18:45 ] @

Odustajem.

BTW, čemu ti služe te tačke koje su kao random a nisu random i koje su blizu, a nisu baš blizu?

[ negyxo @ 27.05.2008. 20:35 ] @

Citat:

jablan: Odustajem.

BTW, čemu ti služe te tačke koje su kao random a nisu random i koje su blizu, a nisu baš blizu?

Dobar si

Vujke stvarno, Jablan ti je dobro rekao ili tacke treba da zadovoljavaju odredjeni uslov ili da su radnom, ili recimo zeilis odredjeni opseg (koji je blizi "proslim" tackama) pa u tom opsegu da izaberes random, mada sve ovo mu onda dodje random

[ jablan @ 27.05.2008. 20:55 ] @

Evo jedne ideje: Uzmeš ovu listu koju ti generiše moj upit i iz nje izabereš jedan par tačaka, ali po Poasonovoj raspodeli (tj. favorizuješ tačke koje su pri vrhu liste, odnosno bliže postojećim tačkama).

Mada stvarno bi pomoglo kad bi objasnio šta ustvari hoćeš da postigneš, tj. koji realni problem rešavaš. Da nije potapanje brodova? :D

[ Zidar @ 28.05.2008. 16:18 ] @

Ako su ti tacke na u ravni X,Y gde X i Y idu od 1 do 100, samo celi brojevi, onda imas 100 X 100 tacaka. Neke od njih su "u bazi".

Mozes da probas ovo: Ako napravis tabelu sa SVIM MOGUCIM parovima koordinata, dakle 100 X 100 = 10,000 tacaka i dodas jos jednu kolonu "Zauzeta", koja je 1 ako je tacka zauzeta ("tacka je u bazi") ili 0 ako je tacka slobodna, onda celu pricu mozes da nacrtas u koordinatnom sistemu.

Ako izaberes bilo koju zauzetu tacku, sa koordinatama (X,Y), ona ce biti u centru nekog kvadrata. Njeni najblizi susedi su tacke na sredinama stranica kvadrata i imace koordinate:

sused levo (x-1, y)
sused desno (x+1, y)
sused gore (x, y+1)
sused dole (x, y-1)

Bilo koja od ovih tacaka je podjednako daleko od izabrane tacke (opet RANDOM

Malo dalje od prethodnih su tacke na temenima kvadrata:

severozapadni sused (x-1,y+1)
severoistocni sused (x+1,y+1)
jugoistocni sused (x+1,y-1)
jugozapadni sused (x-1,y-1)

Ako izaberes bilo koju tacku (evo ga Random) koja je Zauzeta, onda vidis koordinate njenih suseda, i tu trazis prvu slobodnu tacku. Blizih od ovoga nema. Ako ni jedan sused nije slobodna tacka, ides na sledeci kvadrat. Ovaj algoritam ti garantuje da ces izabrati tacku koja je najbliza moguca posmatranoj tacki. Moze psotojati vise od jedne tacke koje su na istoj udaljenosti od posmatrane tacke.

Mislim da sam video knjige u kojim se slicni problemi resavaju cistim SELECT naredbama, bez petlji. Ako nadjem, pokazacu takvo resenje.

[ vujkev @ 29.05.2008. 17:18 ] @

Citat:

jablan: Odustajem.

BTW, čemu ti služe te tačke koje su kao random a nisu random i koje su blizu, a nisu baš blizu?

Sorry, ne znam kako sam zaboravio da odgovorim prošli put kad si pitao.

Učetvujem u izradi igrice slične TribalWars (nadam se da sam dobro napisao) u kom korisnik može da kreira "Selo" na mapi. Zahtev je da na početku igrice (dok je broj korisnika mali) rastojanje između sela bude "malo", tj. da sela budu koncentrisana na mapi. Raspored sela ne bi trebalo da bude uniforman nego "random" tako da mi x-1 i y+1 ne odgovara.

Za sad kod koji sam postavio mi radi najbolje, tj. nova sela jesu "random" u nekom okviru.

[ jablan @ 29.05.2008. 17:23 ] @

Bože blagi, stvarno kodiraš igricu u TSQL-u?!

[ vujkev @ 29.05.2008. 20:49 ] @

Ne kodiram igricu već tražim samo jedan podatak.

Kako bi ti to uradio?

[ jablan @ 29.05.2008. 20:52 ] @

Pa za tako male količine podataka, bazu možeš da koristiš eventualno kao mesto gde snimaš podatke između dva pokretanja programa (i to obično neku embedded), a obično se za to koriste obični tekstualni fajlovi (XML npr). Raspoređivanje sela kao i ostalu logiku radiš u aplikaciji, korišćenjem nekog suvislijeg jezika.

Edit: Tek sam sad pogledao šta je TribalWars (onlajn igrica). Onda i nije mala količina podataka u pitanju, pa možda i ima logike prebaciti to u bazu. Koliko su velike mape?

E da, predlog za algoritam za raspoređivanje novog sela: Zadaš na početku minimalno rastojanje A i maksimalno rastojanje B. Onda nađeš sve nezauzete tačke koje se ne nalaze bliže od B od bilo koje postojeće tačke, niti dalje od B od bilo koje postojeće tačke. Od tih tačaka izabereš jednu random i to ti je to.

_{[Ovu poruku je menjao jablan dana 29.05.2008. u 22:05 GMT+1]}

[ vujkev @ 29.05.2008. 21:34 ] @

Baza je sve, ali nije mala. Trenutno postoji oko 30 tabela, a još nisu dodate sve opcije

Inače velična mape još nije određena, ali mislim da neće biti manja od 200x100.

[ jablan @ 29.05.2008. 21:41 ] @

Mislio sam na veličinu u smislu količine podataka, ne broja tabela. 100x200 nije ništa i nema razloga da sve to ne učitaš u memoriju pri startovanju programa i zaboraviš na SQL.

Sa druge strane, TribalWars kaže da ima 500k igrača. Ako su svi na istoj mapi, veličina mape bi teško mogla da bude manjeg reda veličine od 100kx100k. A i da nisu svi na jednoj mapi, ukupan broj polja bi bio isti (reda veličine milijarde).

[ vujkev @ 29.05.2008. 22:18 ] @

Nisu svi na jednoj mapi već je sve podeljeno u nekoliko desetina "svetova" tako da ipak mislim (nadam se) da će količina podataka biti veća.

[ deerbeer @ 29.05.2008. 23:49 ] @

Citat:

@vujkev
Učetvujem u izradi igrice slične TribalWars (nadam se da sam dobro napisao) u kom korisnik može da kreira "Selo" na mapi.

Pa sto ne rece da si u game-modu .Pitah te pre neki dan a tek sad vidim o cemu se radi ..

Tebi vec radi taj kod sto si postovao al kako kazes nemas dobru "gustinu raspodele" na mapi od 100 X 100
tj. voleo bi da imas neko maximalno dozvoljeno odstupanje tacaka (koje ti odredis) od koordinatnog pocetka.
Takvu bazu treba samo da popunis sa nekim boljim random generatorom iz nekog ozbiljnijeg programskog jezika a ne iz TSQL-a ...

Pogledaj ovde primer u c++ -u :
http://www.codeproject.com/KB/recipes/zigurat.aspx
Probaj da iskoristis ovaj algoritam koji se zasniva na normalnoj (Gausovoj) raspodeli tacaka (pogledaj grafikon u obliku zvona)
a koje ce zadovoljiti uslov standardne devijacije (ili srednje kvadratno odstupanje slucajnih vrednosti od srednje vrednosti ) kod slucajnih brojeva.
Evo malo teorije:
http://en.wikipedia.org/wiki/Standard_deviation
http://en.wikipedia.org/wiki/Variance
Kad pronadjes tj. generises sve moguce tacke ostaje ti samo da ih u bazi flag-ujes sa zauzeto/slobodno ..

EDIT :
Eh da ..setih se da u TSQL-u postoji takva funkcija za dobijanje standardne devijacije ..
Pogledaj STDEV ili STDEVP agregate funkcije ako ti gore pomenuti primer ne pije vodu .....

_{[Ovu poruku je menjao deerbeer dana 30.05.2008. u 11:19 GMT+1]}

_{[Ovu poruku je menjao deerbeer dana 30.05.2008. u 11:30 GMT+1]}

[ deerbeer @ 02.06.2008. 10:23 ] @

Sta bi ? Nista od TribalWars-a ....
Kao sto rekoh za generisanje slucajnih brojeva tj. raspodela sela unutar nekog sveta koristi normalnu (gausovu) raspodelu
jer ako se uzme kao primer neki grad u srbiji statisticki gledano sva naselja, opstine,sela itd
su gusto raspodeljeni u nekom radijusu od recimo 20km (ako racunas ukupan radijus od 100km) od centra tog grada ....

Evo TSQL skripte koja ti mozda bude od pomoci :
STDEVP (ili ti STDEV population) je standardna devijacija slucajnih brojeva za veliki broj uzoraka
A sve statisticke raspodele u matematici priblizavaju se normalnoj(gausovoj) za veliki broj uzoraka
(ZAKON VELIKIH BROJEVA)

Code:

create  table  #temp (locationX int,locationY int)
declare @brojac int
set @brojac = 0
while @brojac <= 100000     /* stdevp primeniti samo za veliki broj uzoraka slucajnih promenjlivih
begin
insert into #temp (locationX,locationY)
values ((rand() * 100),rand()* 100)
set @brojac = @brojac + 1
end

declare @stdevX int
declare @stdevY int

Select @stdevX = stdevp (locationX) FROM #temp
Select @stdevY = stdevp (locationY) FROM #temp

select distinct locationX,locationY from #temp
where locationX < @stdevX and locationY < @stdevX

drop table #temp

--result set --
11          2
2    22
27    4
14    25
1    18
13    11
25    15
16    0
23    22
4    7
11    21
10    14
22    5
8    23
21    9
22    17
19    3
20    19
7    20
24    20
...
...
...

Ovakva raspodela ti daje 784 tacaka ... sto je dovoljno kako si rekao za 500 igraca na mapi ..

Tebi jedino ostaje da ocistis neke lokacije tj. tacke koje dobijes ovakvim generisanjem
a koje su mnogo blizu jedna druge
Na primer : selo1(5,10) i selo2(5,13) jer je malo verovatno da takva sela budu toliko blizu
mada posto je u TribalWars tematika srednji vek
vise je verovatno da su neka sela toliko blizu i da ih naprimer deli jedan most i reka :)

_{[Ovu poruku je menjao deerbeer dana 02.06.2008. u 11:33 GMT+1]}