Оптимизация топологической сортировки

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

Проблема, с которой я сталкиваюсь, - это в основном низкая производительность в моей топологической сортировке. Я не уверен, есть ли что-то, что я упускаю, что может вызвать проблемы с производительностью. Я был бы очень благодарен за любой вклад, который можно было бы использовать для оптимизации топологической сортировки.

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

Соответствующие фрагменты кода:

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++;
    }
}

person Deminth    schedule 13.06.2015    source источник
comment
Что вы имеете в виду под плохим исполнением? Слишком долго? Использует слишком много памяти? Не производит правильный заказ?   -  person lenz    schedule 14.06.2015
comment
@lenz Выдает правильный порядок, но при включении сортировки fps сильно падает. И это также сильно зависит от увеличения количества плиток. Из того, что я могу сказать, он должен иметь временную сложность O (n ^ 2), поэтому он не должен быть слишком плохим (хотя он все еще не самый лучший)   -  person Deminth    schedule 14.06.2015
comment
Первое, что меня беспокоит (хотя и не имеет отношения к вопросу), это то, почему вы сначала используете цикл for и используете индекс только для .get, а затем второй цикл foreach. Теперь, чтобы помочь с вашим вопросом, вы можете использовать Arrays.sort для спрайтов и реализовать собственный компаратор, в основном, если из внутреннего цикла. Это было бы намного быстрее, чем это, что, вероятно, даже хуже, чем O (n ^ 2), поскольку вы вставляете элементы, что значительно увеличивает временную сложность - вставка массива - это сложность O (m), где m - текущая длина (и до n относится к общей длине).   -  person Marko Gresak    schedule 14.06.2015
comment
@MarkoGrešak Я понимаю, что вы имеете в виду под индексированием, и расширенный цикл for, вероятно, лучше. Проблема с созданием собственного компаратора для этого заключается в том, что вы не можете создать компаратор для оператора if (sprite.maxX › a.minX && sprite.maxY › a.minY && sprite.minZ ‹ a.maxZ), потому что он сравнивает различные переменные друг с другом. Я даже не думал о сложности вставки, может быть, это замедляет ее, есть идеи, как я могу этого избежать? Единственный вариант, который я вижу, - это наличие массива (не массива) для вставки O (1) с предопределенной максимальной длиной.   -  person Deminth    schedule 14.06.2015
comment
@MarkoGrešak Я изменил его на расширенный цикл for (IsoSprite a: спрайты), но теперь я получаю сообщение об ошибке #iterator() нельзя использовать вложенным. из libgdx, поэтому я не уверен, что это возможно, но это немного в тему   -  person Deminth    schedule 14.06.2015
comment
Определение компаратора - это то, что вы только что сказали, сравните два элемента (переменные). Взгляните на документы или этот ответ. ArrayList реализован с помощью массива, поэтому вы ничего не улучшите. Вы можете использовать LinkedList для вставки O (1). Вероятно, это лучше, поскольку вы не выполняете индексацию/поиск, что составляет O (n) для LinkedList. Для получения дополнительной информации взгляните на Шпаргалку Big-O (или любой класс алгоритмов CS 101).   -  person Marko Gresak    schedule 14.06.2015
comment
@MarkoGrešak Конечно, совсем забыл про LinkedList! Я обязательно это сделаю и постараюсь собрать компаратор, не нарушающий своего общего контракта, спасибо   -  person Deminth    schedule 14.06.2015
comment
@MarkoGrešak Этот код вставляется только в конец списка, который амортизируется O (1) для ArrayList, поэтому он не должен влиять на сложность.   -  person Kolmar    schedule 14.06.2015
comment
Я пытался реализовать в спрайте метод compareTo: public 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.2015
comment
@Kolmar Я принял set за вставку, я думал, что OP вставляет в behindIndex, а не устанавливает.   -  person Marko Gresak    schedule 14.06.2015
comment
На самом деле, я думаю, у вас может быть O (n ^ 3) в visitNode: в основном для каждого узла, для каждого элемента в behind вы удаляете первый элемент, и это удаление равно O (n), в отличие от добавление в конец. Если вы хотите очистить behind, вызовите back.clear() после цикла или, да, используйте LinkedList, или начните удаление с последнего элемента (итерация в обратном порядке). И если вы каждый раз удаляете все элементы из behind, то часть if (a.behind.size <= behindIndex) { в topological не имеет смысла: за всегда пусто, так что это всегда будет случай добавления, никогда не установленный.   -  person Kolmar    schedule 14.06.2015
comment
@Kolmar Я бы с вами согласился, короче говоря, в этом коде многое можно было сделать проще или даже вообще пропустить. Я не могу представить сценарий топологической сортировки как O (n ^ 2), не говоря уже о O (n ^ 3).   -  person Marko Gresak    schedule 14.06.2015
comment
@Kolmar Я внес предложенные вами изменения, и это немного улучшило производительность, спасибо.   -  person Deminth    schedule 14.06.2015
comment
@MarkoGrešak Я не могу представить сценарий, когда эта топологическая сортировка не будет как минимум O (n ^ 2), не хотите меня просветить? :)   -  person Deminth    schedule 14.06.2015
comment
O(n^2) здесь, потому что для каждого спрайта мы хотим найти спрайты, с которыми он перекрывается (или мы можем просто попробовать каждый другой спрайт (т.е. рассматривать это как полный граф), но тогда это O(n^2). ) так или иначе). Это может быть ускорено с помощью пространственного индексирования, см. здесь: Реализация">stackoverflow.com/questions/7435645/ Возможно, вы сможете быстро подключить некоторую библиотеку R-дерева в свой код, чтобы посмотреть, станет ли он быстрее.   -  person Kolmar    schedule 14.06.2015
comment
@Kolmar Я вижу, я обязательно посмотрю на это   -  person Deminth    schedule 14.06.2015
comment
Кстати, можно ли просто отсортировать все по Z, игнорируя X и Y? Я не понимаю, что такое minZ и maxZ в вашем коде. Я имею в виду, что если вы просто рисуете все в порядке глобального Z, это должно работать так же хорошо, как ваша текущая реализация, и тогда это будет O (n log n).   -  person Kolmar    schedule 14.06.2015
comment
@Kolmar, вероятно, это сработало бы, если бы все было привязано к изометрической сетке, хотя объекты, например, свободно перемещаются по плиткам и также могут свободно прыгать. По крайней мере, я так думаю   -  person Deminth    schedule 14.06.2015
comment
А, извините, не заметил про изометрию. Эта идея аналогична тому, что предложил Марко в своем первом комментарии.   -  person Kolmar    schedule 14.06.2015