Swift equivalent of Python slice assignment

Question

In Python, one can have a list (similar to an array in swift):

>>> li=[0,1,2,3,4,5]

And perform a slice assignment on any / all of the list:

>>> li[2:]=[99]         # note then end index is not needed if you mean 'to the end'
>>> li
[0, 1, 99]

Swift has a similar slice assignment (this is in the swift interactive shell):

  1> var arr=[0,1,2,3,4,5]
arr: [Int] = 6 values {
  [0] = 0
  [1] = 1
  [2] = 2
  [3] = 3
  [4] = 4
  [5] = 5
}
  2> arr[2...arr.endIndex-1]=[99]
  3> arr
$R0: [Int] = 3 values {
  [0] = 0
  [1] = 1
  [2] = 99
}

So far, so good. But, there are a couple of issues.

First, swift does not work for an empty list or if the index is after the endIndex. Python appends if the slice index is after then end index:

>>> li=[]             # empty
>>> li[2:]=[6,7,8]
>>> li
[6, 7, 8]
>>> li=[0,1,2]
>>> li[999:]=[999]
>>> li
[0, 1, 2, 999]

The equivalent in swift is an error:

  4> var arr=[Int]()
arr: [Int] = 0 values
  5> arr[2...arr.endIndex-1]=[99]
fatal error: Can't form Range with end < start

That is easy to test and code around.

Second issue is the killer: it is really slow in swift. Consider this Python code to to perform exact summations of a list of floats:

def msum(iterable):
    "Full precision summation using multiple floats for intermediate values"
    # Rounded x+y stored in hi with the round-off stored in lo.  Together
    # hi+lo are exactly equal to x+y.  The inner loop applies hi/lo summation
    # to each partial so that the list of partial sums remains exact.
    # Depends on IEEE-754 arithmetic guarantees.  See proof of correctness at:
    # www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps

    partials = []               # sorted, non-overlapping partial sums
    for x in iterable:
        i = 0
        for y in partials:
            if abs(x) < abs(y):
                x, y = y, x
            hi = x + y
            lo = y - (hi - x)
            if lo:
                partials[i] = lo
                i += 1
            x = hi
        partials[i:] = [x]
    return sum(partials, 0.0)

It works by maintaining a hi/lo partial summations so that msum([.1]*10) produces 1.0 exactly rather than 0.9999999999999999. The C equivalent of msum is part of the math library in Python.

I have attempted to replicate in swift:

func msum(it:[Double])->Double {
    // Full precision summation using multiple floats for intermediate values 
    var partials=[Double]()
    for var x in it {
        var i=0
        for var y in partials{
            if abs(x) < abs(y){
                (x, y)=(y, x)
            }
            let hi=x+y
            let lo=y-(hi-x)
            if abs(lo)>0.0 {
                partials[i]=lo
                i+=1
            }
            x=hi
        }
        // slow part trying to replicate Python's slice assignment partials[i:]=[x]
        if partials.endIndex>i {
            partials[i...partials.endIndex-1]=[x]
        }
        else {
            partials.append(x)
        }    
    } 
    return partials.reduce(0.0, combine: +)
}

Test the function and speed:

import Foundation
var arr=[Double]()
for _ in 1...1000000 {
    arr+=[10, 1e100, 10, -1e100]
    }

print(arr.reduce(0, combine: +))    // will be 0.0
var startTime: CFAbsoluteTime!
startTime = CFAbsoluteTimeGetCurrent()
print(msum(arr), arr.count*5)          // should be arr.count * 5
print(CFAbsoluteTimeGetCurrent() - startTime)

On my machine, that takes 7 seconds to complete. Python native msum takes 2.2 seconds (about 4x faster) and the library fsum function takes 0.09 seconds (almost 90x faster)

I have tried to replace partials[i...partials.endIndex-1]=[x] with arr.removeRange(i..<arr.endIndex) and then appending. Little faster but not much.

Question:

1. Is this idiomatic swift: partials[i...partials.endIndex-1]=[x]
2. Is there a faster / better way?

Answer 1

First (as already said in the comments), there is a huge difference between non-optimized and optimised code in Swift ("-Onone" vs "-O" compiler option, or Debug vs. Release configuration), so for performance test make sure that the "Release" configuration is selected. ("Release" is also the default configuration if you profile the code with Instruments).

It has some advantages to use half-open ranges:

var arr = [0,1,2,3,4,5]
arr[2 ..< arr.endIndex] = [99]
print(arr) // [0, 1, 99]

In fact, that's how a range is stored internally, and it allows you to insert a slice at the end of the array (but not beyond that as in Python):

var arr = [Int]()
arr[0 ..< arr.endIndex] = [99]
print(arr) // [99]

So

if partials.endIndex > i {
    partials[i...partials.endIndex-1]=[x]
}
else {
    partials.append(x)
} 

is equivalent to

 partials[i ..< partials.endIndex] = [x]
 // Or: partials.replaceRange(i ..< partials.endIndex, with: [x])

However, that is not a performance improvement. It seems that replacing a slice is slow in Swift. Truncating the array and appending the new element with

partials.replaceRange(i ..< partials.endIndex, with: [])
partials.append(x)

reduced the time for your test code from about 1.25 to 0.75 seconds on my computer.

Answer 2

As @MartinR points out, replaceRange is faster than slice assignment.

If you want maximum speed (based on my tests), your best bet is probably:

partials.replaceRange(i..<partials.endIndex, with: CollectionOfOne(x))

CollectionOfOne is faster than [x] because it just stores the element inline within the struct, rather than allocating memory like an array.