Initializing an Array of Alternating Values

Question

My goal in this project is to make something that can—as, quickly, effectively, and efficiently as Array(repeating: , count: )—initialize an Array of alternating values.

Note: I am using Swift 4.1 and Xcode 9.3

---

My Array Initialization:

extension Array {
    init (repeatingValues arr: Array, count: Int) {
        precondition(!arr.isEmpty, "Initialization values cannot be empty")
        precondition(count > 0, "Count cannot be less than 1")
        var newArr = Array<Element>()
        for i in 0..<count {
            newArr.append(arr[i % arr.count])
        }
        self = newArr
    }
}

---

Usage

Initialization - init(repeatingValues: , count: ):

let array = Array(repeatingValues: [true, false], count: 10)

print(array) //prints: [true, false, true, false, true, false, true, false, true, false]

---

Benchmark Comparison

Comparing: Array(repeating: , count: ) vs. Array(repeatingValues: , count: )

Benchmark Time Extension:

extension Date {
      func elapsedTime(to date: Date) -> String {

        let attoseconds100 = date.timeIntervalSince(self) * 10000000000000

        switch attoseconds100 {
        case 6048000000000000000...:
            let weeks : Int = Int(attoseconds100 / 6048000000000000000)
            return "\(weeks)w" + " " + "\(Int(attoseconds100 / 864000000000000000) - (weeks * 7))d"

        case 864000000000000000...:
            let days : Int = Int(attoseconds100 / 864000000000000000)
            return "\(days)d" + " " + "\(Int(attoseconds100 / 36000000000000000) - (days * 24))h"

        case 36000000000000000...:
            let hours : Int = Int(attoseconds100 / 36000000000000000)
            return "\(hours)h" + " " + "\(Int(attoseconds100 / 600000000000000) - (hours * 60))m"

        case 600000000000000...:
            let mins : Int = Int(attoseconds100 / 600000000000000)
            return "\(mins)m" + " " + "\(Int(attoseconds100 / 10000000000000) - (mins * 60))s"

        case 10000000000000...:
            let secs : Int = Int(attoseconds100 / 10000000000000)
            return "\(secs)s" + " " + "\(Int(attoseconds100 / 10000000000) - (secs * 1000))ms"

        case 10000000000...:
            let millisecs : Int = Int(attoseconds100 / 10000000000)
            return "\(millisecs)ms" + " " + "\(Int(attoseconds100 / 10000000) - (millisecs * 1000))μs"

        case 10000000...:
            let microsecs : Int = Int(attoseconds100 / 10000000)
            return "\(microsecs)μs" + " " + "\(Int(attoseconds100 / 10000) - (microsecs * 1000))ns"

        case 10000...:
            let nanosecs : Int = Int(attoseconds100 / 10000)
            return "\(nanosecs)ns" + " " + "\(Int(attoseconds100 / 10) - (nanosecs * 1000))ps"

        case 10...:
            let picosecs : Int = Int(attoseconds100 / 10)
            return "\(picosecs)ps" + " " + "\(Int(attoseconds100 / 0.01) - (picosecs * 1000))fs"

        case 0.01...:
            let femtosecs : Int = Int(attoseconds100 * 100)
            return "\(femtosecs)fs" + " " + "\((Int(attoseconds100 / 0.001) - (femtosecs * 10)) * 100)as"
        case 0.001...:
            return "\(Int(attoseconds100 * 100000))as"

        default:
            return "Less than 100 attoseconds"
        }
    }
}

Array(repeating: , count: ):

let start = Date()
let _ = Array(repeating: true, count: 1000000)
let end = Date()
print(start.elapsedTime(to: end)) //2ms 470μs

Execution Time: 2ms 470μs

Array(repeatingValues: , count: ):

let start = Date()
let _ = Array(repeatingValues: [true, false], count: 1000000)
let end = Date()
print(start.elapsedTime(to: end)) //472ms 555μs

Execution Time: 472ms 555μs

Results:

Array(repeatingValues: , count: ) 191.3x slower than Array(repeating: , count: )

---

How can I match Apple's efficiency and speed?

Answer 1

On my computer (a 1.2 GHz Intel Core m5 MacBook) I measured

Array(repeating:count:)        663μs 995ns
Array(repeatingValues:count:)  13ms 105μs

with the code compiled in the Release configuration, i.e. with optimizations. This is approximately a factor of 20 between those methods.

It seems that one “culprit” is the remainder calculation in

        newArr.append(arr[i % arr.count])

If we replace that by an addition with wrap-around test

public init(repeatingValues arr: Array, count: Int) {
    precondition(!arr.isEmpty, "Initialization values cannot be empty")
    precondition(count > 0, "Count cannot be less than 1")

    var newArr = Array<Element>()
    var srcIndex = 0
    for _ in 0..<count {
        newArr.append(arr[srcIndex])
        srcIndex += 1
        if srcIndex == arr.count { srcIndex = 0 }
    }
    self = newArr
}

then the performance improves to

Array(repeatingValues:count:)   3ms 315μs

which is “only” by a factor of 5 slower than Array(repeating:count).

Another possible bottleneck is the array bounds check on each access. This can be bypassed by accessing the element storage directly:

init (repeatingValues2 arr: Array, count: Int) {
    precondition(!arr.isEmpty, "Initialization values cannot be empty")
    precondition(count > 0, "Count cannot be less than 1")
    var newArr = Array(repeating: arr.first!, count: count)
    newArr.withUnsafeMutableBufferPointer { src in
        arr.withUnsafeBufferPointer { dest in
            var j = 0
            for i in 0..<count {
                src[i] = dest[j]
                j += 1
                if j == arr.count { j = 0 }
            }
        }
    }
    self = newArr
}

This reduces the execution time to

Array(repeatingValues:count:)   1ms 889μs

which is now slower roughly by a factor of 3 than Array(repeating:count).

Other possibly useful technique is to avoid reallocations of the array element storage by calling

    newArr.reserveCapacity(count)

However, this did not make a significant difference in my tests.

One further remark: Requiring the destination count to be strictly positive seems unnecessary restrictive to me. I would change that to

init (repeatingValues arr: Array, count: Int) {
    precondition(!arr.isEmpty, "Initialization values cannot be empty")
    precondition(count >= 0, "Count cannot be negative")
    if count == 0 {
        self = []
        return
    }

    // ...
}

Answer 2

I would take a completely different approach from this.

I would define a CycleSequence, and accompanying CycleIterator, which has several key advantages:

• Users have the freedom to iterate a CycleSequence, without being forced to convert it to an Array.
  • Of course, if someone wishes to store this as an Array, they can call Array(CycleSequence(cycling: whatever).prefix(someLength)). The prefix(someLength) part is critical, otherwise the Array initializer will loop forever, trying to make a copy of an infinitely long, never ending sequence of cycled elements.
• This is more memory efficient, because repeated array elements are only stored once.
• Elements can be taken from any Collection type. Arrays, ranges, Strings, much more flexible!

Example implementation:

struct CycleSequence<C: Collection>: Sequence {
    let cycledElements: C

    init(cycling cycledElements: C) {
        self.cycledElements = cycledElements
    }

    public func makeIterator() -> CycleIterator<C> {
        return CycleIterator(cycling: cycledElements)
    }
}

struct CycleIterator<C: Collection>: IteratorProtocol {
    let cycledElements: C
    var cycledElementIterator: C.Iterator

    init(cycling cycledElements: C) {
        self.cycledElements = cycledElements
        self.cycledElementIterator = cycledElements.makeIterator()
    }

    public mutating func next() -> C.Iterator.Element? {
        if let next = cycledElementIterator.next() {
            return next
        } else {
            self.cycledElementIterator = cycledElements.makeIterator() // Cycle back again
            return cycledElementIterator.next()
        }
    }
}

CycleSequence(cycling: [true, false]).prefix(7).forEach{ print($0) }
print()
CycleSequence(cycling: 1...3).prefix(7).forEach{ print($0) }
print()
CycleSequence(cycling: "ABC").prefix(7).forEach{ print($0) }
CycleSequence(cycling: EmptyCollection()).prefix(7).forEach{ print($0) }