c# - 在 C# 中，为什么从 List 创建 HashSet 比从 HashSet 开始更快？

Question

我有一个方法接受上限，并返回一个不超过该上限的素数列表。

    public static List<int> AllPrimesUnder(int upperLimit)

我后来决定我真的只需要在列表中查找，通常只问“这是素数”这个问题。因为我处理的是小于一百万的所有质数，所以我意识到 HashSet 是我应该使用的结构。当然，使用该方法的结果进行查找更快，但方法本身较慢。

我认为它变慢的原因是 HashSet 在添加之前检查重复项，而 List 只是将它推到最后。令我感到惊讶的是，以及产生问题和标题的原因是，为什么要从 List 开始并使用它来创建 HashSet，如下所示:

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

比使用方法内部的 Hashset 更快，启用这样的调用:

    hashSet = Prime.AllPrimesUnder_Hash(1000000);

如果减速是在重复检查中，无论如何都应该进行相同数量的检查，对吧？这可能是我理解失败的地方。

这是我得到的质数低于 100 万的次数。

• 0.1136s 纯哈希
• 0.0975s 纯列表(预计会更快)
• 0.0998s 纯列表转换为哈希(未预期)

如果可以用简单的术语解释其原因，我很想听听。我想至少我正在寻找的是足够的理解，以了解如果最终结果将是一个大型项目的哈希集，我应该从列表还是哈希集开始。

我在下面添加了 prime 方法的主体，但请注意，两者之间与数据结构的所有交互都是相同的(代码方面)。我不相信我向结构添加数据的方式会影响异常。

    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;
    }

编辑:根据要求，我正在添加 Hash 方法的代码。如果它看起来几乎相同，那是因为它确实如此。

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("#.###################"));

Answer 1

原因是当 HashSet 用集合初始化时，它可以使用集合的大小来设置容量。向空的 HashSet 添加值时，需要不时增加容量，这是一个 O(n) 操作。
出于某种原因，HashSet 不像List 那样将容量作为构造函数中的参数。