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

Question

У меня есть список из примерно 10000 сотрудников в 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 сотрудников накладные расходы, казалось, отбирали большую часть выгоды. Кроме того, было множество других ошибок, например, при поиске «John», пользователь сначала нажимает «J», что приводит в порядок потоки, но когда пользователь нажимает «o», другой набор помещается в буфер до того, как первая партия имела шанс вернуть свои результаты. В большинстве случаев результаты возвращаются в беспорядочном порядке, и случаются всякие неприятные вещи.

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

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

---

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

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

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

Answer 1

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

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

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

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

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

Answer 2

Вы можете попробовать реализовать trie или "префиксное дерево":

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

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

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

Убедитесь, что вы ToLower все свои данные вставили в свою структуру, чтобы вам не приходилось делать сравнения без учета регистра при выполнении поиска.

Answer 3

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

Answer 4

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

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

на

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

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

Answer 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();
        }
    }
}

`