Самый быстрый способ найти объекты из коллекции, соответствующие условию строкового члена

Question

Предположим, у меня есть коллекция (будь то массив, общий список или что-то самое быстрое * решение этой проблемы) определенного класса, назовем его ClassFoo:

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
} 

Предположим, в коллекции будет около 50 000 предметов, все в памяти. Теперь я хочу получить как можно быстрее все экземпляры в коллекции, которые подчиняются условию на своем элементе панели, например, так:

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

Как получить результаты как можно быстрее? Должен ли я рассмотреть некоторые передовые методы индексации и структуры данных?

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

Answer 1

С ограничением на то, что условие может быть «чем угодно», вы ограничены сканированием всего списка и применением условия.

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

Например, пример кода со словарем "byFirstLetter" вообще не помогает с запросом конца-с-нуля.

Итак, все сводится к тому, какие запросы вы хотите выполнить к этим данным.

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

Если у вас есть более конкретное подмножество типов запросов, вы можете принять лучшее решение о том, какая структура лучше. Также вам нужно учитывать объем данных. Если у вас есть список из 10 элементов, каждый размером менее 100 байт, сканирование всего может оказаться самым быстрым, что вы можете сделать, поскольку у вас такой маленький объем данных. Очевидно, что это не масштабируется до элементов 1M, но даже умные методы доступа влекут за собой затраты на настройку, обслуживание (например, обслуживание индекса) и память.

РЕДАКТИРОВАТЬ , на основании комментария

Если это автозаполнение, если данные статические, то сортируйте их и используйте двоичный поиск. Вы действительно не будете быстрее, чем это.

Если данные динамические, сохраните их в сбалансированном дереве и выполните поиск по ним. По сути, это бинарный поиск, позволяющий добавлять данные случайным образом.

Что-то еще является специализацией в этих понятиях.

Answer 2

var ответы = myList.Where (item => item.bar.StartsWith (запрос) || item.bar.EndsWith (запрос));

это самый простой на мой взгляд, должен выполняться довольно быстро.

Answer 3

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

Answer 4

Зависит. Все ваши объекты всегда будут загружаться в память? У вас есть конечный лимит объектов, которые могут быть загружены? Будут ли ваши запросы учитывать объекты, которые еще не были загружены?

Если коллекция станет большой, я бы определенно использовал индекс.

Фактически, если коллекция может вырасти до произвольного размера, и вы не уверены, что сможете разместить все это в памяти, я бы посмотрел на ORM, базу данных в памяти или другую встроенную база данных. Вспоминается XPO от DevExpress для ORM или SQLite.Net для базы данных в памяти.

Если вы не хотите заходить так далеко, создайте простой индекс, состоящий из ссылок «bar», отображающих ссылки на классы.

Answer 5

Вы можете создать какой-то индекс, и он может стать быстрее.

Мы можем построить индекс так:

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

Тогда используйте это так:

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

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

Answer 6

Если вы что-то заполняете список один раз, а затем выполняете много поисков (тысячи или больше), вы можете создать какой-то словарь поиска, который сопоставляет значения, начинающиеся с /, и заканчивая их фактическими значениями. Это был бы быстрый поиск, но использовал бы намного больше памяти. Если вы не выполняете так много поисков или знаете, что собираетесь заполнять список хотя бы не так часто, я бы пошел с запросом LINQ, предложенным CQ.

Answer 7

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

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

Answer 8

Я сейчас не знаком с Java, но я бы подумал о следующих вещах.

Как вы создаете свой список? Возможно, вы можете создать уже заказанный таким образом, чтобы сократить время сравнения.

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

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

Оптимизация вашего запроса сравнения путем определения того, какое сравнение наиболее вероятно будет истинным, и выполнение этого вначале также может помочь. Например: если в общем случае 10% времени член коллекции начинается с вашего запроса, а 30% времени член заканчивается завершением запроса, вам нужно сначала выполнить конечное сравнение.

Answer 9

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

Вы можете распараллелить, если у вас несколько ядер или машин.