Блог

Главная - Вопросы по программированию - Более эффективный способ поиска в нескольких массивах единственного элемента?

Более эффективный способ поиска в нескольких массивах единственного элемента?

#swift

#swift

Вопрос:

Мне нужно выполнить поиск в нескольких больших массивах в поисках одного элемента. Если этот элемент находится хотя бы в одном из массивов, результат должен быть true . Является ли один из трех приведенных ниже примеров более эффективным, чем другой? Или есть более эффективный способ?

 let arr1 = ["a", "b", "c"]
let arr2 = ["d", "e", "f"]
let arr3 = ["g", "h", "i"]

let q = "h"

if arr1.contains(q) || arr2.contains(q) || arr3.contains(q) {
    print("y")
}

for arr in [arr1, arr2, arr3] {
    if arr.contains(q) {
        print("y")
        break
    }
}

if (arr1   arr2   arr3).contains(q) {
    print("y")
}

И я полагаю, я должен спросить, смогу ли я создать эти наборы массивов (если я могу безопасно это сделать, зная, что все они уникальны), это что-нибудь изменит?

Комментарии:

1. Перечисленные примеры отсортированы. Это всегда так?

2. @runcoderun не всегда так, нет

3. Вам следует подумать об использовании словаря или набора, чтобы операция поиска O (1) не преобразовывалась в, потому что преобразование из типа в тип потребляет O (n), где n — длина массива.

4. @LeoDabus Я знаю, что я просто ссылаюсь на операцию поиска и использование структуры данных на основе hashmap, а не на преобразование.

5. @acidgate преобразование массива в набор потребляет O (n)! Это не улучшило производительность

Ответ №1:

Первые два подхода эквивалентны — они прекращают обработку, как только находят существующее решение, и не создают никаких дополнительных списков, т. Е. Они сканируют существующие списки, и если, например, первый список содержит целевой элемент, второй и третий массивы вообще не будут затронуты.

Но третий вариант отличается — он сначала объединяет все массивы в новый, а затем сканирует новый список. В этом случае, если у вас большие массивы, вы столкнетесь с удвоенным потреблением памяти в момент этой операции. Кроме того, может потребоваться дополнительное время для объединения списков в новый.

Изменение списков для проверки одного элемента никоим образом не поможет, потому что это преобразование будет сканировать весь список, то есть ту же операцию, которая выполняется во время поиска. Но если у вас большое количество поисковых запросов, тогда разумно использовать наборы, предпочтительно отсортированные наборы, например, набор деревьев.

Ответ №2:

Предполагая, что массивы содержат несортированные элементы, которые уникальны во всех массивах:

Массивы:

Вариант 1 имеет наихудшее время выполнения 3n. Вариант 2 имеет наихудшее время выполнения 3n. Вариант 3 имеет наихудшее время выполнения 6n

Исключая постоянные факторы, асимптотическое время работы всех трех равноНа.

Наборы:

Преобразование из массива в набор также является Наоперацией. Было бы разумно просто сделать один набор и добавить к нему все. После выполнения .contains() поиск имеет временную сложность введите описание изображения здесь.