Фильтрация уникальных имен массива с огромным количеством объектов

Question

Сейчас я выбираю много объектов, которые содержат как названия, так и координаты улиц. Возвращенный массив содержит около 22 000 объектов, а результирующий массив, который нам нужен, имеет около 4000, остальные являются дубликатами. Проблема с данными такого типа заключается в том, что извлеченные объекты могут иметь одно и то же имя, но разные координаты, и меня интересует только получение объектов на основе уникальных имен. Если существует более одного объекта с одинаковым именем, я хочу сохранить только первый объект.

До сих пор я пытался пройтись по улицам, сравнивая названия. Я бы лучше использовал filter или другое, более эффективное решение.

Моя структура

struct StreetName {
    var name: String
    var polyLine: CLLocationCoordinate2D
}

Мой код пока что

DataManager.shared.getStreetNames { (streets) in  
    var namesArray: [StreetName] = []
    for streetName in streets {
        let name = streetName.name
        if namesArray.count == 0 {
            namesArray.append(streetName)
        } else if namesArray.contains(where: {$0.name == name }) { 
             /* Dont add */ 
        } else {
             namesArray.append(streetName)
        }
    }

    self.streetNames = namesArray.sorted(by: {$0.name < $1.name})
    self.filteredStreetNames = self.streetNames
    OperationQueue.main.addOperation {
        self.streetTableView.reloadData()
    }
}

Этот блок кода работает, но работает на iPhone X примерно за 30 секунд. Это слишком медленно. Есть идеи?

Answer 1

Мой взгляд на это:

// Given an array of elements (here just Ints):
let array = (0..<1000).map { _ in Int(arc4random_uniform(100)) }

// Sort it:
let sorted = array.sorted()

// Define an empty result (array of elements) which is a variable 
// and which gets modified in the subsequent reduce function:
var unique: [Int] = []

// A tailored reduce which depends on a sorted array and appends 
// to the result IFF that element is not the last in result:
let result = sorted.reduce(into: unique) { (result, element) in
    if let last = result.last, last == element {
    } else {
        result.append(element)
    }
}

Наконец, выведите результат:

print(array)

Пример вывода на консоль: console [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]

Answer 2

@ MartinR решил эту проблему с помощью Sets.

Моя новая обновленная структура

struct StreetName: Hashable {
    static func == (lhs: StreetName, rhs: StreetName) -> Bool {
        return lhs.name == rhs.name
    }

    var hashValue: Int {
        return name.hashValue
    }

    var name: String
    var polyLine: CLLocationCoordinate2D
}

Мой новый обновленный код

DataManager.shared.getStreetNames { (returnedNamesSet) in
    var namesArray: [StreetName] = Array(returnedNamesSet)

    self.streetNames = namesArray.sorted(by: {$0.name < $1.name})
    self.filteredStreetNames = self.streetNames
    OperationQueue.main.addOperation {
        self.streetTableView.reloadData()
    }
}

Результаты:

Время обработки увеличилось с 30 секунд до 0,4 секунд с помощью Set

Answer 3

Думаю, если вы профилируете это, вы обнаружите, что sort занимает больше всего времени. Я не могу найти официальную заметку, но есть хороший шанс, что базовая реализация - быстрая сортировка , которая имеет худшую сложность, когда массив уже отсортирован (или массив отсортирован в обратном порядке).

Средняя сложность для быстрой сортировки составляет O (n log n), но в худшем случае это O (n ² ).

Я думаю, что вы должны вместо этого реализовать сортировку вставками или, точнее, всегда вставлять новые элементы в уже отсортированную позицию. Это должно уменьшить вашу сложность до O (n) для всей функции.

псевдокод:

• Выбрать названия улиц
• Для каждого названия улицы
  • найти позицию в существующем массиве, куда будет идти название улицы (я предлагаю бинарный поиск, так как массив уже отсортирован)
  • если название улицы уже существует, пропустите
  • если имя не существует, вставьте его.

Результатом должен быть отсортированный массив уникальных названий улиц, требующий, чтобы каждое название читалось и вставлялось только один раз.