Лучший алгоритм непрерывной сортировки?
Ответ - Вам нужно преобразовать объект геометрии, который у вас есть, в хорошо известный текст. Вы найдете информацию о том, как это сделать в документации API vividsolutions .
geoobject.toText();
- Вставить / обновить данные с помощью метода mysql GeomFromText .
INSERT INTO geom VALUES (GeomFromText(@g));
geoobject.toText();
INSERT INTO geom VALUES (GeomFromText(@g));
9 ответов
Построение самобалансирующегося двоичного дерева, такого как красно-черное дерево или AVL-дерево , позволит вставлять и удалять Θ (lg n), и Θ (n) извлечение всех элементов в отсортированном порядке (путем обхода в глубину) с использованием памяти Θ (n). Реализация несколько сложна, но они эффективны, и большинство языков будут иметь реализации библиотеки, поэтому в большинстве случаев они являются хорошим первым выбором.
Кроме того, получение i-го элемента может быть выполнено путем аннотирования каждого края (или, что то же самое, узел) в дереве с общим количеством узлов под ним. Затем можно найти i-й элемент в Θ (lg n) времени и Θ (1) пространстве с чем-то вроде:
node *find_index(node *root, int i) {
while (node) {
if (i == root->left_count)
return root;
else if (i < root->left_count)
root = root->left;
else {
i -= root->left_count + 1;
root = root->right;
}
}
return NULL; // i > number of nodes
}
Реализацию, поддерживающую это, можно найти в debian's libavl ; к сожалению, сайт разработчика не работает,
Скорее всего, сортировка кучи. Кучи - это только O (log N) для добавления новых данных, и вы можете вывести чистые результаты в любое время в O (N log N) времени.
Если вам всегда нужно каждый раз сортировать весь список, то есть не так много других вариантов, кроме сортировки вставкой . Скорее всего, это будет O (N ^ 2), хотя с ОГРОМНЫМИ хлопотами связанных списков пропуска вы можете сделать это O (N log N).
Я бы использовал очередь кучи / приоритета. Худший случай такой же, как средний случай для времени выполнения. Следующий элемент может быть найден за время O (log n).
Вот шаблонная реализация C # , которую я извлек из этого кода .
Структура , используемая для индексов программ баз данных , представляет собой дерево B +. Это сбалансированное n-арное дерево с сегментами.
Для дерева B + b-порядка с h уровнями индекса:
- Максимальное количество сохраняемых записей - n = b ^ h
- Минимальное количество ключей - 2 (b / 2) ^ (h − 1)
- Пространство, необходимое для хранения дерева, равно O (n)
- Для вставки записи требуется O (log-b (n )) операций в наихудшем случае
- Для поиска записи требуется O (log-b (n)) операций в наихудшем случае
- Удаление (ранее расположенной) записи требует O (log-b (n)) операций в наихудший случай
- Выполнение запроса диапазона с k элементами, встречающимися в пределах диапазона, в худшем случае требует O (log-b (n + k)) операций.
Я использую это в своей программе. Вы можете добавлять свои данные в структуру по мере их поступления, и вы всегда можете перемещаться по ней по порядку, от начала до конца или назад к началу, или быстро искать любое значение. Если вы не найдете значение, у вас будет точка вставки, где вы можете добавить значение.
Вы можете оптимизировать структуру своей программы, поигравшись с b, размером сегментов.
Интересная презентация о деревьях B +: Древовидные индексы
Вы можете получить весь код на C ++ .
Edit: Теперь я вижу ваш комментарий о том, что ваше требование знать «i-й отсортированный элемент в наборе» является важным. Внезапно это делает многие структуры данных менее оптимальными.
Вам, вероятно, лучше всего подходит SortedList или, что еще лучше, SortedDictionary. См. Статью: Повышение производительности с помощью SortedList . Обе структуры имеют функцию GetKey, которая возвращает i-й элемент.
Хорошо, вы хотите, чтобы данные были отсортированы, но вам нужно извлечь их с помощью номера индекса.
Начните с простого дерева, такого как упомянутые красно-черные деревья.
Изменить алгоритм дерева такой, что при вставке элементов в дерево все узлы, встречающиеся во время вставки и удаления, ведут подсчет количества элементов в каждой ветви.
Затем, когда вы извлекаете данные из дерева, вы можете вычислять индекс по мере того, как вы go и узнайте, какую ветвь выбрать, в зависимости от того, больше или меньше индекса, который вы пытаетесь извлечь.
Еще одно соображение. Более 10 миллионов элементов в дереве, использующем динамическое распределение памяти, потребуют много дополнительных ресурсов памяти. т.е. указатели могут занимать больше места, чем ваши фактические данные, плюс любой другой член, используемый для реализации структуры данных. Это приведет к серьезной фрагментации памяти и, в худшем случае, к снижению общей производительности системы. (Возврат данных в виртуальную память и обратно.) Вы можете рассмотреть возможность реализации комбинации блочного и динамического распределения памяти. Что-то там, где вы сортируете дерево на блоки данных, тем самым уменьшая накладные расходы на память.
Check out the comparison of sorting algorithms in Wikipedia.
Рандомизированные списки прыжков тоже интересны. Они требуют меньше места, как BST и Skiplists. Вставка и удаление - O (log n)
By a "set of double data," do you mean a set of real-valued numbers? One of the more commonly used algorithms for that is a heap sort, I'd check that out. Most of its operations are O( n * log(n) ), which is pretty good but doesn't meet all of your criteria. The advantages of heapsort is that it's reasonably simple to code on your own, and many languages provide libraries to manage a sorted heap.
Если вам просто нужно знать i-й наименьший элемент, как сказано в комментариях, используйте алгоритм BFPRT, названный в честь фамилий авторов: Блюм, Флойд, Пратт, Ривест и Тарьян, и в целом согласен быть самой большой концентрацией больших компьютерных мозгов в одной и той же статье. O (n) худший случай.