Jaki jest najszybszy sposób obliczenia rozkładu częstotliwości dla tablicy w C#?

Question

Zastanawiam się, jakie jest najlepsze podejście do tego obliczenia. Załóżmy, że mam wejściową tablicę wartości i tablicę granic - chciałem obliczyć/rozproszyć rozkład częstotliwości dla każdego segmentu w tablicy granic.

Czy warto skorzystać z wyszukiwania kubełkowego?

Właściwie znalazłem na to pytanie Calculating frequency distribution of a collection with .Net/C#

Ale ja nie rozumiem, jak używać łyżki do tego celu powoduje, że wielkość każdego segmentu może być różny w mojej sytuacji.

EDYCJA: Po wszystkich dyskusjach mam rozwiązanie pętli wewnętrznej/zewnętrznej, ale nadal chcę wyeliminować wewnętrzną pętlę ze Słownikiem, aby uzyskać w tym przypadku wydajność O (n), jeśli dobrze zrozumiałem, potrzebuję wejścia mieszającego wartości do indeksu wiadra. A więc potrzebujemy jakiejś funkcji mieszającej o złożoności O (1)? Jakieś pomysły, jak to zrobić?

Answer 1

Najgorszy przypadek sortowania kubełków jest już O (n^2), więc po prostu wykonałbym tutaj prostą pętlę wewnętrzną/zewnętrzną. Ponieważ twoja macierz podręczna jest koniecznie krótsza niż tablica wejściowa, należy ją przechowywać w wewnętrznej pętli. Ponieważ używasz niestandardowych rozmiarów kubełków, tak naprawdę nie ma matematycznych sztuczek, które mogą wyeliminować tę wewnętrzną pętlę.

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; 
     } 
    } 
} 

Jest to również najgorszy przypadek O (n^2), ale nie można pokonać prostoty kodu. Nie martwiłbym się o optymalizację, dopóki nie stanie się prawdziwym problemem. Jeśli masz większą macierz, możesz użyć jakiegoś wyszukiwania binarnego. Ale ponieważ dystrybucje częstotliwości są zazwyczaj < 100 elementów, wątpię, byś zobaczył wiele rzeczywistych korzyści związanych z wydajnością.

Answer 2

Jeśli tablica wejście reprezentuje danych rzeczywistych (z jego wzorców) i tablica granic jest duża iteracyjne go ponownie w pętli wewnętrznej można rozważyć następujące podejście:

• przede wszystkim rodzaju twoja tablica wejściowa. Jeśli pracujesz z danymi rzeczywistymi , polecam rozważyć Timsort - Wiki. To zapewnia bardzo dobre gwarancje wydajności dla wzorców, które można zobaczyć w rzeczywistych danych .

• Przemierz posortowanej tablicy i porównać ją z pierwszej wartości w tablicy granic:

  • Jeśli wartość w tablicy wejściowego jest mniejsza niż granica - licznik przyrostu częstotliwości dla tej obwiedni
  • Jeśli wartość tablica wejściowa jest większa niż granica - przejdź do następnej wartości w tablicy granic i zwiększ ją do nowej granicy.

w kodzie może wyglądać następująco:

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]++; 
    } 
}