從集合中獲取隨機條目

從集合中獲取隨機元素的最佳方法是什麼？我聽到的最好的迭代，所以我做了以下內容：從集合中獲取隨機條目

Collection<Integer> c = new HashSet<Integer>(); 
    Random r = new Random(); 
    for (int i = 0; i < 100000; i++){ 
     c.add(r.nextInt()); 
    } 

    Iterator<Integer> i = c.iterator(); 
    int random = r.nextInt(c.size()); 
    int num = 0; 
    int count = 1; 
    while(i.hasNext()){ 
     num = i.next(); 
     if (count == random){ 
      break; 
     } 
     count++; 
    } 
    System.out.println(num);

它工作正常，據我可以告訴，只需要幾毫秒內完成。但是，我被告知上述過於複雜的問題。我知道你可以將集合轉換爲數組，或者在Java 8中可以使用流。

來源

2016-01-06 The Gaming Grunts

你想用這段代碼實現什麼？ – YoungHobbit

上面的代碼只是一個測試，看看最好的方法是什麼。 –

'Collections.shuffle'並獲得第一個（如果你以後不關心集合的順序） – 2016-01-06 16:59:04

轉換一個Collectionto an array然後訪問一個隨機單元可能會使更緊湊的代碼，但可能性能更少的代碼。

我們認爲Collection你要轉換toArray具有以下底層數據結構的情況下：

陣列。有可能像System.arrayCopy這樣的東西可以用來在固定時間內進行這種轉換。
鏈接列表/樹。在這種情況下，創建數組幾乎肯定會花費線性時間。新陣列將不得不分配，然後通過散步數據結構來填充。

在任何一種情況下，您還通過首先轉換爲數組來增加額外的內存開銷。

在一天結束時，理解您的算法將如何執行取決於預期您希望處理的實例類型的分佈情況。

如果您正在處理使用數組作爲基礎數據結構的Collection，那麼生成一個隨機整數並訪問該單元應該花費（非常短的）恆定時間。

另一方面，如果您的基礎數據結構是鏈表或樹，那麼生成一個隨機整數並訪問該單元可能需要線性時間！

如果您對線性時間感到滿意，那麼您可以保留解決方案。如果您願意通過限制可以使用的Collection的類型來將解決方案放在一起，那麼您可能會提高性能。

來源

2016-01-06 17:14:32 vpiTriumph

Abandon Collection;界面不夠靈活，無法讓您按索引選擇元素。

Abandon HashSet; Set一般不支持隨機索引。

你要使用List，並利用Collections#shuffle完成什麼你感興趣的。

來源

2016-01-06 17:17:40 Makoto

Collection不允許通過索引元素的直接訪問。它是JDK集合類的最通用的接口，因此涵蓋了有序列表和無序列表。

如果您堅持使用Collection接口，這樣的事情應該工作，它類似於你的代碼，但更通用的：

public static <T> T getRandomElement(Collection<T> c) { 
    int random = (int) (Math.random() * c.size()); 
    Iterator<T> it = c.iterator(); 
    for (int i = 0; i < random; i++) { 
     it.next(); 
    } 
    return it.next(); 
}

但是你應該如果使用List接口而不是可能會問自己可能在你的情況下，因爲它允許使用get方法通過（隨機）索引進行簡單訪問。

來源

2016-01-06 17:22:43

從集合中獲取隨機條目

回答

相關問題