Итак, в настоящее время я работаю над изометрической игрой, основанной на тайлах, и я использую топологическую сортировку, чтобы отсортировать порядок тайлов, которые будут отображаться. Что ж, топологическая сортировка на самом деле определяет глубину каждого тайла, и массив тайлов, которые должны быть отрисованы, сортируются компаратором, сравнивающим эти глубины.
Проблема, с которой я сталкиваюсь, - это в основном низкая производительность в моей топологической сортировке. Я не уверен, есть ли что-то, что я упускаю, что может вызвать проблемы с производительностью. Я был бы очень благодарен за любой вклад, который можно было бы использовать для оптимизации топологической сортировки.
Я храню некоторые переменные в полях, я не уверен, что это улучшит производительность. Я также использую открытые поля для необходимых сравнений.
Соответствующие фрагменты кода:
private void topological(Array<IsoSprite> sprites) {
for (int i = 0; i < sprites.size; ++i) {
a = sprites.get(i);
behindIndex = 0;
for(IsoSprite sprite: sprites){
if(sprite != a){
if (sprite.maxX > a.minX && sprite.maxY > a.minY && sprite.minZ < a.maxZ) {
if (a.behind.size <= behindIndex) {
a.behind.add(sprite);
behindIndex++;
} else {
a.behind.set(behindIndex++, sprite);
}
}
}
}
a.visited = false;
}
sortDepth = 0;
for (IsoSprite sprite : sprites) {
visitNode(sprite);
}
}
private void visitNode(IsoSprite sprite) {
if (!sprite.visited) {
sprite.visited = true;
Iterator<IsoSprite> it = sprite.behind.iterator();
while (it.hasNext()) {
visitNode(it.next());
it.remove();
}
sprite.isoDepth = sortDepth++;
}
}
.get
, а затем второй цикл foreach. Теперь, чтобы помочь с вашим вопросом, вы можете использоватьArrays.sort
для спрайтов и реализовать собственный компаратор, в основном, если из внутреннего цикла. Это было бы намного быстрее, чем это, что, вероятно, даже хуже, чем O (n ^ 2), поскольку вы вставляете элементы, что значительно увеличивает временную сложность - вставка массива - это сложность O (m), где m - текущая длина (и до n относится к общей длине). - person Marko Gresak   schedule 14.06.2015public int compareTo(IsoSprite b) { if (b.maxX > minX && b.maxY > minY && b.minZ < maxZ){ return -1; }else if(b.maxX < minX && b.maxY < minY && b.minZ > maxZ){ return 1; } return 0; }
Но все, что я получаю, это ошибка Метод сравнения нарушает его общий контракт!, черт возьми, это было бы так здорово. - person Deminth   schedule 14.06.2015behindIndex
, а не устанавливает. - person Marko Gresak   schedule 14.06.2015visitNode
: в основном для каждого узла, для каждого элемента вbehind
вы удаляете первый элемент, и это удаление равно O (n), в отличие от добавление в конец. Если вы хотите очиститьbehind
, вызовите back.clear() после цикла или, да, используйте LinkedList, или начните удаление с последнего элемента (итерация в обратном порядке). И если вы каждый раз удаляете все элементы изbehind
, то частьif (a.behind.size <= behindIndex) {
вtopological
не имеет смысла: за всегда пусто, так что это всегда будет случай добавления, никогда не установленный. - person Kolmar   schedule 14.06.2015