Lo scopo del mio programma è quello di determinare l'offset del fuso orario corretto (GMT + k) in base a una serie di numeri. ad esempio:
-4 +11 1 -4 -4
Quindi, qui -4 (la modalità della serie) è il valore corretto. Ma questo richiede l'archiviazione delle serie, quindi l'analisi e non ho abbastanza memoria (RAM e FLASH) per questo. La media corrente può essere calcolata facilmente memorizzando la dimensione dell'elenco e la somma. C'è un caso simile per trovare la modalità?
Per calcolare la modalità da un data set irragionevolmente grande (o flusso) contenente solo un numero finito di elementi discreti (come gli interi in un intervallo piccolo), utilizzare una tabella per contare l'occorrenza di ciascun elemento, dove l'elemento in il set di dati è la chiave della nostra tabella. Quindi passiamo attraverso il set di dati e incrementiamo il contatore di quell'elemento. In qualsiasi momento possiamo determinare la modalità della parte elaborata del set di dati.
Esempio di pseudocodice
// all elements are integers in range a to b
a = ...
b = ...
table = new Array(size: b - a, default: 0)
// add items to the table
for item in stream {
table[item]++
}
// find the mode by sorting the table keys by their values
mode = range(a, b).sortBy(item => table[item])
Invece di un array, sarà necessario un tipo Map per scopi generali (ad esempio una mappa hash) se gli elementi non sono numeri interi.
La modalità è il singolo valore più comune. Chiaramente, devi semplicemente contare le occorrenze di ogni valore all'arrivo e alla fine cercare i conteggi per trovare il più grande. Ci sono alcune varianti interessanti.
Se e solo se (a) i valori sono interi (b) si conosce l'intervallo in anticipo (c) si conosce il limite superiore del conteggio, quindi è possibile preallocare una matrice di numeri interi adatti a contenere i conteggi. Questo è probabilmente il caso della tua situazione particolare.
Se (b) non è vero, puoi allocare un array ed essere pronto a ridimensionarlo al volo.
Se (a) non è vero, puoi usare un array hash (dizionario, mappa, ecc.) più o meno allo stesso modo, per alcuni costi delle prestazioni.
Se (c) non è vero (i conteggi potrebbero superare l'intervallo di int), è necessario essere pronti ad allocare un secondo array duplicato per contenere gli overflow. E un terzo, e così via.
Un ultimo aggiustamento. Se ricordi il valore e il conteggio più alto ogni volta che aggiorni la matrice, puoi evitare la ricerca finale.
C'è un modo per farlo se la modalità apparirà almeno il 50% delle volte:
def mode(numbers):
mode, count = 0, 0
for number in numbers:
if not count:
mode, count = number, 1
elif number == mode:
count += 1
else:
count -= 1
return mode
Se la modalità non ha questa proprietà, allora non riesco a pensare a un modo diverso dall'utilizzare un array di 24 contatori, incrementando quello corretto per ogni numero incontrato ( index = number + 11 ), quindi eseguendo il ciclo mantenendo traccia dell'indice con il conteggio maggiore. La modalità sarà quindi index - 11 .
Se non è possibile utilizzare un array, è possibile moltiplicare un numero primo ( number += 11; accumulator *= number * (number + 1) + 41 ) per ogni numero rilevato, quindi calcolare la fattorizzazione primo e tenere traccia dell'indice del fattore con il maggiore esponente. La modalità sarà quindi index - 11 . Il problema con questo è che un numero intero a 64 bit può memorizzare solo pochi numeri primi (8, forse 10) moltiplicati insieme prima di straripare.
Quanto spesso si ripeterà un valore? Se la risposta è "raramente", potrebbe essere meglio memorizzare l'intera serie, in quanto le varie opzioni Mappa / contatore probabilmente utilizzano più memoria. Solo quando c'è una buona dose di ripetizioni sono un vantaggio.
Leggi altre domande sui tag algorithms