Butter wouldn't melt...
Sep. 9th, 2024 01:49 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mns2012Я забил в гпт вопрос.
Вот у меня есть такой-то O(n^2) алгоритм, который стартует со списка кусков линий (в общем случае пространственных), и проверяет: если пара концов каких-либо двух линий из списка ближе, чем ε друг к другу, их нужно слить в один кусок и начать просмотр заново.
Такой, наивный алгоритм. При увеличении размера списка время работы довольно быстро растет поскольку n^2, что неприятно. Спрашиваю: что можно сделать для увеличения быстродействия?
И он пошел мне про какие-то KD-деревья.
А я спросил: а можно ведь разбить изначальный массив на маленькие кусочки и пустить несколько параллельных threads? Потом дождавшись, когда все они выполнятся, в последний раз с результатами из этих веток ещё раз просмотреть на предмет слияния?
Да, говорит. Можно. В данном случае, мне это пойдёт, потому что нет времени на все эти изыски с nearest neighbors. И что?
Нужно этому гпт всё подсказывать. Да ещё и проверять по сто раз, что он такое насоветовал. Но всё равно удобно. Net effect: сильно сокращается время разработки.
Вот у меня есть такой-то O(n^2) алгоритм, который стартует со списка кусков линий (в общем случае пространственных), и проверяет: если пара концов каких-либо двух линий из списка ближе, чем ε друг к другу, их нужно слить в один кусок и начать просмотр заново.
Такой, наивный алгоритм. При увеличении размера списка время работы довольно быстро растет поскольку n^2, что неприятно. Спрашиваю: что можно сделать для увеличения быстродействия?
И он пошел мне про какие-то KD-деревья.
А я спросил: а можно ведь разбить изначальный массив на маленькие кусочки и пустить несколько параллельных threads? Потом дождавшись, когда все они выполнятся, в последний раз с результатами из этих веток ещё раз просмотреть на предмет слияния?
Да, говорит. Можно. В данном случае, мне это пойдёт, потому что нет времени на все эти изыски с nearest neighbors. И что?
Нужно этому гпт всё подсказывать. Да ещё и проверять по сто раз, что он такое насоветовал. Но всё равно удобно. Net effect: сильно сокращается время разработки.
