Как я разделяю строку строками и включаю разделители с помощью.NET?
Существует много подобных вопросов, но по-видимому никакая идеальная пара, вот почему я спрашиваю.
Я хотел бы разделить случайную строку (например. 123xx456yy789) списком строковых разделителей (например. xx, yy) и включайте разделители в результат (здесь: 123, xx, 456, yy, 789).
Хорошая производительность является хорошей премией. Regex нужно избежать, если это возможно.
Обновление: Я сделал некоторые проверки производительности и сравнил результаты (слишком ленивый для формальной проверки их хотя). Протестированные решения (в произвольном порядке):
Другие решения не были протестированы, потому что или они были подобны другому решению, или они вошли слишком поздно.
Это - тестовый код:
class Program
{
private static readonly List, List>> Functions;
private static readonly List Sources;
private static readonly List> Delimiters;
static Program ()
{
Functions = new List, List>> ();
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 ();
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> ();
Delimiters.Add (new List () { });
Delimiters.Add (new List () { "-" });
Delimiters.Add (new List () { "**" });
Delimiters.Add (new List () { "-", "**" });
}
private class Result
{
public readonly int FuncID;
public readonly int SrcID;
public readonly int DelimID;
public readonly long Milliseconds;
public readonly List Output;
public Result (int funcID, int srcID, int delimID, long milliseconds, List 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 ();
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 преуспевает на больших данных и поражает подобную скорость как non-regex решения.
- Мудрое производительностью лучшее, кажется, версия Guffa в целом, которая должна ожидаться от кода.
- Версия Gabe иногда опускает объект, но я не исследовал это (ошибка?).
Для завершения этой темы я предлагаю использовать Regex, который довольно быстр. Если бы производительность очень важна, я предпочел бы реализацию Guffa.
7 ответов
Несмотря на ваше нежелание использовать regex, он действительно сохраняет разделители, используя группу вместе с методом Regex.Split:
string input = "123xx456yy789";
string pattern = "(xx|yy)";
string[] result = Regex.Split(input, pattern);
Если вы удалите скобки из шаблона, используя только "xx|yy", разделители не сохранятся. Обязательно используйте Regex.Escape для шаблона, если вы используете метасимволы, которые имеют особое значение в regex. К таким символам относятся \, *, +, ?, |, {, [, (,), ^, $,., #. Например, разделитель . должен быть экранирован \. . Учитывая список разделителей, вам нужно "OR" их, используя символ трубы |, и это тоже символ, который экранируется. Чтобы правильно построить шаблон, используйте следующий код (спасибо @gabe за указание):
var delimiters = new List<string> { ".", "xx", "yy" };
string pattern = "(" + String.Join("|", delimiters.Select(d => Regex.Escape(d))
.ToArray())
+ ")";
Круглые скобки конкатенируются, а не включаются в шаблон, поскольку они будут неправильно экранированы для ваших целей.
EDIT: Кроме того, если список разделителей окажется пустым, итоговый шаблон будет иметь неправильный вид (), что приведет к пустым совпадениям. Для предотвращения этого можно использовать проверку разделителей. Учитывая все это, фрагмент выглядит так:
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: пока что решение соответствует разделенным лексемам, которые могут быть подстрокой большей строки. Если разделенная лексема должна быть сопоставлена полностью, а не как часть подстроки, например, в сценарии, где слова в предложении используются в качестве разделителей, то вокруг шаблона должен быть добавлен метасимвол word-boundary \b.
Например, рассмотрим это предложение (да, оно банально): "Добро пожаловать в stackoverflow... где стек никогда не переполняется!"
Если бы разделители были { "стек", "поток" }, то текущее решение разделило бы "stackoverflow" и вернуло бы 3 строки { "стек", "over", "поток" }. Если вам нужно точное совпадение, то единственное место, где это разделится, будет слово "stack" позже в предложении, а не "stackoverflow".
Чтобы добиться точного совпадения, измените шаблон так, чтобы он включал \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*";
Хорошо, извините, может быть, этот:
string source = "123xx456yy789";
foreach (string delimiter in delimiters)
source = source.Replace(delimiter, ";" + delimiter + ";");
string[] parts = source.Split(';');
Вот решение, которое не использует регулярное выражение и не создает больше строк, чем нужно:
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;
}
Некоторое время назад я придумал решение для чего-то похожего. Чтобы эффективно разделить строку, вы можете сохранить список следующего появления каждого разделителя. Таким образом вы минимизируете время, необходимое для поиска каждого разделителя.
Этот алгоритм будет хорошо работать даже с длинной строкой и большим количеством разделителей:
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;
}
}
(С оговорками на случай ошибок, я только что собрал эту версию вместе и не тестировал ее полностью.)
Мое первое сообщение / ответ ... это рекурсивный подход.
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);
}
Семантика будет идентична режиму по умолчанию 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);
}
Наивная реализация
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);
}
}
}