Qual è il modo più veloce per calcolare la distribuzione di frequenza per array in C#?

Question

Mi chiedo quale sia l'approccio migliore per questo calcolo. Supponiamo di avere una matrice di input di valori e una matrice di limiti: volevo calcolare/benizzare la distribuzione di frequenza per ciascun segmento nell'array di limiti.

È consigliabile utilizzare la ricerca del bucket per quello?

In realtà ho trovato questa domanda Calculating frequency distribution of a collection with .Net/C#

Ma io non capisco come utilizzare benne a tal fine causano la dimensione di ciascun benna può essere diversa nella mia situazione.

EDIT: Dopo tutte le discussioni ho una soluzione di loop interno/esterno, ma comunque voglio eliminare il ciclo interno con un dizionario per ottenere prestazioni O (n) in quel caso, se ho capito correttamente ho bisogno di hash input valori in un indice bucket. Quindi abbiamo bisogno di una sorta di funzione di hash con complessità O (1)? Qualche idea su come farlo?

Answer 1

L'ordinamento con benna è già O (n^2) nel caso peggiore, quindi farei semplicemente un semplice ciclo interno/esterno qui. Dato che il tuo bucket array è necessariamente più corto del tuo array di input, tienilo sul loop interno. Dal momento che stai utilizzando dimensioni personalizzate del bucket, non ci sono davvero trucchi matematici che possano eliminare quel loop interno.

int[] freq = new int[buckets.length - 1]; 
foreach(int d in input) 
{ 
    for(int i = 0; i < buckets.length - 1; i++) 
    { 
     if(d >= buckets[i] && d < buckets[i+1]) 
     { 
      freq[i]++; 
      break; 
     } 
    } 
} 

È anche O (n^2) il caso peggiore ma non si può battere la semplicità del codice. Non mi preoccuperei dell'ottimizzazione finché non diventerà un vero problema. Se si dispone di un array bucket più grande, è possibile utilizzare una ricerca binaria di qualche tipo. Ma, dato che le distribuzioni di frequenza sono tipicamente di < 100 elementi, dubito che vedresti un sacco di vantaggi in termini di prestazioni nel mondo reale.

Answer 2

Se la matrice di ingresso rappresenta i dati del mondo reale (con i suoi modelli) e la matrice dei confini è grande per scorrere di nuovo e di nuovo nel ciclo interno si può considerare il seguente approccio:

• Prima di ogni sorta il tuo array di input. Se lavori con i dati del mondo reale , ti consiglio di considerare Timsort - Wiki per questo. Lo standard offre ottime garanzie di prestazioni per i modelli che possono essere visualizzati nei dati reali .

• Traverse mediante array filtrate e confrontarlo con il primo valore nella matrice dei confini:

  • Se valore nella matrice di ingresso è inferiore a confine - contatore di frequenza di incremento per questo confine
  • Se valore l'array di input è più grande del limite - passa al valore successivo in una matrice di limiti e incrementa il contatore per il nuovo limite.

In un codice che può assomigliare a questo:

Timsort(myArray); 
int boundPos; 
boundaries = GetBoundaries(); //assume the boundaries is a Dictionary<int,int>() 

for (int i = 0; i<myArray.Lenght; i++) { 
    if (myArray[i]<boundaries[boundPos]) { 
    boundaries[boubdPos]++; 
    } 
    else { 
    boundPos++; 
    boundaries[boubdPos]++; 
    } 
}