0

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

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

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

4 ответа 4

2

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

  1. Из имеющегося массива (array) "Выписать" индексы пустых элементов в список (freeList).

    freeList.add(new Point(i,j))
    
  2. Далее перемешиваем список

    Collections.shuffle(freeList); 
    
  3. Если список freeList не пуст. Достаём первый из freeList.remove(0) и удаляем его из списка. (Конечно холошо удалять последний, поскольку это не двигает массив. Но кому как)

     Point index  = freeList.remove(0);
    
  4. Вставляем в array[index.x, index.j] = new MyObjects();

  5. Повторяем 3 - 4 пока freeList не пуст.

  6. В итоге мы будем иметь freeList который перемешан. И удалять произвольный элемент.

1

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

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

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

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

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

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

1
  • такой вариант не подойдёт по логике программы. Дело вот в чём: логика программы построена на том, что один и тот же null элемент имеет вероятность (небольшую) выпасть подряд несколько раз. В вашем способе, если адрес элемента уже выпал, то до тех пор пока не выпадут все остальные элементы он не выпадет вообще.
    – gibsonff
    24 янв 2021 в 13:25
0
  1. Для начала замените двумерный массив одномерным (любой "прямоугольный" двумерный массив можно представить в виде одномерного).
  2. Далее можете заменить массив типа Integer[] на int[] (null элементы вы представите по другомму).
  3. Заведите переменную int firstEmptyItem. Она будет содержать индекс первой ячейки массива, в которой у вас ничего нет (в вашей версии вы бы поместили в эту ячейку null).
  4. В первую пустую ячейку запишите индекс следующей пустой ячейки и т.д.

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

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

1
  • мне не нужно перебрать в случайном порядке пустые элементы. Мне нужно, чтобы любой пустой элемент мог выпасть в любой момент. Любой null элемент имеет вероятность(хоть и маленькую) выпасть подряд много раз. Ваш способ предполагает перебор все null элементов по ОДНОМУ разу! И только после этого у элемента появляется возможность снова появиться. Такой вариант мне не подходит
    – gibsonff
    24 янв 2021 в 13:34
0

можно так:

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]
.....

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

2
  • видимо я в вопросе не акцентировал внимание на то, что количество null-элементов это не константа. null-элементы могут заполнятся объектами, а элементы с объектами становится null-элементами. Т.е. мой массив сохраняет ТОЛЬКО размер, а его элементы постоянно в цикле изменяются(становятся null или !null ). Как только я создам список индексов (которые могут выпасть), так он тут же устареет на следующей итерации! Потому что массив мог измениться!
    – gibsonff
    24 янв 2021 в 13:46
  • Если не критично, можете держать координаты объекта в самом объекте, и все они в одном списке, таким образом сымитируем матрицу. ---- List<Item> list = new ArrayList<>(); for (int y = 0; y < count; y++) { for (int x = 0; x < count; x++) { list.add(new Item(x, y,null)); } }
    – Mark Cain
    24 янв 2021 в 17:36

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.