Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: milan 04. 09. 2014, 21:22:51
-
Potrebujem poradit, ako najrychlejsie porovnat dve tabulky, ktore maju radovo tisice riadkov.
Tabulka1 ma stlpce ID1 a HODNOTA1.
Tabulka2 ma stlpce ID2 a HODNOTA2.
Potrebujem vypisat
1. vsetky ID1 z Tabulka1, kde ID1 = ID2 a HODNOTA1 <> HODNOTA2
2. vsetky ID1 z Tabulka1, ktore chybaju v Tabulke2
2. vsetky ID2 z Tabulka1, ktore chybaju v Tabulke1
-
A to máš jako na papíře, nebo na čem? Nějak jsi nenapsal, jestli je to excel, relační databáze, texťák,...apod.
-
Protože autor neuvedl, včem to má, budeme předpokládat, že to jsou dva XLS soubory.
porovnat dve tabulky, ktore maju radovo tisice riadkov.
Tabulka1 ma stlpce ID1 a HODNOTA1.
Tabulka2 ma stlpce ID2 a HODNOTA2.
Tisíce řádek je třeba 50 tisíc řádek vs 50 tisíc řádek.
ID má hodnotu řekněme 0 až 50 000, oddělovač, hodnota bude třeba 9 999 999 999 999 999
50 000 řádek * 32 znaků * 2 bajty na znak = 3,2 tabulka má cca tři a půl mega jestli správně počítám, ale nebyl by problém ani se 32 megama a dokonce ani se 320 megama na tabulku. Obojí se ti do paměti vejde.
A zvládneš to jedním průchodem, pokud chceš opravdu jen tohle.
Horší by bylo, kdybys potřeboval porovnat pět mega záznamů vůči jiným pěti megům, jestli se dané číslo nevyskytuje i v druhé skupině.
Taková práce už nějaký čas zabere i na jinak velmi slušném stroji.
Já musím bohužel porovnávat každý prvek s každým.
To tvoje jde jinak udělat i pomocí tří poměrně jednoduchých selectů do databáze, ale tu jistě nemáš, to bys jinak uvedl.
-
Horší by bylo, kdybys potřeboval porovnat pět mega záznamů vůči jiným pěti megům, jestli se dané číslo nevyskytuje i v druhé skupině.
Taková práce už nějaký čas zabere i na jinak velmi slušném stroji.
Já musím bohužel porovnávat každý prvek s každým.
nemusis
-
A tak to mě zajímá.
Mám tu úlohu, kdy mi přichází hodnoty (číselné kombinace), které musím testovat oproti tabulce stávajících hodnot, jestli se daná sekvence v systému už neobjevila. Jedná se o třicet dva nanejvýš douciferných číslech.
Co potřebuji zjistit:
- Jestli ten token už nebyl někdy použit (tabulka historie má 820 mega)
- Jestli vzájemná delta párů čísel není jen kopií jiné delty
Tj: na vstupu dostanu místo dvanácti čísel jen čísla 8 a 24, jejich delta je 24-8=16.
A já se musím podívat do tabulky, jestli jsem už nedostal kombinaci čísel 8 a 24 resp. nebo 24 a 8, případně jestli není delta stejná.
Tj. páry 16 a 32 mají stejnou deltu jako 8 a 24, protože 32-16 = 24-8
Problém delty je ten, že se nedá spočítat dopředu, protože delta je důležitá jen vůči osmi párům.
Tedy, něco mi v tokenu definuje čísla, která vůči sobě musí mít deltu stejnou a která jí mít nesmí, což je pro každý příchozí token jiné.
Zkoušeli jsme různé databáze a nejrychlejší je porování v paměti.
Ale budu rád, jestli máš nápad, jak to geniálně řešit.
-
(Nulové páry jsou povolené, takový pár se pak považuje za nevyplněný.)
Tj: 12-00-04-00-01-01-00-00-00-00-99-75-00-00-07-00-54-00-14-00-12-00-48-00-00-00-00-00-00-00-14-00
A mám tedy vyplěných 12 párů z maximálního počtu 32 párů.
Prázdné pozice se nepočítají, tj. tento klíč má dvanáct párů.
To je povolený a poměrně běžný stav.
Musím kontrolovat tedy toto:
12-00-04-00-01-01-00-00-00-00-99-75-00-00-07-00-54-00-14-00-12-00-48-00-00-00-00-00-00-00-14-00
12-00-04-00-01-01-00-00-00-00-99-75-00-00-07-00-54-00-14-00-12-00-48-00-00-00-00-00-00-00-14-00
Jestli páry nejsou stejné
Jestli to není jen rotovaný už použitý token.
12-00-04-00-01-01-00-00-00-00-99-75-00-00-07-00-54-00-14-00-12-00-48-00-00-00-00-00-00-00-14-00
00-12-00-04-00-01-01-00-00-00-00-99-75-00-00-07-00-54-00-14-00-12-00-48-00-00-00-00-00-00-00-14
14-00-12-00-04-00-01-01-00-00-00-00-99-75-00-00-07-00-54-00-14-00-12-00-48-00-00-00-00-00-00-00
Jestli delta například mezi párem P1-3 není stejná
12-00-04
24-00-16
Pokud číslo vyhovuje, posílá se dál na druhý stupeň.
No a nejrychleji to vychází kontrolovat v paměti...
-
prilis komplikovane na to aky som nevyspaty :-)
ale nenasiel som tam nikde to porovnavanie dvoch 5megovych tabuliek..
je jasne, ze v pamati to je najrychlejsie, ale stale tam hra dost velku ulohu ako to mas upratane v pamati...
-
To jsem myslel na něj, že to nemusí porovnávat jednu tabulku s druhou.
Já porovnávám maximálně 20-30 příchozích párů s historií, víc toho naráz nechodí.
-
este napis ake mas ocakavania co sa tyka rychlosti
-
Já? Dáváme to "realtime" ;D
On? Nejprve by měl poslat vzorek dat a říct, jestli to má v DB/CSV/atd
-
Máme funkční řešení ;) porovnávání se dělá přes GPGPU
-
To bych ovšem pro původního pisatele nedoporučoval ;D
-
Pro Bla:
#include <vector>
#include <limits>
#include <iostream>
int main()
{
std::vector<unsigned int> stream1 = {1, 18, 41, 5819923, 49924, 483885, 3883746, 18288334};
std::vector<unsigned int> stream2 = {1948485, 229318, 433331, 5819923, 49443924, 483885, 38583746, 1};
std::vector<bool> used(std::numeric_limits<unsigned int>::max());
for (unsigned int value : stream1)
{
used[value] = true;
}
for (unsigned int value : stream2)
{
if (used[value])
{
std::cout << value << " JE ve streamu 1" << std::endl;
}
else
{
std::cout << value << " NENI ve streamu 1" << std::endl;
}
}
return 0;
}
Složitost zjištění, jestli už prvek byl, je O(1). Zjištění výskytu diference si můžeš dodělat za domácí úkol. Pokud je rozsah tokenu větší než unsigned int, můžeš to hashovat a řešit kolize, složitost bude stále blízko O(1). Děkovat nemusíš.
-
milan: co zacal novy skolsky rok? :-) OK, kuzelne slovicko: triedenie (sorting)...
gamer: pekny pokus o vtip :-) ten tvoj vektor "used" zaberie X GB pamate, a preto je to O(1) podla mna len teoreticky... Lebo Cache je mensia ako RAM, aspon na mojom systeme :-) A navyse, skor je to neefektivne riesenie pre Milana, ako pre bla... Bla riesi nieco ine...
bla: ked uz to mas vyriesene (cez GPGU), a rychlost sedi... o co ide? O spotrebu? ci dobry pocit, ze je to "najoptimalnejsie" ako sa len da ? :-)
zakladna "optimalizacia"
urcite by bolo fajn pamatat si pocet nenulovych parov, a porovnavat (na identitu, ci rotaciu) len s tymi, ktore maju rovnaky pocet nenulovych parov.. (a potom mas kratsiu postupnost; a pre lepsie vyuzitie cache si urob mozno aj dajme tomu jej "kopiu", kde nie su nuly... ak tym usetris miesto... co pri 12tich nenulovych paroch z 32 urcite usetris...)
dalej, mozno by to chcelo (ked aj tak kontrolujes rotacie), skusit nieco ako definovat si nejaky "normalizovany" tvar:
teda zrotovat si tu postupnost tak, aby na zaciatku boli najmensie cisla... vymysli si nejaky dobry algoritms :-)
aj tak ale nechapem... tie delty musis kontrolovat aj vzhladom k celej historii a vsetkym moznym rotaciam historie???
nejako mi to moc nejde dokopy...
-
gamer: pekny pokus o vtip :-) ten tvoj vektor "used" zaberie X GB pamate, a preto je to O(1) podla mna len teoreticky... Lebo Cache je mensia ako RAM, aspon na mojom systeme :-) A navyse, skor je to neefektivne riesenie pre Milana, ako pre bla... Bla riesi nieco ine...
http://www.cplusplus.com/reference/vector/vector-bool/
The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is stored in a single bit. Většina implementací to dělá, ten vektor má 512 MB. O(1) to je vždycky, cache necache. Bla řeší prakticky to stejné, jenom to ještě neví ;).
-
Nevím, jestli se mi to zdá kvůli pokročilé noční hodině, nebo se tady fakt lidi radí, jak vyřešit nejasně formulovaný problém.
Milan:
- Původní dotaz bych vyřešil setříděním obou tabulek podle ID a následným sekvenčním projitím. Setřídit 50k čísel je hračka.
Bla:
- Zjišťování, zda byl token použit, si vysloveně říká o hashtable.
- Tu deltu jsem asi nepochopil. Pokud jsou ta čísla dvojciferná, můžeš mít nejvíc 99 delt a je to triviální. Tobě ale přichází i pozice, proti které musíš porovnávat? Ve třiceti dvou číslech je jenom comb(32; 2) = 496 párů, ne? Takže si můžeš udělat tabulku 496*99 = 50 kb (resp. 200 kB, pokud potřebuješ držet ještě nějaký index) a pak se podíváš na vybraná políčka.
gamer:
- Chápu správně, že indexuješ pole přímo tou hodnotou? Tazatel vůbec neuvedl, jak může být hodnota velká, klidně to můžou být 32b, nebo dokonce 64b čísla (sám používáš typ int); v prvním případě ti to sežere 4 Gb, ale spíš 4 GB (protože to ten bool vektor asi bude zarovnávat na bajty, ale C++ neznám) paměti, v druhém případě se ti to do paměti nevejde v žádném případě.
-
Bla: to jste vyřešili tak, že na GPU projdete úplně všechny tokeny? Neznám ta vstupní data, ale fakt by je nešlo třídit třeba podle rotace (seřazením prvků, sečtením prvků…) a podle těch delt, a pak už porovnat jenom kandidáty, co prošli?
-
Dakujem za odpovede.
Stlpec ID1 a ID2 obsahuje sestciferne cislo.
Stlpce HODNOTA1 a HODNOTA2 obsahuju MD5 hashe.
Udaje su zatial v dvoch CSV suboroch, neskor ich budem importovat do SQLitu.
-
Zdarec,
zda se mi idealni to resit pomoci algoritmu abecedniho porovnani, ale musis mit obe tabulky setridene podle ID.
Mas dve mnoziny ID - A a B, u kazde v cyklu drzis odkaz na klic mnoziny A a klic mnoziny B, a zacinas cyklus:
<zacatek cyklu>
Pokud je klic A mensi nez klic B -> pak zaznam z A podle klice A neni v mnozine B -> posun ukazatel klic A o jedno dal, KONEC
Pokud je klic A vetsi nez klic B -> pak zaznam z B podle klice B neni v mnozine A -> posun ukazatel klic B o jedno dal, KONEC
Pokud jsou oba klice shodne -> pak zaznamy podle klice A i B existuji v A i B -> porovnej hodnoty a mas rozdil -> posun oba klice A i B o jedno dal, KONEC
<KONEC>
jakmile dorazis na konec s jednim z ukazatelu na klic A nebo B pak ostatni zaznamy v opacne mnozine nejsou
jinak jdi na <zacatek cyklu>
-
Potrebujem vypisat
1. vsetky ID1 z Tabulka1, kde ID1 = ID2 a HODNOTA1 <> HODNOTA2
2. vsetky ID1 z Tabulka1, ktore chybaju v Tabulke2
3. vsetky ID2 z Tabulka1, ktore chybaju v Tabulke1
Pokud to jsou jen tisíce záznamů a cílem je (jednou, ne stokrát za sekundu) dostat výsledek, tak bych sáhl po pro člověka nejjednodušším řešení:
2. select id1 from tabulka1 minus select id2 from tabulka2
3. select id2 from tabulka2 minus select id1 from tabulka1
1. select id1 from tabulka1 join tabulka2 on (id1=id2) where hodnota1<>hodnota2
(a nebo s full outer joinem to přepsat jako jeden dotaz, ale to je už o trošku složitější na pochopení a odladění).