Как разделить строку на строки и включить разделители с помощью .NET? - PullRequest
32 голосов
/ 21 марта 2010

Есть много похожих вопросов, но, видимо, нет идеального соответствия, поэтому я и задаю.

Я хотел бы разбить случайную строку (например, 123xx456yy789) на список разделителей строк (например, xx, yy) и включить в результат разделители (здесь: 123, xx, 456, yy, 789).

Хорошая производительность - хороший бонус. По возможности следует избегать регулярных выражений.

Обновление : я провел некоторые проверки производительности и сравнил результаты (хотя и ленив, чтобы их формально проверить). Проверенные решения (в случайном порядке):

  1. Гейб
  2. Guffa
  3. Mafu
  4. Regex

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

Это тестовый код:

class Program
{
    private static readonly List<Func<string, List<string>, List<string>>> Functions;
    private static readonly List<string> Sources;
    private static readonly List<List<string>> Delimiters;

    static Program ()
    {
        Functions = new List<Func<string, List<string>, List<string>>> ();
        Functions.Add ((s, l) => s.SplitIncludeDelimiters_Gabe (l).ToList ());
        Functions.Add ((s, l) => s.SplitIncludeDelimiters_Guffa (l).ToList ());
        Functions.Add ((s, l) => s.SplitIncludeDelimiters_Naive (l).ToList ());
        Functions.Add ((s, l) => s.SplitIncludeDelimiters_Regex (l).ToList ());

        Sources = new List<string> ();
        Sources.Add ("");
        Sources.Add (Guid.NewGuid ().ToString ());

        string str = "";
        for (int outer = 0; outer < 10; outer++) {
            for (int i = 0; i < 10; i++) {
                str += i + "**" + DateTime.UtcNow.Ticks;
            }
            str += "-";
        }
        Sources.Add (str);

        Delimiters = new List<List<string>> ();
        Delimiters.Add (new List<string> () { });
        Delimiters.Add (new List<string> () { "-" });
        Delimiters.Add (new List<string> () { "**" });
        Delimiters.Add (new List<string> () { "-", "**" });
    }

    private class Result
    {
        public readonly int FuncID;
        public readonly int SrcID;
        public readonly int DelimID;
        public readonly long Milliseconds;
        public readonly List<string> Output;

        public Result (int funcID, int srcID, int delimID, long milliseconds, List<string> output)
        {
            FuncID = funcID;
            SrcID = srcID;
            DelimID = delimID;
            Milliseconds = milliseconds;
            Output = output;
        }

        public void Print ()
        {
            Console.WriteLine ("S " + SrcID + "\tD " + DelimID + "\tF " + FuncID + "\t" + Milliseconds + "ms");
            Console.WriteLine (Output.Count + "\t" + string.Join (" ", Output.Take (10).Select (x => x.Length < 15 ? x : x.Substring (0, 15) + "...").ToArray ()));
        }
    }

    static void Main (string[] args)
    {
        var results = new List<Result> ();

        for (int srcID = 0; srcID < 3; srcID++) {
            for (int delimID = 0; delimID < 4; delimID++) {
                for (int funcId = 3; funcId >= 0; funcId--) { // i tried various orders in my tests
                    Stopwatch sw = new Stopwatch ();
                    sw.Start ();

                    var func = Functions[funcId];
                    var src = Sources[srcID];
                    var del = Delimiters[delimID];

                    for (int i = 0; i < 10000; i++) {
                        func (src, del);
                    }
                    var list = func (src, del);
                    sw.Stop ();

                    var res = new Result (funcId, srcID, delimID, sw.ElapsedMilliseconds, list);
                    results.Add (res);
                    res.Print ();
                }
            }
        }
    }
}

Как видите, это был действительно быстрый и грязный тест, но я запускал тест несколько раз и с другим порядком, и результат всегда был очень последовательным. Измеренные временные рамки находятся в диапазоне от миллисекунд до секунд для больших наборов данных. Я проигнорировал значения в диапазоне низких миллисекунд в моей следующей оценке, потому что они казались незначительными на практике. Вот вывод на мою коробку:

S 0     D 0     F 3     11ms
1
S 0     D 0     F 2     7ms
1
S 0     D 0     F 1     6ms
1
S 0     D 0     F 0     4ms
0
S 0     D 1     F 3     28ms
1
S 0     D 1     F 2     8ms
1
S 0     D 1     F 1     7ms
1
S 0     D 1     F 0     3ms
0
S 0     D 2     F 3     30ms
1
S 0     D 2     F 2     8ms
1
S 0     D 2     F 1     6ms
1
S 0     D 2     F 0     3ms
0
S 0     D 3     F 3     30ms
1
S 0     D 3     F 2     10ms
1
S 0     D 3     F 1     8ms
1
S 0     D 3     F 0     3ms
0
S 1     D 0     F 3     9ms
1       9e5282ec-e2a2-4...
S 1     D 0     F 2     6ms
1       9e5282ec-e2a2-4...
S 1     D 0     F 1     5ms
1       9e5282ec-e2a2-4...
S 1     D 0     F 0     5ms
1       9e5282ec-e2a2-4...
S 1     D 1     F 3     63ms
9       9e5282ec - e2a2 - 4265 - 8276 - 6dbb50fdae37
S 1     D 1     F 2     37ms
9       9e5282ec - e2a2 - 4265 - 8276 - 6dbb50fdae37
S 1     D 1     F 1     29ms
9       9e5282ec - e2a2 - 4265 - 8276 - 6dbb50fdae37
S 1     D 1     F 0     22ms
9       9e5282ec - e2a2 - 4265 - 8276 - 6dbb50fdae37
S 1     D 2     F 3     30ms
1       9e5282ec-e2a2-4...
S 1     D 2     F 2     10ms
1       9e5282ec-e2a2-4...
S 1     D 2     F 1     10ms
1       9e5282ec-e2a2-4...
S 1     D 2     F 0     12ms
1       9e5282ec-e2a2-4...
S 1     D 3     F 3     73ms
9       9e5282ec - e2a2 - 4265 - 8276 - 6dbb50fdae37
S 1     D 3     F 2     40ms
9       9e5282ec - e2a2 - 4265 - 8276 - 6dbb50fdae37
S 1     D 3     F 1     33ms
9       9e5282ec - e2a2 - 4265 - 8276 - 6dbb50fdae37
S 1     D 3     F 0     30ms
9       9e5282ec - e2a2 - 4265 - 8276 - 6dbb50fdae37
S 2     D 0     F 3     10ms
1       0**634226552821...
S 2     D 0     F 2     109ms
1       0**634226552821...
S 2     D 0     F 1     5ms
1       0**634226552821...
S 2     D 0     F 0     127ms
1       0**634226552821...
S 2     D 1     F 3     184ms
21      0**634226552821... - 0**634226552821... - 0**634226552821... - 0**634226
552821... - 0**634226552821... -
S 2     D 1     F 2     364ms
21      0**634226552821... - 0**634226552821... - 0**634226552821... - 0**634226
552821... - 0**634226552821... -
S 2     D 1     F 1     134ms
21      0**634226552821... - 0**634226552821... - 0**634226552821... - 0**634226
552821... - 0**634226552821... -
S 2     D 1     F 0     517ms
20      0**634226552821... - 0**634226552821... - 0**634226552821... - 0**634226
552821... - 0**634226552821... -
S 2     D 2     F 3     688ms
201     0 ** 634226552821217... ** 634226552821217... ** 634226552821217... ** 6
34226552821217... **
S 2     D 2     F 2     2404ms
201     0 ** 634226552821217... ** 634226552821217... ** 634226552821217... ** 6
34226552821217... **
S 2     D 2     F 1     874ms
201     0 ** 634226552821217... ** 634226552821217... ** 634226552821217... ** 6
34226552821217... **
S 2     D 2     F 0     717ms
201     0 ** 634226552821217... ** 634226552821217... ** 634226552821217... ** 6
34226552821217... **
S 2     D 3     F 3     1205ms
221     0 ** 634226552821217... ** 634226552821217... ** 634226552821217... ** 6
34226552821217... **
S 2     D 3     F 2     3471ms
221     0 ** 634226552821217... ** 634226552821217... ** 634226552821217... ** 6
34226552821217... **
S 2     D 3     F 1     1008ms
221     0 ** 634226552821217... ** 634226552821217... ** 634226552821217... ** 6
34226552821217... **
S 2     D 3     F 0     1095ms
220     0 ** 634226552821217... ** 634226552821217... ** 634226552821217... ** 6
34226552821217... **

Я сравнил результаты, и вот что я нашел:

  • Все 4 функции достаточно быстры для обычного использования.
  • Наивная версия (то, что я написал изначально) является худшей с точки зрения времени вычислений.
  • Regex немного медленен для небольших наборов данных (вероятно, из-за издержек инициализации).
  • Regex хорошо справляется с большими данными и достигает той же скорости, что и решения без регулярных выражений.
  • По производительности лучше всего выглядит версия Guffa, чего и следовало ожидать от кода.
  • В версии Гейба иногда отсутствует элемент, но я не исследовал это (ошибка?).

Чтобы завершить эту тему, я предлагаю использовать Regex, который достаточно быстр. Если производительность критична, я бы предпочел реализацию Guffa.

Ответы [ 7 ]

43 голосов
/ 21 марта 2010

Несмотря на ваше нежелание использовать регулярные выражения, на самом деле он прекрасно сохраняет разделители, используя группу вместе с методом Regex.Split:

string input = "123xx456yy789";
string pattern = "(xx|yy)";
string[] result = Regex.Split(input, pattern);

Если вы удалите скобки из шаблона, используя только "xx|yy", разделители не сохранятся. Обязательно используйте Regex.Escape в шаблоне, если вы используете метасимволы, которые имеют специальное значение в регулярном выражении. Символы включают \, *, +, ?, |, {, [, (,), ^, $,., #. Например, разделитель . должен быть экранирован \.. Имея список разделителей, вам нужно «ИЛИ» использовать символ «|», и это тоже символ, который экранируется. Чтобы правильно построить шаблон, используйте следующий код (спасибо @gabe за это):

var delimiters = new List<string> { ".", "xx", "yy" };
string pattern = "(" + String.Join("|", delimiters.Select(d => Regex.Escape(d))
                                                  .ToArray())
                  + ")";

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

РЕДАКТИРОВАТЬ: Кроме того, если список delimiters окажется пустым, окончательный шаблон будет неправильно (), и это приведет к пустым совпадениям. Чтобы предотвратить это, можно использовать проверку разделителей. Учитывая все это, фрагмент становится следующим:

string input = "123xx456yy789";
// to reach the else branch set delimiters to new List();
var delimiters = new List<string> { ".", "xx", "yy", "()" }; 
if (delimiters.Count > 0)
{
    string pattern = "("
                     + String.Join("|", delimiters.Select(d => Regex.Escape(d))
                                                  .ToArray())
                     + ")";
    string[] result = Regex.Split(input, pattern);
    foreach (string s in result)
    {
        Console.WriteLine(s);
    }
}
else
{
    // nothing to split
    Console.WriteLine(input);
}

Если вам необходимо сопоставление регистров без учета регистра, используйте параметр RegexOptions.IgnoreCase: Regex.Split(input, pattern, RegexOptions.IgnoreCase)

РЕДАКТИРОВАТЬ # 2: решение до сих пор соответствует разделенным токенам, которые могут быть подстрокой большей строки. Если разделенный токен должен соответствовать полностью, а не части подстроки, например, в сценарии, где слова в предложении используются в качестве разделителей, то вокруг шаблона должен быть добавлен метасимвол границы \b.

Например, рассмотрим это предложение (да, это банально): "Welcome to stackoverflow... where the stack never overflows!"

Если бы разделителями были { "stack", "flow" }, то текущее решение разделило бы "stackoverflow" и вернуло бы 3 строки { "stack", "over", "flow" }. Если вам нужно точное совпадение, то единственное место, где будет разделяться это слово, будет слово «стек» в предложении, а не «стек-поток».

Чтобы добиться точного соответствия, измените шаблон так, чтобы он включал \b, как в \b(delim1|delim2|delimN)\b:

string pattern = @"\b("
                + String.Join("|", delimiters.Select(d => Regex.Escape(d)))
                + @")\b";

Наконец, если требуется обрезать пробелы до и после разделителей, добавьте \s* вокруг шаблона, как в \s*(delim1|delim2|delimN)\s*. Это может быть объединено с \b следующим образом:

string pattern = @"\s*\b("
                + String.Join("|", delimiters.Select(d => Regex.Escape(d)))
                + @")\b\s*";
12 голосов
/ 21 марта 2010

Хорошо, извините, может быть, это:

    string source = "123xx456yy789";
    foreach (string delimiter in delimiters)
        source = source.Replace(delimiter, ";" + delimiter + ";");
    string[] parts = source.Split(';');
4 голосов
/ 21 марта 2010

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

public static List<string> Split(string searchStr, string[] separators)
{
    List<string> result = new List<string>();
    int length = searchStr.Length;
    int lastMatchEnd = 0;
    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < separators.Length; j++)
        {
            string str = separators[j];
            int sepLen = str.Length;
            if (((searchStr[i] == str[0]) && (sepLen <= (length - i))) && ((sepLen == 1) || (String.CompareOrdinal(searchStr, i, str, 0, sepLen) == 0)))
            {
                result.Add(searchStr.Substring(lastMatchEnd, i - lastMatchEnd));
                result.Add(separators[j]);
                i += sepLen - 1;
                lastMatchEnd = i + 1;
                break;
            }
        }
    }
    if (lastMatchEnd != length)
        result.Add(searchStr.Substring(lastMatchEnd));
    return result;
}
3 голосов
/ 21 марта 2010

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

Этот алгоритм будет хорошо работать даже для длинной строки и большого количества разделителей:

string input = "123xx456yy789";
string[] delimiters = { "xx", "yy" };

int[] nextPosition = delimiters.Select(d => input.IndexOf(d)).ToArray();
List<string> result = new List<string>();
int pos = 0;
while (true) {
  int firstPos = int.MaxValue;
  string delimiter = null;
  for (int i = 0; i < nextPosition.Length; i++) {
    if (nextPosition[i] != -1 && nextPosition[i] < firstPos) {
      firstPos = nextPosition[i];
      delimiter = delimiters[i];
    }
  }
  if (firstPos != int.MaxValue) {
    result.Add(input.Substring(pos, firstPos - pos));
    result.Add(delimiter);
    pos = firstPos + delimiter.Length;
    for (int i = 0; i < nextPosition.Length; i++) {
      if (nextPosition[i] != -1 && nextPosition[i] < pos) {
        nextPosition[i] = input.IndexOf(delimiters[i], pos);
      }
    }
  } else {
    result.Add(input.Substring(pos));
    break;
  }
}

(С оговорками для любых ошибок, я только что собрал эту версию вместе, и я не тестировал ее тщательно.)

2 голосов
/ 21 марта 2010

Наивная реализация

public IEnumerable<string> SplitX (string text, string[] delimiters)
{
    var split = text.Split (delimiters, StringSplitOptions.None);

    foreach (string part in split) {
        yield return part;
        text = text.Substring (part.Length);

        string delim = delimiters.FirstOrDefault (x => text.StartsWith (x));
        if (delim != null) {
            yield return delim;
            text = text.Substring (delim.Length);
        }
    }
}
1 голос
/ 21 марта 2010

Мой первый пост / ответ ... это рекурсивный подход.

    static void Split(string src, string[] delims, ref List<string> final)
    {
        if (src.Length == 0)
            return;

        int endTrimIndex = src.Length;
        foreach (string delim in delims)
        {
            //get the index of the first occurance of this delim
            int indexOfDelim = src.IndexOf(delim);
            //check to see if this delim is at the begining of src
            if (indexOfDelim == 0)
            {
                endTrimIndex = delim.Length;
                break;
            }
            //see if this delim comes before previously searched delims
            else if (indexOfDelim < endTrimIndex && indexOfDelim != -1)
                endTrimIndex = indexOfDelim;
        }
        final.Add(src.Substring(0, endTrimIndex));
        Split(src.Remove(0, endTrimIndex), delims, ref final);
    }
1 голос
/ 21 марта 2010

Это будет иметь семантику, идентичную режиму String.Split по умолчанию (не включая пустые токены).

Это можно сделать быстрее, используя небезопасный код для итерации по исходной строке, хотя для этого требуется, чтобы вы сами написали механизм итерации, а не использовали yield return Он выделяет абсолютный минимум (подстрока на каждый токен без разделителя плюс перечислитель переноса) настолько реалистично, что для повышения производительности вам необходимо:

  • используйте еще более небезопасный код (с помощью 'CompareOrdinal' я эффективно использую)
    • в основном во избежание издержек при поиске символов в строке с буфером символов
  • использовать знание предметной области об источниках ввода или токенах.
    • вы можете быть счастливы отменить нулевую проверку на разделителях
    • вы можете знать, что разделители почти никогда не являются отдельными символами

Код написан как метод расширения

public static IEnumerable<string> SplitWithTokens(
    string str,
    string[] separators)
{
    if (separators == null || separators.Length == 0)
    {
        yield return str;
        yield break;
    }
    int prev = 0;
    for (int i = 0; i < str.Length; i++)
    {
        foreach (var sep in separators)
        {
            if (!string.IsNullOrEmpty(sep))
            {
                if (((str[i] == sep[0]) && 
                          (sep.Length <= (str.Length - i))) 
                     &&
                    ((sep.Length == 1) || 
                    (string.CompareOrdinal(str, i, sep, 0, sep.Length) == 0)))
                {
                    if (i - prev != 0)
                        yield return str.Substring(prev, i - prev);
                    yield return sep;
                    i += sep.Length - 1;
                    prev = i + 1;
                    break;
                }
            }
        }
    }
    if (str.Length - prev > 0)
        yield return str.Substring(prev, str.Length - prev);
}
...