Как объединить два отсортированных массива в Swift?

Я не совсем понимаю, что вы имеете в виду, говоря «еще более Swifty», но начнем.

Я бы написал функцию следующим образом. Он не короче, но гораздо более общий: вы можете объединить любые два Sequence, если они имеют один и тот же тип Element, а Element - это Comparable:

/// Merges two sequences into one where the elements are ordered according to `Comparable`.
///
/// - Precondition: the input sequences must be sorted according to `Comparable`.
func merged<S1, S2>(_ left: S1, _ right: S2) -> [S1.Element]
    where S1: Sequence, S2: Sequence, S1.Element == S2.Element, S1.Element: Comparable
{
    var leftIterator = left.makeIterator()
    var rightIterator = right.makeIterator()

    var merged: [S1.Element] = []
    merged.reserveCapacity(left.underestimatedCount + right.underestimatedCount)

    var leftElement = leftIterator.next()
    var rightElement = rightIterator.next()
    loop: while true {
        switch (leftElement, rightElement) {
        case (let l?, let r?) where l <= r:
            merged.append(l)
            leftElement = leftIterator.next()
        case (let l?, nil):
            merged.append(l)
            leftElement = leftIterator.next()
        case (_, let r?):
            merged.append(r)
            rightElement = rightIterator.next()
        case (nil, nil):
            break loop
        }
    }
    return merged
}

Еще одно интересное усовершенствование - сделать последовательность ленивой, то есть определить MergedSequence и сопутствующую структуру итератора, которая хранит базовые последовательности и создает следующий элемент по запросу. Это было бы похоже на то, что делают многие функции в стандартной библиотеке, например. zip или Sequence.joined. (Если вы не хотите определять новый тип, вы также можете вернуть AnySequence<S1.Element>.)

Не уверен в вашем определении, но вы можете интерпретировать это как более быстрое:

func mergeOrdered<T: Comparable>(orderedArray1: [T], orderedArray2: [T]) -> [T] {

    // Create mutable copies of the ordered arrays:
    var array1 = orderedArray1
    var array2 = orderedArray2

    // The merged array that we'll fill up:
    var mergedArray: [T] = []

    while !array1.isEmpty {

        guard !array2.isEmpty else {
            // there is no more item in array2,
            // so we can just add the remaining elements from array1:
            mergedArray += array1
            return mergedArray
        }

        var nextValue: T
        if array1.first! < array2.first! {
            nextValue = array1.first!
            array1.removeFirst()
        } else {
            nextValue = array2.first!
            array2.removeFirst()
        }
        mergedArray.append(nextValue)
    }

    // Add the remaining elements from array2 if any:
    return mergedArray + array2
}

Потом:

let merged = mergeOrdered(orderedArray1: arr1, orderedArray2: arr2)
print(merged) // prints [1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

Это аналогичная идея и не намного короче по коду, но, на мой взгляд, «быстрее» то, что вам не нужно отслеживать два индекса таким образом.

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

let merged = (arr1 + arr2).sorted()

но, конечно, это зависит от варианта использования.

Ссылаясь на @ Ответ ОлеБегеманна

Another interesting enhancement would be to make the sequence lazy, i.e. define a MergedSequence and accompanying iterator struct that stores the base sequences and produces the next element on demand.

Если мы хотели бы использовать некоторый подход «более Swifty», а также хотели бы достичь ленивой чередующейся последовательности чередующихся (на основе предиката < для поэлементного сравнения), а не, как в вашем примере, массива, мы может использовать sequence(state:next:) и вспомогательный enum, а также повторно использовать часть левой / правой логики switch из ответа Оле Бегеманна:

enum QueuedElement {
    case none
    case left(Int)
    case right(Int)
}

var lazyInterleavedSeq = sequence(
    state: (queued: QueuedElement.none,
            leftIterator: arr1.makeIterator(),
            rightIterator: arr2.makeIterator()),
    next: { state -> Int? in
        let leftElement: Int?
        if case .left(let l) = state.queued { leftElement = l }
        else { leftElement = state.leftIterator.next() }

        let rightElement: Int?
        if case .right(let r) = state.queued { rightElement = r }
        else { rightElement = state.rightIterator.next() }

        switch (leftElement, rightElement) {
        case (let l?, let r?) where l <= r:
            state.queued = .right(r)
            return l
        case (let l?, nil):
            state.queued = .none
            return l
        case (let l, let r?):
            state.queued = l.map { .left($0) } ?? .none
            return r
        case (_, nil):
            return nil
        }
})

Которые мы можем потреблять, например, для регистрации:

for num in lazyInterleavedSeq { print(num) }
/* 1
   2
   5
   7
   17
   17
   25
   29
   31
   38 */

Или построить неизменяемый массив:

let interleaved = Array(lazyInterleavedSeq)
// [1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

Пытался решить вашу проблему в Функциональное программирование и без переменных.

Учитывая 2 массива

let nums0 = [1, 7, 17, 25, 38]
let nums1 = [2, 5, 17, 29, 31]

Мы объединяем первую с версией перевернутый второй.

let all = nums0 + nums1.reversed()

В результате получится такая пирамида.

[1, 7, 17, 25, 38, 31, 29, 17, 5, 2]

Теория

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

[1, 7, 17, 25, 38, 31, 29, 17, 5, 2] -> we pick 1 (left edge)
[7, 17, 25, 38, 31, 29, 17, 5, 2] -> we pick 2 (right edge)
[7, 17, 25, 38, 31, 29, 17, 5] -> we pick 5 (right edge)
[7, 17, 25, 38, 31, 29, 17] -> we pick 7 (left edge)
[17, 25, 38, 31, 29, 17] -> we pick 17 (right edge)
[17, 25, 38, 31, 29] -> we pick 17 (left edge)
[25, 38, 31, 29] -> we pick 25 (left edge)
[38, 31, 29] -> we pick 29 (right edge)
[38, 31] -> we pick 31 (right edge)
[38] -> we pick 38 (both edges)

Теперь давайте посмотрим на массив, который мы построили, выбирая все эти элементы.

We selected 1: [1]
We selected 2: [1, 2]
We selected 5: [1, 2, 5]
We selected 7: [1, 2, 5, 7]
We selected 17: [1, 2, 5, 7, 17]
We selected 17: [1, 2, 5, 7, 17, 17]
We selected 25: [1, 2, 5, 7, 17, 17, 25]
We selected 29: [1, 2, 5, 7, 17, 17, 25, 29]
We selected 31: [1, 2, 5, 7, 17, 17, 25, 29, 31]
We selected 38: [1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

Это похоже на результат, которого мы хотим достичь, верно?

Пришло время написать код на Swifty.

Код!

Хорошо, как мы можем это сделать в функциональном программировании?

Вот код

let merged = all.reduce((all, [Int]())) { (result, elm) -> ([Int], [Int]) in

    let input = result.0
    let output = result.1

    let first = input.first!
    let last = input.last!
    // I know these ☝️ force unwraps are scary but input will never be empty

    if first < last {
        return (Array(input.dropFirst()), output + [first])
    } else {
        return (Array(input.dropLast()), output + [last])
    }

}.1

Как это работает?

1. Мы переходим к сокращению кортежа, содержащего массив all и пустой массив.

all.reduce((all, [Int]()))

We will call first array input and the second one output. Step by step the reduce will remove the minimum element from the edges of input will append it to output.

2. Затем внутри замыкания мы даем собственные имена 2 элементам выходного кортежа.

let input = result.0
let output = result.1

3. Выбираем первый и последний элемент ввода

let first = input.first!
let last = input.last!

Yeah, I don't like force unwraps either but since input will never be empty, these force unwraps will never produce a fatal error.

4. Теперь, если first < last нам нужно:

• вернуть ввод минус первый элемент
• возврат вывода + первый элемент ввода

В противном случае поступаем наоборот.

if first < last {
    return (Array(input.dropFirst()), output + [first])
} else {
    return (Array(input.dropLast()), output + [last])
}

5. Наконец, мы выбираем второй элемент кортежа, возвращаемого функцией reduce, поскольку именно в нем сохраняется наш результат.

}.1  

Сложность времени

Время вычислений равно O (n + m), где n равно nums0.count, а m равно nums1.count, потому что:

nums1.reversed()

Это ☝️ О (1)

all.reduce(...) { ... }

Это ☝️ - О (п + м), поскольку закрытие выполняется для каждого элемента all.

Сложность по времени составляет O (n) ^ 2. См. Ценные комментарии ниже от @dfri.

Версия 2

Эта версия действительно должна иметь временную сложность O (n).

let merged = all.reduce(into: (all, [Int]())) { (result, elm) in
    let first = result.0.first!
    let last = result.0.last!

    if first < last {
        result.0.removeFirst()
        result.1.append(first)
    } else {
        result.0.removeLast()
        result.1.append(last)
    }
}.1

Простое функциональное решение

Мне очень нравится функциональный подход, представленный Лука Анджелетти. Идея с пирамидой тоже хороша, но на мой вкус код недостаточно читабелен / интуитивно понятен из-за использования функции reduce в сочетании с кортежами массивов. Кроме того, концепция пирамиды требует дополнительных объяснений для других разработчиков.

Таким образом, я попытался использовать моя первоначальная идея, медленно «отрубив» два массива спереди и сделав его чисто функциональный. Результат удивительно прост:

/// Merges two sorted arrays into a single sorted array in ascending order.
///
/// - Precondition: This function assumes that both input parameters `orderedArray1` and 
///                 `orderedArray2` are already sorted using the predicate `<`.
func mergeOrdered<T: Comparable>(orderedArray1: [T], orderedArray2: [T]) -> [T] {

    guard let first = orderedArray1.first else {
        return orderedArray2
    }

    guard let second = orderedArray2.first else {
        return orderedArray1
    }

    if first < second {
        return [first] + mergeOrdered(orderedArray1: Array(orderedArray1.dropFirst()),
                                      orderedArray2: orderedArray2)
    } else {
        return [second] + mergeOrdered(orderedArray1: orderedArray1,
                                       orderedArray2: Array(orderedArray2.dropFirst()))
    }
}

Я бы сказал, что его намного легче читать, чем другие алгоритмы, предложенные на этой странице, и, по моему мнению, это даже быстрый! ?

(Следует отметить, что озабоченность dfri, упомянутая в комментариях к Ответ Луки Анджелетти, также применима и здесь: новый массив создается на каждом шаге рекурсии, что может быть дорогостоящим в вычислительном отношении, но общее количество экземпляров массива всегда будет <т + п - 1, где мм> и п - количество элементов в массивах, подлежащих сортировке.)

Думая дальше ...

? Это решение может быть расширено для работы с

• любые предикаты сортировки
• общие последовательности, а не просто массивы, как предлагает Оле Бегеманн

Эталонный тест

ℹ️ Из всех этих методов стандартный алгоритм сортировки Swift - самый быстрый. Я протестировал среду выполнения для всех подходов с этими двумя массивами:

let first  = Array(1...9999)
let second = Array(5...500)

Полученные результаты:

• Итераторная сортировка (как введено Оле Бегеманн):
  37,110 с

• Функциональная сортировка (как представлено в этом ответе):
  6.081 с

• Циклическая сортировка (как введено в мой другой ответ):
  0,695 с

• Стандартная сортировка Swift ((first + second).sorted())
  0,013 с

Конечно, это всегда зависит от конкретных массивов, которые вы хотите объединить, но из этих результатов я бы сказал, что на самом деле используется (first + second).sorted() - это самое быстрое и быстрое решение, которое вы можете сделать!

Вот мой бит ... это расширение протокола Sequence и общая функция, позволяющая объединить две последовательности одного типа (расширение протокола) или даже ЛЮБЫЕ две последовательности с одним и тем же типом Element.

import Cocoa

struct MergeState<T> {
    var lastA: T?
    var iterA: AnyIterator<T>
    var lastB: T?
    var iterB: AnyIterator<T>

    mutating func consumeA() -> T? {
        let aux = lastA
        lastA = nil
        return aux ?? iterA.next()
    }

    mutating func consumeB() -> T? {
        let aux = lastB
        lastB = nil
        return aux ?? iterB.next()
    }
}

extension Sequence where Element: Comparable {
    func createMergeState(with other: Self) -> MergeState<Element> {
        let iterA = AnyIterator(self.makeIterator())
        let iterB = AnyIterator(other.makeIterator())
        return MergeState(lastA: nil, iterA: iterA, lastB: nil, iterB: iterB)
    }

    func mergeSequence(with other: Self) -> UnfoldSequence<Element, MergeState<Element>> {
        let state = createMergeState(with: other)
        return sequence(state: state) { (state) -> Element? in
            guard let valueA = state.consumeA() else {
                return state.consumeB()
            }
            guard let valueB = state.consumeB() else {
                return valueA
            }
            if valueA < valueB {
                state.lastB = valueB
                return valueA
            } else {
                state.lastA = valueA
                return valueB
            }
        }
    }
}

func mergeSequence<S1: Sequence, S2: Sequence>(_ seq1: S1, _ seq2: S2) -> UnfoldSequence<S1.Element, MergeState<S1.Element>> where S1.Element == S2.Element, S1.Element: Comparable {
    return AnySequence(seq1).mergeSequence(with: AnySequence(seq2))
}

let a = [1, 9, 15, 55, 101]
let b = [2, 4, 6, 8]

//merge sequences of the same type
for i in a.mergeSequence(with: b) {
    print("\(i)")
}

let c: IndexSet = [3, 9, 60]

print("---")

//merge any two sequences with the same Element
for i in mergeSequence(c, a) {
    print("\(i)")
}