Высокоскоростное сопоставление строк в С#

У меня есть список из 10 000 сотрудников в List<T>, и у меня есть ListBox, который содержит подмножество этих сотрудников в зависимости от поискового запроса в текстовом поле.

Скажите, что объект Staff имеет следующие общедоступные свойства:

string FirstName
string LastName
string MiddleName
   int StaffID
   int CostCentre

Я мог бы написать такую функцию:

bool staffMatchesSearch(Staff stf)
{
  if (tbSrch.Text.Trim() == string.Empty)
    return true; // No search = match always.

  string s = tbSrch.Text.Trim().ToLower();

  // Do the checks in the order most likely to return soonest:
  if (stf.LastName.ToLower().Contains(s))
    return true;
  if (stf.FirstName.ToLower().Contains(s))
    return true;
  if (stf.MiddleName.ToLower().Contains(s))
    return true;

  if (stf.CostCentre.ToString().Contains(s))
    return true; // Yes, we want partial matches on CostCentre
  if (stf.StaffID.ToString().Contains(s))
    return true; // And also on StaffID

  return false;
}

а затем сделайте что-то вроде:

tbSrch_TextChanged(object sender, EventArgs e)
{
  lbStaff.BeginUpdate();
  lbStaff.Items.Clear();

  foreach (Staff stf in staff)
    if (staffMatchesSearch(stf))
      lbStaff.Items.Add(stf);

  lbStaff.EndUpdate();
}

Фильтрация пересматривается каждый раз, когда пользователь меняет содержимое поля tbSrch.

Это работает, и это не ужасно медленно, но мне было интересно, могу ли я сделать это быстрее?

Я попытался переписать все, чтобы быть многопоточным, однако только с 10 000 сотрудников накладные расходы, казалось, отняли большую часть выгоды. Кроме того, было множество других ошибок, например, при поиске "Джона", пользователь сначала нажимает "J", который разматывает потоки, но когда пользователь нажимает "o", другой набор наматывается до того, как первая партия шанс вернуть свои результаты. Много времени результаты возвращаются в беспорядочном порядке и происходят всевозможные неприятные вещи.

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

Есть ли у вас идеи о том, как это можно улучшить?

Отличные предложения, которые я реализовал далеко, и их результаты:

Добавьте задержку в событие ValueChanged, чтобы, если пользователь быстро набирает 5-значное имя на клавиатуре, он выполняет только 1 поиск в конце, а не 5 в последовательности.
Предварительно оцените ToLower() и сохраните в классе Staff (как атрибут [NonSerialized], чтобы он не занимал лишнего места в файле сохранения).
Добавить свойство get в Staff, которое возвращает все критерии поиска как одну, длинную, строчную, конкатенированную строку. Затем запустите один Contains(). (Эта строка хранится в объекте Staff, поэтому она создается только один раз.)

До сих пор они сокращали время поиска с примерно 140 мс до примерно 60 мс (хотя эти цифры очень субъективны в зависимости от фактического выполнения поиска и количества возвращенных результатов).

Ответ 1

1), как указано в комментариях, вы, вероятно, не должны. ToString числовые поля - просто соответствуют номерам

2) вызовы ToLower являются безусловным утечкой. Добавьте нижние версии этих свойств в класс Staff, поэтому ToLower нужно сделать только один раз

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

4) используйте таймер, чтобы ввести задержку между тем, когда пользователь вводит и когда вы начинаете поиск. если они набирают несколько символов быстро, вы также можете подождать, пока они не сделают паузу в течение половины секунды

5) Проверьте нажатую клавишу. Если NaN затем не проверяет свойства int.

Ответ 2

Вы можете добавить частную собственность SearchTerm в объект Staff, который (FirstName + LastName + MiddleName + StaffID + CostCentre).ToLower(), и вместо этого выполнить проверку Contains(). Это помешало бы вам делать ToLower() для каждой строки каждый раз и уменьшать количество проверок Contains() от 5 до 1.

Ответ 3

Вы можете попробовать реализовать trie или "prefix-tree":

http://en.wikipedia.org/wiki/Trie

Это позволит вам искать текст, начинающийся со значения.

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

Удостоверьтесь, что все ваши данные ToLower при вставке в вашу структуру, поэтому при выполнении поиска вам не нужно делать нечувствительные к регистру сравнения.

Ответ 4

Увидев, что вы сделали (в основном из комментариев по запросу @mikel), похоже, что вы туда попали. Одно из предложений, которое я не видел, которое может предложить увеличение скорости, - это сравнение с помощью StringComparison.OrdinalIgnoreCase. В вашем случае это означало бы замену

if (stf.LastName.ToLower().Contains(s))
  return true;

с

if (stf.LastName.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0)
  return true;

Ниже приведена ссылка MSDN, в которой обсуждаются быстрые сравнения строк.

Ответ 5

using System;
using System.Text.RegularExpressions;
namespace PatternMatching1
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                Console.WriteLine("Please enter the first string.");
                string str = Console.ReadLine(); ;
                string replacestr = Regex.Replace(str, "[^a-zA-Z0-9_]+", " ");



                Console.WriteLine("Please enter the second string.");
                string str1 = Console.ReadLine(); ;
                string replacestr1 = Regex.Replace(str1, "[^a-zA-Z0-9_]+", " ");



                if (replacestr.Length == replacestr1.Length)
                {
                    char[] cFirst = replacestr.ToLower().ToCharArray();
                    char[] cSecond = replacestr1.ToLower().ToCharArray();

                    Array.Sort<char>(cFirst);
                    Array.Sort<char>(cSecond);

                    if ((new string(cFirst)).Equals((new string(cSecond))))
                        Console.WriteLine("Both String Same");
                    else
                        Console.WriteLine("Both String Not Same");
                }
                else
                    Console.WriteLine("oopsss, something going wrong !!!! try again");
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }
            Console.Read();
        }
    }
}

`