Алгоритм для ускорения обработки этих данных? (сортировка стека размером 4,2 МБ)

-1

Ситуация: в конце процесса, порождающего мир моей игры, я остаюсь с 2048^2 (~ 4.2 миллиона) Размер Стек плитки. Затем мне нужно вычислить, где в списке моих обработчиков стеков им нужно идти. Вот мой метод:Алгоритм для ускорения обработки этих данных? (сортировка стека размером 4,2 МБ)

public static final void addTile(Tile t){ 
     for(int i = 0; i < sections.length; i++) 
      for(int j = 0; j < sections[i].length; j++) 
       if(sections[i][j].contains(t.x, t.y)){ //<-- determine which list according to tile's pos 
        world.get(i).get(j).get(TILE_LIST).push(t); 
        return; 
       } 
    }

Существует Rectangle[][], что соответствует каждой точке, в «мире» arraylist. Как вы можете видеть, это цикл O(n^2), который необходимо выполнить 4,2 миллиона раз. Даже с 4 потока, выполняющихся одновременно Обработка всех плиток занимает ~ 20 секунд.

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

источник

2016-05-11 Mitch Weaver

Было бы здорово знать, что ваш "содержит" делает. Если это какой-то поиск, я бы предложил хранить данные по-разному (для лучшего обратного поиска). Если это фактически функция, нужно было бы знать структуру, чтобы «инвертировать» ее. –

@JFMeier Meier Это прямоугольник содержит метод, как я уже сказал, «разделы» - это прямоугольник [] []. –

Сохранены ли разделы в отсортированном порядке? Если так, возможно, петли могут быть заменены двоичным поиском. –

R-дерево, как уже упоминалось, MBO, является хорошим пространственный индекс для произвольной точки/поли поиска, однако, так как мы ищем прямоугольники (ось выровнена многоугольники), вы, вероятно, будет лучше используя квадратное дерево (или oct-tree в 3 измерениях).

https://gamedev.stackexchange.com/questions/63536/how-do-shapes-rectangles-work-in-quad-trees

источник

2016-05-11 16:52:57

да это выглядит как лучший подход. Честно, чтобы лучше понять вопрос, я должен скорее объяснить его как квадратную сетку прямоугольников, и мы проверяем случайные точки 4.2 м, помещенные где-то в сетку. –

quadtree на 100% подходит именно вам. –

после того, как вы прочтете, что у вас есть область, уже состоящая из произвольных (100% упакованных) прямоугольников, это можно было бы оптимизировать, просто сохранив список границ индекса прямоугольника вдоль оси x (некоторые будут перекрываться) и список границ прямоугольника индекс вдоль оси y (перекрытие). Поиск значения, которое разделяется обоими результатами (ровно 1 будет соответствовать этому). –

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

R-tree предназначен для обработки таких запросов очень быстро.

источник

2016-05-11 16:31:55 MBo

спасибо, заглядывая в него сейчас –

Алгоритм для ускорения обработки этих данных? (сортировка стека размером 4,2 МБ)

ответ

Смежные вопросы