Porovnanie dvoch tabuliek

[milan]

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

[Reklama]

[MK]

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.

[Bla]

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.

[lobo]

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

[Bla]

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.

[Reklama]

[Bla]

(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...

[lobo]

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...

[Bla]

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í.

[lobo]

este napis ake mas ocakavania co sa tyka rychlosti

[Bla]

Já? Dáváme to "realtime"
On? Nejprve by měl poslat vzorek dat a říct, jestli to má v DB/CSV/atd

[Bla]

Máme funkční řešení porovnávání se dělá přes GPGPU

[Bla]

To bych ovšem pro původního pisatele nedoporučoval

[gamer]

Pro Bla:

Kód: [Vybrat]

#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íš.

[monitor]

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]

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í .