Вопрос:
У меня вопрос о том, как эффективно искать два контейнера, чтобы найти одинаковые элементы.
Например, у меня есть two list A, B, и я хочу выяснить все согласованные элементы в списке B для списка A.
В этом случае мне нужно иметь два цикла, один внутри другого. Это не хорошо, потому что для каждого элемента A я выполняю весь поиск в B.
У вас есть идеи или стандартная библиотека (boost is OK) для ее решения;)?
Большое спасибо!
Лучший ответ:
Вы можете std::sort() контейнеры, а затем использовать std::set_intersection() (я не совсем уверен в имени этого алгоритма). Сложность была бы O(n ln n + m ln m) а не O(n * m) где n и m были размером последовательностей.
Ответ №1
Как вы можете видеть из разных ответов, существует несколько подходов. Любой из них может быть правильным в зависимости от того, какие ваши контейнеры включены и включены, если диапазоны отсортированы и типичный размер диапазонов, и если сортировка диапазонов является опцией.
- Если оба контейнера отсортированы, то std::set_intersection – лучший способ, это сложность O(n+m)
- Сортировка контейнера размером n имеет сложность O(n log(n)) с точки зрения сравнений и свопов. Сортировка списка означает узлы списка обмена, что является дешевым. Сортировка вектора означает фактическую замену элементов, а стоимость зависит от типа элемента.
- С помощью одного сортированного и одного несортированного контейнера лучше всего использовать std::binary_search для каждого элемента несортированного диапазона в отсортированном диапазоне. Сложностью этого будет O(n log(m)) где n – размер несортированного m диапазона сортировки. Сначала сортировка несортированного диапазона и использование set_intersection будут иметь сложность O(n log(n) + m) что хуже.
- Имея два несортированных контейнера, он рассчитывает, что один из них будет отсортирован, а затем применит binary_search для элементов другого, что binary_search сложность O((m+n) log(m)), поэтому, если оба контейнера имеют одинаковые тип, сортировка меньшего контейнера лучше.
Ответ №2
Если у вас есть два списка A (размер n) и B (размер m), то поиск каждого элемента в B, который существует в A, – O (nm) с использованием вложенного цикла.
Я бы предложил использовать хеш-набор. Если вы создадите хэш-набор с элементами из B, вы потратите O (m) на создание набора, а затем O (n), просматривая каждый элемент A в hash_set (B). Таким образом, сложностью будет O (n + m)
Ответ №3
Возможно, вы можете сортировать A и B в массиве в первую очередь. Затем подсчитайте те же элементы. Это O (n * log (n)), но нужно больше места.
Ответ №4
Если вы хотите оптимизировать решение, вам нужно предоставить дополнительную информацию о проблемном домене. Например, если вы знали, что все элементы в списках были целыми числами от 1 до 100, вы могли бы использовать простой массив Booleans [100] и завершить задачу, выполнив один раз на A (повышение соответствующих флагов), а затем один раз на B (тестирование флагов).
Если списки имеют произвольное содержимое, вам нужно решить, какое именно решение будет принято. Наивное решение было бы иметь двойной цикл, как вы предполагали, что не обязательно так плохо. Вы можете сделать несколько практических оптимизаций:
- Внешний цикл должен выполняться в более коротком списке (если вы знаете их длину). Это означает, что ваш внутренний цикл может сломаться, как только вы найдете свой предмет (если найдете его…).
- Если память не является проблемой, вы можете отсортировать оба списка, а затем перейти к обоим из них параллельно, перемещаясь вперед по одному списку, пока другой элемент списка больше (например, вы сортируете их слияние). Это имеет порядок O (NlogN + MlogM + max (N, M)), который, вероятно, лучше, чем O (N * M), но также расточительно с точки зрения памяти.
