Array Содержит Too Slow 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 вызывает функцию getRealPosition много раз при вызове heightForRowAt и при заполнении ячейки, что приводит к увеличению задержки, так как добавляется больше комментариев ids «скрытый» массив.

Есть ли способ улучшить скорость массива «содержит» поиск (возможно, с использованием другого типа коллекции)? Я сделал профилирование приложения, и «содержит» был методом, который занимал больше всего времени.

Спасибо

Answer 1

я думаю, что вам нужно realPosition связать из крана на строку в Tableview в исходном массиве?

1) сделать второй массив с данными только для копии tableViewDataSource

все видимые элементы этого нового массива. создайте специальную ViewModel как класс или лучшую структуру, которая имеет только необходимые данные для отображения в виде таблицы. сохраните в этом новом ViewModel значение realdataposition также как значение. Теперь у вас есть обратная ссылка на исходном массив

2), а затем заполнить этот TableView только из нового источника данных

3) выглядит более в functional programming в скор - там вы можете лучше перейти на массивы, например:

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

или в вашем случае:

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

или перечисленной создать 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) }  

Answer 2

И 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) для логических значений (истина или ложь).

Тогда вы должны сделать следующее ...

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) 

Тогда ваш код будет действительно летать!

Чтобы использовать быстрое внедрение BITSET в Swift, включают следующее Package.swift (это свободное программное обеспечение):

import PackageDescription 

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