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

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

Можно ли использовать поиск в bucket для этого?

На самом деле я нашел этот вопрос Вычисление частотного распределения коллекции с .Net/С#

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

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

Ответ 1

Сортировка ковша уже 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 элементов, я сомневаюсь, что вы увидите много преимуществ в реальном мире.

Ответ 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]++;
  }
}