У меня есть несколько миллионов целых чисел от 0 до 64K. Я хотел бы разделить их на N сегментов, где каждый сегмент содержит примерно одинаковое количество элементов из непрерывного диапазона. Так, например, если бы у меня была только одна точка данных с каждым возможным значением и 64 сегмента, в идеале я бы получил сегмент для 0-1024, один для 1025-2048 и т. д.
Какой алгоритм расчета диапазонов корзин наиболее равномерно распределяет количество элементов?
Если вы стремитесь к равномерному распределению, проще всего будет отсортировать список и затем поместить первые (list_length / N) элементов в первое ведро, затем следующие (list_length / N) элементов в следующее ведро и т. д. Поскольку у вас довольно большой список для сортировки, это, вероятно, не самое эффективное решение.
Одной из возможностей является сортировка ваших чисел и заполнение корзин, содержащих желаемое количество элементов, по мере прохождения отсортированного списка.
Вы можете сделать что-то подобное, но, вероятно, быстрее, используя кучу: вы заполняете куча с вашими элементами, и вы можете очень быстро извлечь самые маленькие list_length/N элементы.
Однако, если скорость не слишком важна, сортировка 1 миллиона чисел является одновременно простой и быстрой (доля секунды в Python с Numpy).
