| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Хитрая сортировка |
| Автор: Anton Vatchenko 26.1.2007, 15:37 |
| Есть массив объектов, которые нельзя сравнить между собой напрямую (то есть нет зависимости A < B < C < D). Знаем только некоторые зависимости... Для понимания приведу конкретный пример: Есть много перекрывающихся окон, о некоторых мы знаем, что одно перекрывает другое, а некоторые не перекрывают друг друга. Но нужно получить правильный список. Как это быстрее всего сделать? Кстати, список может меняться - можно удалить один объект, добавить, переместить объект (могут нарушиться условия, связанные с этим объектом,). |
| Автор: MBo 26.1.2007, 15:50 |
| Топологическая сортировка графа |
| Автор: Anton Vatchenko 26.1.2007, 16:07 |
| Да, но проблема в том, что список может меняться, и может состоять из 100 элементов (для мобилок это критично), и хранить это в виде графа немного сложновато... Двигаем, например, один объект, и для 10 элементов эти связи меняются (пусть их будет где-то 500) |
| Автор: Michael_Rybak 29.1.2007, 22:22 |
| Тогда просто хранить упорядоченный список, и пробегать по нему каждый раз, когда что-то меняется. 100 операций - это и для мобилки мало. |