| Autor | Zpráva | ||
|---|---|---|---|
| Witiko Profil |
#1 · Zasláno: 8. 2. 2011, 20:02:58 · Upravil/a: Witiko
Zdravím PHP subfórum.
Mám databázi se dvěmi tabulkami, z nichž jedna obsahuje jednotky a druhá definuje vztahy a převoditelnost mezi jednotkami. Vypadá to nějak takto: UNITS (ID, NAME) >> 0, centimetry >> 1, milimetry CONVERSIONS (FROM, TO, RATIO) >> 0, 1, 10 >> 1, 0, 0.1 Snažím se dospět ke scriptu, který by dokázal projít i přes několik vrstev a doplnit veškeré chybějící vztahy mezi jednotkami. Vezměme si, že mám následující obsah tabulek: UNITS (ID, NAME) >> 0, gramy >> 1, kilogramy >> 2, mililitry >> 3, decilitry CONVERSIONS (FROM, TO, RATIO) >> 0, 1, 0.001 >> 1, 0, 1000 >> 2, 3, 0.01 >> 3, 2, 100 Nyní do tabulky UNITS vložíme řádek o hodnotách (4, litry) a do tabulky CONVERSIONS řádky (4, 1, 1) - kilogramy jsou rovny litrům (berme, že jde o vodu) - a (4, 3, 10) - litr se rovná 10 decilitrům. Tímto došlo k propojení jednotek váhy a objemu a vzniká zde spousta vztahů mezi jednotkami, které je třeba doplnit, aby ve výsledku vypadaly tabulky takto: UNITS (ID, NAME) >> 0, gramy >> 1, kilogramy >> 2, mililitry >> 3, decilitry >> 4, litry CONVERSIONS (FROM, TO, RATIO) >> 0, 1, 0.001 >> 0, 2, 1 >> 0, 3, 0.01 >> 0, 4, 0.001 >> 1, 0, 1000 >> 1, 2, 1000 >> 1, 3, 10 >> 1, 4, 1 >> 2, 0, 1 >> 2, 1, 0.001 >> 2, 3, 0.01 >> 2, 4, 0.001 >> 3, 0, 10 >> 3, 1, 0.1 >> 3, 2, 100 >> 3, 4, 0.1 >> 4, 0, 0.001 >> 4, 1, 1 >> 4, 2, 0.001 >> 4, 3, 10 Nejspíš bude potřeba volat rekurzivně funkci / použít cyklus, případně nadefinovat cyklus již přímo v MySQL žádosti (tzn. cyklus by se neprováděl na straně php, ale MySQL), nicméně ačkoliv jsem si nad problémem lámal hlavu, nenapadlo mě vhodné řešení. Proto poprosím o postrčení vhodným směrem, případně k lepšímu návrhu vztahové tabulky tak, aby její správa byla jednodušší (při n spolu souvisejících jednotkách bude mít tabulka CONVERSIONS n * (n - 1) řádků). |
||
| Alphard_ Profil * |
#2 · Zasláno: 9. 2. 2011, 01:40:45
Nebylo by jednodušší vždy při přidání nového záznamu vygenerovat vše, co je potřeba, než potom hledat, co chybí (a potenciálně přebývá)?
|
||
| Witiko Profil |
#3 · Zasláno: 9. 2. 2011, 13:26:50
Alphard
Dobrá tedy, po dodání dat vypadá tabulka takto: UNITS (ID, NAME) >> 0, gramy >> 1, kilogramy >> 2, mililitry >> 3, decilitry >> 4, litry CONVERSIONS (FROM, TO, RATIO) >> 0, 1, 0.001 >> 1, 0, 1000 >> 1, 4, 1 >> 2, 3, 0.01 >> 3, 2, 100 >> 3, 4, 10 >> 4, 1, 1 >> 4, 3, 10 Jak by tedy (alespoň schématicky) vypadal cyklus, který vztahy doplní na CONVERSIONS (FROM, TO, RATIO) >> 0, 1, 0.001 >> 0, 2, 1 >> 0, 3, 0.01 >> 0, 4, 0.001 >> 1, 0, 1000 >> 1, 2, 1000 >> 1, 3, 10 >> 1, 4, 1 >> 2, 0, 1 >> 2, 1, 0.001 >> 2, 3, 0.01 >> 2, 4, 0.001 >> 3, 0, 10 >> 3, 1, 0.1 >> 3, 2, 100 >> 3, 4, 0.1 >> 4, 0, 0.001 >> 4, 1, 1 >> 4, 2, 0.001 >> 4, 3, 10 Script musí doplnit všechny nově vzniklé vztahy mezi gramy, kilogramy, mililitry a decilitry. Ty nelze doplnit "postupně při přidání nového záznamu", tyto vazby vznikají až s přidáním jednotky litru. |
||
| TomášK Profil |
#4 · Zasláno: 9. 2. 2011, 13:35:18
Následující pseudokód jsem neověřoval, ale zdá mi, že by mohl fungovat. Idea je založena na Floyd-Warshallově algoritmu z oblasti teorie grafů.
Vytvoř matici M o velikosti n x n, kde n je počet jednotek (záznamů v UNITS). Inicializuj M[i][j] := (poměr převodu i -> j) nebo 0, pokud je neznámý // poměr převodu je ratio z CONVERSIONS Prožeň matici následující procedurou: procedure DoplneniJednotek ()
for k := 1 to n
for i := 1 to n
for j := 1 to n
M[i][j] := M[i][k] * M[k][j];Ve výsledku bude na pozici M[i][j] poměr převodu i->j, pokud takový převod lze odvodit ze zadání, jinak 0. Výpočet nekontroluje, zda vstup neobsahuje spor - dva různé způsoby převodu i->j, které by daly jiný výsledek, které , ale šlo by to doplnit. Nejrychlejší možný způsob to není, ale na implementaci jednoduchý. Předpokládám, že jednotek nebude tolik, aby se vyplatilo hledat něco rychlejšího, i když to taky určitě někdy někdo vymyslel. |
||
| Witiko Profil |
#5 · Zasláno: 9. 2. 2011, 16:24:05
TomášK:
Super, to vypadá, že by to mohlo být, co potřebuji. Jen je to až podezřele implementačně snadné, z pohledu na algorytmus mám pochybnosti, že počítá s hlubšími vztahy (tzn. kupříkladu vztahy jsou definované pouze mezi jednotkami 1 - 4 - 12 - 8 - 2 - 9, otázka je, jestli algoritmus nalezne vztah mezi 1 a 9). Vykouším to. :) |
||
| Alphard Profil |
#6 · Zasláno: 11. 2. 2011, 21:47:16
Witiko:
„Jak by tedy (alespoň schématicky) vypadal cyklus“ Je už problém (ať už s pomocí [#4] nebo bez) vyřešen, nebo ještě ne? Dřív jsem neměl čas, a teď se tím nechci zabývat čistě akademicky, jestli to už funguje :-) |
||
| Witiko Profil |
#7 · Zasláno: 12. 2. 2011, 13:03:45
Alphard:
Ještě jsem nestihl script nasadit, ale podle logiky algoritmu by měl, tedy ano. :-) |
||
| Segi_L Profil |
#8 · Zasláno: 12. 2. 2011, 14:46:11
Witiko
Tie tabulky platia a budú platit len pre vodu? |
||
| Witiko Profil |
#9 · Zasláno: 12. 2. 2011, 19:04:11
Segi_L:
Ne, to bylo jen pro ukázku. |
||
| Witiko Profil |
#10 · Zasláno: 14. 2. 2011, 17:15:10 · Upravil/a: Witiko
Řeším nyní problém s odstraněním jednotek z databáze. Pojďme vyjít z předchozího příkladu. Před přidáním litrů vypadají vztahy definované v databázi graficky nějak takto:
Po přidání litrů a prohnání matice algoritmem skončíme nějak takto: 
Pokud bychom nyní chtěli jednotku odebrat i s veškerými na ní závisícími vztahy z databáze, byl by postup poměrně triviální. Stačilo by nám odstranit veškeré "oranžové" vztahy - tedy vztahy vytvořené algoritmem bezprostředně po přidání jednotky litrů do databáze. Pojďme však do databáze přidat další jednotku, např. centilitry, které si definujeme ve vztahu k dalším jednotkám objemu: 
V tuto chvíli pokud bychom chtěli odstranit veškeré vztahy závisící na jednotce litrů, jsme nahraní. I při odstranění veškerých vztahů vytvořených algoritmem bezprostředně po přidání jednotky litrů do databáze a veškerých přímích vztahů s jednotkou litrů, stále nám zůstanou vztahy mezi centilitry a gramy / kilogramy. Je tedy nějaký způsob / cyklus, kterým by spolu s jednotkou bylo možné odstranit veškeré vztahy vzniklé díky ní? Z hlediska příkladu algoritmus, který by navrátil vztahy do takovéhoto stavu: 
|
||
| TomášK Profil |
#11 · Zasláno: 14. 2. 2011, 17:53:02 · Upravil/a: TomášK
Witiko:
Pěkné grafy :-) Tentokrát nic algoritmicky přímočarého nevidím. Ale předpokládám, že jednotek by nemusel být tolik, aby to šlo udělat "hloupě" - hrany, které mi vygeneruje matice, si označím jako vygenerované, ostatní jako definované. Když budu chtít odebrat nějakou jednotku, tak ji odeberu, smažu všechny vygenerované hrany v celém grafu a nechám matici, ať mi je spočítá znovu. Edit1: Stačí se omezit na vrcholy, které jsou z odstraňovaného dosažitelné. |
||
| Witiko Profil |
#12 · Zasláno: 14. 2. 2011, 20:05:46 · Upravil/a: Witiko
TomášK:
Ano, to zní rozumně, měl jsem se na to podívat z tohohle úhlu, možná by mě to trklo. :-) Dík, pustím se do implementace. |
||
|
Časová prodleva: 13 let
|
|||
0