Оптимизация алгоритма размещения бина

Question

Хорошо, у меня есть две коллекции, и мне нужно поместить элементы из collection1 в ячейки (элементы) collection2 в зависимости от того, попадает ли их значение в диапазон заданной ячейки.

Для конкретного примера предположим, что у меня есть отсортированные объекты коллекции (ячейки), которые имеют диапазон int ([1 ... 4], [5..10] и т. Д.). Мне нужно определить диапазон, в который входит int, и поместить его в соответствующую ячейку.

foreach(element n in collection1) {
 foreach(bin m in collection2) {
  if (m.inRange(n)) {
   m.add(n);
   break;
  }
 }
}

Так что очевидный алгоритм сложности NxM есть, но я действительно хотел бы видеть Nxlog (M). Для этого я хотел бы использовать BinarySearch вместо внутреннего цикла foreach. Чтобы использовать BinarySearch, мне нужно реализовать класс IComparer для поиска. Проблема, с которой я сталкиваюсь, заключается в том, что этот подход потребует от меня создания функции IComparer.Compare, которая сравнивает два разных типа объектов (элемент с его корзиной), и это не представляется возможным или правильным. Вот я и спрашиваю, как мне написать этот алгоритм?

Answer 1

Давайте переформулируем проблему. Вы хотите написать

foreach(int item in items)
    bins[GetBinIndex(item)].Add(item);

так, что производительность GetBinIndex лучше, чем O (n) в количестве бинов.

Это зависит от топологии бункеров.

Если ячейки представляют собой просто непрерывные неотрицательные целочисленные диапазоны, скажем, 0..4, 5..9, 10..14 и т. Д., То просто разделите элемент на 5, готово. Это O (1).

Если ячейки представляют собой непрерывные целочисленные диапазоны разных размеров, скажем, 0..4, 5..14, 15..16, 17..17, 18..32, ... тогда:

• Создайте List<int>, в котором хранится вершина каждого диапазона. Так что в этом случае {4, 14, 16, 17, 32, ...}
• BinarySearch список для элемента.
• если результат - неотрицательное число, то это индекс корзины, и у вас есть элемент, находящийся вверху его корзины.
• если результат - отрицательное число, то это дополнение к лучшей корзине, верхний элемент которой больше, чем элемент. Возьмите дополнение индекса, и это мусорное ведро.

Это O (lg n) для поиска и O (n) для построения списка.

Если ячейки представляют собой несмежные целочисленные диапазоны, то есть, если диапазоны имеют дыры или перекрываются, то структура данных, которую вы хотите построить для эффективного поиска наилучшего диапазона, представляет собой дерево интервалов . Деревья интервалов обычно O (lg n) для поиска в непатологических ситуациях и O (n lg n) для построения дерева в первую очередь.

Answer 2

Я не уверен, что полностью понимаю вопрос, потому что я не получил эту часть:

Проблема, с которой я сталкиваюсь, заключается в следующем подход потребует от меня сделать IComparer.Compare функция, которая сравнивает два разных типа объекты (элемент в его корзину)

Тем не менее, я постараюсь сделать все возможное:

IComparer используется для сортировки коллекции, чтобы вы могли выполнить двоичный поиск. Взгляните на статью MSDN: http://msdn.microsoft.com/en-us/library/system.collections.icomparer.aspx

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

Вы не собираетесь использовать метод Array.BinarySearch (http://msdn.microsoft.com/en-us/library/system.array.binarysearch.aspx), потому что он ищет определенный объект в массиве (возможно, это то, на что вы ссылались в приведенной выше цитате?), Но вы может реализовать собственный бинарный поиск без особых затруднений.

Answer 3

ЕСЛИ (это большое значение, если) ваши бины имеют вычисляемые верхний и нижний индексы, тогда ваша проблема переходит в относительно простую и эффективную задачу разработки алгоритма хеширования и прохождения вашей коллекции элементов, которые будутодин раз.И если ваши бины не имеют вычислимых индексов, почему бы не преобразовать вашу проблему так, чтобы они ее имели?есть ли правило для вычисления границ по номеру бина.Итак, если у ваших корзин были границы 1..5, 6..10, 11..15 и т. Д., То правило:

bin_bounds = (bin_number-1)*5+1..(bin_number*5)

Функция хеширования просто обратнаяэтой функции, т. е. с учетом целого числа, вычислить порядковый номер ячейки.

НО, если границы на ваших ячейках по существу произвольны, найти такую ​​хеш-функцию будет практически невозможно.По моему опыту, ящики относительно необычного размера.Конечно, я не знаю вашей проблемы в деталях, поэтому все это может вам не помочь.

Answer 4

Двоичный поиск будет работать, только если элементы в Bin2 отсортированы. Итак, измените коллекцию Bin2 на отсортированную коллекцию (например, массив). Сортируйте его по m*logm времени, а затем используйте бинарный поиск, чтобы разместить новые элементы по logm времени. Всего: m*logm + n*logm. Это можно оптимизировать и дальше - но это только начало.