Il modo più veloce per trovare tutti i numeri con cifre

Facciamo un passo indietro per un momento e cerchiamo di capire perché vuoi farlo. Vuoi essere in grado di eseguire una ricerca per l'esistenza di un valore in un elenco di milioni di numeri? Hai bisogno di farlo più volte o solo una volta?

Il motivo per cui lo chiedo è che se è solo una volta, il modo più efficiente è semplicemente di caricare i numeri in memoria per eseguire un singolo passaggio per l'esistenza di quel numero nell'array. Le discussioni renderebbero questo ancor più efficiente, rompendo il lavoro in pezzi più piccoli. Se l'array fosse troppo grande per questo, potresti caricarlo un chunk alla volta, anche se presumo che tu stia potenzialmente duplicando i numeri in 10 array diversi, uno per cifra, la memoria non è un problema qui.

Se devi eseguire ricerche ripetute, ti consigliamo di utilizzare un trie . Si creano 9 bin con la prima cifra da cercare. Quel bambino ha quindi 10 contenitori contenenti la seconda cifra da cercare. Ripeti tutte le volte che vuoi. Rispetto all'approccio dei 10 array che hai menzionato, questo sicuramente occuperebbe meno memoria (i nodi non fogliari nella struttura rappresentano più numeri, non solo uno).

Il motivo per cui il tuo approccio potrebbe essere potenzialmente inefficiente è perché la probabilità di un numero contenente una cifra aumenta in modo significativo con ogni cifra aggiuntiva. Con un numero di 10 cifre, la probabilità che una cifra particolare non venga visualizzata è all'incirca (9/10) ^ 10 o 34%. Ciò significa che esiste il 66% di probabilità che un numero di 10 cifre venga visualizzato in un determinato set, il che significa più o meno che stiamo parlando di una duplicazione dei dati del 66%. I numeri più piccoli potrebbero essere più favorevoli, ma anche un numero a 3 cifre ha una frequenza di duplicazione del 27%.

Anche se la memoria non fosse un problema, la replica dei numeri sta rendendo meno efficiente l'algoritmo di ricerca.

Quindi la mia raccomandazione è di usare un Trie per le ricerche. Anche se per rispondere alla tua domanda, per ottenere un elenco di tutti i numeri contenenti una cifra specifica, il tuo approccio è il migliore. Sebbene a meno che non riesca a vedere l'albero dalla foresta, questo approccio non è probabilmente quello che vuoi ottenere.

Impostare l'intersezione è sicuramente una possibilità. Un altro metodo consiste nell'utilizzare un campo bit per descrivere quali cifre sono contenute in un numero. Quindi puoi fare una semplice operazione logica e confrontare. Ad esempio, per il numero 773, avrebbe i bit 7 e 3 impostati, quindi la sua maschera bit sarebbe: 0x88 (binario = 10001000). È quindi possibile utilizzare il "AND" logico del bit mask di qualsiasi numero e 0x88 e, se il risultato è 0x88, quel numero contiene le cifre in questione.

Trovare l'intersezione di insiemi coinvolgerebbe qualcosa come un accesso all'hash . Mentre gran parte del setup può essere precalcolato e conservato in memoria, devi comunque eseguire tutte le seguenti operazioni:

1. Supponiamo di cercare la lista N per le cifre a e b .
2. Passare a N, che ha ~ un milione di numeri
3. Per ogni numero nell'elenco:
   • Cerca nella tabella hash la cifra a per vedere se esiste N[i]
     • Scansiona i puntatori hash per il bucket hash giusto
     • Scansiona il bucket hash per vedere se N[i] esiste
   • Cerca nella tabella hash la cifra b per vedere se esiste N[i]
     • Scansiona i puntatori hash per il bucket hash giusto
     • Scansiona il bucket hash per vedere se N[i] esiste

D'altra parte, se hai saltato le tabelle e hai scritto un algoritmo efficace per il controllo sul posto, potresti:

1. Supponiamo di cercare la lista N per le cifre a e b .
2. Passare a N, che ha ~ un milione di numeri
3. Per ogni numero nell'elenco:
   • Per ogni cifra nel numero
     • Dividi per 10
     • Confronta il resto con a e b

Quindi per l'hash join, hai diverse complicate funzioni di ricerca e localizzazione, per ogni N[i] , tutte richiedono operazioni di lettura, incremento e confronto della memoria. Ciò significa {numero di numeri} x {numero di hashtables} x {righe nella ricerca hash + righe nel bucket hash}. Si moltiplicano tutti! Nel frattempo, per una scansione lineare, hai due operazioni di basso livello (un'operazione di divisione + modulo e un confronto) per numero. Questo è molto, molto meno elaborazione.

È difficile valutare le prestazioni da soli, ma suppongo che non otterrete molte prestazioni, se ve ne sono, da una soluzione di hash join. In realtà potrebbe essere peggiore a causa della bassa selettività - dato un numero compreso tra 1 e 1.000.000, circa il 50% di loro avrà una data cifra. Se quel numero fosse molto più piccolo, una tabella hash aumenterebbe un po 'le prestazioni, ma se stai ritirando la metà o più dei dati, una scansione inizia ad apparire sempre migliore. Se consideri l'aumento dell'utilizzo della memoria (e quindi l'aumento del working set) necessario per supportare le tabelle hash, ho intenzione di scommettere che le prestazioni del design hash / intersezione sarebbero peggiori.

Ecco un semplice codice che controlla in modo efficiente la presenza di un set di cifre. Ho usato questo algoritmo sul mio portatile Dell Precision e sono riuscito a scansionare 1.000.000 di numeri in 0.0120 secondi. Vorrei solo eseguire questa funzione, per numero nell'elenco, quando necessario.

int ContainsDigits(int numberToCheck, int digitsToFind[], int digitCount)
{
    int result;
    int digits[10];

    memcpy(digits, digitsToFind, digitCount * sizeof(int));

    while (numberToCheck > 0)
    {
        std::div_t result = std::div(numberToCheck, 10);
        for (int i = digitCount -1; i >= 0; i--)
        {
            if (result.rem == digits[i])
            {
                if (!--digitCount) return 1;
                digits[i] = digits[digitCount];
            }
        }
        numberToCheck = result.quot;
    }
    return 0;
}

L'algoritmo controlla la cifra meno significativa (data da n % 10 ) in un ciclo, quindi sposta il numero a destra (equivalente a n / 10 ). Possiamo ottenere il modulo e il quoziente in un'unica operazione ( std::div ).

Le cifre ricercate sono memorizzate in un array. Quando viene trovata una cifra, la matrice viene abbreviata di un elemento, con l'elemento finale spostato nella posizione della cifra scoperta, mantenendo così la lista compattata. Quando la matrice è vuota, tutte le cifre sono state trovate. Se il ciclo termina e non tutte le cifre sono state trovate, la funzione restituisce false.

È abbastanza facile farlo in Python:

def find_nums_with_digits(nums, digits):
    digits = ''.join(sorted(digits))

    char_map = {c: c if c in digits else None for c in '0123456789'}
    trans = str.maketrans(char_map)

    for num in nums:
        if digits in ''.join(sorted(num.translate(trans))):
            yield num

nums = ['773', '2267', '8957251', '170597519', '373590109', '982451707', '999999937']
for num in find_nums_with_digits(nums, '73'):
    print(num)

L'idea è che se ordiniamo le stringhe delle cifre e rimuoviamo le cifre a cui non siamo interessati, la tua condizione diventa solo un test di sottostringa.

Come menzionato nelle altre risposte, ci saranno modi più efficienti per farlo se stai cercando di testare molte combinazioni di cifre con lo stesso grande set di stringhe numeriche.

Un'altra opzione che assomiglia alla tua idea originale è quella di creare una struttura simile a hashtable in cui l'hash è la maschera di bit (come descritto nella risposta di user1118321) delle cifre in ciascun numero. Ogni numero viene quindi inserito in uno dei 1024 set possibili. Quindi per cercare, si utilizza la maschera bit corrispondente e i tasti AND per trovare l'insieme come nell'altra risposta. La differenza è che devi controllare al massimo 1024 valori anziché eseguire il ciclo sull'intero insieme.

Un vantaggio di questo è che ci sarebbe zero duplicazione attraverso i bucket. Lo spazio di archiviazione sarebbe N più i 1024 tasti. Se volevi costruire un trie sui tasti alla soluzione di Neil, puoi anche farlo.