Получить случайную запись из коллекции

Question

Каков наилучший способ получить случайный элемент из коллекции? Я слышал итерацию в лучшем случае, так что я сделал следующее:

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 вы можете использовать потоки.

Answer 1

Преобразование Collectionto an array, а затем доступ к случайной ячейке, скорее всего, приведет к более компактному коду, но, возможно, к менее результативному коду.

Рассмотрим случай, когда Collection вы собираетесь конвертировать toArray имеет следующую базовую структуру данных:

1. массив. Возможно, что-то вроде System.arrayCopy может использоваться для этого преобразования в постоянное время.
2. Связанный список/дерево. В этом случае создание массива почти наверняка займет линейное время. Новый массив нужно будет выделить, а затем заполнить, пройдя структуру данных.

В любом случае вы также добавили дополнительные служебные данные памяти, сначала преобразовывая их в массив.

В конце дня понимание того, как будет выполняться ваш алгоритм, зависит от того, как распределить типы экземпляров , с которыми вы рассчитываете иметь дело.

Если вы имеете дело с Collection s, которые используют массив в качестве базовой структуры данных, тогда генерируют случайное целое число и доступ к этой ячейке должен занимать (очень короткое) постоянное время.

С другой стороны, если ваша базовая структура данных является связанным списком, или дерево затем генерирует случайное целое число и доступ к этой ячейке может занять линейное время!

Если вы довольны линейным временем, то вы, вероятно, можете оставить свое решение таким, как есть. Если вы хотите собрать решение менее общее, ограничив типы Collection s, которые можно использовать, вы, вероятно, можете повысить производительность.

Answer 2

Abandon Collection; интерфейс не является достаточно гибким, чтобы дать вам возможность выбирать элемент по индексу.

Abandon HashSet; Set s вообще не поддерживают случайную индексацию.

Вы хотите использовать List и использовать Collections#shuffle, чтобы сделать то, что вы заинтересованы в.

Answer 3

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.