- PHP
- matematică
- Tehnologii de căutare
- algoritmi
Aplicația Web compară în perechi seturile de numere întregi pozitive.
Fiecare set nu conține repetări în sine, oricare dintre numere nu depășește 210 de milioane (28 de biți).
Într-un set de ele pot fi de la 1 la 5 milioane.
Comparând seturile A și B, trebuie să obțineți seturile "unic pentru A", "unic pentru B" și "comun de bază". În special, răspundeți pur și simplu la întrebările "Există un număr N în setul S?"
Implementare, din păcate, pe php și în timpul găzduirii în comun. Implementarea greșită prin încărcarea găzduirii MySQL: pentru fiecare set un tabel temporar cu un singur index-coloană. În cele mai multe cazuri, tabelele depășesc dimensiunea care este plasată în motor = Memorie, iar pe tabelele pe disc aceasta nu este foarte rapidă, dar funcționează.
Cum să păstrați în mod eficient un astfel de set, astfel încât compararea celor două seturi să se efectueze rapid, ținând amprenta minimă din memorie?
A apărut să se noteze fiecare set cu o mască bitară cu o lungime de 2 ^ 28 biți (32Mb). Din 210 de milioane de biți, doar 5 milioane de unități, restul de 0: pot fi scrise cu numărul de zerouri dintr-un rând, de exemplu. Foarte similar cu o bicicletă. Spuneți tuturor, cu excepția mea, un algoritm cunoscut care este eficient pentru comprimarea datelor binare în cazul particular al "multor zerouri dintr-un rând"?
Despre codarea lui Huffman citi, se pare, că va fi ineficient să găsești fiecare din cele 5 milioane de numere ale celui de-al doilea set în interiorul primului.
nu 19Mb. În plus, în memoria PHP va dura de două ori mai mult. Acum, așa că "în frunte" și stocați - în baza de date, o coloană indexată de numere pe 32 de biți. În același loc pe care îl compar. Unicitatea cazului particular în absența repetării, lipsa ordinii și a gamei cunoscute. Din aceste trei detalii, vreau să storc compresia efectivă, viteza și memoria mică necesară.
Pentru a comprima o secvență de biți zero, aveți nevoie de o etichetă, care este urmată de nu un număr, ci un număr și apoi un număr. Să presupunem că aceste numere vor avea o dimensiune fixă de 32 de biți - atunci veți avea nevoie de aceleași cinci milioane de numere pe 32 de biți pentru a denumi secțiunile comprimate. Poate, probabil, într-un fel să pervertiți și să utilizați numere de lungime variabilă, dar acest lucru va complica codul și acesta deja trage unul dificil. Sortați aceeași matrice poate fi stocată într-un fișier simplu și citiți-o în părți (deși va fi mai dificil să umpleți o astfel de matrice). Apropo, nu doar numărul de 32 de biți, puteți utiliza biți superioare pentru informații de serviciu - de exemplu, pentru a crea o singură matrice, iar în biții de sus pentru a nota ceea ce seturi de acest număr se referă.
Trimiteți-le prietenilor: