arrays - 数组包含太慢的 Swift

Question

我一直在将我在 Java (Android) 中使用的算法移植到 Swift (iOS)，但在 Swift 版本上遇到了一些速度问题。

基本思想是存在具有深度的对象(评论树)，我可以通过与隐藏对象列表进行匹配来隐藏和显示来自数据集的回复。下面是一个可视化

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

从数据集中隐藏之后

Top
- Reply 1
- Reply 4

我从Java转过来的相关方法如下

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

这与 UITableViewController 一起使用以将评论显示为树。

在 Java 中，使用 array.contains 足够快，不会造成任何延迟，但 Swift 版本在调用 heightForRowAt 和填充单元格时多次调用 getRealPosition 函数，导致延迟增加，因为更多评论 ID 添加到“隐藏”数组。

有什么方法可以提高数组“包含”查找的速度(可能使用不同类型的集合)？我对应用程序进行了分析，“包含”是占用时间最多的方法。

谢谢

Answer 1

Java 和 Swift 都必须遍历数组中包含的所有元素。随着数组变大，这会变得越来越慢。

没有先验的理由让 Java 表现得更好，因为它们都使用完全相同的算法。但是，字符串在每种语言中的实现方式非常不同，因此这可能会使 Swift 中的字符串比较成本更高。

无论如何，如果字符串比较会减慢您的速度，那么您必须避免它。

轻松修复:使用 Set

如果您想要一个简单的性能提升，您可以用一组字符串替换一个字符串数组。 Swift 中的集合是用哈希表实现的，这意味着您希望进行恒定时间查询。实际上，这意味着对于大型集合，您会看到更好的性能。

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

为了获得最佳性能:使用 BitSet

但是你应该能够比一组人做得更好。让我们看看您的代码

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

如果您总是以这种方式访问​​hidden，那么这意味着您拥有的是从整数 (i) 到 bool 值(true 或 false)的映射.

那么你应该做以下...

    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)

那你的代码就真的飞起来了!

要在 Swift 中使用快速的 BitSet 实现，请在 Package.swift(它是免费软件)中包含以下内容:

    import PackageDescription

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