В C++ предположим, что у вас есть неупорядоченный набор (https://en.cppreference.com/w/cpp/container/unordered_set) строк — есть ли способ эффективно извлечь все строки из этого набора, которые соответствуют определенным критериям (например, найти все строки в наборе, начинающиеся с буквы «а»), используя метод кроме перебора всего набора с помощью цикла for и проверки первого символа каждой отдельной строки?
эффективное извлечение элементов из неупорядоченного набора C++
comment
Технически нет. Конечно, вы можете использовать некоторые алгоритмы или функции, но они будут перебирать контейнер в цикле. Вы можете использовать цикл while вместо цикла for ;-)
- person Thomas Sablik schedule 18.06.2020
comment
Если вам нужно проверить каждый элемент, это невозможно сделать, не перебирая набор так или иначе. Вы можете использовать стандартные функции алгоритма, чтобы скрыть итерацию от вас и высоко оптимизированы, но их все еще нужно повторять.
- person Some programmer dude schedule 18.06.2020
Ответы (3)
Для любых критериев это невозможно, см. этот ответ для более подробной информации.
В зависимости от ваших других потребностей, отсортированный std::vector с большой вероятностью будет наиболее эффективным только для части извлечения. Используйте такие алгоритмы, как std::lower_bound для работы с отсортированными std::vector. В конце концов, ваши фактические варианты использования определяют, какой контейнер лучше всего подходит с точки зрения производительности. оптимизация непрерывного хранилища).
При этом, как правило, рекомендуется использовать контейнер, который лучше всего подходит для решения поставленной задачи, и выполнять разумную оптимизацию только в том случае, если есть реальное узкое место в производительности.
person
darune
schedule
18.06.2020
Для общего случая любого критерия нет ничего лучше, чем перебирать каждый элемент.
У каждого контейнера есть конкретные критерии, с которыми он может работать лучше, например.
std::set<std::string> strings = /* something */;
auto first = strings.lower_bound("a"); // O(log(strings)), "a" is the least string that starts with 'a'
auto last = strings.lower_bound("b"); // O(log(strings)), "b" is the first string after those that start with 'a'
strings.erase(first, last); // O(log(strings) + distance(first, last)), all the strings starting with 'a' are removed
Здесь мы удаляем элементы, начинающиеся с 'a', со сложностью O(log(strings) + distance(first, last)), что на O(alphabet) лучше, чем повторение всех элементов.
Или более надуманный
std::unordered_set<std::string> strings = /* something */;
auto hashed = strings.hash_function()("Any collision will do"); // O(1)
strings.erase(strings.begin(hashed), strings.end(hashed)); // O(distance(first, last))
Здесь мы удаляем элементы с таким же хэшем, как "Any collision will do", со сложностью O(distance(first, last)).
person
Caleth
schedule
18.06.2020
Вместо использования неупорядоченного набора адаптируйте свою структуру данных к чему-то вроде дерева. В этом случае он может оказаться для вас более полезным.
Для получения более подробной информации проверьте: https://en.wikipedia.org/wiki/Trie
Реализация: https://www.geeksforgeeks.org/trie-insert-and-search /.
В зависимости от ваших потребностей вы можете подумать о некоторых других алгоритмах, таких как Aho-Corasick/Suffix-Arrays и т. д. Возможно, вам потребуется провести некоторое исследование структуры данных, которая вам нужна, на основе объема данных, которые у вас есть, пересчет, который вам нужен и количество запросов, которые вы делаете.
Надеюсь, это поможет.
person
afkid
schedule
18.06.2020
Отредактировано, я имел в виду
std::unordered_set, но оно такое же, как и для std::set.
- person afkid; 18.06.2020
Я имел в виду, что не думайте скорее о расширении вашей структуры данных, которую вы сначала сочтете уместной, что может привести к действительно плохим результатам сложности, а скорее взгляните на несколько структур данных и в зависимости от ваших потребностей используйте лучшее, что вы необходимость.
- person afkid; 18.06.2020
