數字長度是否影響分揀時間？

我有一個簡單的問題，需要排序的數字長度是否會影響排序時間？例子：假設我們需要10萬個6位數字進行排序（如：204134）和1000萬個的2/3位數字（如：24，143），併爲兩個組分別進行排序。具有6位數字的集合是否需要比具有2/3位數字的集合更多的時間？數字長度是否影響分揀時間？

我知道硬件使用每個邏輯門，用於單個數字，以便6邏輯門爲6位數字相比2/3柵極爲另一組，但我不知道這是否影響排序時間或沒有。有人可以解釋我這一點。幫助將不勝感激。謝謝

來源

2014-05-01 Explorer

你在使用哪種語言進行此類操作？（和/或硬件有什麼特別是它運行嗎？） – MrTheWalrus

在標準x86或類似的處理器，它完全取決於排序算法，但我會很期待的一個較小的數字採取_more_時間，由於碰撞。但是，如果完全使用專用硬件完成，它仍然取決於算法，但我希望更小的數字更快。您是否在談論專門設計用來對一百萬個6位數字進行分類的硬件，還是一個通用CPU？ –

當然，如果您想對[0; 99]內的所有數字進行排序，您可能需要使用計數排序。（是的，我知道我可能讀了一個簡單的例子。） – delnan

該硬件與位，不與十進制數字。而且，硬件總是以相同的固定位數工作（對於給定的操作）;較小的值被填充。例如，32位CPU通常具有32位比較器單元，其32位比較所需的電路數量完全相同，並且使用這些比較器，而不管當前比較的值是否適合較少的位。

與你的思維的另一個問題是邏輯門的具體數額並沒有多大關係的表現。單個門的傳播時間比一個時鐘週期小得多，只有具有長依賴鏈的相當複雜的電路實際上比單個週期花費更長的時間（並且即使這樣，它仍然可能被流水線化以每個週期仍然獲得1歐姆的吞吐量）。令人驚訝大量的邏輯門在序列的（和在平行邏輯門的幾乎無限數量）可以很容易地在一個時鐘週期內完成其工作。因此，智能64位比較不需要比8位更多的時鐘週期。

來源

2014-05-01 19:03:19 delnan

簡短的回答：這取決於，但可能不會

較長的答案：因爲你還沒有說太多關於硬件或排序算法很難知道。你稍後提到你正在使用Quicksort的一些MPI變體。所以你問，由於硬件，6位數和3位數之間是否會有性能差異。那麼，如果你將這些數字打包在一起，那麼當將數據集從內存傳輸到處理器時，你將獲得更好的帶寬。既然你沒有提到任何關於壓縮數組的問題，我會假設你沒有這樣做。一旦該值在寄存器中，它將具有相同的延遲和吞吐量，無論是6位還是3位。

有算法，如基數排序是執行不同取決於需要爲您的數字範圍的位數。既然你沒有使用它，它不適用。

來源

2014-05-02 10:59:43 hayesti

謝謝hayesti和delnan – Explorer

數字長度是否影響分揀時間？

回答

相關問題