Для моего проекта мне нужно очень эффективно дедуплицировать очень большие наборы строк. Т.е., учитывая список строк, которые могут содержать дубликаты, я хочу создать список всех строк в этом списке, но без дубликатов.
Вот упрощенный псевдокод:
set = # empty set
deduped = []
for string in strings:
if !set.contains(string):
set.add(string)
deduped.add(string)
Вот упрощенный C ++ для него (примерно):
std::unordered_set <const char *>set;
for (auto &string : strings) {
// do some non-trivial work here that is difficult to parallelize
auto result = set.try_emplace(string);
}
// afterwards, iterate over set and dump strings into vector
Однако, это не достаточно быстро для моих нужд (я тщательно его протестировал). Вот некоторые идеи, чтобы сделать это быстрее:
- Использовать другую реализацию набора C ++ (например, abseil)
- Вставить в набор одновременно (однако, согласно комментарию в реализации C ++ , это сложно. Кроме того, при распараллеливании будет происходить снижение производительности)
- Поскольку набор строк очень мало меняется при разных запусках, возможно, кешируйте, генерирует ли функция ha sh коллизии или нет. Если он не генерирует ничего (при учете изменений), тогда строки можно сравнивать по их ha sh во время поиска, а не по фактическому равенству строк (
strcmp). - Сохранение данных строк в файле при каждом запуске (однако, хотя это может показаться простым, здесь много сложностей)
Все эти решения, которые я обнаружил, либо непомерно хитры, либо не не может обеспечить такое большое ускорение. Любые идеи для быстрого дедупликации? В идеале, то, что не требует распараллеливания или кеширования файлов.