Array Contains Too Slow Swift

Question

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

Try using an NSOrderedSet? I realize that it's not a particularly Swift-y approach, but an ordered set is what you want for maximum speed membership tests. Alternatively, you can try this open-source implementation of a Swift OrderedSet. — Vatsal
– Vatsal, Commented Jan 6, 2017 at 8:54
The problem is not contains. The problem, I believe, is that your data model is wrong for the data you want to display and what you want to do with it. If you can't lay your hands on the data instantly, your data model is wrong. — matt
– matt, Commented Jan 6, 2017 at 16:17

Daniel Lemire · Accepted Answer · 2017-01-06 16:09:06Z

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)
        ]
    )

muescha · Accepted Answer · 2017-01-06 11:05:26Z

1

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) }

edited Jan 6, 2017 at 11:05

answered Jan 6, 2017 at 10:24

muescha

1,5392 gold badges12 silver badges22 bronze badges

1 Comment

ccrama Over a year ago

Thank you very much for the suggestion! I ended up filtering a new array whenever I took items out of the dataset, and used that new array to populate the data without having to use getHiddenCountUpTo. That made the whole thing much faster, and I'll definitely look into making a better model with less overhead

Collectives™ on Stack Overflow

Array Contains Too Slow Swift

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related