[Py] Divide et Impera sau cel mai potrivit algoritm pentru solutie

[fedorffixxzz]

Am nevoie de ajutorul vostru in a ma decide ce algoritm sa folosesc pentru urmatoarea problema.

Se da o baza de date cu un tabel ce cuprinde 10 milioane de randuri:

+---+-------+

| id | value |

+---+-------+

ID: de la "a" la "n".

Atunci cand baza de date porneste, scriptul meu cheama functia "get_values()" ce returneaza sub forma urmatoare fiecare id si valoarea sa:

"'<id>':\t'<value>'"

Scriptul meu la randul sau, este un wrapper, si returneaza un dictionar de forma urmatoare:

dict = {'id[0]': 'value', ... , 'id[n]': 'value'} (faceti abstractie la forma de array pentru id-uri, exemplifica faptul ca returneaza fiecare id si valoarea sa intr-un dictionar).

Un motor de testare injecteaza diferite input-uri incercand sa faca baza de date sa rezulte in crash. Odata ce baza de date a facut crash, un alt motor ce monitorizeaza va restarta baza de date cu tabelul si randurile cum au fost lasate ultima data, nu este nicio procedura de fail-safe sau abstractie intre parinte -> child pentru a izola fault-urile.

Procesul se repeta, se returneaza un dictionar, insa de data asta se compara cu cel original.

Sa zicem:

control = {'a': 'a value', ... , 'n': 'n value'}

crash = {'a': 'some value', ... , 'n': 'some value'}

Presupunem ca doar jumatate din toate id-urile au ramas intacte, alta jumatate sunt rasfirate cu valori schimbate.

Procesul urmator, este de a face diferenta intre acestea. Insa eu am posibilitatea sa specific functiei "make_diff(*exclusions)" ce sa exclud. De exemplu, nu vreau ca 'e' si 'f' (id-urile) sa fie comparate, asa ca le exclud si vreau sa mi se returneze fara ele.

Tinand cont ca am i = 0, iterez prin cele doua in acelasi timp, asa ca in control si crash sunt aceleasi key comparate (valorile sale): control['a'] si crash['a'] cand i =0, apoi control['b'] si crash['b'] cand i = 1, etc. Insa nu cred ca este eficient, asta inseamna de la stanga la dreapta sa itereze prin fiecare.

Divide et impera:

Tinand cont ca am n elemente, incep de la jumatate: n/2. Daca elementul din stanga lui n/2 este diferit de n/2 (n/2 != n/2-1) atunci pornim in stanga, daca sunt la fel, pornim in dreapta:

[ 0 ] [ ... ] [n/2-1] [n/2] [n/2+1] ... [n+1] [ n ]
----------------------/    \----------------------------

Este adecvat pentru aceste dictionare? Daca am un element dupa n/2-1 (n/2-2) care nu este la fel cu n/2, insa n/2-1 este la fel cu n/2 ar insemna sa pierd pe n/2-2 din moment ce pornesc spre dreapta.

Ideea este sa returneze key-ul (exemplu: 'a') cu valoarea sa inainte ('a value') si apoi valoarea sa dupa ('some value'): 'a' -> 'before: a value | after: some value'.

Si mai mult cred ca este o matrice 2d din moment ce nu am array ci dictionare. Ce credeti?

Trebuie tinut cont ca pe un array 1d ar fi o complexitate de log(O)n banuiesc, iar daca luam 10 mil de intrari pe o iterare de la stanga la dreapta completa ar lua 15 secunde (presupunem), iar cu D et I ar lua 0.001.

Daca luam 10 secunde pentru a ne conecta la baza de date, si 15 secunde sa luam toate entry-urile si sa le returnam comparate cu diferentele intre ele, iar daca inmultim astea cu 10 sisteme, ar insemna 250 de secunde, ceea ce este enorm de mult.

Edited July 16, 2013 by fedorffixxzz