Stránky: 1

 

#1 před 2 lety

Koubas
Člen
Registrovaný: 20. 2. 2009
Příspěvky: 8

Algoritmus: max. počet rezervovaných mist v daném období

Řeším následující problém:

  • mám tabulku, kde každý řádek představuje časový rozsah (podstatné sloupce: od a do)
  • časové rozsahy se libovolně překrývají, jsou libovolně dlouhé

cíl: je dán rozsah od-do, pro který potřebuju získat maximální počet rozsahů z tabulky, které se v daném rozsahu překrývají.

účel: parkoviště má omezený počet parkovacích míst a chci si rezervovat místo na daný časový rozsah, pokud je /hodnota kterou se snažím získat/ větší nebo rovna počtu míst, tak je parkoviště v tuto dobu obsazené a mám smůlu.

Pokud by někoho napadlo efektivější řešení, než které právě implementuji, tak sem s ním :)

Moje řešení:

  • z tabulky vytáhnu rozsahy, které zasahují, nebo přímo spadají do daného rozsahu
  • krajní hodnoty částečně zasahujících rozsahů seříznu tak, aby kompletně spadaly do daného rozsahu
  • tyto rozsahy rozkrájím v překrývajících se krajních od/do hodnotách na mnohem více menších rozsahů, které již není možné dále dělit (žádný z těchto rozsahů se s druhým nepřekrývá častečně – buď jsou některé identické, nebo spolu naopak žádný časový úsek nesdílí)
  • tyto „zagreguji“ – spočítám pro každý unikátní rozsah počet jeho výskytů – ten s nevyšším počtem je vítěz!

Nejvíce by se mi líbílo, kdyby existovalo nějaké jednoduché řešení přímo pomocí (My)SQL, které mě minulo :) S programováním funkcí přímo v prostředí DB se moc nekamarádím, ale pokud by to šlo relativně jednoduše, tak proč ne.

Předem díky

Editoval Koubas (29. 8. 2009 21:54)

 

#2 před 2 lety

phx
Moderator
Registrovaný: 17. 4. 2008
Příspěvky: 878

Re: Algoritmus: max. počet rezervovaných mist v daném období

Pokud je rozliseni pouze na dny tak by se to dalo resit vice zpusoby.

  1. projet do den po dni (mrte dotazu)
  2. nagenerovat si do temp tabulky dny a udelat join, group by datum a count (to same jako 1. v par dotazech)

Otazka zni jak to bude vykonne.

Dlasi moznost je pouzit triggry a mit dalsi tabulku kde ty dny budou jiz agregovane. Tz prida se nova rezervace od do a triger upravi/vytvori prislusne radky v te agregovane tabulce (pk, date, pocet_aut). Pote by dotaz byl pouze MAX() z agregovane tabulky v prislusnem intervalu.

Posledni co me napada je trosku silene, ale asi by to mohlo jit. JOIN sam se sebou tak aby se k 1 radku pridaly vsechny prekryvajici.

SELECT R1.date, COUNT(R2.id) as pocet FROM rezervace R1
LEFT JOIN rezervace R2 ON
        R1.od >= R2.do AND R1.do <= R2.od
GROUP BY R1.date

Nevim zkuz to. Strilim to od boku. Mozna by to slo i jako … FROM rezervace R1, rezervace R2 …

Pokud tam bude mrte dat tak si chce dost pohrat s klici a optimalizaci dotazu (EXPLAIN SELECT …). Jinak se to pak povlece.

 

#3 před 2 lety

Koubas
Člen
Registrovaný: 20. 2. 2009
Příspěvky: 8

Re: Algoritmus: max. počet rezervovaných mist v daném období

diky za odpověď. Bohužel rozlišení by stačilo na minuty, možná hodiny, ale už i to je moc na procházení jednotlivých intervalů, parkovacích míst je 80 a parkovišť je víc :) Ten uvedený dotaz vlastně odpovídá kroku 1 mého řešení, pak je potřeba ještě provést ty další operace, aby to dávalo smysl.
Mám implementované to své řešení, funguje skvěle, jen performance jsem ještě nezkoušel. Na DB to náročné není – jeden range dotaz, žádné joiny, ale php by se mohlo zapotit s postprocesingem – nejsem schopen odhadnout bez benchmarku. Pokud to PHP nebude stíhat, tak se to pokusím přepsat do C++ jako PHP extenzi a bude :)

 

RSS feed RSS tématu

Zápatí