隨機排序的子陣列

比方說，我有一個對象有一個重要的標準，也許還有一些其他的數據。隨機排序的子陣列

class MyObject { 
    int criteria; 
    String otherData; 
}

我想「洗牌排序」，從而給出的數據X列表，Y是x爲標準和y是otherData，所有的類似X的分組（和排序），但內亞羣，它是洗牌

我給出的目標順序運行，可能給下面的結果

/ 1s first\|/ 2s next \|/ then 3s \ 
----------------------------------- 
1,a 1,b 1,c 2,d 2,e 2,f 3,g 3,h 3,i // other data is in 
1,a 1,c 1,b 2,e 2,d 2,f 3,i 3,h 3,g // a random order 
1,c 1,a 1,b 2,d 2,f 2,e 3,h 3,i 3,g // within the subgroup 
1,b 1,c 1,c 2,e 2,d 2,f 3,g 3,h 3,i

我目前的計劃是建立一個可比較的，只有比較第一準則。然後我的「洗牌排序」可以簡單地

list.shuffle(); // get a random ordering 
list.sort(); // now group by criteria, leaving the others in a still random state

我的問題是，這是最有效的方式做到這一點？它會實際達到我的目標嗎？有沒有可能出現的一些模式？如果是這樣，什麼？

來源

2011-11-03 corsiKa

我相信這會起作用並且是漸近最優的。如果你確定使用穩定的排序，分析起來最容易，但我認爲分組階段不會引入偏見。

如果要編寫更明顯地表達意圖的代碼，可以將值插入TreeMap<Integer, List<MyObject>>，將給定整數的所有值分組到同一列表中。然後以鍵順序（從最低到最高）迭代映射的內容，混洗每個子列表，然後將其內容轉儲到最終輸出列表中。在我看來，這種方法更「明顯正確」，但我相信你的工作也是如此。

來源

2011-11-03 23:17:36 jacobm

比較器不知道未排序的字段。因此，我相當確定，在這裏引入偏見是不可能的。 – olivieradam666

是的，我同意。所有我的意思是，如果你想做一個正式的論證，你需要說（a）這種排序不考慮其他領域，（b）統一排列無偏序隨機洗牌的順序是也是一個無偏見的隨機洗牌。這兩個事實看起來很明顯，但它們確實使論點更加微妙。 – jacobm

我看到你的方法的唯一優化是使用某種混洗迭代器而不是實際混洗數據。但是這不會改變算法的複雜性，因爲混洗成本最差是線性的，排序最好是n log（n）

來源

2011-11-03 23:17:03 olivieradam666

想想你想做什麼，之前你考慮實現，並嘗試從現有的JDK類找到一個合適的。

我會用Map<Integer, List<MyObject>>這將解決分組問題馬上，然後我可以Collections.shuffle()名單，如果我真的希望有一個單一的名單，我可以放棄在地圖值列表到一個列表：

Map<Integer, List<MyObject>> map = new HashMap<Integer, List<MyObject>>(); 
... 
List oneList = new ArrayList<MyObject>(map.values()); 
for (List<?> list : map.values()) 
    oneList.addAll(list);

來源

2011-11-03 23:26:42 Bohemian

我曾想過這件事，但這是在應用程序中最關鍵的循環。它必須在每次迭代中重新排列優先級，並且這樣做，我必須每次都重新創建整個地圖/列表結構。我還看到，我必須對'oneList'進行排序，以確保它們都按照正確的順序排列，看看values（）沒有賦值給它。 – corsiKa

我還應該注意，列表的長度不能超過10，這進一步增加了這種開銷的大小。 – corsiKa

您可以使用有序地圖來維護'int criteria'的秩序。此外，我建議您全天保持地圖，並且只在絕對需要時將其渲染到列表中 - 或者更改您的應用以使用地圖。順便說一下，它應該是'criteria'，而不是'criteria'：'criteria'是'criteria'的* plural *，並且只有一個'int'，除非它是一個位掩碼:) – Bohemian

隨機排序的子陣列

回答

相關問題