6

I have a big array of objects and would like to split it into two arrays containing the objects in alternate order.

Example:

[0, 1, 2, 3, 4, 5, 6]

Becomes these two arrays (they should alternate)

[0, 2, 4, 6] and [1, 3, 5]

There are a ton of ways to split an array. But, what is the most efficient (least costly) if the array is huge.

1
  • 1
    The best you're going to get is O(n). Just create two new arrays and loop through the old one, alternating where you put an element on each iteration. Commented Mar 15, 2015 at 2:51

7 Answers 7

4

There are various fancy ways to do it with filter but most would probably require two passes rather than one, so you may as well just use a for-loop.

Reserving space up-front could make a big difference in this case since if the source is large it’ll avoid unnecessary re-allocation as the new arrays grow, and the calculation of space needed is in constant time on arrays.

// could make this take a more generic random-access collection source
// if needed, or just make it an array extension instead
func splitAlternating<T>(source: [T]) -> ([T],[T]) {
    var evens: [T] = [], odds: [T] = []

    evens.reserveCapacity(source.count / 2 + 1)
    odds.reserveCapacity(source.count / 2)

    for idx in indices(source) {
        if idx % 2 == 0 {
            evens.append(source[idx])
        }
        else {
            odds.append(source[idx])
        }
    }

    return (evens,odds)
}

let a = [0,1,2,3,4,5,6]
splitAlternating(a)  // ([0, 2, 4, 6], [1, 3, 5])

If performance is truly critical, you could use source.withUnsafeBufferPointer to access the source elements, to avoid the index bounds checking.

If the arrays are really huge, and you aren’t going to use the resulting data except to sample a small number of elements, you could consider using a lazy view instead (though the std lib lazy filter isn’t much use here as it returns sequence not a collection – you’d possibly need to write your own).

Sign up to request clarification or add additional context in comments.

1 Comment

Many extremely knowledgable answers provided. I chose this one because it goes a little further in explaining ways to improve performance.
4

You can use the for in stride loop to fill two resulting arrays as follow:

extension Array {
    var groupOfTwo:(firstArray:[T],secondArray:[T]) {
        var firstArray:[T] = []
        var secondArray:[T] = []
        for index in stride(from: 0, to: count, by: 2) {
            firstArray.append(self[index])
            if index + 1 < count {
                secondArray.append(self[index+1])
            }
        }
        return (firstArray,secondArray)
    }
}



[0, 1, 2, 3, 4, 5, 6].groupOfTwo.firstArray   // [0, 2, 4, 6]
[0, 1, 2, 3, 4, 5, 6].groupOfTwo.secondArray  // [1, 3, 5]

update: Xcode 7.1.1 • Swift 2.1

extension Array {
    var groupOfTwo:(firstArray:[Element],secondArray:[Element]) {
        var firstArray:[Element] = []
        var secondArray:[Element] = []
        for index in 0.stride(to: count, by: 2) {
            firstArray.append(self[index])
            if index + 1 < count {
                secondArray.append(self[index+1])
            }
        }
        return (firstArray,secondArray)
    }
}

1 Comment

In case anyone is looking this code doesn't work in Swift 2.. stride(from: to: by:) doesn't exist and [T] is changed to [Element]
4

A more concise, functional approach would be to use reduce

let a = [0,1,2,3,4,5,6]

let (evens, odds) = a.enumerate().reduce(([Int](),[Int]())) { (cur, next) in
    let even = next.index % 2 == 0
    return (cur.0 + (even ? [next.element] : []),
            cur.1 + (even ? [] : [next.element]))
}

evens // [0,2,4,6]
odds // [1,3,5]

Comments

1

Big/huge array always pose problems when being partially processed, like in this case, as creating two extra (even if half-sized) arrays can be both time and memory consuming. What if, for example, you just want to compute the mean and standard deviation of oddly and evenly positioned numbers, but this will require calling a dedicated function which requires a sequence as input?

Thus why not creating two sub-collections that instead of duplicating the array contents, they point to the original array, in a transparent manner to allow querying them for elements:

extension Collection where Index: Strideable{
    func stride(from: Index, to: Index, by: Index.Stride) -> StridedToCollection<Self> {
        return StridedToCollection(self, from: from, to: to, by: by)
    }
}

struct StridedToCollection<C>: Collection where C: Collection, C.Index: Strideable {
    private let _subscript : (C.Index) -> C.Element
    private let step: C.Index.Stride

    fileprivate init(_ collection: C, from: C.Index, to: C.Index, by: C.Index.Stride)  {
        startIndex = from
        endIndex = Swift.max(to, startIndex)
        step = by
        _subscript = { collection[$0] }
    }

    let startIndex: C.Index
    let endIndex: C.Index

    func index(after i: C.Index) -> C.Index {
        let next = i.advanced(by: step)
        return next >= endIndex ? endIndex : next
    }

    subscript(_ index: C.Index) -> C.Element {
        return _subscript(index)
    }
}

The Collection extension and the associated struct would create a pseudo-array that you can use to access only the elements you are interested into.

Usage is simple:

let numbers: [Int] = [1, 2, 3, 4]
let stride1 = numbers.stride(from: 0, to: numbers.count, by: 2)
let stride2 = numbers.stride(from: 1, to: numbers.count, by: 2)
print(Array(stride1), Array(stride2))

With the above you can iterate the two strides without worrying you'll double the amount of memory. And if you actually need two sub-arrays, you just Array(stride)-ify them.

Comments

0

Use for loops. If the index value is even then send that to one array and if the index value is odd, then send that to odd array.

Comments

0

Here's, in my opinion, the easiest way

old_list = [0, 1, 2, 3, 4, 5, 6]
new_list1 =[]
new_list2 = []
while len(old_list)>0:
    new_list1.append(old_list.pop(-1))
    if len(old_list) != 0:
        new_list2.append(old_list.pop(-1))

new_list1.reverse()
new_list2.reverse()

Comments

0

I just had to do this where I split an array into two in one place, and three into another. So I built this:

extension Array {
    /// Splits the receiving array into multiple arrays
    ///
    /// - Parameter subCollectionCount: The number of output arrays the receiver should be divided into
    /// - Returns: An array containing `subCollectionCount` arrays. These arrays will be filled round robin style from the receiving array.
    ///            So if the receiver was `[0, 1, 2, 3, 4, 5, 6]` the output would be `[[0, 3, 6], [1, 4], [2, 5]]`. If the reviever is empty the output
    ///            Will still be `subCollectionCount` arrays, they just all will be empty. This way it's always safe to subscript into the output.
    func split(subCollectionCount: Int) -> [[Element]] {
        precondition(subCollectionCount > 1, "Can't split the array unless you ask for > 1")
        var output: [[Element]] = []

        (0..<subCollectionCount).forEach { (outputIndex) in
            let indexesToKeep = stride(from: outputIndex, to: count, by: subCollectionCount)
            let subCollection = enumerated().filter({ indexesToKeep.contains($0.offset)}).map({ $0.element })
            output.append(subCollection)
        }

        precondition(output.count == subCollectionCount)
        return output
    }
}

It works on Swift 4.2 and 5.0 (as of 5.0 with Xcode 10.2 beta 2)

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.