Вопрос по .net, vb.net, c#, stringbuilder, performance – Самый быстрый метод поиска в StringBuilder

13

у меня естьStringBuilder названныйstb_Swap_Tabu используется для хранения названий курсов, Я использую следующий метод, чтобы найти курс:

stb_Swap_Tabu.ToString.Contains("CourseName")

в моем случае производительность является наиболее важной проблемой. Есть ли более быстрый способ?

У вас есть пример того, что эта строка на самом деле? Вы говорите, что в нем хранятся «Имена курсов» - является ли "курс" с или нет; на самом деле означает «курсы», «имена»; предлагает более одного имени - так что, предположительно, это строка с разделителями. В этом случае переключение наList<string> или жеHashSet<string> изindividual имена будут иметь много смысла Marc Gravell♦
Если вам нужно использоватьStringBuilder тогда вам, вероятно, понадобится позвонитьToString каждый раз, когда вы хотите выполнить поиск, что не является хорошей идеей с точки зрения производительности.StringBuilder используется дляbuild strings; по-видимому, если вы строите струны, то у вас уже есть составные части; почему вы не ищите в этих составных частях напрямую? LukeH
HashSet для большего количества струн,list для меньших. Chibueze Opata
StringBuilder возможно, наименее подходящий тип данных для хранения списка доступных для поиска имен. Почему бы не использоватьList<string> вместо этого и использоватьContains методList? Rotem
Я согласен, что вряд ли это то, что нужно здесь. Тем не менее, поиск подстроки в StringBuilder подходит. Jon Hanna

Ваш Ответ

2   ответа
24

Если вам действительно нужно искать один, вы должны написать свой собственный метод.

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

Ниже приведена простая реализация алгоритма Кнута, Морриса и Пратта, который заботится только о совпадениях по порядку (без сворачивания регистра, без сопоставления, связанного с культурой, просто простая кодовая точка для соответствия кодовой точке). Это имеет некоторые начальныеΘ(m) где над головойm длина искомого слова, а затем находит вΘ(n) гдеn это расстояние до искомого слова или длина целого строителя строк, если его там нет. Это превосходит простое сравнение за символом, котороеΘ((n-m+1) m) (КудаO() нотация описывает верхние границы,Θ() описывает как верхнюю, так и нижнюю границы).

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

public static class StringBuilderSearching
{
  public static bool Contains(this StringBuilder haystack, string needle)
  {
    return haystack.IndexOf(needle) != -1;
  }
  public static int IndexOf(this StringBuilder haystack, string needle)
  {
    if(haystack == null || needle == null)
      throw new ArgumentNullException();
    if(needle.Length == 0)
      return 0;//empty strings are everywhere!
    if(needle.Length == 1)//can't beat just spinning through for it
    {
      char c = needle[0];
      for(int idx = 0; idx != haystack.Length; ++idx)
        if(haystack[idx] == c)
          return idx;
      return -1;
    }
    int m = 0;
    int i = 0;
    int[] T = KMPTable(needle);
    while(m + i < haystack.Length)
    {
      if(needle[i] == haystack[m + i])
      {
        if(i == needle.Length - 1)
          return m == needle.Length ? -1 : m;//match -1 = failure to find conventional in .NET
        ++i;
      }
      else
      {
        m = m + i - T[i];
        i = T[i] > -1 ? T[i] : 0;
      }
    }
    return -1;
  }      
  private static int[] KMPTable(string sought)
  {
    int[] table = new int[sought.Length];
    int pos = 2;
    int cnd = 0;
    table[0] = -1;
    table[1] = 0;
    while(pos < table.Length)
      if(sought[pos - 1] == sought[cnd])
        table[pos++] = ++cnd;
      else if(cnd > 0)
        cnd = table[cnd];
      else
        table[pos++] = 0;
    return table;
  }
}
Разве это не должно быть простоreturn m;неreturn m == needle.Length ? -1 : m;?
@JuriRobl этот бит должен соответствовать соглашению .NET -1 для not found. Хотя я не знаю, что является причиной этой ошибки, я посмотрю позже, если у меня будет шанс.
Точно так же, как упомянул @JonHanna, у меня есть веская причина иметь строителя, поэтому мой заголовок вопроса таков:Fastest search method in StringBuilder, В результате моего теста ответ, предоставленный @JonHanna после некоторых изменений, оказался на 28% лучше, чем при использованииConatins, Я постараюсь сделать абстрагированный код и поделиться им здесь. Alaa
Этот код не работает для меня с haystack & quot; abcde & quot; и needle & quot; cd & quot ;, он возвращает false.
Не имеет смысла, что StringBuilder имеетReplace функция, которая неизбежно должна искать строку и даже принимает начальный и конечный индексы, но не обеспечиваетindexOf функция. Почему нам осталось повторить то, что уже было сделано?
1

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

Private Function valueFormatter(ByVal value As String) As String
        ' This will correct any formatting to make the value valid for a CSV format
        '
        ' 1) Any value that as a , in it then it must be wrapped in a " i.e. Hello,World -> "Hello,World"
        ' 2) In order to escape a " in the value add a " i.e. Hello"World -> Hello""World
        ' 3) if the value has a " in it then it must also be wrapped in a " i.e. "Hello World" -> ""Hello World"" -> """Hello World"""
        ' 
        ' VB NOTATAION 
        ' " -> """"
        ' "" -> """"""

        If value.Contains(",") Or value.Contains("""") Then
            Dim sb As New StringBuilder(value)
            If value.Contains("""") Then sb.Replace("""", """""")
            sb.Insert(0, """").Append("""")
            Return sb.ToString
        Else
            Return value
        End If
    End Function

Похожие вопросы