Разбивка выделения при закачке на части

[zed]

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

[zed]

И собираешься ли ты реализовывать оптимизированный алгоритм расчета тайлов, в рамках данной хотелки?

[vdemidov]

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

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

И собираешься ли ты реализовывать оптимизированный алгоритм расчета тайлов, в рамках данной хотелки?

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

[zed]

В общем, вырисовывается сильно низкая производительность (и разбиение ты даже в будущем никак не оптимизируешь), с минимумом усилий на реализацию (максимум, часа два на все про все?). Т.е абы с рук долой.

[zed]

Побуду немного занудой и приведу оценки алгоритмов.

1. Вариант с доп. потоком сулит скорость порядка O(N) - за один проход мы подсчитываем число тайлов и определяем точки запуска для рабочих потоков. Скорость не зависит от того, на сколько частей мы планируем разбивать область. После завершения работы доп. потока, рабочие потоки все разом, без задержек, начинают закачку своих частей.

2. Вариант без доп. потока запускает сразу M рабочих потоков (M - число на которое пользователь решил разбить область) и в каждом из них выполняет 2 операции:
- Подсчёт числа тайлов во всей области. Сейчас это O(N), в неопределённом будущем, возможно быстрее.
- Определение точки запуска. Эту операцию каждый из потоков будет завершать за разное время - в среднем, первый стартует сразу же, второй через 1/M * O(N), третий через 2/M * O(N) и т.д. до (M-1)/M * O(N). В сумме, это даст ((M-1) / 2) * O(N).

Таким образом, суммарное время у этого варианта будет: M * O(N) + (M-1) / 2 * O(N). Очевидно, что тут скорость запуска закачки сильно зависит от того, на сколько частей мы будем разбивать область. Но, поскольку расчёты выполняются в различных потоках, ситуацию будет сглаживать наличие многоядерного процессора у пользователя.

Теперь, сравним скорость начала загрузки для области с разбиением на 8 частей, которая в норме сейчас запускается минут за 5 (т.е. наше O(N) занимает 5 минут).

1. Первый вариант выполняет запуск за 5 минут.
2. Второй выполняет запуск за: 8 * 5 + (8-1) / 2 * 5 = 40 + 17.5 = 57.5 минут (через 40 минут начнёт загружать первый поток, и в течении 17 минут постепенно будут начинать работу остальные).
2а. Если у пользователя двух-ядерный процессор: 8 * 5 / 2 + (8-1) / 2 * 5 / 2 = 20 + 8.75 = 29 минут.
2б. Если наступит неопределённое будущее и алгоритм расчёта количества тайлов будет ускорен на столько, что им можно будет пренебречь, то всё равно на двух-ядерном процессоре запуск будет занимать 9 минут.

Делать вариант без доп. потока можно только в случае, когда оба алгоритма (подсчёт тайлов и определение точки запуска) будут выполняться за пренебрежимо-малое время. Сейчас это не так, плюс, если для алгоритма подсчёта и существует теоретическая возможность ускорения, то вот для алгоритма определения точки запуска, я пока такой возможности не вижу и предполагаю, что ускорить его не получится.

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

"Та ну нафиг. Такой код я ревертну без малейших угрызений" (с).

[vdemidov]

А теперь подумаем сколько будет занимать именно закачка полигона, просчет которого занимает 5 минут? По моим прикидкам часов 50 минимум. И какая разница при таком общем времени начнется закачка через 5 минут или через 50. Ради этого заводить отдельный поток, делать для него отдельное окно прогресса и тд. ИМХО совершенно неоправданное усложнение архитектуры. В то же время простым усовершенствованием итератора, которое локально, легко проверяется на корректность тестами можно эти 5 минут превратить в секунды. Другое дело, что лично мне никогда не приходится закачивать полигоны предпросчет которых занимает больше пары секунд. Поэтому приоритет этой оптимизации для меня минимальный.

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

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

[vdemidov]

ЗЫЖ

Делать вариант без доп. потока можно только в случае, когда оба алгоритма (подсчёт тайлов и определение точки запуска) будут выполняться за пренебрежимо-малое время. Сейчас это не так, плюс, если для алгоритма подсчёта и существует теоретическая возможность ускорения, то вот для алгоритма определения точки запуска, я пока такой возможности не вижу и предполагаю, что ускорить его не получится.

Получится ускорить оба алгоритма - было бы желание.

[zed]

А теперь подумаем сколько будет занимать именно закачка полигона, просчет которого занимает 5 минут?

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

Получится ускорить оба алгоритма - было бы желание.

Как ускорить второй? Скажи и я отстану, или даже сам реализую.

[vdemidov]

Как ускорить второй? Скажи и я отстану, или даже сам реализую.

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

[vdemidov]

Еще у меня есть мысль преобразовывать полигон в множество непересекающихся прямоугольников покрывающих полигон полностью. Это можно сделать на этапе просчета количества. Тогда если пожертвовать строгим поколоночным обходом - можно сильно ускорить скорость итерирования. Ну и позицию находить очень просто.