Каков самый быстрый способ рассчитать распределение частот для массива в C#?

Question

Мне просто интересно, какой лучший подход для этого расчета. Предположим, что у меня есть входной массив значений и массив границ - я хотел рассчитать/bucketize распределение частот для каждого сегмента в массиве границ.

Полезно ли использовать поиск в ковше для этого?

На самом деле я обнаружил, что вопрос Calculating frequency distribution of a collection with .Net/C#

Но я не понимаю, как использовать ведра для этой цели вызвать размер каждого сегмента может быть различным в моей ситуации.

EDIT: После всех обсуждений у меня есть решение для внутреннего/внешнего контура, но все же я хочу исключить внутреннюю петлю с помощью словаря, чтобы получить производительность O (n) в этом случае, если я правильно понял, мне нужен хэш-вход значения в индекс ковша. Итак, нам нужна какая-то хеш-функция с сложностью O (1)? Есть идеи, как это сделать?

Answer 1

Bucket Sort уже O (n^2) наихудший случай, поэтому я бы просто сделал простой внутренний/внешний цикл здесь. Поскольку ваш массив ведра обязательно короче, чем ваш входной массив, держите его во внутреннем цикле. Поскольку вы используете пользовательские размеры ведра, на самом деле нет математических трюков, которые могут устранить этот внутренний цикл.

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

Это также O (n^2) наихудший случай, но вы не можете победить простоту кода. Я бы не стал беспокоиться об оптимизации, пока это не станет реальной проблемой. Если у вас большой массив ведра, вы можете использовать двоичный поиск. Но, поскольку частотные распределения обычно составляют < 100 элементов, я сомневаюсь, что вы увидите много преимуществ в реальном времени.

Answer 2

Если входной массив представляет реальные данные (с его узорами) и массив границ велик, чтобы перебирать его снова и снова во внутреннем цикле вы можете рассмотреть следующий подход:

• Прежде всего рода ваш входной массив. Если вы работаете с реальными данными , я бы рекомендовал рассмотреть Timsort - Wiki. Он обеспечивает очень хорошие гарантии производительности для моделей, которые можно увидеть в данных реального мира.

• траверса через отсортированный массив и сравнить его с первым значением в массиве границ:

  • Если значение входного массива меньше, то граница - частоты приращения счетчика для этой границы
  • Если значение входной массив больше, чем граница - перейти к следующему значению в массиве границ и увеличить счетчик для новой границы.

В коде может выглядеть следующим образом:

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