Выбор диапазонов для разделения набора данных

Question

У меня есть несколько миллионов целых чисел от 0 до 64К.Я хотел бы разделить их на N сегментов, где каждый блок содержит примерно одинаковое количество элементов из непрерывного диапазона.Так, например, если бы у меня была только одна точка данных с каждым возможным значением и 64 сегмента, в идеале я бы в итоге выделил интервал для 0-1024, один для 1025-2048 и т.д.алгоритм расчета диапазонов сегментов, который наиболее равномерно распределяет количество элементов?

Answer 1

Сортировка ваших чисел и заполнение блоков, которые содержат желаемое количество элементов, по мере того, как вы проходите через отсортированный список, является одной из возможностей.

Вы можете сделать что-то подобное, но, вероятно, быстрее, используя кучу : вы заполняете кучу своими элементами, а затем очень быстро извлекаете самые маленькие list_length/N элементы.

Однако, если скорость не слишком важна, сортировка 1 миллиона чисел является простой и быстрой (доли секунды в Python с Numpy).

Answer 2

Если вы сосредоточены на равномерном распределении, возможно, самый простой способ - отсортировать список, а затем поместить первые (list_length / N) элементы в первое ведро, затем следующие (list_length / N) элементы в следующее ведение и т. Д. Поскольку у вас достаточно большой список для сортировки, это, вероятно, не самое эффективное решение.