#c
#c
Вопрос:
Я выполняю проект колледжа по управлению библиотеками с использованием двусвязных списков. Двусвязный список содержит идентификаторы книг во время сортировки.
Я попытался рассчитать время, прошедшее для наихудшего случая для линейного и двоичного поиска. Следующие результаты:
Binary search: 0.311ms
Linear search: 0.228ms
[Number of inputs(id's): 10000000]
МОЙ ВОПРОС:
Несмотря на то, что для двоичного поиска требуется O (logn) сравнений, затраченное время было больше из-за того, что потребовалось O (n) обходов, пока не найдено среднее значение. Есть ли лучший алгоритм поиска для отсортированного двусвязного списка, а не громоздкий линейный поиск?
Моя реализация для нахождения среднего значения, необходимого для двоичного поиска:
struct node* middle(node* start, node* last)
{
if (start == NULL)
return NULL;
struct node* slow = start;
struct node* fast = start -> next;
while (fast != last)
{
fast = fast -> next;
if (fast != last)
{
slow = slow -> next;
fast = fast -> next;
}
}
return slow;
}
Комментарии:
1. Выбор связанных списков ваш или это обязательно? Потому что, извините, но я действительно не вижу смысла двоичного поиска в связанном списке.
2. По определению, связанный список не допускает двоичный поиск. Ускорить поиск можно, только если у вас есть (и поддерживать) дополнительную структуру данных, указывающую на определенные точки в списке, но это никогда не будет бинарный поиск.
3. @-Bob__ выбор не является обязательным. Во время запуска программы сведения о книге (например, название, автор, цена, количество), которые находятся в файле, загружаются в dbl (они хранятся в структуре, а dbl содержит всю структуру в качестве своих элементов). Затем все необходимые операции, такие как поиск, выполняются непосредственно в dbl. Я действительно не хочу создавать другую структуру данных только для упрощения операции поиска и пустой траты памяти. Я ищу лучший алгоритм поиска для отсортированного dbl
4. @user8570772: Учитывая выбор между «простым» и «хорошим», вы выбрали «простой», и теперь вы задаетесь вопросом, почему это не хорошо?
5. Чтобы бинарный поиск был эффективным, вы должны иметь возможность получить прямой доступ к элементу — произвольный доступ . Хорошим примером является массив: для доступа к массиву [N] программа берет базовый адрес массива и добавляет N * sizeof(элемент) и, таким образом, знает, где найти данные, без итеративного обхода. Потому что, как вы заметили, последовательный доступ к списку требует итеративного обхода для поиска среднего элемента, что компенсирует повышение эффективности двоичной сортировки.
Ответ №1:
Ваше сравнение должно было бы быть невероятно медленным, чтобы оправдать всю эту навигацию. В нынешнем виде я не могу придумать лучшего способа, чем линейный поиск. Если вы можете изменить структуры и CRUD, вы, безусловно, можете индексировать ключевые точки («A» начинается здесь, «B» начинается здесь и т.д.), И это позволило бы вам лучше угадать начало и направление вашего линейного поиска.
Я думаю, вы обнаружите, что связанный список, двойной или иной, не является отличным выбором для случайного поиска или обновления по порядку. Используйте B-дерево, которое, по-видимому, лучше подходит для ситуаций, которые вы описали в своем вопросе и комментариях.
Комментарии:
1. У меня есть глобальный средний указатель (который содержит среднее значение), указатели head и tail просто для ускорения операций поиска.
Ответ №2:
затраченное время было больше из-за того, что потребовалось O (n) обходов, пока не было найдено среднее значение.
Когда вы вставляете новые элементы в связанный список, вы также можете отслеживать средний элемент, как вы делаете с первым и последним. Хотя функция insert будет более сложной.
Я бы использовал структуру для связанного списка с 4 полями:
- начальный узел
- средний узел
- последний узел
- длина
Комментарии:
1. Также взгляните на список пропусков
2. Да, у меня есть глобальный средний указатель, содержащий среднее значение. Но это становится все более и более сложным по мере продолжения поиска среднего значения, пока не будет найден запрошенный идентификатор. ПРИМЕР: Допустим, я хочу найти 799999 из 1000000 идентификаторов, поиск среднего указателя становится затруднительным
3. Было бы дорого, если бы вы делали это с циклом while, который проходит через список наполовину. Но я хочу сказать, что когда вы вставляете новый элемент, проверьте, нужно ли обновлять средний элемент, если да, то ему пришлось бы переместить только одну позицию, на следующую или предыдущую.
Ответ №3:
Двоичный поиск достигает O (log N) сложности в количестве сравнений. При использовании с массивом доступ к i-му элементу массива выполняется за постоянное время, следовательно, не влияет на общую временную сложность.
При использовании списка, односвязного или двусвязного, доступ к i-му элементу занимает i шагов. В вашем примере доступ к среднему элементу занимает количество шагов, пропорциональных длине списка. Как следствие, сложность этого поиска по-прежнему заключается в O (log N) сравнениях, но O (n) для выбора элементов для сравнения, что становится доминирующим фактором.