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

Question

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

Это хорошая идея - использовать поиск по сегменту для этого?

На самом деле я обнаружил, что вопрос Расчет частотного распределения коллекции с помощью .Net / C #

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

РЕДАКТИРОВАТЬ: После всех обсуждений у меня есть решение внутреннего / внешнего цикла, но все же я хочу исключить внутренний цикл с помощью словаря для получения производительности 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 элементов, я сомневаюсь, что вы увидите значительное повышение производительности в реальных условиях. </p>

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