0

如果我理解大 O 表示法，并且相信我此时的理解可能远低于大多数人，那么根据 Keyser 的评论，以下代码行是O(n 2 )，这实际上已经是O(n)操作：

"Hello, World!".ToLower().Contains("a");

因为ToLower()是一个O(n)操作，Contains也是。也许是O(n + n)，再说一次，我的理解仍然模糊。

注意：下面是在Release构建中运行的测试方法列表，并利用Stopwatch该类来跟踪运行时间。

但是，我想让它更快，所以考虑这三种测试方法：

private static void TestToLower(int i)
{
    var s = "".PadRight(i, 'A');

    var sw = Stopwatch.StartNew();
    s.ToLower().Contains('b');
    sw.Stop();

    _tests.Add(string.Format("ToLower{0}", i), sw.ElapsedMilliseconds);
}

private static void TestHashSet(int i)
{
    var s = "".PadRight(i, 'A');

    var sw = Stopwatch.StartNew();
    var lookup = new HashSet<char>(s.ToLower().AsEnumerable());
    lookup.Contains('b');
    sw.Stop();

    _tests.Add(string.Format("ToHashSet{0}", i), sw.ElapsedMilliseconds);
}

private static void TestHashSet2(int i)
{
    var s = "".PadRight(i, 'A');

    var sw = Stopwatch.StartNew();
    var lookup = new HashSet<char>(s.ToLower().ToArray());
    lookup.Contains('b');
    sw.Stop();

    _tests.Add(string.Format("ToHashSet2{0}", i), sw.ElapsedMilliseconds);
}

现在考虑执行这样的操作：

TestToLower(1000000);
TestToLower(2000000);
TestToLower(4000000);

TestHashSet(1000000);
TestHashSet(2000000);
TestHashSet(4000000);

TestHashSet2(1000000);
TestHashSet2(2000000);
TestHashSet2(4000000);

结果如下：

ToLower1000000: 22.00 ms
ToLower2000000: 40.00 ms
ToLower4000000: 84.00 ms
ToHashSet1000000: 48.00 ms
ToHashSet2000000: 73.00 ms
ToHashSet4000000: 145.00 ms
ToHashSet21000000: 58.00 ms
ToHashSet22000000: 107.00 ms
ToHashSet24000000: 219.00 ms

他们每个人显然仍然必须使用该ToLower方法，但我正在尝试使用该方法HashSet来加快查找速度。理想情况下，您不必扫描整个字符串。此外，我真的认为第二个整体测试TestHashSet会更快，因为它不必创建大量内存来分配HashSet.

回想起来，我认为为什么最后两种方法较慢。我相信它们更慢，因为我有与第一个相同的算法（即我必须至少遍历整个字符串两次），但除此之外，我还在进行查找。

我怎样才能使这个算法更快？我们经常使用它，无论大小写如何，我们都必须比较字符串。

4

2 回答 2

3

无意冒犯，但你不懂大O。O(n + n) 与 O(n) 相同。big-O 的全部意义在于“隐藏”常数因子。在这个问题上，使用一个处理器你不能做得比 O(n) 更好。通过将字符串分成 k 段并使用单独的线程搜索它们，您可能会在 k 核上获得 O(n/k)。

将字符转换为小写是一个常数时间操作。检查与所需字符的匹配是一种廉价的恒定时间操作。在散列集中插入一个字符是一个相当昂贵的常数时间操作。在您的哈希集测试中，您在处理每个字符时添加了这个相当大的常量成本。由于它比仅查看字符以查看它是否与模式字符串匹配的恒定成本要大，因此您的运行时间会变长。

仅当您要查找许多值时，使用散列集进行查找才有意义。如果您需要对同一个字符串进行多次查找以查看它是否包含任何或全部 k 个不同字符，那么您可能会通过构建哈希集受益，因为 k 查找将花费 O(k) 时间而不是 O( kn) 为每个字符扫描整个字符串的时间。

如果您只在每个字符串中查找一个字符，请忘记 big-O。恒定的因素是您最大的希望。您应该考虑一个低级循环。它会是这样的：

static bool findChar(string str, char charToFind) {
  char upper = Char.toUpper(charToFind);
  char lower = Char.toLower(charToFind);
  for (int i = 0; i < str.length; i++) {
    if (str[i] == upper || str[i] == lower) {
      return true;
    }
  }
  return false;
}

提前抱歉语法问题。我不是 C# 程序员。请注意，这最多扫描一次字符串。如果角色被提前找到，它就会停止。检查的预期字符数是字符串中的一半。这个函数也不会产生垃圾。

另一方面，预期的字符数

str.ToLower().Contains("a");

是长度的1.5倍str，会产生垃圾。所以你可能会用显式循环获胜

如果这仍然太慢，则本机函数可能会产生很小的增益。你得试一试才能知道。

于 2013-08-14T01:15:39.410 回答
1

我相信你的代码是O(2n) = O(n)。那是因为每次调用都会遍历输入字符串 2 次。为了减少运行时间的算法界限，您需要一个具有对数界限或O(n^k) 且 k<1算法的算法，我认为这在您的场景中是不可能的。我能建议的最好的方法是利用不变的特定信息：例如，如果你知道你的字符串总是有大写的第一个字母，只更改字符串中的第一个字符。这是一个如何利用特定领域知识的示例。

于 2013-08-13T20:33:29.927 回答