Сравнение двух массивов строк наиболее эффективным способом

Question

Эта проблема связана с поиском строки в основном массиве (содержит список всех UID). Второй массив содержит все строки для поиска.

Например:

Первый массив (Master List) содержит: UID1 UID2 UID3... UID99

Второй массив содержит: UID3 UID144 UID50

Если совпадение найдено в первом массиве затем 1 возвращается в противном случае 0 обратно. Таким образом, выход для приведенного выше примера должен быть 101.

Какой может быть наиболее эффективный подход (таргетинг на C), чтобы решить вышеуказанное, имея в виду, что традиционным способом борьбы с этим было бы n^2 !!!

Answer 1

Сортируйте массив основных строк и выполните двоичный поиск.

Answer 2

Эффективно с точки зрения чего?

Я бы предложил предложение @ Trying как хороший компромисс между достойной скоростью работы, низким потреблением памяти и очень (очень!) Низкой сложностью реализации.

Просто используйте qsort(), чтобы отсортировать первый массив на месте, затем используйте bsearch() для его поиска.

Предполагая п элементов в массиве мастер и м во втором массиве, это должно дать O (м * войти п) временную сложность, которая кажется достойной.

Answer 3

Другой вариант - построить хэш для строк в главном списке, это один O (M) (при условии, что длина равна O (1)), тогда предполагается, что хеш распределяется равномерно, поиск одного элемента следует возьмем среднее значение O (M/S), причем S является размером хеша (четное распределение означает, что в среднем это количество элементов, отображаемых в одну и ту же запись хеширования). Вы можете дополнительно контролировать размер для тонкой настройки компромисса между пространством и эффективностью

Answer 4

Есть в основном два хороших подхода к этой проблеме:

• Используйте бинарного поиск: бинарный поиск требует UIDs в первом массиве, который нужно отсортировать, и позволяет найти решение в O(log n), где n - это количество элементов в основном массиве. Общая сложность будет O(m log n) с m количеством элементов для поиска.

• Используйте HashMap: Вы можете хранить элементы главного массива в HashMap (O(n)), а затем проверить, являются ли ваши элементы второго массива в HashMap (O(m)). Общая сложность будет O(n+m).

Хотя сложность второго подхода выглядит лучше, вы должны иметь в виду, что если ваш хэш плохо, это может быть в худшем случае O(m*n) (но было бы очень и очень маловероятно).Также вы будете использовать больше памяти, а операции также будут медленнее. В вашем случае я бы использовал первый подход.