Какой самый эффективный класс сбора в C # для поиска строк

#c# #data-structures #collections #linq-to-objects

#c# #структуры данных #Коллекции #linq-to-objects

Вопрос:

 string[] words = System.IO.File.ReadAllLines("word.txt");
var query = from word in words
            where word.Length > "abe".Length amp;amp; word.StartsWith("abe")
            select word;
foreach (var w in query.AsParallel())
{
    Console.WriteLine(w);
}

В основном word.txt содержит 170000 английских слов. Существует ли класс сбора данных в C #, который быстрее, чем массив строк для приведенного выше запроса? Не будет вставки или удаления, просто выполните поиск, если строка начинается с «abe» или «abdi».

Каждое слово в файле уникально.

EDIT 1 Этот поиск потенциально будет выполняться миллионы раз в моем приложении. Также я хочу использовать LINQ для запроса сбора данных, потому что мне может понадобиться использовать агрегатную функцию.

EDIT 2 Слова из файла уже отсортированы, файл не изменится

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

Ответ №1:

сам я бы создал Dictionary<char, List<string>> , где я бы группировал слова по их первой букве. Это существенно сократит время поиска нужного слова.

1. также вы можете захотеть проверить Wiki о дереве префиксов и суффиксов. Они предназначены для быстрого поиска по словам.

2. Я полагаю, что структура, которую вы используете в своем комментарии, является Trie .

3. Не усложнит ли это запрос linq?

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

5. @Eugen знаете ли вы какую-либо известную реализацию Trie в C #?

Ответ №2:

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

Если вам нужно выполнить повторный поиск, вы можете рассмотреть возможность сортировки массива (n Log n), и поиск по любому префиксу будет быстрым (long n). В зависимости от типа поиска использование словаря списков строк, индексированных по префиксу, может быть другим хорошим вариантом.

1. Если вы хотите сохранить код как можно ближе к оригинальному и выполнять большое количество запросов, SortedList<строка, string> выглядит хорошим вариантом. Префиксные деревья, упомянутые Евгением, вероятно, дали бы вам лучшую производительность, но потребовали бы большего ручного кодирования.

Ответ №3:

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