Problema algoritmico: trovare rapidamente tutti i # in cui il valore% x è un determinato valore

6

Problema che sto cercando di risolvere, mi scuso in anticipo per la lunghezza:

Dato un gran numero di record archiviati, ognuno con un campo (String) unico S. Mi piacerebbe poter trovare attraverso una query indicizzata tutti i record dove Hash (S)% N == K per qualsiasi N arbitrario , K (ad esempio, dato un milione di stringhe, trova tutte le stringhe in cui HashCode (s)% 17 = 5. Esiste un modo di memoizzarlo per poter rispondere rapidamente a qualsiasi domanda di questo modulo senza fare la% su ogni valore?

La motivazione per questo è un sistema di N nodi distribuiti, in cui ogni record deve essere assegnato ad almeno un nodo. I nodi sono numerati 0 - (K-1) e ogni nodo deve caricare tutti i record che corrispondono al suo numero:

Se abbiamo 3 nodi

  • Il nodo 0 carica tutti i record in cui Hash% 3 == 0
  • Il nodo 1 carica tutti i record in cui Hash% 3 == 1
  • Il nodo 2 carica tutti i record in cui Hash% 3 == 2

aggiungendo un quarto nodo, ovviamente tutti i compiti devono essere ricalcolati -

  • Il nodo 0 carica tutti i record in cui Hash% 4 == 0
  • ...
  • etc

Mi piacerebbe trovare facilmente questi record attraverso una query indicizzata senza dover calcolare singolarmente la mod.

Il meglio che ho potuto fare finora:

Se prendiamo i fattori primi di N (p1 * p2 * ...)

se N% M == I allora p% M == I% p per tutti i fattori primi di N

es. 10 nodi:

N% 10 == 6 quindi

  • N% 2 = 0 == 6% 2
  • N% 5 = 1 == 6% 5

quindi l'archiviazione di un array di "%" di N per il primo numero "ragionevole" di numeri primi del mio set di dati dovrebbe essere utile. Ad esempio nell'esempio precedente memorizziamo l'hash e i primi

HASH PRIMES (array di% 2,% 3,% 5,% 7, ...])

16 [0 1 1 2 ..]

quindi cercare N% 10 == 6 equivale a cercare tutti i valori dove array [1] == 1 e array [2] == 1.

Tuttavia, questo si rompe al primo primo più grande del numero più alto che sto memorizzando nella tabella dei fattori. Esiste un modo migliore?

    
posta Steve B. 23.08.2012 - 18:13
fonte

2 risposte

3

Quanto è importante la formula essere "Hash% num_machines"? Questa formula è usata per cache distribuite, come memcached. Funziona benissimo finché non aggiungi / rimuovi nodi. A quel punto, il consiglio è di abbandonarlo e utilizzare hashing coerente.

    
risposta data 23.08.2012 - 20:40
fonte
0

A meno che non abbia frainteso qualcosa, la tua congettura è errata.

If we take the prime factors of N (p1 * p2 * ... )

if N % M == I then p % M == I % p for all of N's prime factors

Come sei arrivato a questo?

Diciamo N = 36 e M = 6

La fattorizzazione principale di N = 2 * 2 * 3 * 3 . 36 % 6 = 0

Secondo la tua dichiarazione, dovrebbe contenere quanto segue:

p % 6 = 0 % p = 0

Ma chiaramente, questo non è il caso: 2 % 6 = 2 != 0

    
risposta data 31.08.2012 - 12:56
fonte

Leggi altre domande sui tag