Как можно ускорить код поиска в List C#

Question

Есть класс. В ней для переопределил метод ToString() который создает строку в формате ФИО (и заодно удаляет пробелы лишние, если такоевые есть).

public struct FullName
{
    public string Name;
    public string Surname;
    public string Patronymic;

    public override string ToString()
    {
        var str = string.Join(' ', Surname?.Trim(), Name?.Trim(), Patronymic?.Trim()).Trim();
        return str;
    }
}

И есть класс с методом Search. В этом классе есть поле List<FullName>.

private readonly List<FullName> _fullNames; //заполняются извне

public List<string> Search(string prefix)
{
    var items = _fullNames.ToArray();
    List<string> result = new List<string>();

    if (string.IsNullOrEmpty(prefix) || string.IsNullOrWhiteSpace(prefix))
        throw new ArgumentNullException();

    if (prefix.Length > 100)
        throw new ArgumentException();


    for(int i = 0; i < items.Length; i++)
    {
        if (items[i].ToString().Contains(prefix))
            result.Add(items[i].ToString());
    }
    return result;
}

Вот сама задача (.NET 3.1): Надо сделать поиск физ. лиц. Дана структура FullName с полями Surname, Name, Patronomyc и метод Search(string prefix) в отдельном классе.

Условия:

Поиск только по префиксу, без исправления ошибок и без поиска по подстроке.
Поиск по префиксу должен работать только по полной строке сформированной из FullName (нет случаев когда в FullName есть имя и фамилия и надо искать одновременно по префиксу имени и фамилии)
Строка из FullName имеет вид: "Фамилия Имя Отчество", один или несколько свойств могут быть null.
Результат выполнения метода может быть отсортирован в каком угодно порядке.

Answer 1

Предложения по оптимизации:

Устранить дублирование алгоритма поиска: сначала выполняется перебор _fullNames и запись результатов в searched, потом опять выборка из _fullNames через LINQ.
Использовать для поиска подстроки метод Contains.

Цитата из Практическое руководство. Поиск по строкам:

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

Сравнение производительности Performance Test — String.Contains vs String.IndexOf vs Regex.IsMatch

Вызов .Trim() в GetPersonalDataAsString не нужен. Кстати, метод GetPersonalDataAsString можно изменить на переопределение метода .ToString()

Для всех изменений желательно замерять время выполнения, например, через Stopwatch.

Для дальнейших оптимизаций необходимы дополнительные данные по задаче, например, какое ориентировочно количество ФИО в списке _fullNames и что может приходить в prefix. Например, если в prefix может приходить что-то вида "Иван Иванов", то алгоритм не сработает.

Еще, если нужно возвращать только ФИО и поиск только по ним, тогда может быть лучше работать сразу со строками, а не со структурой. Тогда не понадобится множество раз вызывать метод string.Join.

Также нужно ограничение на длину префикса, например, минимум 3 символа.

Answer 2

У вас задача поиска по префиксу - для этого есть специальная структура данных - префиксное дерево или trie

Код поиска простой. Добавим пару методов в вашу структуру (чтобы избавиться от дубликатов в конце)

public struct FullName
{
    public string Name;
    public string Surname;
    public string Patronymic;

    public override string ToString()
    {
        var str = string.Join(" ", Surname?.Trim(), Name?.Trim(), Patronymic?.Trim()).Trim();
        return str;
    }

    public override bool Equals(object obj)
    {
        return obj is FullName name
        && Name == name.Name
        && Surname == name.Surname
        && Patronymic == name.Patronymic;
    }

    public override int GetHashCode()
    {
        int hash = 17;
        if (Name != null)
            hash = hash * 23 + Name.GetHashCode();
        if (Surname != null)
            hash = hash * 23 + Surname.GetHashCode();
        if (Patronymic != null)
            hash = hash * 23 + Patronymic.GetHashCode();
        return hash;
    }
}

Потом определим узел дерева с нужными методами

public class TrieNode
{
    private FullName? data;
    private Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();

    public void Add(string path, FullName data)
    {
        if (path == null) return;
        Add(path, 0, data);
    }

    private void Add(string path, int index, FullName data)
    {
        if (index == path.Length)
        {
            this.data = data;
            return;
        }

        var c = path[index];
        if (!children.ContainsKey(c)) children.Add(c, new TrieNode());
        children[c].Add(path, index + 1, data);
    }

    public void GetByPrefix(string prefix, HashSet<FullName> result)
    {
        GetByPrefix(prefix, 0, result);
    }

    private void GetByPrefix(string prefix, int index, HashSet<FullName> result)
    {
        if (data.HasValue)
            result.Add(data.Value);

        if (index >= prefix.Length)
        {
            foreach (var node in children.Values)
                node.GetByPrefix(prefix, index, result);
        }
        else
        {
            var c = prefix[index];
            if (children.ContainsKey(c))
                children[c].GetByPrefix(prefix, index + 1, result);
        }
    }
}

Ну и использование элементарное

TrieNode root = new TrieNode();

var names = new FullName[] { 
    new FullName() {Surname = "Ivanov", Name = "Ivan", Patronymic = "Petrovich"},
    new FullName() {Surname = "Vasilyev", Name = "Ivan", Patronymic = "Petrovich"},
};  

foreach(var name in names) {
    root.Add(name.ToString(), name);
    root.Add(name.Name, name);
    root.Add(name.Surname, name);
    root.Add(name.Patronymic, name);
}

var ret = new HashSet<FullName>();
root.GetByPrefix("Iva", ret);
root.GetByPrefix("Pet", ret);   
foreach(var name in ret) Console.WriteLine(name.ToString());

Вывод в консоль

Vasilyev Ivan Petrovich
Ivanov Ivan Petrovich

Answer 3

А вы уверены, сортировка деревом быстрая? У меня скопированный код от пользователя "tym32167" , увеличился по результатам на 21лям наносекунд, по сравнению с вариантом из LINQ , который был всего 9к.

БЛОГ НА HUSL

Как можно ускорить код поиска в List C#

Ответы (3 шт):