Distribuzione della frequenza per algoritmo di intervallo

Ci sono molti approcci, ma inizierò col dire che molti di loro rientrano nel regno delle micro-ottimizzazioni.

Il problema di base è O (N x M), dove N è il numero di valori di input e M è il numero di intervalli.

Nel peggiore dei casi, potresti avere M uguale o superiore a N, ma è improbabile. In tutto il codice di bucketing che ho scritto, M tende ad essere piuttosto piccolo: circa mezzo dozzina a una dozzina di valori.

In questo caso, il sovraccarico di ripetuti test di if è piccolo e il problema è essenzialmente O (N) (dove la costante è il numero di test). Dovresti essere in grado di elaborare diversi milioni di valori di input al secondo (dovrai eseguire i tuoi test per vedere cosa significa "diversi").

Se M è grande, ci sono diverse ottimizzazioni che puoi fare:

• Dato che Killian Foth ha detto, se gli intervalli sono uguali, dividi semplicemente per la spaziatura. Questo riduce il problema a O (N) (anche se con una costante diversa che può essere o meno inferiore ai test ripetuti, a seconda del costo di basso livello della ramificazione rispetto alla divisione).
• Se l'intervallo dei valori di input è vincolato, utilizzare un contatore per ciascun valore di input e quindi sommare quei contatori in seguito. Ad esempio, se sai che ognuno dei tuoi valori di input sarà compreso nell'intervallo 0-999, basta allocare un array di migliaia di elementi. Quanto grande è il valore di input che puoi gestire dipende dalla quantità di RAM che hai. Anche questo è O (N), con forse la costante più bassa.
• Se disponi di intervalli di dimensioni arbitrarie, puoi trasformarli in un albero binario. Questo ti darà O (N log M).
• Se i valori di input si estendono su un intervallo molto ampio, allora forse puoi cambiare il problema per usare il bucketing per logaritmo (es .: 0 - > 0-9, 1 - > 10-99, 2 - > 100- 999 e così via). Anche questo sarà O (N), ma la costante sarà enorme poiché i logaritmi sono un'operazione costosa.

Secondo me, l'approccio migliore è usare la semplice implementazione del test iterativo a meno che tu non abbia una buona ragione per non farlo. Una cosa che io farebbe , tuttavia, è implementare usando una tabella di intervalli piuttosto che test espliciti. Credo che quest'ultimo sia più incline ai bug, specialmente se è necessario modificare gli intervalli.

In effetti c'è. L'intuizione chiave è che division abbrevia esattamente questo approccio iterativo, nello stesso modo in cui moltiplicazione abbrevia l'aggiunta ripetuta dello stesso numero.

Poiché l'intervallo inizia da 0, la soluzione è particolarmente semplice. Basta dividere per 10 e guardare il numero risultante - non devi nemmeno preoccuparti di un valore di offset.

Dictionary<int,int> dic = new Dictionary;
for num in numbers
{  
  int key is num / 10;
  if(dic.ContainsKey(key))
      dic[key] ++;
  else 
      dic.Add(key,1);
}
return dic;