Как правильно выбрать случайный элемент из массива?

Question

Программа создаёт массив

MyObjects[][] array = new Myobjects[30][30];

логика программы заполняет некоторые элементы объектами, а некоторые элементы остаются null. Мне нужно выбрать случайный элемент из тех которые равны null. Я решил сделать это так: а) в цикле перебираю массив array и в новый пустой (freeList) список сохраняю адреса null-элементов массива, б) с помощью Random из списка freeList выбираю случайный элемент и по его адресу в массив array сохраняю следующий объект. Но этот способ мне не нравиться, потому что 1)придётся постоянно перебирать циклом весь массив(даже когда осталось всего несколько null-элементов), 2)создавать новый пустой список freeList (или очищать старый), добавлять в него новые элементы и это нужно повторять довольно часто по логике программы. Подскажите, как правильнее выбрать из массива случайный null-элемент? Чтобы это не слишком загружало процессор и уборщик мусора.

Answer 1

Предлагаю вариант такой

Создаете одномерный массив вместо 2 мерного. Так как преобразование индексов вы знаете.

Создаете массив с 900 integer'ами (30*30). Заполняя его от 1 до 900 и перемешиваете 1 раз.

Каждый раз когда нужен будет следеюшый null элемент, берете след индекс от массива900 и берете след индексы пока не будет найден null элемент.

Если дошли до 900 элемента, перемешиваете массов900 еще раз и начинаете с 1 индекса.

Это думаю быстрее чем полный массив пробежать.

Answer 2

Для начала замените двумерный массив одномерным (любой "прямоугольный" двумерный массив можно представить в виде одномерного).
Далее можете заменить массив типа Integer[] на int[] (null элементы вы представите по другомму).
Заведите переменную int firstEmptyItem. Она будет содержать индекс первой ячейки массива, в которой у вас ничего нет (в вашей версии вы бы поместили в эту ячейку null).
В первую пустую ячейку запишите индекс следующей пустой ячейки и т.д.

В результате этих манипуляций у вас получится очень компактная структура, которая хранит информацию как о пустых ячейках, так и о заполненных.

Насчет рандомного выбора пустой ячейки - т.к. ваши пустые ячейки массива образуют что-то вроде связного списка, перебрать их в обычном цикле будет не проблемой. Как именно при переборе вы определите - какую именно вам нужно использовать ячейку - уже ваш выбор. Главное работайте с с пустыми ячеками по тем же правилам, что и с односвязным списком.

Answer 3

можно так:

public static void main(String[] args) {
        int count = 30;
        // создаем массив очередей
        List<Queue<Integer>> list = new LinkedList<>();
        for (int i = 0; i < count; i++) {
            list.add(createShuffleQueue(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
        }

        for (int i = 0; i < 60; i++) {
            // берем случайный 'y'
            int h = new Random().nextInt(count);
            // берем случайный 'x'
            Queue<Integer> q = list.get(h);
            // если пустой можем удалить (если не через цикл как у меня) для повышения производительности,
            // но нужно следить чтобы не получить IndexOutOfBoundsException
            if (!q.isEmpty())
            //и удаляем из массива
                q.poll();
        }

        // выводим что осталось
        for (Queue<Integer> q : list) {
            System.out.println(q.toString());
        }
    }

    // получить смешаную очередь чего угодно
    public static <T> Queue<T> createShuffleQueue(T... t){
        List<T> arr = Arrays.asList(t);
        Collections.shuffle(arr);
        return new LinkedList<>(arr);
    }

вывод примерно такой:

[9, 1, 5, 7, 3, 6]
[9, 3, 5, 4, 8, 7]
[7, 5, 3, 4]
[2, 9, 7, 10, 5, 8, 3]
[9, 10, 7, 5, 1]
[9, 1, 7, 4, 3]
[]
[2, 10, 9]
.....

таким образом теряете время только один раз при старте. Однако теряете больше оперативной памяти.

Answer 4

По мне вы правильно начали.

Из имеющегося массива (array) "Выписать" индексы пустых элементов в список (freeList).
```
freeList.add(new Point(i,j))
```
Далее перемешиваем список
```
Collections.shuffle(freeList); 
```
Если список freeList не пуст. Достаём первый из freeList.remove(0) и удаляем его из списка. (Конечно холошо удалять последний, поскольку это не двигает массив. Но кому как)
```
 Point index  = freeList.remove(0);
```
Вставляем в array[index.x, index.j] = new MyObjects();
Повторяем 3 - 4 пока freeList не пуст.
В итоге мы будем иметь freeList который перемешан. И удалять произвольный элемент.

БЛОГ НА HUSL

Как правильно выбрать случайный элемент из массива?

Ответы (4 шт):