Удалить элементы массива 2d, значения 1-го столбца которых являются дубликатами (Swift)

Question

Этот запрос является небольшим изменением часто задаваемого вопроса.

Цель состоит в том, чтобы отфильтровать массив 2d для удаления дублирующих пар элементов, у которых значения в первом столбце являются дубликатами. Например:

[[1, 1, 1,  2, 2,  3, 3, 3, 3], [0.1, 0.15, 0.2,  0.05, 0.1,  0.2, 0.25, 0.3, 0.35]]
     ->    [[1, 2, 3],[0.2, 0.1, 0.35]]

Поскольку значения во втором столбце различаются, очевидно, что при фильтрации необходимо соблюдать некоторую свободу действий: здесь выбирается последнее значение из набора дубликатов.

Один из множества ответов на этот связанный вопрос - функциональное решение для программирования Тим МБ - может быть адаптирован к задаче:

// Use FP-style filtering to eliminate repeated elements
let rawArray: [[Float]] = [...]
let filteredArray = rawArray
    .transpose
    .enumerated()
    .filter{ (rawArray[0]).lastIndex(of: $0.1[0]) == $0.0 }
    .map{ $0.1 }
    .transpose

Тем не менее, это решение довольно медленное, что, к сожалению, изящно.

Более быстрое решение, которое поддерживает дух FP, - это использование хэширования словаря:

// Use array -> dict -> array trick to remove repeated elements
let rawArray: [[Float]] = [...]
let filteredArray = Array( Array(
    rawArray
        .transpose
        .reduce(into: [:], { dict, elements in
            dict[elements[0], default:(0,0)] = elements[1] 
        } )
        .map{ ($0.key, $0.value) } )
    .sorted{ $0.0 < $1.0 }
    .map{ [$0.0, $0.1] }
    .transpose) as! Array2D

Мои вопросы:

1. Является ли этот словарный фокус хорошей идеей? Учитывая, что в качестве ключей он использует float?
2. Почему решение FP работает медленно? Можно ли его ускорить?
3. Есть ли лучшие альтернативы?

Answer 1

Примечание по терминологии: я буду использовать a для ссылки на ваш массив, length для ссылки на его count (a.count) и width для ссылки на ширину его элементов (a[0].count) .

Здесь есть несколько вещей, каждый из которых довольно жесток с вашей производительностью.

Транспонирование

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

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

Дедупликация

Реализация дедупликации, на которую вы наткнулись (.filter{ (rawArray[0]).lastIndex(of: $0.1[0]) == $0.0 }), является горячим мусором. Это также O(width * height). Это на самом деле хуже, чем подходы, которые используют Array.contains для поддержки массива "уже увиденных" элементов. Когда contains ищет g для элемента, он может сделать ранний возврат, когда найдет совпадение. lastIndex(of:) всегда должен go по всему массиву, никогда не возвращая рано, потому что всегда может быть более поздний экземпляр искомого элемента.

Где возможно, используйте реализацию, которая использует преимущества Hashability ваших элементов. Использование Set для отслеживания «уже увиденных» элементов позволяет вам делать O(1) contains проверок над массивом O(count). Я настоятельно рекомендую Реализацию Cœur .

Есть только одна загвоздка: эта реализация сохраняет только первые элементы, а не последние. К счастью, это действительно легко исправить: просто переверните элементы, уникальные их (сохранение первых инвертированных элементов подобно сохранению последних элементов оригинальных элементов), и переверните их обратно.

Мое решение:

extension Sequence {
    /// Returns an array containing, in order, the first instances of
    /// elements of the sequence that compare equally for the keyPath.
    func unique<T: Hashable>(for keyPath: KeyPath<Element, T>) -> [Element] {
        var unique = Set<T>()
        return filter { unique.insert($0[keyPath: keyPath]).inserted }
    }
}

let points = zip(array[0], array[1])
let pointsUniquedByXs = points.reversed() // O(1) for collections
            .unqiue() // O(count)
            .reversed() // O(1) until you need to materalize as a reversed collection

Answer 2

Вы можете sh выполнить то, что хотите, сначала отфильтровав индексы первого массива, в котором элемент является первым вхождением, в обратном порядке. Затем вам просто нужно отобразить подпоследовательности, используя их:

let rawArray: [[Float]] = [[1, 1, 1, 2, 2, 3, 3, 3, 3], [0.1, 0.15, 0.2, 0.05, 0.1, 0.2, 0.25, 0.3, 0.3]]
var set: Set<Float> = []
let indices = rawArray
    .first?
    .indices
    .reversed()
    .filter { set.insert(rawArray.first![$0]).inserted }
    .reversed() ?? []
let result = rawArray.map { elements in indices.map { elements[$0] } }
print(result) //  [[1, 2, 3], [0.2, 0.1, 0.3]]

Другой вариант - создать две пустые подпоследовательности, выполнить итерацию первых индексов подпоследовательностей rawArray в обратном порядке и попытаться вставить значение с плавающей точкой в ​​набор, если вставлено добавление соответствующие элементы подпоследовательности, тогда вам просто нужно воссоздать результирующий массив с этими двумя новыми последовательностями в обратном порядке:

let rawArray: [[Float]] = [[1, 1, 1, 2, 2, 3, 3, 3, 3], [0.1, 0.15, 0.2, 0.05, 0.1, 0.2, 0.25, 0.3, 0.3]]
var set: Set<Float> = []
var sub1: [Float] = []
var sub2: [Float] = []
rawArray[0].indices.reversed().forEach {
    let value = rawArray[0][$0]
    if set.insert(value).inserted {
        sub1.append(value)
        sub2.append(rawArray[1][$0])
    }
}
let result: [[Float]] = [sub1.reversed(), sub2.reversed()] // [[1, 2, 3], [0.2, 0.1, 0.3]]

Вы можете сделать это еще быстрее, если массив result объявлен как обращенная коллекция плавающих точек. Это будет O (1) для [ReversedCollection<[Float]>] вместо O (n) для [[Float]] для каждой подпоследовательности.

Answer 3

Благодаря Александру , вот решение, адаптированное из метода Керра в длинном связанном потоке.

let rawArray: [[Float]] = [[1, 1, 1,  2, 2,  3, 3, 3, 3],
                           [0.1, 0.15, 0.2,  0.05, 0.1,  0.2, 0.25, 0.3, 0.35]]
let filteredArray = rawArray
    .transpose
    .reversed()
    .map{ ($0[0],$0[1]) }
    .unique(for: \.0)
    .map{ [$0.0,$0.1] }
    .reversed()
    .transpose

Все это происходит из-за того, что данные являются массив с двумя столбцами, а не массив 1d кортежей, и поскольку требуется выбрать последнее, а не первое дублирующее значение.

Чтобы это работало, Array должны иметь следующие расширения: первая любезность Александра и Кера, вторая (редакция) благодаря Льву Дабусу :

extension RangeReplaceableCollection {
    /// Returns a collection containing, in order, the first instances of
    /// elements of the sequence that compare equally for the keyPath.
    func unique<T: Hashable>(for keyPath: KeyPath<Element, T>) -> Self {
        var unique = Set<T>()
        return filter { unique.insert($0[keyPath: keyPath]).inserted }
    }
}

extension RandomAccessCollection where Element: RandomAccessCollection {
    /// Peform a transpose operation
    var transpose: [[Element.Element]] {
        guard !isEmpty,
            var index = first?.startIndex,
            let endIndex = first?.endIndex
            else { return [] }
        var result: [[Element.Element]] = []
        while index < endIndex {
            result.append(map{$0[index]})
            first?.formIndex(after: &index) }
        return result
    }
}