Получить индекс n-го вхождения строки?
Если я не пропустил очевидный встроенный метод, каков самый быстрый способ получить n- ное вхождение строки в строке?
Я понимаю, что мог бы зациклить метод IndexOf, обновляя его начальный индекс на каждой итерации цикла. Но делать это таким образом мне кажется расточительным.
11 ответов
Это в основном то, что вам нужно сделать - или, по крайней мере, это самое простое решение. Все, что вы "потеряете", это стоимость n вызовов методов - вы не будете проверять ни одного случая дважды, если подумаете об этом. (IndexOf вернется, как только найдет совпадение, и вы продолжите с того места, где оно остановилось.)
Вы действительно могли бы использовать регулярное выражение /((s).*?){n}/ искать n-е вхождение подстроки s,
В C# это может выглядеть так:
public static class StringExtender
{
public static int NthIndexOf(this string target, string value, int n)
{
Match m = Regex.Match(target, "((" + Regex.Escape(value) + ").*?){" + n + "}");
if (m.Success)
return m.Groups[2].Captures[n - 1].Index;
else
return -1;
}
}
Примечание: я добавил Regex.Escape к оригинальному решению, чтобы позволить поиск символов, которые имеют особое значение для regex engine.
Это в основном то, что вам нужно сделать - или, по крайней мере, это самое простое решение. Все, что вы "потеряете", это стоимость n вызовов методов - вы не будете проверять ни одного случая дважды, если подумаете об этом. (IndexOf вернется, как только найдет совпадение, и вы продолжите с того места, где оно остановилось.)
Вот рекурсивная реализация (вышеупомянутой идеи) как метод расширения, имитирующий формат метода (ов) фреймворка:
public static int IndexOfNth(this string input,
string value, int startIndex, int nth)
{
if (nth < 1)
throw new NotSupportedException("Param 'nth' must be greater than 0!");
if (nth == 1)
return input.IndexOf(value, startIndex);
var idx = input.IndexOf(value, startIndex);
if (idx == -1)
return -1;
return input.IndexOfNth(value, idx + 1, --nth);
}
Кроме того, вот некоторые (MBUnit) модульные тесты, которые могут вам помочь (чтобы доказать, что это правильно):
using System;
using MbUnit.Framework;
namespace IndexOfNthTest
{
[TestFixture]
public class Tests
{
//has 4 instances of the
private const string Input = "TestTest";
private const string Token = "Test";
/* Test for 0th index */
[Test]
public void TestZero()
{
Assert.Throws<NotSupportedException>(
() => Input.IndexOfNth(Token, 0, 0));
}
/* Test the two standard cases (1st and 2nd) */
[Test]
public void TestFirst()
{
Assert.AreEqual(0, Input.IndexOfNth("Test", 0, 1));
}
[Test]
public void TestSecond()
{
Assert.AreEqual(4, Input.IndexOfNth("Test", 0, 2));
}
/* Test the 'out of bounds' case */
[Test]
public void TestThird()
{
Assert.AreEqual(-1, Input.IndexOfNth("Test", 0, 3));
}
/* Test the offset case (in and out of bounds) */
[Test]
public void TestFirstWithOneOffset()
{
Assert.AreEqual(4, Input.IndexOfNth("Test", 4, 1));
}
[Test]
public void TestFirstWithTwoOffsets()
{
Assert.AreEqual(-1, Input.IndexOfNth("Test", 8, 1));
}
}
}
private int IndexOfOccurence(string s, string match, int occurence)
{
int i = 1;
int index = 0;
while (i <= occurence && (index = s.IndexOf(match, index + 1)) != -1)
{
if (i == occurence)
return index;
i++;
}
return -1;
}
или в C# с методами расширения
public static int IndexOfOccurence(this string s, string match, int occurence)
{
int i = 1;
int index = 0;
while (i <= occurence && (index = s.IndexOf(match, index + 1)) != -1)
{
if (i == occurence)
return index;
i++;
}
return -1;
}
После некоторого бенчмаркинга это кажется самым простым и эффективным решением.
public static int IndexOfNthSB(string input,
char value, int startIndex, int nth)
{
if (nth < 1)
throw new NotSupportedException("Param 'nth' must be greater than 0!");
var nResult = 0;
for (int i = startIndex; i < input.Length; i++)
{
if (input[i] == value)
nResult++;
if (nResult == nth)
return i;
}
return -1;
}
Вот и я снова! Еще один тестовый ответ от вашего покорного слуги :-) Еще раз, основанный на фантастическом пакете BenchmarkDotNet (если вы серьезно относитесь к тестированию кода dotnet, пожалуйста, используйте этот пакет).
Мотивация для этого поста двоякая: PeteT (который спрашивал об этом изначально) задавался вопросом, что кажется расточительным использоватьString.IndexOfменяяstartIndexпараметр в цикле для поиска n-го вхождения символа, при этом, по сути, это самый быстрый метод, и потому, что в некоторых ответах используются регулярные выражения, которые на порядок медленнее (и не добавляют никаких преимуществ, на мой взгляд, даже не читаемость , в данном конкретном случае).
Вот код, который я использовал в своей библиотеке расширений строк (это не новый ответ на этот вопрос, поскольку другие уже разместили здесь семантически идентичный код, я не беру на себя ответственность за это). Это самый быстрый способ (даже, возможно, включая небезопасные варианты — об этом позже):
public static int IndexOfNth(this string str, char ch, int nth, int startIndex = 0) {
if (str == null)
throw new ArgumentNullException("str");
var idx = str.IndexOf(ch, startIndex);
while (idx >= 0 && --nth > 0)
idx = str.IndexOf(ch, startIndex + idx + 1);
return idx;
}
Я сравнил этот код с двумя другими методами, и результаты следующие:
Тестовыми методами были:
[Benchmark]
public int FindNthRegex() {
Match m = Regex.Match(text, "((" + Regex.Escape("z") + ").*?){" + Nth + "}");
return (m.Success)
? m.Groups[2].Captures[Nth - 1].Index
: -1;
}
[Benchmark]
public int FindNthCharByChar() {
var occurrence = 0;
for (int i = 0; i < text.Length; i++) {
if (text[i] == 'z')
occurrence++;
if (Nth == occurrence)
return i;
}
return -1;
}
[Benchmark]
public int FindNthIndexOfStartIdx() {
var idx = text.IndexOf('z', 0);
var nth = Nth;
while (idx >= 0 && --nth > 0)
idx = text.IndexOf('z', idx + 1);
return idx;
}
The FindNthRegexметод является более медленным из группы, занимая на порядок (или два) больше времени, чем самый быстрый. петли над каждымcharв строке и считает каждое совпадение, пока не найдет n-е вхождение.FindNthIndexOfStartIdxиспользует метод, предложенный автором этого вопроса, который действительно является тем же самым, который я использовал целую вечность для достижения этой цели, и он является самым быстрым из всех.
Почему это намного быстрее, чемFindNthByChar? Это связано с тем, что Microsoft приложила большие усилия, чтобы максимально быстро манипулировать строками в среде dotnet. И они добились этого! Они проделали потрясающую работу! Я провел более глубокое исследование манипуляций со строками в dotnet в статье CodeProject, в которой пытался найти самый быстрый метод удаления всех пробелов из строки:
Самый быстрый способ удалить все пробелы из строк в .NET
Там вы узнаете, почему манипуляции со строками в dotnet выполняются так быстро, и почему почти бесполезно пытаться выжать больше скорости, написав собственные версии кода манипуляций со строками в фреймворке (например,string.IndexOf,string.Split,string.Replace, и т. д.)
Полный тестовый код, который я использовал, выглядит следующим образом (это консольная программа dotnet6):
ОБНОВЛЕНИЕ: добавлено два методаFindNthCharByCharInSpanиFindNthCharRecursive(и сейчасFindNthByLinq).
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Text;
using System.Text.RegularExpressions;
var summary = BenchmarkRunner.Run<BenchmarkFindNthChar>();
public class BenchmarkFindNthChar
{
const string BaseText = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
[Params(100, 1000)]
public int BaseTextRepeatCount { get; set; }
[Params(500)]
public int Nth { get; set; }
private string text;
[GlobalSetup]
public void BuildTestData() {
var sb = new StringBuilder();
for (int i = 0; i < BaseTextRepeatCount; i++)
sb.AppendLine(BaseText);
text = sb.ToString();
}
[Benchmark]
public int FindNthRegex() {
Match m = Regex.Match(text, "((" + Regex.Escape("z") + ").*?){" + Nth + "}");
return (m.Success)
? m.Groups[2].Captures[Nth - 1].Index
: -1;
}
[Benchmark]
public int FindNthCharByChar() {
var occurrence = 0;
for (int i = 0; i < text.Length; i++) {
if (text[i] == 'z')
occurrence++;
if (Nth == occurrence)
return i;
}
return -1;
}
[Benchmark]
public int FindNthIndexOfStartIdx() {
var idx = text.IndexOf('z', 0);
var nth = Nth;
while (idx >= 0 && --nth > 0)
idx = text.IndexOf('z', idx + 1);
return idx;
}
[Benchmark]
public int FindNthCharByCharInSpan() {
var span = text.AsSpan();
var occurrence = 0;
for (int i = 0; i < span.Length; i++) {
if (span[i] == 'z')
occurrence++;
if (Nth == occurrence)
return i;
}
return -1;
}
[Benchmark]
public int FindNthCharRecursive() => IndexOfNth(text, "z", 0, Nth);
public static int IndexOfNth(string input, string value, int startIndex, int nth) {
if (nth == 1)
return input.IndexOf(value, startIndex);
var idx = input.IndexOf(value, startIndex);
if (idx == -1)
return -1;
return IndexOfNth(input, value, idx + 1, --nth);
}
[Benchmark]
public int FindNthByLinq() {
var items = text.Select((c, i) => (c, i)).Where(t => t.c == 'z');
return (items.Count() > Nth - 1)
? items.ElementAt(Nth - 1).i
: -1;
}
}
ОБНОВЛЕНИЕ 2. Ниже приведены новые результаты тестов (с тестом на основе Linq):
Решение на основе Linq только лучше, чем рекурсивный метод, но хорошо иметь его здесь для полноты картины.
Может быть, было бы неплохо поработать с String.Split() Метод и проверьте, находится ли запрошенное вхождение в массиве, если вам нужен не индекс, а значение в индексе
Или что-то вроде этого с циклом do while
private static int OrdinalIndexOf(string str, string substr, int n)
{
int pos = -1;
do
{
pos = str.IndexOf(substr, pos + 1);
} while (n-- > 0 && pos != -1);
return pos;
}
System.ValueTuple ftw:
var index = line.Select((x, i) => (x, i)).Where(x => x.Item1 == '"').ElementAt(5).Item2;
написание функции от этого является домашним заданием
Ответ Тода может быть несколько упрощен.
using System;
static class MainClass {
private static int IndexOfNth(this string target, string substring,
int seqNr, int startIdx = 0)
{
if (seqNr < 1)
{
throw new IndexOutOfRangeException("Parameter 'nth' must be greater than 0.");
}
var idx = target.IndexOf(substring, startIdx);
if (seqNr == 1) { return idx; }
return target.IndexOfNth(substring, --seqNr, ++idx); // skip
}
static void Main () {
Console.WriteLine ("abcbcbcd".IndexOfNth("bc", 2));
}
}
Выход
3
Это может сделать это:
Console.WriteLine(str.IndexOf((@"\")+2)+1);