Обратный Zip Коллекция

Question

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

let a = [1, 2, 3, 4, 5, 6, 7]
let (left, right) = a.reverseZip()

print(left)  // [1, 3, 5, 7] 
print(right) // [2, 4, 6]

У меня есть реализация, которая, кажется, работает (см. Мой ответ, приведенный ниже), но у меня есть два вопроса, которые я надеюсь обсудить:

1. Какое правильное название для этого вида операции?Это не совсем противоположно zip (и я уверен, что этот шаблон существует в другом месте на другом функциональном языке)
2. Есть ли более оптимальный алгоритм для этого метода?

Answer 1

Это семя идеи.Вместо возврата массивов было бы более эффективно возвращать последовательности.

Вот расширение Array, которое возвращает два LazyMapSequence<StrideTo<Int>, Element>.Преимущество в том, что на самом деле не генерирует последовательности;они предоставляются по запросу, потому что они lazy.Это очень похоже на то, как reversed() работает на Array.

extension Array {

    func reverseZip() -> (LazyMapSequence<StrideTo<Int>, Element>, LazyMapSequence<StrideTo<Int>, Element>) {

        let left = stride(from: 0, to: self.count, by: 2).lazy.map { self[$0] }
        let right = stride(from: 1, to: self.count, by: 2).lazy.map { self[$0] }

        return (left, right)
    }
}

Пример:

let a = [1, 2, 3, 4, 5, 6, 7]
let (left, right) = a.reverseZip()

// iterate left
for i in left {
    print(i)
}

1
3
5
7

// turn them into arrays to print them
print(Array(left))

[1, 3, 5, 7]

print(Array(right))

[2, 4, 6]

Я уверен, что это можно обобщить до чего-то более общего, чем Array.Это оставлено в качестве упражнения для читателя.

---

Если вы хотите два массива

Если вы действительно хотите два массива, то вы просто вернетесьрезультат map (вынимает lazy):

extension Array {

    func reverseZip() -> ([Element], [Element]) {

        let left = stride(from: 0, to: self.count, by: 2).map { self[$0] }
        let right = stride(from: 1, to: self.count, by: 2).map { self[$0] }

        return (left, right)
    }
}

Answer 2

Основываясь на идее vacawama возвращать ленивые коллекции вместо массивов, возможное обобщение для произвольных коллекций с произвольными шагами:

extension Collection {

    func makeStrideIterator(stride: Int) -> AnyIterator<Element> {
        precondition(stride > 0, "The stride must be positive")
        var it = makeIterator()
        var first = true
        return AnyIterator<Element> {
            if first {
                first = false
            } else {
                // Skip `stride - 1` elements:
                for _ in 1..<stride {
                    guard let _ = it.next() else { return nil }
                }
            }
            return it.next()
        }
    }
}

Метод возвращает AnyIterator (который является одновременно итератором и последовательностью) элементов коллекции в позициях

0, stride, 2*stride, ...

Распаковка массива (или любой другой коллекции) может быть выполнена с помощью

let a = [1, 2, 3, 4, 5]
let left = a.makeStrideIterator(stride: 2)
let right = a.dropFirst().makeStrideIterator(stride: 2)

for e in left { print(e) }
// 1, 3, 5
for e in right { print(e) }
// 2, 4

Здесьпример выбора каждого третьего символа из строки:

for c in "ABCDEFG".makeStrideIterator(stride: 3) {
    print(c)
}
// A D G

Специальный случай распаковки в два массива может быть реализован как

extension Collection {
    func unzip() -> ([Element], [Element]) {
        return (Array(makeStrideIterator(stride: 2)),
                Array(dropFirst().makeStrideIterator(stride: 2)))
    }
}

Пример:

print([1, 2, 3, 4, 5].unzip())
// ([1, 3, 5], [2, 4])

Answer 3

extension Collection {

    func reverseZip() -> ([Element], [Element]) {

        var left  = [Element]()
        var right = [Element]()

        let capacity = Double(self.count) / 2.0
        left .reserveCapacity(Int(ceil(capacity)))
        right.reserveCapacity(self.count / 2)

        for element in self {

            if left.count > right.count {
                right.append(element)
            } else {
                left.append(element)
            }
        }
        return (left, right)
    }
}

ОБНОВЛЕНИЕ (03/10/18) Спасибо всем за помощь.Похоже, многие из вас привязаны к Stride, что, безусловно, является хорошим способом.Я сопротивлялся этому подходу по двум причинам:

1. Я стремлюсь сохранить эту функцию как расширение Collection, а не Array
2. Строго говоря, startIndex для данного Collection необязательно 0, и прогресс индексов не обязательно увеличивается на 1 каждый раз.

Подход Мартина Р. с использованием пользовательского итератора определенно выглядел какправильный подход, поэтому я использовал это вместе с реализацией WWDC 2018 «EveryOther» , чтобы создать стандартный последовательный итератор, который просто проходит по двум элементам в каждом блоке цикла while, пока не достигнет конца.

extension Collection {

    func deinterleave() -> ([Element], [Element]) {
        let smallHalf = count / 2
        let bigHalf   = count - smallHalf

        var left  = [Element]()
        var right = [Element]()

        left .reserveCapacity(bigHalf)
        right.reserveCapacity(smallHalf)

        let start = self.startIndex
        let end   = self.endIndex

        var iter = start
        while iter != end {
            left.append(self[iter])
            iter = index(after: iter)

            if iter == end { break }
            right.append(self[iter])

            iter = index(after: iter)
        }
        return (left, right)
    }
}

let a = [1,2,3,4,5,6,7]
print(a.deinterleave()) // ([1, 3, 5, 7], [2, 4, 6])

Без сомнения, есть некоторые возможности для дальнейшего улучшения и использования реализации LazyMapSequence в vacawama, но сейчас это делает все, что мне нужно.