C# içindeki dizi için frekans dağılımını hesaplamanın en hızlı yolu nedir?

Question

Sadece bu hesaplama için en iyi yaklaşımın ne olduğunu merak ediyorum. Bir dizi girdi dizisi ve sınır dizisi olduğunu varsayalım - Sınır dizisindeki her segment için frekans dağılımını hesaplamak/hesaplamak istedim.

Bunun için kova aramayı kullanmak iyi bir fikir midir?

Aslında bu soruyu Calculating frequency distribution of a collection with .Net/C#

bulundu Ama her bir bölüm boyutu benim durumda farklı olabilir neden bu amaçla kovaları nasıl kullanılacağını anlamıyorum.

DÜZENLEME: iç/dış döngü çözüm, ama giriş karma gereken doğru anlamış hala, bu durumda O (n) performans elde etmek için bir sözlük ile iç döngü ortadan kaldırmak için kullanılmaktadır bütün tartışmalar sonra bir kepçe dizinine değerler. Yani O (1) karmaşıklığı ile bir çeşit karma işlevine ihtiyacımız var? Herhangi bir fikir nasıl yapılır?

Answer 1

Kova Sıralama zaten O (n^2) en kötü durumdur, bu yüzden burada basit bir iç/dış döngü yapardım. Kova diziniz zorunlu olarak giriş dizinizden daha kısa olduğundan, iç döngüde tutunuz. Özel kepçe boyutlarını kullandığınızdan, bu iç döngüyü ortadan kaldıracak hiçbir matematiksel hile yoktur.

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

Ayrıca O (n^2) en kötü durumdur, ancak kodun sadeliğini geçemezsiniz. Gerçek bir sorun haline gelene kadar optimizasyon konusunda endişelenmem. Daha büyük bir kova diziniz varsa, bir çeşit ikili arama kullanabilirsiniz. Ancak, frekans dağılımları genellikle < 100 eleman olduğundan, çok fazla gerçek dünya performans avantajı göreceğinizden şüpheliyim.

Answer 2

senin girdi dizi (kendi desenlerle) gerçek dünya verileri temsil eder ve sınırların dizisi tekrar tekrar yineleme iç döngüde sen şu yaklaşımı düşünebilirsiniz büyükse: Bütün çeşit

• İlk giriş diziniz. Gerçek dünya verisi ile çalışıyorsanız bunun için Timsort - Wiki'u dikkate almanızı öneririz. , gerçek dünya verilerinde görülebilen desenler için çok iyi performans garantileri sağlar. kriteri dizi aracılığıyla

• Traverse ve sınırların dizideki ilk değeri ile karşılaştırmak:

  • giriş dizideki değer, sınır daha sonra daha az ise
    - bu sınır için artış frekans sayacı
  • Eğer değer girdi dizisi daha sonra sınırdır - sınır dizisinde bir sonraki değere gidin ve yeni sınır için sayacı artırın. Böyle bakabilirsiniz bir kodda

:

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