Il modo più efficace per archiviare questa raccolta di moduli e remainder?

Question

Il modo più efficace per archiviare questa raccolta di moduli e remainder?

#1 da (1 voti)
#2 da (-1 voti)

2

Ho un'enorme collezione di moduli diversi e associato a ogni modulo una lista abbastanza ampia di remainder. Voglio memorizzare questi valori in modo da poter determinare in modo efficiente se un intero è equivalente a uno qualsiasi dei remainders rispetto a uno qualsiasi dei moduli (non importa quale, voglio solo un vero / falso ritorno).

Ho pensato di archiviare questi valori come una lista collegata di alberi binari bilanciati, ma mi stavo chiedendo se c'è un modo migliore?

Modifica

Forse un po 'più di dettaglio sarebbe utile. Per quanto riguarda la dimensione di questa struttura, sarà in grado di contenere circa 10 s di migliaia di moduli (prime-1) e associati a ciascun modulo sarà una quantità variabile di resti. La maggior parte dei moduli avrà solo uno o due remainders associati ad esso, ma a pochi rarissimi ne saranno associati un paio di centinaia.

Questo fa parte di un programma più ampio che gestisce numeri con un paio di migliaia di cifre (decimali). Questo programma trarrà vantaggio dal fatto che questa tabella è la più ampia possibile e può essere ricercata rapidamente.

Ecco una piccola parte del set di dati in cui i moduli sono tra parentesi e i resti sono separati da virgola:

(46) k = 20
(58) k = 15, 44    
(70) k = 57        
(102) k = 36, 87    
(106) k = 66        
(156) k = 20, 59, 98, 137     
(190) k = 11, 30, 68, 87, 125, 144, 182 
(430) k = 234
(520) k = 152, 282
(576) k = 2, 11, 20, 29, 38, 47, 56, 65, 74, ...(add 9 each time), 569

Avevo detto che i moduli erano primi, ma mi sbagliavo sono tutti sotto un primo.

data-structures efficiency

posta Robert Wolfe 15.05.2014 - 00:34

fonte

2 risposte

Leggi altre domande sui tag data-structures efficiency

L'oggetto PaypalCheckout è composto da oggetti PaypalQuery. Nascondere oggetti PaypalQuery agli utenti di PaypalCheckout? Devo utilizzare SignalR per sincronizzare e memorizzare i dati CRUD in un'app mobile?

score 1 · Answer 1

La tua migliore scommessa sarà analizzare i dati mentre li leggi e buttare via ciò che non ti serve. Dal momento che non ti interessa il modulo a cui corrisponde un dato resto, o quante volte un dato resto appare, puoi semplicemente tenere un elenco di resti.

In pseudocodice, la compilazione potrebbe essere simile a:

while (data = ReadNextModulus())
   foreach (rem in data.Remainders)
      if !allRemainders.HasRemainder(rem) // We do this check because presumably lookups are faster 
         allRemainders[rem] = true        // than inserts, so we want to skip the insert if possible.

Quindi, quando hai finito e lo stai effettivamente utilizzando, devi solo controllare allRemainders.HasRemainder(rem) .

In termini di migliore struttura dei dati per archiviare ciò, non ho alcuna raccomandazione specifica da solo, ma posso indicarti la giusta direzione. Avrai un elenco di valori di int per i quali hai bisogno di una ricerca rapida. L'implementazione ingenua sarebbe quella di archiviarlo come una matrice non ordinata di int s. Ciò avrebbe richiesto O(n) . Se lo hai ordinato prima di usarlo, si ridurrebbe a O(log n) , supponendo che tu usi una ricerca binaria.

Ci sono altre opzioni là fuori, però. Questa domanda ne parla. Le risposte suggeriscono di provare un albero Van Emde Boas , una bitmap o semplicemente l'array ordinato discusso in precedenza. Dovrai dare un'occhiata a loro, considerare la scarsità dei dati che hai e la tua lingua di scelta come costruita nelle strutture dati, e scegliere quello che pensi sia il migliore.

Ma la chiave è che stai salvando se è stato visto un dato resto, non la struttura completa dei dati .

score -1 · Answer 2

Dato che non ti interessa a quale promemoria è collegato il numero intero e vedo che 87 è duplicato (e conterai solo una volta), potresti usare una struttura unica per memorizzare questi valori. Un array booleano fornisce la complessità O (1) per trovare se un elemento esiste o meno (se si conosce la dimensione massima e si può avere tutto nella RAM). Se anche questi valori possono avere migliaia di cifre e la RAM non è sufficiente, dovresti usare le strutture come albero (ad esempio alberi B) per avere complessità O (log n) (l'altezza dell'albero).