小编Ear*_*dil的帖子

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

    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 …