trjhtr

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?

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
 

 // ...

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)