0

私が Big O 記法を理解していて、この時点での私の理解がおそらくほとんどのものよりもはるかに低いと信じている場合、Keyser のコメントによると、次のコード行はO(n 2 )であり、これは実際にはすでにO(n)操作です。

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

ToLower()操作であり、O(n)操作でもあるためですContains。多分それO(n + n)は、繰り返しますが、私の理解はまだ曖昧です。

注:Release以下は、ビルドで実行されたテスト メソッドのリストであり、Stopwatchクラスを利用して実行時間を追跡します。

しかし、もっと速くしたいので、次の 3 つのテスト方法を検討してください。

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理想的には、文字列全体をスキャンする必要はありません。さらに、2 番目の全体的なテストでTestHashSetある は、HashSet.

振り返ってみると、最後の 2 つの方法が遅い理由がわかると思います。最初のアルゴリズムと同じアルゴリズムを使用しているため (つまり、文字列全体を少なくとも 2 回処理する必要があるため)、速度が遅いと思いますが、その上で、その後にルックアップを行っています。

このアルゴリズムを高速化するにはどうすればよいですか? 大文字と小文字を区別せずに文字列を比較する必要がある場合に、これをよく使用します。

4

2 に答える 2

3

気分を害するつもりはありませんが、あなたはビッグオーを理解していません。O(n + n) は O(n) と同じです。big-O の要点は、一定の要素を「隠す」ことです。この問題では、1 つのプロセッサで O(n) よりも優れた処理を行うことはできません。文字列を k 個の断片に分割し、それらを別々のスレッドで検索することにより、k 個のコアで O(n/k) を取得できます。

文字を小文字に変換するのは一定時間の操作です。目的の文字との一致を確認することは、安価な一定時間の操作です。ハッシュ セットに文字を挿入することは、かなりコストのかかる一定時間の操作です。ハッシュ セットのテストでは、各文字の処理にこのかなり大きな一定のコストを追加しました。文字がパターン文字列に一致するかどうかを調べるだけの一定のコストよりも大きいため、実行時間は長くなります。

検索にハッシュ セットを使用することは、多くの値を検索する場合にのみ意味があります。k個の異なる文字のいずれかまたはすべてが含まれているかどうかを確認するために、同じ文字列に対して複数のルックアップを行う必要がある場合は、ハッシュセットを構築することでおそらく利益が得られます。 kn) 文字ごとに文字列全体をスキャンする時間。

各文字列で 1 文字だけを探している場合は、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# プログラマーではありません。これにより、文字列が最大1 回スキャンされることに注意してください。文字が早期に見つかった場合、停止します。チェックされる予想文字数は、文字列内の文字数の半分です。この機能もガベージを発生しません。

一方、タッチされた予想文字数は

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

の 1.5 倍の長さにstrなり、ガベージが生成されます。したがって、明示的なループで勝つ可能性があります

それでも遅すぎる場合は、ネイティブ関数がわずかな改善をもたらす可能性があります。あなたは見つけるためにそれを試してみる必要があります.

于 2013-08-14T01:15:39.410 に答える
1

あなたのコードはO(2n) = O(n)だと思います。これは、各呼び出しが入力文字列を 2 回トラバースするためです。実行時間のアルゴリズムの限界を減らすには、k<1 アルゴリズムで対数限界または O(n^k) を持つアルゴリズムが必要になりますが、これはシナリオでは不可能だと思います。私が提案できる最善の方法は、不変の特定の情報を利用することです。たとえば、文字列の最初の文字が常に大文字であることがわかっている場合は、文字列の最初の文字のみを変更します。これは、ドメイン固有の知識を活用する方法の例です。

于 2013-08-13T20:33:29.927 に答える