Алгоритм быстрого поиска с std :: vector

Question

    for (std::vector<const std::string>::const_iterator it = serverList.begin(); it != serverList.end(); it++)
    {
        // found a match, store the location
        if (index == *it) // index is a string
        {
            indexResult.push_back(std::distance(serverList.begin(), it)); // std::vector<unsigned int>
        }
    }

Я написал приведенный выше код для просмотра вектора строк и возврата другого вектора с расположением любых "совпадений".

Есть ли способ сделать то же самое, но быстрее? (Если в контейнере 10 000 предметов, это займет некоторое время). Обратите внимание, что я должен проверить ВСЕ предметы на совпадения и сохранить их позицию в контейнере.

Бонусная слава: любой знает, каким образом / ссылками, как я могу сделать поиск, чтобы он нашел частичные результаты (Пример: поиск по "coolro" и сохранение местоположения переменной "coolroomhere")

Answer 1

Использовать двоичный_поиск после сортировки вектора

1. std :: sort (serverList.begin (), serverList.end ())
2. std :: lower_bound (serverList.begin (), serverList.end (), valuetoFind) для поиска первого совпадения
3. Используйте std :: equal_range , если хотите найти все совпадающие элементы

The lower_bound & equal_range поиск, потому что он двоичный, является логарифмическим по сравнению с вашим поиском, который O (N)

Answer 2

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

Если вы собираетесь делать много таких поисков в списке и в списке не меняется, вы можете подумать о расчете второй таблицы с хорошим хеш-код записей; снова в зависимости от типа данных, являющихся посмотрел вверх, это может быть более эффективным для вычисления хэш-кода индексировать и сначала сравнивать хеш-коды, сравнивая только строки, если хэш-коды были равны. Является ли это улучшением или нет в значительной степени зависит от размера таблицы и типа данных в ней. Ты можешь также быть в состоянии использовать знания о данных в строках; если все они, например, URL, в основном начинающиеся с "http://www.", начать сравнение с десятого символа и вернуться только к сравните первые 10, если все остальные равны, может закончиться большим выиграть.

Что касается поиска подстрок, вы можете использовать std::search для каждой элемент:

for ( std::vector<std::string::const_iterator iter = serverList.begin();
        iter != serverList.end();
        ++ iter ) {
    if ( std::search( iter->begin(), iter->end(),
                      index.begin(), index.end() ) != iter->end() ) {
        indexResult.push_back( iter - serverList.begin() );
    }
}

В зависимости от количества искомых элементов и длины участвующие строки, может быть более эффективно использовать что-то вроде BM-поиск, однако, предварительно компилирует строку поиска до необходимого таблицы перед входом в цикл.

Answer 3

Если вы сделаете контейнер std::map вместо std::vector, используемая базовая структура данных будет такой, которая оптимизирована для поиска по ключевым словам, подобным этому.

Если вы вместо этого используете std::multimap, функция-член equal_range () вернет пару итераторов, покрывающих каждое совпадение на карте.Для меня это звучит как то, что вы хотите.

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