我目前正在學習 Prata 的“C Primer Plus”一書。在第 16 章練習題中，我遇到了以下練習：
與陣列相比，鏈表的特點是添加和洗掉元素更容易，但排序較慢。這提出了一種可能性：將串列復制到陣列，對陣列進行排序，然后將排序結果復制回陣列可能會更快串列比簡單地使用串列演算法進行排序。（但它也可以使用更多記憶體。）使用以下方法測驗速度假設：創建一個大型矢量物件 vi0，使用 rand() 提供初始值。灣。創建第二個向量物件 vi 和一個與原始向量大小相同的串列物件 li，并將它們初始化為原始向量中的值。C。計算程式使用 STL sort() 演算法對 vi 進行排序所需的時間，然后計算使用 list sort() 方法對 li 進行排序所需的時間。d。將li重置為vi0中未排序的內容。時間將li復制到vi的組合操作，對 vi 進行排序，并將結果復制回 li。要對這些操作進行計時，您可以使用 ctime 庫中的 clock()。如代碼清單 5.14 所示，您可以使用以下陳述句開始第一個計時：clock_t start = clock(); 然后在操作結束時使用以下命令來獲取經過的時間：clock_t end = clock(); cout << (double)(end - start)/CLOCKS_PER_SEC; 這絕不是一個確定的測驗，因為結果將取決于多種因素，包括可用記憶體、是否正在進行多處理以及陣列或串列的大小。（人們會期望陣列相對于串列的相對效率優勢會隨著被排序的元素數量而增加。）此外，如果您可以在默認構建和發布構建之間進行選擇，請使用發布構建進行測量。今天的高速電腦，
我的實作是這樣的：
#include <iostream>
#include <vector>
#include <list>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAX = 10'000'000;
int main()
{
// Make real random
srand(time(0));
vector<int> vi0(MAX);
for( int i=0; i<MAX; i )
{
int r = rand();
vi0[i] = r;
}
vector<int> vi(MAX);
list<int> li;
for( int i=0; i<MAX; i )
{
int r = vi0[i];
vi[i] = r;
li.push_back(r);
}
clock_t start = clock();
sort( vi.begin(), vi.end() );
clock_t end = clock();
cout << "Time to sort vector 'vi': '" << (double)(end-start)/CLOCKS_PER_SEC << "'\n";
start = clock();
li.sort();
end = clock();
cout << "Time to sort list 'li': '" << (double)(end-start)/CLOCKS_PER_SEC << "'\n";
// Reset values
li.clear();
for( int i=0; i<MAX; i )
{
li.push_back(vi0[i]);
}
// Get time to copy values to 'vi', sort them & copy back to 'li'
start = clock();
auto x = vi.begin();
auto i = li.begin();
while( i != li.end() )
{
*x = *i;
x;
i;
}
sort( vi.begin(), vi.end() );
x = vi.begin();
i = li.begin();
while( x != vi.end() )
{
*i = *x;
i;
x;
}
end = clock();
cout << "Time to copy 'li' to 'vi'. Sort 'vi' and copy values to 'li': '" <<
(double)(end-start)/CLOCKS_PER_SEC << "'\n";
return 0;
}
編譯代碼為：g -O3 CompareListAndArraySorting.cc
輸出：
對向量“vi”進行排序的時間：“1.02916”對串列“li”進行排序的時間：“7.87467”將“li”復制到“vi”的時間。排序“vi”并將值復制到“li”：“3.73348”
我想知道，對我來說，這看起來令人費解，串列排序比將值復制到向量、向量排序和復制值要慢。我想知道你是否知道：
- 這是由于特定的機器加工嗎？
- list.sort() 的主要原因是為了節省將值復制到向量的額外空間嗎？如果軟體在額外空間分配方面沒有問題，將 vals 復制到向量、排序和復制回比慢速 list.sort() 更好的解決方案？
我錯過了練習的一些要點嗎？
uj5u.com熱心網友回復：
這是由于特定的機器加工嗎？
這個問題的一般答案幾乎總是肯定的。例如，如果處理器提供 SIMD 指令來幫助排序，那么對向量進行排序會比不連續存盤在記憶體中的鏈表快得多。記憶體層次結構的速度也起著巨大的作用，更不用說亂序執行和指令級并行性了。話雖如此，如今主流處理器非常相似，因此性能行為通常不會從一個處理器到另一個處理器發生巨大變化（至少只要它們是主流 x86/ARM 桌面/服務器處理器）。
鏈表很慢，因為這是一個不連續的資料結構，會進行許多不可預測的記憶體訪問。結果，這會在執行期間導致大量流水線停頓，從而減慢程式的速度。在不久的將來，對向量進行排序的速度肯定會更好，因為最近的SIMD 指令集合可以加速一些演算法，如快速排序或合并排序的變體（例如，BitonicSort），這些演算法經常用于有效地對資料進行排序（STL 之一應該是大量基于快速排序的 Introsort）。更準確地說，AVX-512 (x86-64) 和 SVE (ARM) 將能夠加速磁區步驟，假設編譯器可以自動矢量化這部分演算法或實作使用 SIMD 友好的代碼（通常還不是這樣）。AFAIK，英特爾 TBB 庫能夠對此類排序進行矢量化。鏈表不會明顯更快，因為硬體供應商幾乎無法優化間接記憶體加載鏈（無論如何，每次訪問都不能快于 1 個周期）。
list.sort() 的主要原因是為了節省將值復制到向量的額外空間嗎？如果軟體在額外空間分配方面沒有問題，將 vals 復制到向量、排序和復制回比慢速 list.sort() 更好的解決方案？
不僅。復制的速度取決于您復制的內容。雖然復制 int 非常便宜，但復制/移動大型復雜物件可能要昂貴得多。這么大的物體還是可以快速比較的。此外，像 int 這樣的基本型別可以參考句柄或一種指向比較慢的大型復雜物件的指標（例如，使用 lambda）。因此，這就是在副本成本與比較運算子成本之間找到一個閾值。
在您的情況下，使用向量遠比鏈表好。事實上，鏈表在高性能演算法中很少使用（幾乎總是有更好的資料結構）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/491645.html
上一篇：為快速加載檔案格式注冊寬度和決議