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

StackOverflow https://stackoverflow.com/questions/97329

Вопрос

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

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

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

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

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

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

Это было полезно?

Решение

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

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

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

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

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

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

Редактировать, основанный на комментарии

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

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

Все остальное - это некоторая специализация на этих понятиях.

Другие советы

var Answers = Мой список.Где(item => item.bar.StartsWith(запрос) || item.bar.EndsWith(запрос));

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

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

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

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

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

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

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

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

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

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

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

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

Мы можем создать такой индекс, как этот:

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, как в вашем примере, но опять же мы должны поддерживать индекс в актуальном состоянии.Нет никакой гарантии, что это будет быстрее, но это определенно сложнее.

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top