在C#中,为什么从List创建HashSet更快,而不是从HashSet开始？

Question

我有一个采用上限的方法,并返回一个素数列表,直到该限制.

    public static List<int> AllPrimesUnder(int upperLimit)

我后来决定我真的只需要在列表上进行查找,通常只是询问"Is This Prime"这个问题.由于我在处理价值百万的所有素数时,我意识到HashSet是我应该使用的结构.当然使用该方法的结果查找速度更快,但其自身的方法较慢.

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

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

比使用方法内部的Hashset更快,启用如下调用:

    hashSet = Prime.AllPrimesUnder_Hash(1000000);

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

以下是我获得100万以下素数的时间.

• 0.1136s Pure Hash
• 0.0975s纯清单(预计会更快)
• 0.0998s Pure List转换为Hash(不是预期的)

如果可以用简单的术语解释原因,我很乐意听到.我想至少我正在寻找的是足够的理解知道我是否应该从List或HashSet开始,如果最终结果将是一个大的HashSet项.

我在下面添加了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;
    }

编辑:根据请求我添加哈希方法的代码.如果它看起来几乎相同,那是因为它.

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

另外通过请求我用来测试执行时间的(丑陋的hackish)代码:

        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.

Answer 2

您AllPrimesUnder多次枚举主要列表（每个主要候选者一次）。枚举 aList比枚举 a 更快，HashSet因为 a 的内部数组HashSet更加稀疏。

没有看到代码，AllPrimesUnder_Hash我猜这是主要原因。

我不相信调整包含数千个项目的列表的大小会消耗 20 毫秒。使用复制内存memcpy（这是内部发生的事情）是您可以执行的最高吞吐量操作之一。每个核心每秒可以复制数十 GB 数据。