10

我有一个采用上限的方法，并返回一个质数列表，直到该限制。

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

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

这是我得到一百万以下素数的时间。

  • 0.1136s 纯哈希
  • 0.0975s 纯列表（预计更快）
  • 0.0998s 纯列表转换为哈希（未预期）

如果可以简单地解释其原因，我很想听听。我想至少我正在寻找的东西足以了解我是否应该从 List 或 HashSet 开始，如果最终结果将是一个大的 HashSet 项目。

我在下面添加了主要方法的主体，但请注意，与数据结构的所有交互在两者之间都是相同的（代码方面）。我不相信我如何将数据添加到结构中会影响异常。

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

还应要求提供我用来测试执行时间的（丑陋的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("#.###################"));
4

3 回答 3

14

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

于 2013-09-24T17:17:15.590 回答
3

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

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

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

于 2013-09-24T17:38:24.937 回答
2

查看您的算法，我怀疑纯散列较慢，因为它是散列，而不是有序列表。使用有序列表时，您按顺序测试 2、3、5、7 等的可除性，因此首先测试较小的除数（更常见的除数）。使用散列时，顺序是任意的，因此您可以在测试可被 3 整除之前测试可被 23 整除。

顺便说一句，你应该使用 testnumber += 2，并从你的素数列表中排除 2，当你完成循环时插入 2。

更好的是，埃拉托色尼筛法通常是计算相对较小数字的所有素数的更快方法。或者更好的是，预先计算你的低值素数并从磁盘加载它

编辑——添加

不是我最初所期望的（散列乱序），但它看起来像 MoveNext() 中的更多开销——这就是 foreach 在内部的工作方式

比较 MoveNext() 函数的差异——您将在最内层循环中调用数百万次。

// HashSet<>.MoveNext()
public bool MoveNext()
{
    if (this.version != this.set.m_version)
    {
        throw new InvalidOperationException(SR.GetString("InvalidOperation_EnumFailedVersion"));
    }
    while (this.index < this.set.m_lastIndex)
    {
        if (this.set.m_slots[this.index].hashCode >= 0)
        {
            this.current = this.set.m_slots[this.index].value;
            this.index++;
            return true;
        }
        this.index++;
    }
    this.index = this.set.m_lastIndex + 1;
    this.current = default(T);
    return false;
}


List<>.MoveNext()
public bool MoveNext()
{
    List<T> list = this.list;
    if ((this.version == list._version) && (this.index < list._size))
    {
        this.current = list._items[this.index];
        this.index++;
        return true;
    }
    return this.MoveNextRare(); // this call should be rare as the name implies
}

private bool MoveNextRare()
{
    if (this.version != this.list._version)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
    }
    this.index = this.list._size + 1;
    this.current = default(T);
    return false;
}
于 2013-09-24T17:32:00.153 回答