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

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» вообще не помогает с запросом «endsWith».

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

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

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

EDIT, основанный на комментарии

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

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

Что-то еще есть специализация по этим понятиям.

Answer 2

var Answers = myList.Where (item => item.bar.StartsWith (query) || item.bar.EndsWith (query));

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

Answer 3

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

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

Answer 4

Я сейчас не нахожусь на своей Java, но я подумал о следующих вещах.

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

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

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

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 8

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

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

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

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

Answer 9

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