你能加快这个算法吗?C# / C++

本文关键字：C++ 算法 | 更新日期: 2023-09-27 18:34:29

嘿，我一直在做一些事情，现在它变得相对较大(而且很慢(。然而，在近距离测量性能与时间的函数后，我设法查明了瓶颈。

假设我想"排列"字符串"ABC"。我所说的"排列"不完全是一个排列，而是一个遵循此模式的连续子字符串集：

A
AB
ABC
B
BC
C

我必须检查每个子字符串是否包含在另一个字符串 S2 中，所以我做了一些快速的脏文字实现，如下所示：

for (int i = 0; i <= strlen1; i++)
{
   for (int j = 0; j <= strlen2- i; j++)
   {
      sub = str1.Substring(i, j);
      if (str2.Contains(sub)) {do stuff}
      else break;

这最初非常慢，但是一旦我意识到如果第一部分不存在，则无需检查后续部分，这意味着如果sub不包含在str2中，我可以在内部循环上调用break。

好的，这给出了非常快的结果，但计算我的算法复杂性时，我意识到在最坏的情况下这将是 N^4 ？我忘了str.contains((和str.substr((都有自己的复杂性(N或N^2我忘了哪个(。

事实上，我对第二个 for 循环内的人有大量的调用，这使得它的表现相当......好吧 N^4 ~ 说得够多了。

但是，我使用概率

论在数学上计算了它的平均运行时间，以评估随机生成的字符串池中子字符串的增长概率(这是我的基线(，测量概率>何时变为 0.5 (50%(

这显示了不同字符的数量与字符串长度(大致(之间的指数关系，这意味着在我使用算法的情况下，string1 的长度(很可能(永远不会超过 7

因此，平均复杂度为 ~O(N * M(，其中 N 是字符串长度 1，M 是字符串长度 2。由于我已经测试了 N 与常数 M 的函数，我得到了线性增长 ~O(N((与 N^4 相对还不错，嗯？

我做了时间测试并绘制了一个显示近乎完美的线性增长的图表，所以我得到了与我的数学预测相匹配的实际结果(耶！

但是，这没有考虑到string.contains((和string.substring((的成本，这让我想知道是否可以进一步优化？

我也一直在考虑在C++中制作这个，因为我需要相当低级的东西？你们怎么看？我花了很多时间来分析这个希望，我已经把一切都说得足够清楚:)！

你能加快这个算法吗?C# / C++

您的问题被标记为C++和 C#。

C++最佳解决方案是使用迭代器，然后std::search .原始字符串保持不变，并且不会创建任何中间对象。根本不会发生与您的 Substring(( 等效的发生，因此这消除了这部分开销。

这应该达到理论上最好的性能：暴力搜索，测试所有排列，除了迭代器本身之外，没有中间对象构造或破坏，它只是替换了你的两个int索引变量。我想不出任何更快的方法来实现这个基本算法。

您是否正在针对一个字符串测试一个字符串？如果你用另一串字符串测试一堆字符串，那就完全不同了。即使您有将一个字符串与另一个字符串进行比较的最佳算法O(X)，这并不意味着重复 M*N 次，您将获得处理 N 字符串的最佳算法。

当我做一些简单的东西时，我构建了所有 N 个字符串的所有子字符串的字典

Dictionary<string, List<int>>

string是子字符串，int是包含该子字符串的字符串的索引。然后我针对它测试了所有 M 字符串的所有子字符串。速度突然不是O(M*N*X)，而是O(max(M,N)*S)，其中S是一个字符串的子串数。根据 M、N、X、S 的不同，可能会更快。我并不是说子字符串字典是最好的方法，我只是想指出你应该总是尝试看到整个画面。

相关文章：