производительность — C ++ для сравнения 2 списков строк

Question

производительность — C ++ для сравнения 2 списков строк

В Python set довольно удобен для сравнения 2 списков строк (см. Это ссылка на сайт). Мне было интересно, есть ли хорошее решение для C ++ с точки зрения производительности. Поскольку каждый список содержит более 1 миллиона строк.

Это регистрозависимое соответствие.

3

c++performance set-intersection string-matching

Решение

Другие решения

Если вам не нужна большая производительность, я предлагаю использовать карту / набор из STL:

list<string> list, list2;
...
set<string> sndList;
list<string> result;

for(list<string>::iterator it = list2.begin(); it != list2.end(); ++it)
sndList.insert(*it);

for(list<string>::iteratir it = list.begin(); it != list.end(); ++it)
if(sndList.count(*it) > 0)
result.push_back(*it);

В противном случае я предлагаю для сравнения некоторую функцию хеширования.

0

Если это действительно std::list у вас есть, сортировать их и использовать set_intersection:

list<string> words1;
list<string> words2;
list<string> common_words;

words1.sort();
words2.sort();

set_intersection(words1.begin(), words1.end(),
words2.begin(), words2.end(),
back_inserter(common_words));

0

Источник

Accepted Answer

Типы данных std::set<> (обычно реализуется в виде сбалансированного дерева) и std::unordered_set<> (из C ++ 11, реализованный в виде хэша). Существует также удобный алгоритм под названием std::set_intersection это вычисляет фактическое пересечение.

Вот пример.

#include <iostream>
#include <vector>
#include <string>
#include <set>             // for std::set
#include <algorithm>       // for std::set_intersection

int main()
{
std::set<std::string> s1 { "red", "green", "blue" };
std::set<std::string> s2 { "black", "blue", "white", "green" };

/* Collecting the results in a vector. The vector may grow quite
large -- it may be more efficient to print the elements directly. */
std::vector<std::string> s_both {};

std::set_intersection(s1.begin(),s1.end(),
s2.begin(),s2.end(),
std::back_inserter(s_both));

/* Printing the elements collected by the vector, just to show that
the result is correct. */
for (const std::string &s : s_both)
std::cout << s << ' ';
std::cout << std::endl;

return 0;
}

Заметка. Если вы хотите использовать std::unordered_set<>, std::set_intersection не может использоваться как это, потому что он ожидает, что входные наборы будут упорядочены. Вы должны будете использовать обычную технику цикла for для итерации по меньшему набору и нахождения элементов в большем, чтобы определить пересечение. Тем не менее, для большого количества элементов (особенно строк) std::unordered_set<> может быть быстрее Есть также STL-совместимые реализации, такие как в Boost (boost::unordered_set) и тот, который создан Google (sparse_hash_set а также dense_hash_set). Для различных других реализаций и тестов (в том числе для строк) см. Вот.

9