志 李華

摘要：計算質數個數，最常用的是質數定理函數x/ln(x)和高斯函數Li(x)。但是兩者對質數個數的估計前者總是小于，后者總是大于質數的實際個數，并且隨著數量級的增加，偏差擴大。前文已經提出了對x/ln(x)進行改進的函數p(x)。現對高斯函數Li(x)進行動態修正，得到了一個更為理想的質數個數估計函數 q(x)。數值實驗表明，與p(x)和黎曼函數R(x)計算結果比較，改進后的q（x）計算簡便，且精確度較高。

關鍵詞：質數定理 質數個數 質數計數函數 動態修正

計算質數個數，最常用的是質數定理函數x/ln(x)和高斯函數Li(x)（1）。高斯函數 Li(x) 表示為（2）：

高斯在1792年，勒讓德在1798年就發現了質數定理（2）。但是質數定理函數和高斯函數對質數個數的估計均存在較大偏差。前文已經對x/ln(x)進行了改進，獲得了改進的質數估計函數p(x)（3），表示為：

其中：n=1.2為質數函數常數。

黎曼函數R(x) 的一種表示是（4）：

其中：

是黎曼 函數。

黎曼函數的計算復雜，在給定數量級非常大時與Li(x)同樣偏離真實值（4）。因此有必要探索更為精確的質數計數函數。

質數的分布類型屬于確定性隨機分布（5）。因此，理論上存在能夠相對精確表示質數個數的函數。

現對高斯函數Li(x)進行動態修正，到了一個較理想的質數個數估計公式q(x)。數值實驗表明，改進后的q(x)與p(x)和R(x)計算結果比較，它計算簡便，且精確度較高。

一、小于給定數量級的質數個數

實驗觀察可知，高斯函數Li(x)計算數值偏差較大，并總是大于實際的質數計數。本文對高斯函數Li(x)進行動態修正，在其積分式的分母上添加一個適當的正的函數，以減少積分的值，使其更接近實際的質數計數。經過大量實驗，并進一步優化，確定了函數表達式，給出如下定義。

定義q(x)為修正后的質數計數函數：

。

二、實驗驗證

應用q(x)計算小于給定數量級的質數個數，并與應用p(x)和R(x)的計算結果進行比較，詳見表1~表2和以及圖1~圖9。實驗表明，很多情況下q(x)與 p(x) 和 R(x) 非常近似于質數計數函數π(x)，并隨著 x 的增大，q(x)與 p(x) 和 R(x) 以及π(x) 互有交叉, q(x)表現了良好的逼近性能。q(x)函數形式簡單，計算方便，且具有相對較高精確度。

注：x為整數，π(x)為質數的實際個數函數，p(x)為改進的質數計數函數，R(x)為黎曼質數計數函數，q(x）為本文改進的質數計數函數。

圖1 棕色Li(x)，綠色q(x)，紅色p(x)，藍色π(x)，黑色R(x)，紫色x/ln(x)。

圖2 棕色Li(x)，綠色q(x)，紅色p(x)，藍色π(x)，黑色R(x)，紫色x/ln(x)。

圖3 綠色q(x)，紅色p(x)，藍色π(x)，黑色R(x)，紫色x/ln(x)。

圖4 綠色q(x)，紅色p(x)，藍色π(x)，黑色R(x)。

圖5 綠色q(x)，紅色p(x)，藍色π(x)，黑色R(x)。

圖6 綠色q(x)，紅色p(x)，藍色π(x)，黑色R(x)。

圖7 綠色q(x)，紅色p(x)，藍色π(x)，黑色R(x)。

圖8 綠色q(x)，紅色p(x)，藍色π(x)，黑色R(x)。

圖9 綠色q(x)，紅色p(x)，藍色π(x)，黑色R(x)。

三、討論與結論

表1結果可見，應用q(x)計算小于給定數量級的質數個數相對較精確，優于應用p(x)和R(x)的計算結果。

表2結果可見，在給定區間內q(x)、p(x)和R(x)共有19組數據。q(x)與p(x)和R(x)計算值與π(x)計算值比較，q(x)與p(x)和R(x)變動方向完全一致，同步率達到100.00%；大于和小于π(x)計算值的分別為6組和13組，占31.58%和68.42%；其中q(x)有7組優于R(x)，占比達36.84%；q(x)有14組優于p(x)，占比達73.68%。

q(x)計算結果與p(x)和R(x)計算結果相近，但最大偏差和平均偏差均略優于R(x)。

圖1顯示了六個函數之間在區間[10，1000]上的關系，Li(x)總是大于、x/ln(x)總是小于 p(x),q(x),π(x),和R(x)；而q(x),π(x),R(x)三者相互纏繞。圖2~圖9結果顯示，q(x)與p(x)和R(x)的函數曲線與π(x)的函數曲線出現多處糾纏和穿越，表明計算不同區間質數個數時，會出現q(x)與p(x)和R(x)交替為優的情況。另外，q(x)與p(x)、π(x)和R(x)的函數曲線非常接近，擬合較佳。在圖4以及之后，由于x/ln(x)偏差較大，在圖上已經不再出現。

因為質數的分布存在一定的隨機性，實際質數個數始終在q(x)函數值的上下浮動，頻繁變化，呈現波動狀態。因此q(x)的函數曲線可稱為質數曲線，q(x)可稱為質數計數函數。

易知q(x)計算簡便，精確度高于p(x)和R(x)的計算結果。q(x)是一個較為理想的質數計數函數，具有廣泛的應用前景。

四、參考文獻

[1] G. H.Hardy and E. M. Wright. An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008

[2] https://mathworld.wolfram.com/PrimeCountingFunction.html

[3] Zhi Li and Hua Li.A Revised Prime Number Counting Function. https://vixra.org/abs/2301.0104.

[4] https://primes.utm.edu/howmany.html

[5] Zhi Li and Hua Li.Proof of N^2+1 Conjecture. https://vixra.org/abs/2209.0059

言

計劃開一個新的系列，來講一講在工作中經常用到的性能優化手段、思路和如何發現性能瓶頸，后續有時間的話應該會整理一系列的博文出來。
今天要談的一個性能優化的Tips是一個老生常談的點，但是也是很多人沒有注意的一個點。在使用集合類型是，你應該設置一個預估的初始大小，那么為什么需要這樣做？我們一起來從源碼的角度說一說。

集合類型

我們先來聊一聊.NET BCL庫中提供的集合類型，對于這個大家肯定都不陌生，比如List、HashSet、Dictionary、Queue、Stack等等，這些都是大家每天都用到，非常熟悉的類型了，那么大家在使用的時候有沒有注意過它們有一個特殊構造函數呢？像下面代碼塊中的那樣。

public Stack (int capacity) 
public List (int capacity)
public Queue (int capacity)
public HashSet (int capacity)
public Dictionary (int capacity)

哎？為什么這些構造函數都有一個叫capacity的參數呢？我們來看看這個參數的注釋。初始化類的新實例，該實例為空并且具有指定的初始容量或默認初始容量。
這就很奇怪了不是嗎？在我們印象里面只有數組之類的才需要指定固定的長度，為什么這些可以無限添加元素的集合類型也要設置初始容量呢？這其實和這些集合類型的實現方式有關，廢話不多說，我們直接看源碼。

List源碼

首先來看比較簡單的List的源碼（源碼地址在文中都做了超鏈接，可以直接點擊過去，在文末也會附上鏈接地址）。下面是List的私有變量。

// 用于存在實際的數據，添加進List的元素都由存儲在_items數組中
internal T[] _items;

// 當前已經存儲了多少元素
internal int _size;

// 當前的版本號，List每發生一次元素的變更，版本號都會+1
private int _version;

從上面的源碼中，我們可以看到雖然List是動態集合，可以無限的往里面添加元素，但是它底層存儲數據的還是使用的數組，那么既然使用的數組那它是怎么實現能無限的往里面添加元素的？我們來看看Add方法。

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Add(T item)
{
    // 版本號+1
    _version++;
    T[] array = _items;
    int size = _size;
    // 如果當前已經使用的空間 小于數組大小那么直接存儲 size+1
    if ((uint)size < (uint)array.Length)
    {
        _size = size + 1;
        array[size] = item;
    }
    else
    {
        // 注意！！ 如果已經使用的空間等于數組大小，那么走AddWithResize方法
        AddWithResize(item);
    }
}

從上面的源碼可以看到，如果內部_item數組有足夠的空間，那么元素直接往里面加就好了，但是如果內部已存放的元素_size等于_item數組大小時，會調用AddWithResize方法，我們來看看里面做了啥。

// AddWithResize方法
[MethodImpl(MethodImplOptions.NoInlining)]
private void AddWithResize(T item)
{
    Debug.Assert(_size == _items.Length);
    int size = _size;
    // 調用Grow方法，并且把size+1，至少需要size+1的空間才能完成Add操作
    Grow(size + 1);
    _size = size + 1;
    _items[size] = item;
}

// Grow方法
private void Grow(int capacity)
{
    Debug.Assert(_items.Length < capacity);
    // 如果內部數組長度等于0，那么賦值為DefaultCapacity(大小為4)，否則就賦值兩倍當前長度
    int newcapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;
    // 這里做了一個判斷，如果newcapacity大于Array.MaxLength(大小是2^31元素)
    // 也就是說一個List最大能存儲2^32元素
    if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;
    // 如果newpapacity小于預算需要的容量，也就是說元素數量大于Array.MaxLength
    // 后面Capacity會拋出異常
    if (newcapacity < capacity) newcapacity = capacity;
    // 為Capacity屬性設置值
    Capacity = newcapacity;
}

// Capacity屬性
public int Capacity
{
    // 獲取容量，直接返回_items的容量
    get => _items.Length;
    set
    {
        // 如果value值還小于當前元素個數
        // 直接拋異常
        if (value < _size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        }

        // 如果value值和當前數組長度不匹配
        // 那么走擴容邏輯
        if (value != _items.Length)
        {
            // value大于0新建一個新的數組
            // 將原來的數組元素拷貝過去
            if (value > 0)
            {
                T[] newItems = new T[value];
                if (_size > 0)
                {
                    Array.Copy(_items, newItems, _size);
                }
                _items = newItems;
            }
            // value小于0 那么直接把_items賦值為空數組
            // 原本的數組可以被gc回收了
            else
            {
                _items = s_emptyArray;
            }
        }
    }

通過上面的代碼我們可以得到兩個有意思的結論。

一個List元素最大能存放2^31個元素.不設置Capacity的話，默認初始大小為4，后面會以2倍的空間擴容。

List底層是通過數組來存放元素的，如果空間不夠會按照2倍大小來擴容，但是它并不能無限制的存放數據。
在元素低于4個的情況下，不設置Capacity不會有任何影響；如果大于4個，那么就會走擴容流程，不僅需要申請新的數組，而且還要發生內存復制和需要GC回收原來的數組。
大家必須知道分配內存、內存復制和GC回收內存的代價是巨大的，下面有個示意圖，舉了一個從4擴容到8的例子。

上面列舉了我們從源碼中看到的情況，那么不設置初始化的容量，對性能影響到底有多大呢？所以構建了一個Benchmark，來看看在不同量級下的影響，下面的Benchmark主要是探究兩個問題。

• 設置初始值容量和不設置有多大的差別
• 要多少設置多少比較好，還是可以隨意設置一些值

public class ListCapacityBench
{
    // 宇宙的真理 42
    private static readonly Random OriginRandom = new(42);

    // 整一個數列模擬常見的集合大小 最大12萬
    private static readonly int[] Arrays =
    {
        3, 5, 8, 13, 21, 34, 55, 89, 100, 120, 144, 180, 200, 233, 
        250, 377, 500, 550, 610, 987, 1000, 1500, 1597, 2000, 2584,
        4181, 5000, 6765, 10946, 17711, 28657, 46368, 75025, 121393
    };

    // 生成一些隨機數
    private static readonly int[] OriginArrays = Enumerable.Range(0, Arrays.Max()).Select(c => OriginRandom.Next()).ToArray();
       
    // 不設置容量
    [Benchmark(Baseline = true)]
    public int WithoutCapacity()
    {
        return InnerTest(null);
    }

    // 剛好設置需要的容量
    [Benchmark]
    public int SetArrayLengthCapacity()
    {
        return InnerTest(null, true);
    }

    // 設置為8
    [Benchmark]
    public int Set8Capacity()
    {
        return InnerTest(8);
    }
    
    // 設置為16
    [Benchmark]
    public int Set16Capacity()
    {
        return InnerTest(16);
    }

    // 設置為32
    [Benchmark]
    public int Set32Capacity()
    {
        return InnerTest(32);
    }
    
    
    // 設置為64
    [Benchmark]
    public int Set64Capacity()
    {
        return InnerTest(64);
    }
    
    // 實際的測試方法
    // 不使用JIT優化，模擬集合的實際使用場景
    [MethodImpl(MethodImplOptions.NoOptimization)]
    private static int InnerTest(int? capacity, bool setLength = false)
    {
        var list = new List<int>();
        foreach (var length in Arrays)
        {
            List<int> innerList;
            if (capacity == null)
            {
                innerList = setLength ? new List<int>(length) : new List<int>();
            }
            else
            {
                innerList = new List<int>(capacity.Value);
            }
            
            // 真正的測試方法  簡單的填充數據
            foreach (var item in OriginArrays.AsSpan()[..length])
            {
                innerList.Add(item);
            }
            
            list.Add(innerList.Count);
        }

        return list.Count;
    }

從上面的Benchmark結果可以看出來，設置剛好需要的初始容量最快(比不設置快40%)、GC次數最少(50%+)、分配的內存也最少(節約60%)，另外不建議不設置初始大小，它是最慢的。
要是實在不能預估大小，那么可以無腦設置一個8表現稍微好一點點。如果能預估大小，因為它是2倍擴容，可以在2的N次方中找一個接近的。

8 16 32 64 128 512 1024 2048 4096 8192 ......

Queue、Stack源碼

接下來看看Queue和Stack，看看它的擴容邏輯是怎么樣的。

private void Grow(int capacity)
{
    Debug.Assert(_array.Length < capacity);
    const int GrowFactor = 2;
    const int MinimumGrow = 4;
    int newcapacity = GrowFactor * _array.Length;

    if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;

    newcapacity = Math.Max(newcapacity, _array.Length + MinimumGrow);

    if (newcapacity < capacity) newcapacity = capacity;
    SetCapacity(newcapacity);
}

基本一樣，也是2倍擴容，所以按照我們上面的規則就好了。

HashSet、Dictionary源碼

HashSet和Dictionary的邏輯實現類似，只是一個Key就是Value，另外一個是Key對應Value。不過它們的擴容方式有所不同，具體可以看我之前的博客，來看看擴容的源碼，這里以HashSet為例。

private void Resize() => Resize(HashHelpers.ExpandPrime(_count), forceNewHashCodes: false);
private void Resize(int newSize, bool forceNewHashCodes)
{
    // Value types never rehash
    Debug.Assert(!forceNewHashCodes || !typeof(T).IsValueType);
    Debug.Assert(_entries != null, "_entries should be non-null");
    Debug.Assert(newSize >= _entries.Length);
    var entries = new Entry[newSize];
    int count = _count;
    Array.Copy(_entries, entries, count);
    if (!typeof(T).IsValueType && forceNewHashCodes)
    {
        Debug.Assert(_comparer is NonRandomizedStringEqualityComparer);
        _comparer = (IEqualityComparer<T>)((NonRandomizedStringEqualityComparer)_comparer).GetRandomizedEqualityComparer();
        for (int i = 0; i < count; i++)
        {
            ref Entry entry = ref entries[i];
            if (entry.Next >= -1)
            {
                entry.HashCode = entry.Value != null ? _comparer!.GetHashCode(entry.Value) : 0;
            }
        }
        if (ReferenceEquals(_comparer, EqualityComparer<T>.Default))
        {
            _comparer = null;
        }
    }
    // Assign member variables after both arrays allocated to guard against corruption from OOM if second fails
    _buckets = new int[newSize];
#if TARGET_64BIT
    _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)newSize);
#endif
   for (int i = 0; i < count; i++)
   {
       ref Entry entry = ref entries[i];
       if (entry.Next >= -1)
       {
           ref int bucket = ref GetBucketRef(entry.HashCode);
           entry.Next = bucket - 1; // Value in _buckets is 1-based
           bucket = i + 1;
       }
   }
   _entries = entries;
}

從上面的源碼中可以看到Resize的步驟如下所示。

1. 通過HashHelpers.ExpandPrime獲取新的Size
2. 創建新的數組，使用數組拷貝將原數組元素拷貝過去
3. 對所有元素進行重新Hash，重建引用

從這里大家就可以看出來，如果不指定初始大小的話，HashSet和Dictionary這樣的數據結構擴容的成本更高，因為還需要ReHash這樣的操作。
那么HashHelpers.ExpandPrime是一個什么樣的方法呢？究竟每次會擴容多少空間呢？我們來看HashHelpers源碼。

public const uint HashCollisionThreshold = 100;

// 這是比Array.MaxLength小最大的素數
public const int MaxPrimeArrayLength = 0x7FFFFFC3;
public const int HashPrime = 101;

public static int ExpandPrime(int oldSize)
{
    // 新的size等于舊size的兩倍
    int nwSize = 2 * oldSize;
    // 和List一樣，如果大于了指定最大值，那么直接返回最大值
    if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize)
    {
        Debug.Assert(MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");
        return MaxPrimeArrayLength;
    }
    // 獲取大于newSize的第一素數
    return GetPrime(newSize);
}   

public static int GetPrime(int min)
{
    if (min < 0)
        throw new ArgumentException(SR.Arg_HTCapacityOverflow);
    // 獲取大于min的第一個素數
    foreach (int prime in s_primes)
    {
        if (prime >= min)
            return prime;
    }
    // 如果素數列表里面沒有 那么計算
    for (int i = (min | 1); i < int.MaxValue; i += 2)
    {
        if (IsPrime(i) && ((i - 1) % HashPrime != 0))
            return i;
    }
    return min;
}

// 用于擴容的素數列表
private static readonly int[] s_primes =
{
    3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
    1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
    17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
    187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
    1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
};

// 當容量大于7199369時，需要計算素數
public static bool IsPrime(int candidate)
{
    if ((candidate & 1) != 0)
  {
        int limit = (int)Math.Sqrt(candidate);
        for (int divisor = 3; divisor <= limit; divisor += 2)
        {
            if ((candidate % divisor) == 0)
                return false;
        }
        return true;
    }
    return candidate == 2;
}

從上面的代碼我們就可以得出HashSet和Dictionary每次擴容后的大小就是大于二倍Size的第一個素數，和List直接擴容2倍還是有差別的。
至于為什么要使用素數來作為擴容的大小，簡單來說是使用素數能讓數據在Hash以后更均勻的分布在各個桶中(素數沒有其它約數)，這不在本文的討論范圍，具體可以戳鏈接1、鏈接2、鏈接3了解更多。

總結

從性能的角度來說，強烈建議大家在使用集合類型時指定初始容量，總結了下面的幾個點。

• 如果你知道集合將要存放的元素個數，那么就直接設置那個大小，那樣性能最高.比如那種分頁接口，頁大小只可能是50、100或者做Map操作，前后的元素數量是一致的，那就可以直接設置
• 如果你不知道，那么可以預估一下個數，在2的次方中找一個合適的就可以了.可以盡量的預估多一點點，能避免Resize操作就避免

文章來自https://www.cnblogs.com/InCerry/p/Dotnet-Opt-Perf-You-Should-Set-Capacity-For-Collection.html