10

上限を取り、その上限までの素数のリストを返すメソッドがあります。

    public static List<int> AllPrimesUnder(int upperLimit)

私は後で、「これはプライムですか」という質問をするだけで、リストを検索するだけでよいと判断しました。100 万の値以下のすべての素数を扱っていたので、HashSet が使用すべき構造であることに気付きました。確かにメソッドの結果を使ったルックアップの方が速かったのですが、メソッド自体の方が遅かったです。

遅い理由は、 HashSet が追加する前に重複をチェックするのに対し、 List は最後にそれを押し込むためだと思います。私が驚いたのは、そして質問とタイトルを生み出したのは、リストから始めて、それを使用して HashSet を作成する理由です。

    hashSet = new HashSet<int>(Prime.AllPrimesUnder(1000000));

メソッドの内部で Hashset を使用するよりも高速で、次のような呼び出しが可能です。

    hashSet = Prime.AllPrimesUnder_Hash(1000000);

スローダウンが重複チェックにある場合は、何があっても同じ量のチェックを行う必要がありますよね? これはおそらく私の理解が私を失敗させているところです。

これが、100万未満の素数の取得時間です。

  • 0.1136 秒の純粋なハッシュ
  • 0.0975 秒の純粋なリスト (より高速であると予想される)
  • ハッシュに変換された 0.0998 秒の純粋なリスト (予期しない)

この理由を簡単に説明できるなら、ぜひ聞きたいです。少なくとも、最終結果が項目の大きな HashSet になる場合、リストまたは HashSet から開始する必要があるかどうかを知るには、私が探しているものは十分であると思います。

以下にプライム メソッドの本体を追加しましたが、データ構造とのやり取りはすべて (コード的に) 2 つの間で同じであることに注意してください。構造にデータを追加する方法が異常に影響するとは思いません。

    public static List<int> AllPrimesUnder(int upperLimit)
    {
        List<int> primeList = new List<int>();
        primeList.Add(2);
        int testNumber = 3;
        bool isPrime;

        while (testNumber <= upperLimit)
        {
            isPrime = true;

            foreach (int prime in primeList)
            {
                if (testNumber % prime == 0)
                {
                    isPrime = false;
                    break;
                }
                if (testNumber < prime*prime)
                    break;
            }

            if (isPrime)
                primeList.Add(testNumber);

            testNumber++;
        }

        return primeList;
    }

編集：リクエストにより、ハッシュメソッドのコードを追加しています。ほぼ同じに見える場合は、それが原因です。

public static HashSet<int> AllPrimesUnder_Hash(int upperLimit)
{
    HashSet<int> primeHash = new HashSet<int>();
    primeHash.Add(2);
    int testNumber = 3;
    bool isPrime;

    while (testNumber <= upperLimit)
    {
        isPrime = true;

        foreach (int prime in primeHash)
        {
            if (testNumber % prime == 0)
            {
                isPrime = false;
                break;
            }
            if (testNumber < prime*prime)
                break;
        }

        if (isPrime)
            primeHash.Add(testNumber);

        testNumber++;
    }

    return primeList;
}

また、リクエストにより、実行時間をテストするために使用した（醜いハックっぽい）コードがあります。

        Stopwatch stopWatch = new Stopwatch();
        int iterations = 1;
        HashSet<int> hashSet = new HashSet<int>();
        List<int> list = new List<int>();

        stopWatch.Restart();
        for (int i = 0; i < iterations; i++)
        {
            hashSet = Prime.AllPrimesUnder_Hash(1000000);
        }
        stopWatch.Stop();

        Console.WriteLine("Hash: " + (stopWatch.Elapsed.TotalSeconds / iterations).ToString("#.###################"));

//////////////////////////

        stopWatch.Restart();
        for (int i = 0; i < iterations; i++)
        {
            hashSet = new HashSet<int>(Prime.AllPrimesUnder(1000000));
        }
        stopWatch.Stop();


        Console.WriteLine("List converted: " + (stopWatch.Elapsed.TotalSeconds / iterations).ToString("#.###################"));
4

3 に答える 3

14

これは、 がコレクションで初期化されるときにHashSet、コレクションのサイズを使用して容量を設定できるためです。空に値を追加する場合HashSet、容量を時々増やす必要があり、それは O(n) 操作です。
何らかの理由で、HashSetはコンストラクタのように容量をパラメータとして取りませんList。

于 2013-09-24T17:17:15.590 に答える