Как улучшить поиск связанных списков. C++

Question

У меня есть простой метод в C++, который ищет строку в связанном списке. Это работает хорошо, но мне нужно сделать это быстрее. Является ли это возможным? Может быть, мне нужно вставить элементы в список в алфавитном порядке? Но я не думаю, что это может помочь в серфинге. В списке имеется около 300 000 наименований (слов).

int GetItemPosition(const char* stringToFind) 
{ 
    int i = 0; 
    MyList* Tmp = FistListItem; 
    while (Tmp){ 
     if (!strcmp(Tmp->Value, stringToFind)) 
     { 
      return i; 
     } 
     Tmp = Tmp->NextItem; 
     i++; 
    } 
    return -1; 
} 

Метод возвращает номер позиции, если найденный элемент, в противном случае возвращает -1. Любой sugesstion будет полезен.

Спасибо за ответы, я могу изменить структуру. У меня есть только одно ограничение. Код должен реализовывать следующий интерфейс:

int Count(void); 
int AddItem(const char* StringValue, int WordOccurrence); 
int GetItemPosition(const char* StringValue); 
char* GetString(int Index); 
int GetOccurrenceNum(int Index); 
void SetInteger(int Index, int WordOccurrence); 

Какая структура будет по вашему мнению наиболее подходящей?

Answer 1

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

Элементы заказа не очень помогают, потому что вам все равно нужно перебирать каждый элемент.

Wikipedia article говорит:

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

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

Итак, в первом случае вы можете немного улучшить (по статистическим предположениям) свою эффективность поиска, перемещая предметы, найденные ранее ближе к началу списка. Это предполагает, что ранее найденные элементы будут искать более часто.

Второй способ требует использования других структур данных.

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

Answer 2

Рассмотрите возможность использования массива или std :: vector в качестве хранилища вместо связанного списка и используйте двоичный поиск, чтобы найти определенную строку или даже лучше, std :: set, если вам не нужен числовой индекс. Если по каким-то причинам невозможно использовать другие контейнеры, сделать это не так много - вам может понадобиться ускорить процесс сравнения, сохранив хэш строки вместе с ней в узле.

Answer 3

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

Answer 4

Вместо использования линейного связанного списка вы можете использовать дерево двоичного поиска или красное/черное дерево. Эти деревья предназначены для минимизации обходов, чтобы найти предмет.

Вы также можете сохранить «короткие ссылки». Например, если в списке есть строки, у вас может быть массив ссылок для начала поиска на основе первой буквы.

Например, shortcut['B'] вернет указатель на первую ссылку, чтобы начать поиск строк, начинающихся с 'B'.

Answer 5

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

В порядке вещей, сортировка списка не даст вам более быстрого поиска случайных предметов.

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

Итак, можете ли вы отредактировать свой вопрос и объяснить нам свои ограничения?

• Можете ли вы использовать совершенно другую структуру данных, такую ​​как массив или дерево? (как предлагали другие)
• Если нет, можете ли вы изменить способ связывания связанного списка?
• Если нет, то мы вряд ли поможет ...

Answer 6

Наилучшим вариантом является использование более быстрой структуры данных для хранения строк:

• станд :: карта - красно-черного дерева за кулисами. Имеет O (logn) для операций поиска/вставки/удаления. Подходит, если вы хотите сохранить дополнительные значения со строками (например, позиции).
• std :: set - в основном одно и то же дерево, но без значений. Лучше всего, если вам нужно только содержит.
• std :: unordered_map - хеш-таблица. O (1).
• std :: unordered_set - hash set. Также O (1) доступ.

Примечание. Но во всех этих случаях есть улов. Сложность рассчитывается только на основе n (количество строк). В действительности сравнение строк не является бесплатным. Таким образом, O (1) становится O (m), O (logn) становится O (mlogn) (где m - максимальная длина строки). Это не имеет значения в случае относительно коротких строк. Но если это неверно, используйте Trie. На практике trie может быть даже быстрее, чем хеш-таблица - каждый символ строки запроса обращается только один раз, а не несколько раз. Для хэш-таблицы/установите ее, по крайней мере, один раз для вычисления хеша и по крайней мере один раз для фактического сравнения строк (в зависимости от стратегии разрешения конфликтов - не уверен, как она реализована на C++).