Сортировка элементов в «бункеры» C ++

Question

Здравствуйте. Мне было интересно, какой самый эффективный способ сортировки элементов в «корзины» в c ++.

Например, у нас может быть 3 корзины:

• Корзина A принимает целые числа от 0-10
• Bin B принимает целые числа от 5-20
• Bin C принимает целые числа от 25-30

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

Какой самый эффективный способ сделать это?

Answer 1

Это зависит.

Если количество бинов мало, простой линейный поиск обычно достаточно эффективен. Особенно, если принять во внимание время программиста.

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

Если набор целые числа большие, но сами бины относительно малы, мы можем сделать что-то похожее, но используя таблицу ha sh вместо вектора.

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