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.
Citace od: milan kdy 04. 09. 2014, 21:22:51
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.
Citace od: Bla kdy 04. 09. 2014, 23:12:22
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...
Citace od: monitor kdy 05. 09. 2014, 01:46:44
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>
Citace od: milan kdy 04. 09. 2014, 21:22:51
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í).