合併排序java - 高效地合併和重新排序已排序的列表



verilog排序法 (5)

  1. 保持一個地圖,這是一個獨特的東西映射到實際的學生信息。

    Map<String, Student> scores = new HashMap<>();
  2. 遍歷所有的列表,並把它們放到分數圖中

    for (Student s : list1) {
        if (scores.containsKey(s.name)) {
            scores.put(s.name, s.score + scores.get(s.name));
        } else {
            scores.put(s.name, s.score); 
        } 
    }
  3. 使用Java 8流對entrySet進行排序

    scores.entrySet()
      .stream()
      .sorted((s1, s2) -> (s2.getValue().score - s1.getValue().score)
      .map(s1 -> s1.getValue())
      .collect(Collectos.toList());

這仍然是O(N Log N)

您不能使用標準合併算法對其進行排序,因為列表包含名稱的位置不相同。 標準合併算法不處理相同的元素兩次。 找到重複並添加學生成績後,您需要重新排序。 您打破了合併排序的前提條件,即兩個列表始終按其值排序。

這不是經典的“合併兩個已排序的”列表問題,這在線性時間內是相當微不足道的

我想要做的是將已經按value排序的兩個(key, value)對列表合併,這兩個列表中的對象具有相同的key :這些對象應該合併(添加)它們的value ,這可能改變他們的排列順序。 我主要感興趣的是如何使用已排序列表中的信息有效地執行排序,因為排序是該算法中最慢的部分。

我們舉一個具體的例子。 想像一下Student對象List

class Student {
  final String name;
  final int score;
  ...
}

給定輸入兩個List<Student>score排序,我想要創建新的學生合併列表,其中出現在兩個列表中的任何學生(由Student.name標識)出現在最終列表中一次,分數等於他們在兩個名單上的得分總和。 原始列表應該保持不變。

例如,

List 1:
{"bob", 20}
{"john", 15}
{"mark", 14}

List 2:
{"bill", 11}
{"mark", 9}
{"john", 1}

Result:
{"mark", 23}
{"bob", 20}
{"john", 16}
{"bill", 11}

合併本身(識別出現在兩個列表中的學生)可以使用任何O(1)查找/插入結構(如HashMap )在預期的O(1)時間內完成。 我最感興趣的是排序步驟(儘管我不排除同時進行合併和排序的解決方案)。

問題是,我如何有效地重新排序這樣一個列表? 現有清單的排序清楚地對合併清單中的要素的最終位置進行了一些限制。 例如,如果一個學生在第一個列表中的位置i和第二個列表中的第j個,則他必須通過分析可以具有較高分數的學生的最大數目的簡單論證出現在合併列表中的第一i + j學生中。 但是,目前還不清楚該信息是否有助於排序清單。

你可以認為在很多情況下,在一個列表中獲得高分的學生在另一個列表中獲得高分。 如果不是這種情況,該算法應該可以工作,但除了列表已經排序之外,它還會提供一些關於可能有用的分佈的附加信息。

似乎這種類型的操作對於任何類型的分佈式查詢+排序實現來說都是常見的。 例如,設想一個“按狀態計數(*)組”的查詢問題類型(對每個狀態的記錄數進行計數) - 自然你會得到一個排序列表(狀態,計數)對像從每個節點返回,然後在reduce操作期間想要合併和重新排序這些對象。 丟棄已經在分佈式節點上完成的所有工作似乎很愚蠢。

數量說明

我感興趣的是要合併和重新排序的列表很少:通常大約256個條目。 分數的範圍在一些情況下從0到100,在另一些情況下高達約0到10,000,000。 當然,由於元素數量較少,每個操作在絕對時間內都會很快,即使使用天真的算法 - 也會執行數十億次,這就加起來了。

事實上,下面的答案之一已經證明 ,一般來說,你不可能比簡單的排序來增加列表大小(即,將n作為列表大小的組合),但實際上我更感興趣在這麼多次,對於固定大小的列表,具有良好的經驗表現。


(關閉首先合併,然後重新排序,)我的第一個刺將是聲明排序的輸入列表(半靜態) 優先級隊列 ,並分兩個階段進行。 為了避免術語合併中的歧義,我將調用創建/改變對象來表示“共同對象”的組合 / 組合的值 ; 為了減少混亂,我將表示優先級隊列 PQ。

  1. 識別出現在兩個/多個“輸入隊列”中的對象
    (在這裡次要的利益的方式)
    • 結合(可能無效列表中的位置),
    • 把他們放在另一個(動態)PQ(如有必要)
    • 在(輸入)隊列中刪除/無效,不再有效。
  2. 以通常的方式合併PQ

這應該在線性時間內在對象的數量n中加上,對於c “common”對象加上O(c log c) ,其中組合的對象將不按順序代替任何組合的對象。 (...給定預期的常量時間(識別和)組合一個(一組通用)對象 (請參閱關於期望的O(1)的評論))
那麼,恐怕沒有妥善解決主要觀點:

有沒有辦法利用最後的關鍵是 (線性的,單調的)
至少有一個有序序列和“其他值”的組合?
(有很多常見的條目 - 都在想)

如果組合的優先級單調下降(在本例中,增加(正值)分數值會增加優先級),那麼在合併PQ時不需要合併階段和合併對象,這可能會減少內存以及所需的時間。
否則 ,選擇一個 PQ從(優先級降低)對像中獲取對象,以便與其他對象結合。
這個“最糟糕的情況”看起來似乎沒有任何相關性,但我認為答案是重要的
一般來說,不 。 (請參閱user2570465的答案為明確的參數)
(正如BeeOnRope所指出的那樣 ,被挑選的對象的(順序)組合(不利的選擇)可能實際上變成一個好的情況,如果可以被檢測和利用的話)。
然而,即使沒有(正相關)(在問題中假設),(線性的,單調的) 組合也可以預期偏斜鍵的分佈:確保使用(動態的)PQ實現,其中按順序插入是最好的情況比最糟糕的是:
首先, 在數組中隱含堆 (索引i處的元素的子元素位於2i2i + 1 (或者2i + 12i + 2 “不浪費元素0”),但索引操作更多一些):
只是附加項目(分配傾斜到優先級降低 )到最後:
與父母的期望交換次數低於1(幾乎是1,沒有歪斜)。


在我看來,任何解決方案通常應歸入O(n * log(n))複雜度(n =長度(L1)+長度(L2)或n = max(長度(L1)),長度L2)))。

我的基本算法如下

  Let's use two intermediate structures:
  - a TreeSet R, which guarantees ordering by rank, 
  - an HashMap M, which guarantees constant time insertion and retrieve 
  Call R's size n

  1 for each student in each list
      1.1 find the student in M by name (O(1)).
      1.2 if the student is found          
         1.2.1 find the student in R by its rank (O(log(n)).  
         1.2.2 remove the student from R (O(log(n))
         1.2.3 update the student rank 
      1.3 else 
        1.3.1. put the student in M O(1)
      1.4 put the student in R (O(log(n))
  2 At the end (if needed) transform the TreeSet in a list

總的O複雜度是O(n * log(n)),

假設L1是2個列表中最長的一個,一個小的優化將避免在遍歷L1時找到學生,在這種情況下,O的複雜性是相同的,但是絕對的操作更少。 最好的情況當然是Len(L1)>> Len(L2)。

可能有更複雜的解決方案或更好的數據結構來減少操作數量,但我不認為可能有更好的O複雜性,基本上你有兩種可能性

1-保留結果列表的順序,所以掃描列表,找到匹配,並重新計算位置

2-使用中間映射降低匹配查找的複雜性,然後對結果進行排序

這兩種可能性通常以O(n * log(n))計算


它看起來像你想要一個O(N)合併,就像他們做合併排序。 我想我可能會有一些壞消息給你。 我希望(希望)證明,對於廣義問題,你不能比O(nlog(n))做得更好:(因此,你應該只使用其他人提出的任何最優的O(nlog(n) )。 首先,我將從直覺開始,為什麼會出現這種情況,然後我會寫一個非正式的證明。

直覺

這個想法是把列表排序的問題轉化為你的問題,並且表明如果你能比O(nlog(n))更快地解決你的問題,那麼我可以比O(nlog(n))更快地排序列表,我們知道是錯誤的。 我們只要用整數就可以使事情簡單化。

假設你有一些奇怪的序列進行排序: X = 1, 3, 2, -10, 5, 4, 7, 25 。 我現在將構造兩個名單Dec和Inc.我從1 = 1 + 0 (即x_1 = x_1 + 0 )開始。 那麼之後,如果x_{i-1} -> x_i是一個增長,那麼我從Dec中減去1,然後計算Inc中的必要值,總和為x_i 。 如果x_{i-1} -> x_i是一個減少,那麼我將1加到我在Inc中的值,然後在Dec中計算必要的值以便和x_i相加。 我們將這個算法應用到下表中的序列中:

idx   x     Dec    Inc      
----------------------
 1 |  1  =  1   +  0
 2 |  3  =  0   +  3
 3 |  2  =  -2  +  4
 4 | -10 =  -15 +  5
 5 |  5  =  -16 +  21
 6 |  4  =  -18 +  22
 7 |  7  =  -19 +  23
 8 |  25 =  -20 +  45

請注意,我可以從排序轉換為O(n)中的問題 - 注意:在O(n)時間內反轉Inc以獲得兩個遞減序列。 然後我們可以輸入你的問題

A = {(1, 1), (2, 0), (3, -2), (4, -15), (5, -16), (6, -18), (7, -19), (8, -20)}
B = {(8, 45), (7, 23), (6, 22), (5, 21), (4, 5), (3, 4), (2, 3), (1, 0)}

現在如果你可以通過它們的值(有序對中的第二個元素)的總和將A和B組合成排序順序,並得到類似

C = {(8, 25), (7, 7), (5, 5), (6, 4), (2, 3), (3, 2), (1, 1), (4, -10)

那麼你基本上已經完成了初始序列x_i一個argsort(按索引排序)。 所以,如果你比O(nlog(n))更快地解決你的問題,那麼我可以通過先解決你的問題,然後將解決方案轉換為排序列表的問題來比O(nlog(n))更快地排序。 特別是,我將排序的複雜性O(N)+ O(複雜性來解決你的問題)

聲明被證明

讓你的兩個鍵值列表

A = [(ka_i, va_i) | i = 1..n]
B = [(kb_i, vb_i) | i = 1..m] 

按價值降序排列。 您無法找到組合列表

C = [(ka_i, va_i + va_j) | ka_i = kb_j]

比O(nlog(n))時間快。

證明大綱

這個證明唯一的假設是,你不能比O(nlog(n))時間更快地排序列表,並且這個證明將通過提供一個從任意列表排序到你的問題的O(n)時間的運算來進行。

實質上,我們將顯示如果我們比O(nlog(n))更快地解決問題,那麼我們也可以比O(nlog(n))更快地排序任意列表。 而且我們已經知道不可能比nlog(n)更快地排序列表,所以你想要的解決方案也是不可能的。

證明細節

為了簡單起見,我們將排序整數列表。 令S = x_1, x_2, ..., x_n是任何整數序列。 我們現在將構建兩個名單,Dec和Inc.

我們有三個約束:

  1. 公司正在嚴格增加
  2. 12月嚴格下降
  3. 在算法的迭代i上, Inc[j] + Dec[j] = x_j for all j = 1..i-1Inc[j] + Dec[j] = x_j for all j = 1..i-1

正如他們的名字所暗示的那樣,12月將嚴格減少,公司將嚴格增加。 x_i = Dec[i] + Inc[i] for i = 1..n ,我們將保持x_i = Dec[i] + Inc[i] for i = 1..n的不變量

這是減少:

# (Assume 1-indexed lists)
1. Initialize Inc = [x_1] and Dec = [0]
2. For i = 2..n:
    a. if x[i] > x[i-1] then
          Dec.append(Dec[i-1] - 1)
          Inc.append(x_i - Dec[i])
       else   # We must have x[i] <= x[i-1]
          Inc.append(Inc[i-1] + 1)
          Dec.append(x_i - Inc[i])

3. Create list A and B:
    A = [(i, Dec[i]) | i = 1..n]
    B = [(i, Inc[i]) | i = 1..n]
4. B = reverse(B) # Reverse B because B was in increasing order and we
                  # need both lists to be in decreasing order
5. A and B are inputs to your algorithm.
  If your algorithm can combine A and B into sorted order,
  then we have also sorted S (via argsort on the keys).

你可能也渴望證明我選擇將Inc增加1或者將Dec減1的作用。 那麼這是一個非正式的“證明”(你可以通過使用歸納法來形式化):

案例x_ {i}> x_ {i-1}

回想一下,在這種情況下,我們選擇將Dec遞減1.我們得到x_{i} > x_{i-1}並且我們知道Dec_{i-1} + Inc_{i-1} = x_{i-1} 。 我們也可以說(Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1}

由於x_{i} > x_{i-1} ,我們必須有x_{i} >= x_{i-1} + 1 。 因此, x_{i} >= (Dec_{i-1} - 1) + (Inc_{i+1} + 1) 。 因此,如果我們只將Dec遞減1,我們將被迫增加至少1個Inc,所以Inc仍然嚴格增加。

情況x_ {i}≤x_ {i-1}

回想一下,在這種情況下,我們選擇將Inc遞增1.我們給出了x_{i} <= x_{i-1}並且我們知道Dec_{i-1} + Inc_{i-1} = x_{i-1} 。 我們也可以說(Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1}並且由於x_{i} <= x_{i-1} (Dec_{i-1} - 1) + (Inc_{i+1} + 1) <= x_{i} 。 因此,如果我們給公司加1,我們確信我們必須從12月份減去至少1。

結論

你的問題不能做得比O(nlog(n))快。 你最好把它合併成一個HashMap,然後在O(nlog(n))中排序它的元素,因為找不到更快的解決方案。

如果您發現減少的問題或有疑問,請隨時發表評論。 我很確定這是正確的。 當然,如果我誤認為排序不會比O(nlog(n))快,這整個證明就會崩潰,但最後我檢查了一下,有人已經證明O(nlog(n))是排序中最快的複雜度。 評論你是否喜歡正式的減價。 現在對我來說已經越來越晚了,我跳過了一些“形式化”,但是當我有機會的時候我可以編輯它們。

如果您對創建縮減的算法進行編碼,則可能會獲得更好的理解。

另外:看到這個帖子,如果你想對O(nlog(n))綁定排序的解釋排序算法的“Ω(n log n)障礙”的規則是什麼?


這聽起來像你需要使用自適應排序算法。

“如果排序算法利用輸入序列中現有的順序,則排序算法屬於適應性排序系列,它受益於輸入序列中的預分類 - 或者對於混亂度量的各種定義的有限數量的混亂 - 並且排序更快。通常通過修改現有的排序算法來進行排序“。 - 上面鏈接的維基百科文章。

例子包括插入排序和Timsort; 看到上面的文章更多。 請注意,在Java 8中, Arrays.sort(Object[])庫方法使用修改的Timsort。

我不知道任何已發布的算法處理您的示例的具體要求,但這是一個想法:

  1. 在兩個輸入列表L1和L2上執行經典合併:

    • 在合併一對對象並更改確定排序的鍵時,將合併的對象放入臨時列表A.
    • 否則將對象放入臨時列表B ...將保持有序。
  2. 排序臨時列表A.

  3. 合併列表A和B.

假如說:

  • 原始列表L1和L2的長度分別是M和N,
  • 其密鑰改變的合併對象的數量為R(小於max(M,N)),

那麼總的複雜度就是O(M + N + RlogR)。 如果R相對於M + N很小,那麼這應該是一個改進。

在你的例子中,輸入列表中元素匹配的每個情況都可能會按順序移動元素。 如果它移動的元素,它將移動到以後的順序(而不是更早)。 因此,另一個想法是在原始的2個列表和一個優先級隊列之間進行三方合併。 當你得到一個匹配,你合併計數,並將結果添加到優先級隊列。

複雜性與以前相似,但是您避免了額外的傳遞來合併列表。 RlogR也變為RlogA ,其中A是優先級隊列的平均大小。

請記住,我特別感興趣的是R近似等於max(M,N),也是M == N.

(你沒有在你的問題中說過,而且事實上R對於min(M,N)沒有任何意義!)

在這種情況下,可能只是使用優先隊列作為增量分揀機。 拋出所有合併的記錄和所有不能合併到隊列中的記錄,並且如果他們的鍵/分數小於兩個列表的當前頭部,則拉取我們的記錄。 假設M和N是列表長度,A是平均優先級隊列大小,則復雜度為max(M,N)* log A)。 這是否是對簡單重新排序的改進,將取決於平均值A是否顯著(大於0)小於最大值(M,N)。 這將取決於輸入...和合併功能。

數字(N)是不同的,但典型的是256到1,000。 也許多達一萬。

對於這個典型大小的列表,你處於復雜性分析不會有用的水平。 而且,如果你的操作很多次,或者是緊張的“時間預算”,那麼你的優化就變得毫無意義了。

這是非常近似的,我的數學充其量是“粗略的”。

一個適當的調查將需要數百小時的研究,編碼,測試,基準,分析各種替代方案......我們可能仍然會得到答案,它取決於輸入數據集的大小和分佈。





time-complexity