Какой самый быстрый способ фильтрации списка строк при создании списка Intellisense / Autocomplete?

Question

Я пишу Intellisense / Autocomplete, как тот, который вы найдете в Visual Studio.Все нормально, пока список не содержит, вероятно, более 2000 элементов.

Я использую простой оператор LINQ для выполнения фильтрации:

var filterCollection = from s in listCollection
                       where s.FilterValue.IndexOf(currentWord,     
                       StringComparison.OrdinalIgnoreCase) >= 0
                       orderby s.FilterValue
                       select s;

Затем я назначаю эту коллекцию WPFItemSource Listbox, и на этом все, работает нормально.

Заметим, что Listbox также виртуализирован, поэтому в памяти и в дереве визуальных элементов будет не более 7-8 визуальных элементов.

Однако предостережение в настоящее время заключается в том, что, когда пользователь очень быстро печатает в richtextbox, и при каждом нажатии клавиши я выполняю привязку filtering +, возникает это условие полу-гонки или несинхронной фильтрации, напримерфильтрация первого нажатия клавиш все еще может выполнять свою работу по фильтрации или привязке, в то время как четвертый ход клавиш также делает то же самое.

Я знаю, что могу применить задержку перед применением фильтра, но я пытаюсьчтобы добиться плавной фильтрации, как в Visual Studio.

Я не уверен, в чем именно заключается моя проблема, поэтому я также приписываюПримените его к строковой операции IndexOf, или, возможно, мой список строк можно оптимизировать с помощью какого-либо индекса, что может ускорить поиск.

Любые предложения примеров кода приветствуются.

Спасибо.

Answer 1

Я думаю, проблема в том, что ваш фильтр выполняет O(n) (где n - общее количество элементов для автозаполнения), то есть он должен пройти через каждый элемент , чтобы выяснить, какие из них соответствуют. Чем больше у вас предметов, тем хуже будет работать фильтр.

Вместо использования списка, попробуйте использовать trie . Выполнение попытки O(m), где m - количество символов в строке. Это означает, что размер набора данных не влияет на производительность поиска.

В Promptu (средство запуска приложений, которое я написал) я использую попытки в intellisense / autocomplete. Если вы хотите увидеть пример попыток в действии, вы можете скачать его и попробовать.

Answer 2

Задержка не ваша проблема, если у вас есть набор результатов из 2000 элементов.Здесь я делаю некоторые большие предположения, но вам действительно нужно вернуть максимум 500 элементов - ваш пользователь будет продолжать печатать, чтобы сузить набор результатов, пока он не станет приемлемым размером для просмотра.

Вам следует оптимизироватьтипичный случай (я предполагаю, где он в конечном итоге скажет ~ 50 элементов) - если ваш пользователь просматривает небольшой список из 2000 элементов, что-то еще не так, и интерфейс требует дополнительной работы.

Answer 3

Я бы посоветовал попытаться ограничить ваш набор результатов некоторым количеством элементов и посмотреть, исчезнет ли проблема. То есть у вас может быть 5000 на выбор, но попробуйте вернуть не более 100, даже если больше совпадений. Скажи:

var filterCollection = (from s in listCollection
  where s.FilterValue.IndexOf(currentWord,StringComparison.OrdinalIgnoreCase)>=0
  orderby s.FilterValue
  select s).Take(100);

Если ваша проблема исчезнет, ​​замедление может быть вызвано слишком большим количеством элементов, возвращаемых для списка. Я не уверен, что проблема исчезнет, ​​поскольку ListBox виртуализирован, но его стоит попробовать. Вы также можете попробовать то же самое, но ограничив результат фильтрации до 100 элементов, перед сортировкой (т. Е. Orderby) и посмотреть, поможет ли это. В любом случае это эффективнее делать в таком порядке:

var filterCollection = (from s in listCollection
  where s.FilterValue.IndexOf(currentWord,StringComparison.OrdinalIgnoreCase)>=0
  select s).Take(100)
           .OrderBy(s => s.FilterValue);

В нижней строке определяется, является ли проблема функцией количества элементов, возвращенных и назначенных для filterColection, или начального количества элементов, или обоих.

Answer 4

Вот ваше "состояние гонки".

orderby s.FilterValue

Рассмотрим последовательность букв d, o, g.

• «d» начинает работать и будет соответствовать, скажем, 30% набора. Необходимо заказать 6000 наименований.
• «do» начинает работать и будет соответствовать, скажем, 6% от набора. 1200 предметов должны быть заказаны.
• «собака» начинает бегать и будет соответствовать, скажем, 0,5% от набора. 100 предметов должны быть заказаны.

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

Самое правильное поведение, которое я могу себе представить, - это предотвратить привязку любых предыдущих активных событий при запуске события. Если вы можете предотвратить привязку, остановив выполнение этих событий, тем лучше. Вспомните эти ракеты, у них больше нет целей.

Answer 5

Действительно простая оптимизация - это

if(currentWord.StartsWith(lastWord))

, которую вы можете отфильтровать по списку отфильтрованных элементов, возвращаемых по последнему запросу.То есть, если вы не уменьшите количество элементов, возвращаемых вашим запросом LINQ, как предлагается в некоторых других ответах.Вы всегда можете сохранить то, что содержится в запросе, в переменной, а затем выполнить Take (100) после этого, хотя вам нужно будет убедиться, что ленивое выполнение LINQ в этом случае вас не укусит.Вместо того, чтобы заменять всю коллекцию, вы можете использовать ObservableCollection и просто добавлять / удалять элементы из нее.Было бы неплохо инвертировать то, что возвращает ваш фильтр, если вы собираетесь это сделать, но вы бы увидели гораздо более быстрый отклик и не увидели бы такого большого снижения производительности, если бы пользователь печатал быстро.