如何计算字符串中字符或子字符串的出现次数？

Question

我想要统计一个字符串中有多少个斜杠（/）。有几种方法可以做到这一点，但我无法决定哪种方法是最好（或最简单）的。

目前我正在使用类似以下的方法：

string source = "/once/upon/a/time/";
int count = source.Length - source.Replace("/", "").Length;

或者对于长度大于1的字符串：

string haystack = "/once/upon/a/time";
string needle = "/";
int needleCount = ( haystack.Length - haystack.Replace(needle,"").Length ) / needle.Length;

- in.spite

---

我必须说这是一种非常不同的计数方式。我对基准测试结果感到惊讶 :) - naveen

这并不是很不同寻常... 这是在SQL中实现此功能的典型方式：LEN(ColumnToCheck) - LEN(REPLACE(ColumnToCheck,"N",""))。 - Sheridan

事实上，你应该用 "/" 符号来进行除法运算。"Length"翻译为长度。 - Gerard

我可以问一下，您的要求是在"/////"中出现"//"的次数应该是多少呢？是2还是4？ - Les

使用正则表达式可能是最好的方法。 - Adam Higgins

你说的“挖掘正则表达式”是什么意思？我猜你指的是Linq，因为它可能更加晦涩，而且可能没有任何减少开销的好处，对吗？ - barlop

Answer 1

如果你正在使用 .NET 3.5，你可以使用 LINQ 在一行代码中实现这个功能：

int count = source.Count(f => f == '/');

如果您不想使用LINQ，您可以这样做：

int count = source.Split('/').Length - 1;

---

您可能会惊讶地发现，您最初的技术似乎比这两种方法快约30％！我刚刚用“/once/upon/a/time/”进行了一个快速基准测试，结果如下：

您的原始方法 = 12秒
source.Count = 19秒
source.Split = 17秒
foreach (Bobwienholt答案中提供的方法) = 10秒

（这些时间是针对5000万次迭代的，因此您在现实世界中不太可能注意到什么区别。）

- Luke

---

是的，VS隐藏了在字符串类上的LINQ扩展方法。我猜他们认为开发人员不希望所有这些扩展方法都显示在字符串类上。这可能是一个明智的决定。 - Judah Gabriel Himango

这种行为可能是因为VS2010自动在新类文件中包含System.Linq，而VS2008可能不包含。命名空间需要存在才能使用智能感知功能。 - Sprague

请注意，计数和拆分的解决方案仅适用于字符计数。它们不能处理字符串，就像原帖中的解决方案可以处理的那样。 - Peter Lillevold

f == '\' 是关于字符串中的字符，而不是字符串中的字符串。 - Thomas Weller

似乎这是对另一个问题的答案：“如何计算字符串中字符的出现次数？” - Ben Aaronson

Answer 2

string source = "/once/upon/a/time/";
int count = 0;
foreach (char c in source) 
  if (c == '/') count++;

必须比仅使用source.Replace()更快。

- bobwienholt

---

如果您使用 for 而不是 foreach，可能会稍微提高一点点性能，但仅仅只是极小的改善。 - Mark

不，该问题要求计算字符串出现的次数，而不是字符。 - YukiSakura

@Mark 应该会更快 - foreach 会创建一个枚举器对象并在每次迭代时调用一些方法。而且我们只是在谈论微小的改进。 - user3638471

这是在字符串中计算字符数。标题应该是关于在字符串中计算字符串的数量。 - Thomas Weller

@Mark 刚刚用 for 循环测试了一下，实际上比使用 foreach 更慢。可能是因为边界检查的原因吗？（时间为 1.65 秒，而在 500 万次迭代中为 2.05 秒。） - Measurity

虽然问题要求在一个字符串中查找另一个字符串，但是OP实际上只是提供了一个字符的例子。在这种情况下，我认为这个答案仍然是有效的解决方案，因为它展示了一种更好的方式（字符搜索而不是字符串搜索）来解决手头的问题。 - Chad

Answer 3

int count = new Regex(Regex.Escape(needle)).Matches(haystack).Count;

- Yet Another Code Maker

---

有时候你可能希望添加 RegexOptions.IgnoreCase。 - TrueWill

这不是非常低吗？ - Thomas Ayoub

正则表达式的开销不理想，而且“我真的不想为此深入了解正则表达式，是吧？” - Chad

也许不需要使用 Regex.Escape(...)，只需使用 new System.Text.RegularExpressions.Regex(needle).Matches(haystack).Count;。 - barlop

我选择了这个因为它可以搜索字符串，而不仅仅是字符。 - James in Indy

从.NET 7开始，我们拥有了一个快速且无需分配内存的正则表达式解决方案。 - Timo

Answer 4

如果您想要搜索整个字符串，而不仅仅是字符：

src.Select((c, i) => src.Substring(i))
    .Count(sub => sub.StartsWith(target))

读作“对于字符串中的每个字符，以该字符为起点取其后面所有字符组成的子字符串；如果该子字符串以目标字符串开头，则计数。”

- mqp

---

超级慢！在一个HTML页面上尝试了一下，大约需要2分钟，而其他方法只需要2秒钟。虽然答案是正确的，但速度太慢了，无法使用。 - JohnB

同意，太慢了。我非常喜欢 Linq 风格的解决方案，但这个不可行。 - Sprague

请注意，这么慢的原因是因为它会创建n个字符串，从而大约分配n^2/2个字节的空间。 - Peter Crabtree

我的字符串有210000个字符，导致抛出了OutOfMemoryException异常。请帮我翻译。 - ender

现在，有了新的 Span API，你可以更少地浪费时间地完成这个操作。首先准备两个变量，srcSpan = src.AsSpan() 和 targetSpan = target.AsSpan()。然后将 src.Substring(i) 替换为 srcSpan.Slice(i)，将 sub.StartsWith(target) 替换为 sub.StartsWith(targetSpan)。这样可以避免大量的堆分配，但不能避免 O(N^2) 的时间复杂度。 - Timo

Answer 5

LINQ适用于所有集合，由于字符串只是一系列字符的集合，那么这个漂亮的一行代码怎么样：

var count = source.Count(c => c == '/');

请确保你的代码文件顶部包含using System.Linq;，因为.Count是该命名空间中的扩展方法。

- Judah Himango

---

在那里使用var真的值得吗？有没有可能将Count替换为不返回int的内容？ - Whatsit

@Whatsit：你可以只用左手输入“var”，而“int”需要双手输入 ;) - Sean Bright

“int”字母都在主键位上，而“var”不在。呃...等等，我正在使用Dvorak布局。 - Michael Buen

@BDotA 确保你的文件开头有 'using System.Linq;' 这一行。此外，智能提示可能会将 .Count 调用隐藏起来，因为它是一个字符串。即使如此，它也会编译并正常运行。 - Judah Gabriel Himango

我认为，尤其是在变量类型明显的情况下（考虑到简洁性和一致性），应该使用 var。 - EriF89

Answer 6

经过一些研究，我发现Richard Watson的解决方案在大多数情况下是最快的。这是该帖子中每个解决方案的结果表格（除了那些使用正则表达式的，因为它在解析像“test {test”这样的字符串时会引发异常）。

    Name      | Short/char |  Long/char | Short/short| Long/short |  Long/long |
    Inspite   |         134|        1853|          95|        1146|         671|
    LukeH_1   |         346|        4490|         N/A|         N/A|         N/A|
    LukeH_2   |         152|        1569|         197|        2425|        2171|
Bobwienholt   |         230|        3269|         N/A|         N/A|         N/A|
Richard Watson|          33|         298|         146|         737|         543|
StefanosKargas|         N/A|         N/A|         681|       11884|       12486|

在查找短字符串（10-50个字符）中短子字符串（1-5个字符）的出现次数时，最好使用原始算法。

此外，对于多字符子字符串，您应该使用以下代码（基于Richard Watson's的解决方案）

int count = 0, n = 0;

if(substring != "")
{
    while ((n = source.IndexOf(substring, n, StringComparison.InvariantCulture)) != -1)
    {
        n += substring.Length;
        ++count;
    }
}

- tsionyx

---

我本来要添加自己的“低级”解决方案（不使用创建子字符串、替换/拆分或任何Regex/Linq），但你的可能比我的甚至更好（至少更短）。谢谢！ - Dan W

对于正则表达式的解决方案，请添加 Regex.Escape(needle)。 - Thymine

只是为了提醒其他人，需要检查搜索值是否为空，否则你会陷入无限循环。 - WhoIsRich

也许只有我一个人这样想，但对于 source="aaa" substring="aa"，我希望得到的结果是2而不是1。为了“修复”这个问题，把n += substring.Length 改成 n++。 - ytoledano

你可以像这样添加 overlapped 标志以满足你的需求：overlapped=True;.... if(overlapped) {++n;} else {n += substring.Length;} - tsionyx

还进行了一些性能测试，发现对于多字符子字符串，Ben的解决方案使用string.Replace比Richard Watson的解决方案快大约三倍。 - Chronicle

Answer 7

string source = "/once/upon/a/time/";
int count = 0;
int n = 0;

while ((n = source.IndexOf('/', n)) != -1)
{
   n++;
   count++;
}

在我的电脑上，对于5000万次迭代，它比逐个字符的解决方案快大约2秒。

2013版本：

将字符串更改为char[]并遍历。这将为5000万次迭代的总时间再缩短一两秒钟！

char[] testchars = source.ToCharArray();
foreach (char c in testchars)
{
     if (c == '/')
         count++;
}

这种方法更快：

char[] testchars = source.ToCharArray();
int length = testchars.Length;
for (int n = 0; n < length; n++)
{
    if (testchars[n] == '/')
        count++;
}

为了更好的效果，从数组尾部开始迭代到0似乎是最快的，速度比其他方法快大约5%。

int length = testchars.Length;
for (int n = length-1; n >= 0; n--)
{
    if (testchars[n] == '/')
        count++;
}

我在想这可能是为什么，然后进行了谷歌搜索（我记得反向迭代比较快），并偶然发现了这个SO问题，但很让人烦恼的是它已经使用了字符串转字符数组技巧。虽然我认为这种反转技巧在这种情况下是新的。

C#中迭代单个字符的最快方法是什么？

- Richard Watson

---

你可以使用 source.IndexOf('/', n + 1) 替换 n++ 和 while 循环中的括号 :) 另外，使用变量 string word = "/" 代替字符。 - neeKo

嘿，Niko，请查看新的答案。虽然制作可变长度子字符串可能更难。 - Richard Watson

我在某个地方读到过，反向迭代更快，因为将一个值与0进行比较更快。 - reggaeguitar

@RichardWatson ToCharArray 是一项廉价操作吗？ - shitpoet

@shitpoet 是的。如果你看底层代码，它是一个本地调用。public char[] toCharArray() {... System.arraycopy(value, 0, result, 0, value.length); ... } - Richard Watson

Answer 8

这两种方法只适用于单个字符的搜索项...

countOccurences("the", "the answer is the answer");

int countOccurences(string needle, string haystack)
{
    return (haystack.Length - haystack.Replace(needle,"").Length) / needle.Length;
}

可能会发现对于较长的针更好...

但必须有一种更优雅的方式。 :)

- ZombieSheep

---

为了考虑多字符替换。如果没有它，在“the test is the key”中计算“the”将返回6。 - ZombieSheep

经过基准测试和与 string.Split 方法的比较，这种方法的速度大约快了 1.5 倍。值得赞扬。 - Alex from Jitbit

Answer 9

编辑：

source.Split('/').Length-1

- Brian Rudolph

---

这是我的工作。对于使用多个字符作为分隔符的情况，可以使用source.Split(new[]{"//"}, StringSplitOptions.None).Count - 1。请注意，该翻译尽量保持原意，同时使语言更加通俗易懂。 - bzlm

这将在堆上至少执行n个字符串分配，再加上（可能的）一些数组重新调整大小 - 这些都是为了获取计数吗？极其低效，不具有良好的可扩展性，任何重要代码都不应使用。 - Zar Shardan

注意：如果出现Count问题，请使用Length。 - Gray Programmerz

Answer 10

Regex.Matches(input,  Regex.Escape("stringToMatch")).Count

- cederlof

---

如果输入包含正则表达式特殊字符，例如|，那么这是不正确的。需要使用Regex.Escape(input)。 - Esben Skov Pedersen

实际上，需要转义的是 stringToMatch 而不是 input。 - Theodor Zoulias

没错，已经修好了。 - cederlof