Фильтровать огромный массив, оптимизируя производительность

Question

У меня есть массив с более чем 300k объектов, которые я показываю в UITableView. При фильтрации по совпадению префиксов с использованием метода filter первый поиск занимает чуть более 60 секунд! После этого поиск выполняется намного быстрее и занимает около 1 с, что я бы хотел еще улучшить.

Объект выглядит так:

struct Book {
    let id: Int
    let title: String
    let author: String
    let summary: String
}

Вот как яm фильтрация на данный момент:

filteredBooks = books.filter { $0.title.lowercased().hasPrefix(prefix.lowercased()) }

Данные поступают из файла JSON, который я декодирую с использованием Codable (который также занимает немного больше времени, чем хотелось бы). Я пытаюсь достичь этого без базы данных или каких-либо реализаций фреймворка, без ленивой загрузки элементов. Я хотел бы иметь возможность показывать 300 тыс. Объектов в UITableView и в реальном времени filter с приличной производительностью.

Я немного погуглил и нашел поиск Binary Search и Trieалгоритмы, но не знал, как их реализовать, чтобы иметь возможность использовать их с Codable и моим struct. Также может помочь замена struct другим типом данных, но не уверен, какой из них тоже.

Answer 1

Поскольку мне понравился вызов, я соединила что-то

По сути, это дерево, каждый слой которого содержит префикс заголовка, а также элементы с таким точным соответствием, а также список нижних деревьев, каждый из которых имеет одинаковый префикс плюс еще одну букву алфавита:

extension String {
    subscript (i: Int) -> String {
        let start = index(startIndex, offsetBy: i)
        return String(self[start...start])
    }
}

struct Book {
    let id: Int
    let title: String
    let author: String
    let summary: String
}

class PrefixSearchable <Element> {
    let prefix: String
    var elements = [Element]()
    var subNodes = [String:PrefixSearchable]()
    let searchExtractor : (Element) -> String

    private init(prefix: String, searchExtractor:@escaping(Element) -> String) {
        self.prefix = prefix
        self.searchExtractor = searchExtractor
    }

    convenience init(_ searchExtractor:@escaping(Element) -> String) {
        self.init(prefix: "", searchExtractor: searchExtractor)
    }

    func add(_ element : Element) {
        self.add(element, search: searchExtractor(element))
    }

    private func add(_ element : Element, search : String) {
        if search == prefix {
            elements.append(element)
        } else {
            let next = search[prefix.count]
            if let sub = subNodes[next] {
                sub.add(element, search: search)
            } else {
                subNodes[next] = PrefixSearchable(prefix: prefix + next, searchExtractor: searchExtractor)
                subNodes[next]!.add(element, search: search)
            }
        }
    }

    func elementsWithChildren() -> [Element] {
        var ele = [Element]()
        for (_, sub) in subNodes {
            ele.append(contentsOf: sub.elementsWithChildren())
        }
        return ele + elements
    }

    func search(search : String) -> [Element] {
        print(prefix)
        if search.count == prefix.count {
            return elementsWithChildren()
        } else {
            let next = search[prefix.count]
            if let sub = subNodes[next] {
                return sub.search(search: search)
            } else {
                return []
            }
        }
    }
}

let searchable : PrefixSearchable<Book> = PrefixSearchable({ $0.title.lowercased() })
searchable.add(Book(id: 1, title: "title", author: "", summary: ""))
searchable.add(Book(id: 2, title: "tille", author: "", summary: ""))

print(searchable.search(search: "ti")) // both books
print(searchable.search(search: "title")) // just one book
print(searchable.search(search: "xxx")) // no books

Вероятно, его можно улучшить с точки зрения читабельности (мой swift сейчас довольно ржавый). Я не гарантирую, что это работает во всех угловых случаях.
Возможно, вам придется добавить «предел поиска», который прекратит рекурсивный возврат всех дочерних элементов, если точное совпадение не найдено.

Answer 2

Прежде чем начать что-либо менять, запустите Instruments и определите, где находятся ваши узкие места. Очень легко преследовать неправильные вещи.

Я очень подозрительно отношусь к этому числу 60-х годов. Это огромное количество времени и предполагает, что вы действительно делаете эту фильтрацию неоднократно. Могу поспорить, вы делаете это один раз в видимый ряд или что-то в этом роде. Это объясняет, почему во второй раз это происходит намного быстрее. 300к это много, но на самом деле это не так уж много. Компьютеры работают очень быстро, и минута - это очень много времени.

Тем не менее, существуют некоторые очевидные проблемы с вашим существующим фильтром. Он пересчитывает prefix.lowercased() 300k раз, что не нужно. Вы можете извлечь это:

let lowerPrefix = prefix.lowercased()
filteredBooks = books.filter { $0.title.lowercased().hasPrefix(lowerPrefix) }

Точно так же вы пересчитываете все title.lowercased() для каждого поиска, и вам почти никогда не нужно все это. Вы можете кэшировать версии в нижнем регистре, но вы также можете просто прописать в нижнем регистре то, что вам нужно:

let lowerPrefix = prefix.lowercased()
let prefixCount = prefix.count // This probably isn't actually worth caching
filteredBooks = books.filter { $0.title.prefix(prefixCount).lowercased() == lowerPrefix }

Я сомневаюсь, что вы получите много пользы таким образом, но это то, что нужно изучить, прежде чем исследовать романструктуры данных.

Тем не менее, если единственный вид поиска, который вам нужен, это поиск по префиксу, Trie определенно предназначен именно для этой проблемы. И да, двоичный поиск также стоит рассмотреть, можете ли вы сохранить свой список в порядке заголовка, и поиск префиксов - единственное, что вас волнует.

Хотя это не поможет при первом поиске, имейте в виду, чтоВаш второй поиск часто может быть намного быстрее путем кэширования последних поисков. В частности, если вы уже искали «a», то вы знаете, что «ap» будет подмножеством этого, поэтому вам следует использовать этот факт. Точно так же подобные поиски очень часто повторяются, когда пользователи делают опечатки и возврат. Таким образом, сохранение некоторых недавних результатов может быть большим выигрышем за счет памяти.

При таких масштабах распределение памяти и копирование могут быть проблемой. Тип вашей книги имеет порядок 56 байтов:

MemoryLayout.stride(ofValue: Book()) // 56

(размер такой же, но шаг немного более значим, когда вы думаете о размещении их в массиве; он включает любые отступы между элементамиВ этом случае отступ равен 0. Но если вы добавите свойство Bool, вы увидите разницу.)

Содержимое строк не нужно копировать (если нет мутации), поэтомуэто не имеет значения, как долго строки. Но метаданные должны быть скопированы, и это складывается.

Таким образом, полная копия этого массива порядка 16 МБ данных, которые необходимо скопировать. Самое большое подмножество, которое вы ожидаете, будет 10-15% (10% слов начинаются с самой распространенной буквы, s , в английском языке, но названия могут немного исказить это). Это по-прежнему порядка мегабайта копирования на фильтр.

Вы можете улучшить это, работая исключительно с индексами, а не с полными элементами. К сожалению, в stdlib нет хороших инструментов для этого, но их не так сложно написать.

extension Collection {
    func indices(where predicate: (Element) -> Bool) -> [Index] {
        indices.filter { predicate(self[$0]) }
    }
}

Вместо того, чтобы копировать 56 байтов, это копирует 8 байтов на результат, что может значительно уменьшить отток памяти.

Вы также можете реализовать это как IndexSet;Я не уверен, с кем будет работать быстрее.