Dotaz: Algoritmus seřazení dat z různých souborů

[vhaji]

Dobrý den.

Marně se pokouším vymyslet co nejoptimálnější algoritmus řazení dat ze dvou neznámých zdrojů. Dejme tomu že mám 2 soubory či obecně zdroje dat, každý obsahuje 2 sloupce - jméno a číslo, soubory obsahují hrozně moc dat a já je potřebuju seřadit podle obou souborů a limitovat zobrazení dat. Zde na fórech jsem našel algoritmus řazení: seřadit n řádek z 1. souboru, pak n řádek s 2. a pak seřadit výsledek n+n a omezit zase na n - jenže to nebude fungovat. Z popisu asi není jasné o co mi jde - zde je příklad (např. 2 spojené soubory podle klíče username):

"user1";"1";"7"
"user2";"2";"6"
"user3";"3";"5"
"user4";"3";"4"
"user5";"4";"3"
"user6";"4";"2"
"user7";"4";"1"

Pokud chci 3 záznamy řazené podle 2. sloupce a potom 3. sloupce, tak to musí vrátit user1, user2, user4. Nepřišel jsem na optimální algoritmus jak dostat 3 záznamy aniž bych musel přečíst celý 1. soubor, celý 2. soubor a pak to limitovat až ve výsledku, což je ale velice datově a výpočetně náročné pro větší množství dat. Určitě už někdo podobný problém řešil. Prosím o pomoc/popis algoritmu pro toto řazení.

Odpovědi

[deadmail]

Ak tie dva subory su utriedene, tak naozaj staci n prvych riadkov z prveho suboru a n riadkov z druheho suboru utriedit a vybrat z nich prvych n.

Ak nie su, tak sa musia utriedit - bud kazdy zvlast, alebo spojene.

Ak treba viackrat z tych istych dat rozne n, tak raz utriedit oba subory a ulozit. Potom pouzit prvy sposob.

[kuka]

Nejak to nechapu - pokud ty soubory nejsou setridene, musi se vzdy cele projit, to se mi zda zrejme na prvni pohled.

[vhaji]

Zdroje dat (zde soubory) jsou setříděné. Nicméně výběr n a n řádků a jejich následné omezení fungovat nebude. Viz. příklad dat:

sloupec1+sloupec2 = soubor1, řazený vzestupně podle 2. sloupce
sloupec1+sloupec3 = soubor2, řazený vzestupně podle 3. sloupce


"user1";"1";"7"
"user2";"2";"6"
"user3";"3";"5"
"user4";"3";"4"
"user5";"4";"3"
"user6";"4";"2"
"user7";"4";"1"


1. z prvního souboru vyberu první 3 =>
 user1,
 user2,
 user3

2. z druhého souboru vyberu první 3 =>
 user7,
 user6,
 user5

3. spojím a zobrazím všechna data
 "user1";"1";"7"
 "user2";"2";"6"
 "user3";"3";"5"
 "user7";"4";"1"
 "user6";"4";"2"
 "user5";"4";"3"

4. omezím na první 3
 => user1, user2, user3 = CHYBA

Neboť primárně řadím podle 2. sloupce, tak user3 a user4 jsou nerozhodně (oba = 3), pomocí druhého sloupce ale zjistím, že user4 je před user3, což se ale při tomto algoritmu neprojeví.

[wamba]

co vybrat jich n plus všechny, co mají stejný druhý sloupec jak n-tý

[rADOn]

Pises ze zdroje dat jsou setridene, nicmene uvedeny priklad setrideny neni (resp. je setrideny podle jineho klice)

[zulu]

což je ale velice datově a výpočetně náročné pro větší množství dat

Proto je dobré mít ta data v dobře zpracovatelném formátu a udržovat další informace pro jejich rychlé prohledávání a propojování. A tak vznikly databáze.

[vhaji]

Ta data nakonec budou uložena v nějakých databázích, ale pokaždé v jiných a na jiných místech ČR Nicméně nakonec asi budu řadit tímto algoritmem:

1. vyberu n řádků ze zdroje 1
 .. - zjistím že m z n řádků nemají jednoznačné pořadí, tak prohledám zdroj 1 znovu a vyberu z n řádky které nemají jednoznačné pořadí + řádky s tímto "indexem", ale za limitem dotazu a postoupím dalšímu zdroji
2. to samé
.......

[dustin]

Možná by bylo rychlejší je rovnou uložit třeba do mysql, i kdyby to mělo být jen dočasné :)

K překlopení by měl stačit jednoduchý skript.

[Goheeca]

opravdu ten algoritmus funguje mne se nezda (nebo jsem ho treba nepochopil) nebot:

sloupec1+sloupec2 = soubor1, řazený vzestupně podle 2. sloupce
sloupec1+sloupec3 = soubor2, řazený vzestupně podle 3. sloupce

tzn. ze vuci sobe nejsou serazeny vubec (teda ano 1. sloupcem) -> to musis imho projit vsechny zaznamy ...

[Goheeca]

to se resi takto: mam ukazatel na radek pro kazdy soubor. nastavim je na zacatek souboru. chci n zaznamu tak nkrat provedu nasledujici: porovnam navzajem vsechny radky a vyberu ten nejmensi (vzestupne razena data v souborech) a v patricnem souboru posunu ukazatel ...

[Martin Doucha]

1) sort obou souborů podle společného sloupce

2) join na společný sloupec (join vyžaduje setříděné soubory)

3) sort na příslušné sloupce spojeného souboru

4) vypsat správný počet řádek

Podrobnosti v manuálových stránkách příkazů sort, join a head. Řešení je asymptoticky optimální.

[vhaji]

Jo to by šlo kdybych měl soubory a ty byly na stejném stroji. Jenže zdrojem dat může být nejenom soubor. Většinou se bude jednat o různé typy relačních databází. A kdybych to měl spojovat tímto mechanismem tak se může stát že při pokusu o vypsání 5 řádků budu muset spojit několik milionů záznamů a v nich filtrovat už programem, což je mírně řečeno velice neoptimální. Ten algoritmus na který jsem nakonec přišel by měl fungovat. Příklad se "syntaxí" mysql:

jmeno; cislo; cislo2
-----------------------
"user1";"1";"7"
"user2";"2";"6"
"user3";"3";"5"
"user4";"3";"4"
"user5";"4";"3"
"user6";"4";"2"
"user7";"4";"1"

order by cislo, cislo2 limit 3 = user1, user2, user4


teď ten algoritmus:
- select cislo ... order by cislo limit 3
1 2 3
- select jmeno ... where cislo in (1,2,3) => user1, user2, user3, user4
- pak zjistim ze sporne cislo je u user3 a user4
- select jmeno ... where jmeno in ("user3", "user4") order by cislo2 limit3 => user4, user3 => prerovnam puvodni vyber "user1, user2, user3, user4" na "user1, user2, user4, user3" a omezim na 3 => "user1, user2, user4"

Zásadní vada na kráse je ale ta že tento algoritmus je docela složitý.

[deadmail]

Většinou se bude jednat o různé typy relačních databází.

Tak pri dotaze z kazdej databazy treba prvych n riadkov utriedenych podla vyslednych ziadanych stlpcov. A nasledne utriedit vsetky takto ziskane riadky (pri 3 databazach teda 3*n riadkov).

To je algoritmus uvedeny uz v otazke (a takisto posledny sposob uvedeny v 1. komentari). Ale to utriedenie musi byt vsade rovnake ako vysledne ziadane.

[deadmail]

Aha, kazda databaza je iny stlpec ... teda sa neda dopredu utriedit ...

tak potom v databaze s prvym stlpcom vybrat prvych n riadkov a k nim najst vsetky odpovedajuce v dalsich databazach (pokial vzdy existuje prisluchajuci riadok, resp. sa pouzije null, t.j. left join). Tie potom utriedit. Tak to bude optimalne z pohladu prenosu co najmenej dat.

To je tebou uvedeny algoritmus.

[vhaji]

A jak jsem zjistil tak tento můj algoritmus je rovněž velice neefektivní. Praktický příklad: mám dvě databáze/tabulky. V první jsou sloupce jméno,pohlaví a v druhé jméno,výška. Každá obsahuje několik desítek tisíc řádků a já je chci seřadit podle pohlaví a pak podle výšky. Zde je kámen úrazu protože i když chci třeba 5 záznamů, tak musím z první tabulky vzít několik tisíc řádků abych je postoupil k té druhé tabulce a jakékoliv umělé omezování že max. počet postupujících záznamů je m by velice razantně změnilo výsledné hodnoty. Začínám být přesvědčený, že žádný algoritmus se asi na tohle vymyslet nedá.

[vhaji]

Nakonec to asi budu muset vzít z druhé strany: řadit jen podle jednoho sloupce/klíče a naprogramovat nějaké pokročilé možnosti filtrování dat.

[vhaji]

Tak to je ještě horší než to řazení. Nejhorší je to, že aplikace má za úkol pouze data číst a ta data jsou velice často měněna, takže možnost lokálního cache odpadá.