在一个字符串中获取某个字符的所有索引的更高效方法

Question

不要通过循环每个字符来确定它是否是你想要的那个，然后将其索引添加到列表中，如下所示：

     var foundIndexes = new List<int>();
     for (int i = 0; i < myStr.Length; i++)
     {
        if (myStr[i] == 'a')
           foundIndexes.Add(i);
     }

- Mark W

---

没有更快的方法来查找一个字符；然而，如果你正在搜索更长的模式，不同的算法存在，允许你一次跳过多个字符，比如Boyer-Moore字符串搜索算法。 - Olivier Jacot-Descombes

Answer 1

你可以使用 String.IndexOf，请参考下面的示例：

    string s = "abcabcabcabcabc";
    var foundIndexes = new List<int>();

    long t1 = DateTime.Now.Ticks;
    for (int i = s.IndexOf('a'); i > -1; i = s.IndexOf('a', i + 1))
        {
         // for loop end when i=-1 ('a' not found)
                foundIndexes.Add(i);
        }
    long t2 = DateTime.Now.Ticks - t1; // read this value to see the run time

- m.zam

---

虽然我同意@cdhowie的评论，但如果为了追求最后一点性能而奋斗，这是另一个尝试的选择。我不确定JIted for是否总是会删除在IndexOf中不存在的边界检查，但对于稀有字符的长字符串可能会更快。 - Alexei Levenkov

你的评论是基于假设的。我已经测试过了。我的解决方案更快。测试一下就会相信。比较两个解决方案之前和之后的滴答值。我已经编辑了我的答案，向你展示我如何测试它。 - m.zam

+1 非常好，即使您正在搜索字符串而不是单个字符，这也很有用。 - Fabio Marcolini

只是问一下，如果不是为了每个字符都调用IndexOf而是迭代字符串中的每个字符，会不会更快更直接？ - CyberFox

我只想指出使用StopWatch而不是在“基准测试”方面减去滴答声。 - Gonzo345

Answer 2

我使用以下扩展方法来yield所有结果:

public static IEnumerable<int> AllIndexesOf(this string str, string searchstring)
{
    int minIndex = str.IndexOf(searchstring);
    while (minIndex != -1)
    {
        yield return minIndex;
        minIndex = str.IndexOf(searchstring, minIndex + searchstring.Length);
    }
}

用法：

IEnumerable<int> result = "foobar".AllIndexesOf("o"); // [1,2]

边缘情况的注意事项：这是一种适用于一个或多个字符的字符串方法。在"fooo".AllIndexesOf("oo")的情况下，结果只是1https://dotnetfiddle.net/CPC7D2

- fubo

---

嘿fubo。在+ searchstring.Length的位置上使用+ 1可能更正确。考虑一下AllIndexesOf("11111", "11")的例子。它返回(0, 2)，因为它从原始索引0处的11末尾开始搜索，然后从索引2开始搜索。实际答案应该是(0, 1, 2, 3)，因为可以从所有这些索引中找到11。这是我对你的.NET Fiddle的分支，演示了更新后的代码，可以生成“正确”的答案，具体取决于你的世界观：https://dotnetfiddle.net/RGQWd8。 - Aaron Newton

@AaronNewton 对，那是我的附注，哪个结果是正确的取决于需求。 - fubo

Answer 3

怎么样？

string xx = "The quick brown fox jumps over the lazy dog";

char search = 'f';

var result = xx.Select((b, i) => b.Equals(search) ? i : -1).Where(i => i != -1);

- Nikhil Agrawal

---

算法上几乎没有更高的效率，你只是使用LINQ来做同样的事情。除非有一些LINQ魔法将两个搜索组合起来（我对LINQ优化不是很熟悉），否则你实际上引入了第二个循环并使性能变差。 - Ed S.

@EdS：LINQ中没有延迟执行。实际上，它只是一个单一的循环工作。 - Nikhil Agrawal

无论是单循环还是不循环，它都不会更快，只会使本应简单的代码变得复杂。 - Ed S.

刚在我的并行算法中进行了测试：http://stackoverflow.com/questions/12765329/plinq-query-need-to-know-how-many-iterations-performed，速度慢得多。 - Mark W

使用LINQ几乎总是比使用命令式方式慢。LINQ-to-objects依赖于委托，它们实际上是函数指针。对于源可枚举集合中的每个元素，都会调用该指针。C#编译器、JIT或主机CPU无法优化函数指针调用。在实际应用中，相比内联代码，它们要慢得多。(我并不是说永远不要使用LINQ，但请注意，你正在为可读性和可维护性而牺牲性能——假设你的LINQ代码是易读且易维护的。) - cdhowie

发布一句话引发了一场风波。任何合格的.NET程序员都知道使用linq会带来性能上的权衡，就像@cdhowie所说的那样。由于我的项目对性能要求更高，因此我不会使用这个解决方案。但对于一次性操作来说，这个方案是完美的。感谢发布者为我们提供了如此方便的内容。 - CyberFox

Answer 4

直接使用原始迭代方式，这是最优化的方法。除非任务比较复杂，你不需要寻找更好的优化解决方案...

因此我建议继续使用：

var foundIndexes = new List<int>();

for (int i = 0; i < myStr.Length; i++)

     if (myStr[i] == 'a') foundIndexes.Add(i);

- loxxy

Answer 5

如果字符串很短，一次搜索并计算该字符出现的次数可能更有效，然后分配一个该大小的数组，并再次搜索字符串，记录下标到数组中。这将跳过任何列表重新分配。

关键是字符串的长度和字符出现的次数。如果字符串很长且字符出现次数较少，则搜索一次并将索引附加到List<int>中将更快。如果字符出现多次，则搜索字符串两次（一次计数，一次填充数组）可能更快。转折点在哪里完全取决于许多无法从您的问题中推断出的因素。

如果您需要搜索字符串以获取多个不同字符并单独获取这些字符的索引列表，则可能更快地一次搜索字符串并构建Dictionary<char,List<int>>（或使用偏移量从\0作为外部数组中的索引的List<List<int>>）。

最终，应该对应用程序进行基准测试以找出瓶颈。通常，我们认为会执行缓慢的代码实际上非常快速，而我们大部分时间都在阻塞I/O或用户输入。

- cdhowie

---

+1，我也在写类似的东西，但是我没有时间运行任何基准测试，所以我决定不这样做。 - Ed S.

Howie，如果你不介意的话，你会用什么来对这个应用程序进行基准测试？我没有高级版的VS，所以无法使用分析工具，只能使用专业版。 - Mark W

Answer 6

    public static List<int> GetSubstringLocations(string text, string searchsequence)
    {
        try
        {
            List<int> foundIndexes = new List<int> { };

            int i = 0;
            while (i < text.Length)
            {
                int cindex = text.IndexOf(searchsequence, i);

                if (cindex >= 0)
                {
                    foundIndexes.Add(cindex);
                    i = cindex;
                }

                i++;

            }

            return foundIndexes;
        }
        catch (Exception ex) { }
        return new List<int> { };
    }

- ArnaldoRivera

Answer 7

public static String[] Split(this string s,char c = '\t')
    {
        if (s == null) return null;
        var a = new List<int>();
        int i = s.IndexOf(c);
        if (i < 0) return new string[] { s };
        a.Add(i);
        for (i = i+1; i < s.Length; i++) if (s[i] == c) a.Add(i);
        var result = new string[a.Count +1];            
        int startIndex = 0;
        result[0] = s.Remove(a[0]);
        for(i=0;i<a.Count-1;i++)
        {
            result[i + 1] = s.Substring(a[i] + 1, a[i + 1] - a[i] - 1);
        }
        result[a.Count] = s.Substring(a[a.Count - 1] + 1);
        return result;
    }

- Solarev Sergey

Answer 8

另一个代码更少的解决方案：

public static int[] IndexOfAll(this string source, char target)
{
    return source.Select((c, idx) => c == target ? idx : -1).Where(idx => idx != -1).ToArray();
}

使用方法：

var result = "foobar".IndexOfAll('o'); // [1,2]

- iojancode