4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ What are you "benchmarking" this with? On my 2015 2.5GHz i7, testing this code against a 8S simulator gives me 0.005 sec and 0.2 sec, which is only a difference of 40x, not 191. Don't use custom benchmarking code, run your tests as a UnitTest and use self.measure{} . I was able to shave off 0.03 seconds by assigning arr.count to a variable, as it's cheaper then lookup against the arr object. That being said, Apple is very likely initializing the array in a low-level function, so you aren't going to be reaching their level of performance unless you do the same. \$\endgroup\$ – n_b Apr 15 '18 at 21:44
  • \$\begingroup\$ I don't think this is a job for an Array extension. Some users might need to "cycle" elements and store them in an array, but some (perhaps even most), would just want to iterate the cycled elements, without needing to store them in an array. Thus, it's better to just define your own sequence and iterator, which wrap this array of element to cycle. \$\endgroup\$ – Alexander Apr 25 '18 at 18:15
  • \$\begingroup\$ Just thought of a cheeky implementation: (0..<count).flatMap { [true, false] } \$\endgroup\$ – Alexander Apr 25 '18 at 19:49
4
\$\begingroup\$

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
    }

    // ...
}
\$\endgroup\$
0
\$\begingroup\$

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) }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.