quick - sorting algorithms




在計算機科學中進行分類與在“真實”世界中進行分類 (8)

在每個節點上有一些開銷(附加到每個節點上的某個值或方法)是否有可能“強制”列表的順序?

當使用計算機程序進行排序時,我們選擇要排序的值的屬性。 這通常是數字的大小或字母順序。

類似於離心機,其中只有每個元素都在乎其在空間中的相對位置(相對於其他節點)

這種類比恰當地使我想起了簡單的氣泡排序。 每次迭代中冒出的數字越小。 就像您的離心機邏輯一樣。

因此,要回答這個問題,我們實際上不是在基於軟件的排序中做這種事情嗎?

我當時正在考慮對軟件中的算法進行排序,以及可能克服 O(nlogn) 障礙的可能方法。 從實際意義上講,我認為不可能進行更快的排序,所以請不要以為我可以。

話雖如此,看來對於幾乎所有的排序算法,軟件都必須知道每個元素的位置。 否則有意義的是,它將如何知道根據某些排序標準將每個元素放置在何處?

但是,當我將這種想法與現實世界相衝突時,離心機不知道每個分子在按密度對分子進行“分類”時所處的位置。 實際上,它並不關心每個分子的位置。 但是,由於每個分子都遵循密度和引力定律,因此它可以在相對較短的時間內對數万億個項目進行分類-這使我思考。

在每個節點上有一些開銷(附加到每個節點上的某個值或方法)是否有可能“強制”列表的順序? 類似於離心機,其中只有每個元素都在乎其在空間中的相對位置(相對於其他節點)。 或者,這是否違反了計算中的某些規則?

我認為這裡提出的主要觀點之一是自然界的量子力學效應以及它們如何同時並行應用於所有粒子。

也許經典計算機會固有地將排序限制在 O(nlogn) ,因為量子計算機可能能夠將閾值越過進入並行運行的 O(logn) 算法。

離心機基本上是 平行氣泡排序 的觀點似乎是正確的,它的時間複雜度為 O(n)

我想下一個想法是,如果自然可以按 O(n) 排序,為什麼計算機不能呢?


另一個觀點是,您用離心機描述的內容類似於所謂的“意大利面排序”( https://en.wikipedia.org/wiki/Spaghetti_sort )。 假設您有一盒未煮熟的意大利麵條棒,它們的長度各不相同。 將它們握在拳頭中,然後鬆開手以垂直放低它們,使末端全部放在水平桌上。 繁榮! 它們按高度排序。 O(恆定)時間。 (或者O(n),如果您包括按高度挑出桿子,然後將它們放在..意大利麵條架上,我猜是嗎?)

您可以在此處注意到,意大利麵條的個數為O(常數),但是由於意大利麵條的發聲速度有限,最長麵條的長度為O(n)。 因此,沒有什麼是免費的。


恕我直言,人們認為log(n)。 O(nlog(n))實際上是O(n)。 您只需要O(n)即可讀取數據。

快速排序等許多算法的確提供了一種非常快速的元素排序方法。 您可以實施快速排序的變體,這種變體在實踐中會非常快。

本質上,所有物理系統都是無限平行的。 您可能在沙粒中有大量的原子,自然有足夠的計算能力可以計算出每個原子中的每個電子應位於的位置。 因此,如果您有足夠的計算資源(O(n)個處理器),則可以按log(n)時間對n個數字進行排序。

來自評論:

  1. 給定一個具有k個元素的物理處理器,它可以實現最多O(k)的並行度。 如果您任意處理n個數字,它仍將以與k相關的速率對其進行處理。 同樣,您可以從物理上解決這個問題。 您可以創建n個重量與您要編碼的數字成比例的鋼球,這可以通過理論上的離心機解決。 但是這裡您使用的原子數量與n成正比。 在標準情況下,處理器中的原子數量有限。

  2. 考慮這一點的另一種方法是,假設您在每個數字上附加了一個小型處理器,並且每個處理器都可以與其鄰居通信,則可以在O(log(n))時間內對所有這些數字進行排序。


排序仍然是O(n)總時間。 之所以比那快,是因為 並行化

您可以將離心機視為由n個原子組成的 Bucketsort ,在n個核上並行化(每個原子充當處理器)。

由於處理器數量有限,O(n / C)仍為O(n)(CPU通常具有<10個內核且GPU <6000),因此可以通過並行化來加快排序速度,但是只能通過一個恆定因子來加快排序速度


總是相對於某些計算模型來定義計算複雜性。 例如,如果在 Brainfuck 實現,則在典型計算機上為 O n )的算法可能為 O (2 n )。

離心機的計算模型具有一些有趣的特性。 例如:

  • 它支持任意並行性; 無論溶液中有多少顆粒,都可以同時對其進行分類。
  • 它並沒有給出嚴格的線性按質量排序的粒子,而是非常接近的(低能量)近似值。
  • 檢查結果中的單個粒子是不可行的。
  • 無法通過不同的屬性對粒子進行分類; 僅支持質量。

鑑於我們沒有能力在通用計算硬件中實現類似的功能,因此該模型可能沒有實際意義。 但仍然值得一試,看看是否有什麼要學習的。 例如,不 確定性算法 量子算法 一直是研究的活躍領域,儘管目前都無法實現。


考慮:“離心機分類” 真的 更好地擴展嗎? 想一想當您擴大規模時會發生什麼。

  • 試管必須越來越長。
  • 沉重的東西必須走得越來越遠才能走到最底下。
  • 慣性矩增加,需要更多的功率和更長的時間才能加快分揀速度。

還值得考慮離心機分類的其他問題。 例如,您只能在狹窄的尺寸範圍內操作。 計算機排序算法可以處理1到2 ^ 1024甚至更高的整數,不費吹灰之力。 將比氫原子重2 ^ 1024倍的東西放入離心機中,好吧,這是一個黑洞,星系已被破壞。 算法失敗。

當然,真正的答案是,計算複雜度是相對於某些計算模型而言的,如其他答案中所述。 在常見的計算模型(例如RAM模型或IO模型或多帶Turing機器)的上下文中,“離心排序”沒有意義。


離心機不對節點進行分類,而是對節點施加力,然後它們平行地對其進行反應。 因此,如果要實現一個冒泡排序,其中每個節點都基於其“密度”並行地上下移動,那麼將有一個離心機實現。

請記住,在現實世界中,您可以運行大量並行任務,而在計算機中,您可以擁有的最大並行任務數量等於物理處理單元的數量。

最後,您也將無法訪問元素列表,因為它不能被兩個節點同時修改...


首先,您正在比較兩種不同的上下文,一種是邏輯(計算機),另一種是物理(到目前為止)已證明我們可以使用數學公式對其中的某些部分進行建模,並且作為程序員,我們可以使用此公式進行仿真(邏輯的某些部分)邏輯工作中的物理(例如游戲引擎中的物理引擎)。

其次,在計算機(邏輯)世界中,我們有一些可能性,這在物理學中幾乎是不可能的,例如,我們可以每次訪問內存並找到每個實體的確切位置,但是在物理學中,這是 海森堡不確定性原理的 一個巨大問題。

第三,如果您想將離心機及其在現實世界中的操作映射到計算機世界,就好比某人(上帝)給了您一台應用了所有物理規則的超級計算機,並且您正在其中進行小型排序(使用離心機),並說在o(n)中解決了排序問題,您就忽略了背景中正在進行的巨大物理模擬...







time-complexity