CODEWITHSUNDEEP
arraysswiftperformancecontains
ccrama
ccrama

Reputation: 754

Array Contains Too Slow Swift

I have been porting over an algorithm I've been using in Java (Android) to Swift (iOS), and have run into some issues with speed on the Swift version.

The basic idea is there are objects with depths (comment tree), and I can hide and show replies from the dataset by matching against a list of hidden objects. Below is a visualization

Top
- Reply 1
- - Reply 2
- - Reply 3
- Reply 4

and after hiding from the dataset

Top
- Reply 1
- Reply 4

The relevant methods I've converted from Java are as follows

 //Gets the "real" position of the index provided in the "position" variable. The comments array contains all the used data, and the hidden array is an array of strings that represent items in the dataset that should be skipped over.

    func getRealPosition(position: Int)-> Int{

        let hElements = getHiddenCountUpTo(location: position)
        var diff = 0
        var i = 0
        while i < hElements {
            diff += 1
            if(comments.count > position + diff && hidden.contains(comments[(position + diff)].getId())){
                i -= 1
            }
            i += 1
        }
        return position + diff
    }

    func getHiddenCountUpTo(location: Int) -> Int{
        var count = 0
        var i = 0
        repeat {
            if (comments.count > i && hidden.contains(comments[i].getId())) {
                count += 1
            }
            i += 1
        } while(i <= location && i < comments.count)
        return count
    }

This is used with a UITableViewController to display comments as a tree.

In Java, using array.contains was quick enough to not cause any lag, but the Swift version calls the getRealPosition function many times when calling heightForRowAt and when populating the cell, leading to increasing lag as more comment ids are added to the "hidden" array.

Is there any way I can improve on the speed of the array "contains" lookups (possibly with a different type of collection)? I did profiling on the application and "contains" was the method that took up the most time.

Thank you

Upvotes: 3

Views: 3740

Answers (2)

Daniel Lemire
Daniel Lemire

Reputation: 3618

Both Java and Swift have to go through all elements contained in the array. This gets slower and slower as the array gets larger.

There is no a priori reason for Java to fare better, as they both use the exact same algorithm. However, strings are implemented very differently in each language, so that could make string comparisons more expensive in Swift.

In any case, if string comparison slows you down, then you must avoid it.

Easy fix: use a Set

If you want a simple performance boost, you can replace an array of strings with a set of strings. A set in Swift is implemented with a hash table, meaning that you have expected constant time query. In practice, this means that for large sets, you will see better performance.

    var hiddenset Set<String> = {}
    for item in hidden {
      strset.insert(item)
    }

For best performance: use a BitSet

But you should be able to do a whole lot better than even a set can do. Let us look at your code

    hidden.contains(comments[i].getId()))

If you are always accessing hidden in this manner, then it means that what you have is a map from integers (i) to Boolean values (true or false).

Then you should do the following...

    import Bitset;

    let hidden = Bitset ();
    // replace hidden.append(comments[i].getId())) by this:
    hidden.add(i)
    // replace hidden.contains(comments[i].getId())) by this:
    hidden.contains(i)

Then your code will really fly!

To use a fast BitSet implementation in Swift, include the following in Package.swift (it is free software):

    import PackageDescription

    let package = Package(
        name: "fun",
        dependencies: [
       .Package(url: "https://github.com/lemire/SwiftBitset.git",  majorVersion: 0)
        ]
    )

Upvotes: 9

muescha
muescha

Reputation: 1539

i think you need the realPosition to link from a tap on a row in the tableview to the source array?

1) make a second array with data only for the tableViewDataSource

copy all visible elements to this new array. create a special ViewModel as class or better struct which only has the nessesary data to display in the tableview. save in this new ViewModel the realdataposition also as value. now you have a backlink to the source array

2) then populate this TableView only from the new datasource

3) look more into the functional programming in swift - there you can nicer go over arrays for example:

var array1 = ["a", "b", "c", "d", "e"]
let array2 = ["a", "c", "d"]
array1 = array1.filter { !array2.contains($0) }

or in your case:

let newArray = comments.filter{ !hidden.contains($0.getId()) }

or enumerated to create the viewmodel

struct CommentViewModel {
  var id: Int
  var text: String
  var realPosition: Int
}

let visibleComments: [CommentViewModel] = comments
   .enumerated()
   .map { (index, element) in
      return CommentViewModel(id: element.getId(), text: element.getText(), realPosition: index)
   }
   .filter{ !hidden.contains($0.id) }

Upvotes: 1

Related Questions