Здравствуйте, ncoder, Вы писали:

N>объйсните как достигнуть результата?
Вот например, специальное упоминание о непригодности R-tree и k-d-tree для поиска соседей при размерностях пространства более чем 10. Попробуй реадизовать алгоритм, предложенный этими парнями:
http://citeseer.ist.psu.edu/cache/papers/cs/24095/http:zSzzSzwww.cse.unsw.edu.auzSz~jaszSzresearchzSzpaperszSzspie99zSzpaper.pdf/shepherd99fast.pdf

объйсните как достигнуть результата?
алгоритм написан — работает правильно, но начиная с 4 теста где количество входных данных возрастает наблюдается дикий спад производительности. Не знаю в чем проблема. Работает одновременно 32 потока но не смотря на это надо пару часов что бы выполнить один из последних запросов (лимит 15 секунд)

дано 2 массива n-dimentional точек

А и В

надо найти каждой точке из В ближайшую из А

точки заданы массивом строк (одна точка — одна строка)

пример:
А[0] = "0.697344 0.949788 0.405156 0.807306 0.748683 0.063167 0.445903 0.865539 0.468755 0.670751 0.581446 0.900283 0.704465 0.470243 0.432790" ;
А[1] = "0.485991 0.660617 0.130041 0.402206 0.297961 0.797648 0.310834 0.694292 0.696510 0.485337 0.135352 0.408756 0.888509 0.706390 0.781251" ;

B[0] = "0.933437 0.432483 0.510766 0.201532 0.243190 0.773406 0.573988 0.021734 0.147825 0.297345 0.161019 0.020401 0.253313 0.108317 0.889064";
B[1] = "0.525418 0.892353 0.109219 0.177398 0.451098 0.337748 0.886455 0.420074 0.035418 0.509325 0.701530 0.449287 0.775009 0.012290 0.030044";

то есть есть А и В содержат по две точки 15D измерения

расстояние от B[0] до А[0] составляет Math.Sqrt(Math.Pow(X1b — X1a, 2) + Math.Pow(X2b — X2a, 2) + ... + Math.Pow(X15b-X15a, 2))

оргинал задания вот здесь

вот здесь даже можно зарегаться на competition

вообщем проблемы начинаются когда исходных точек в каждом массиве более 1000 а конкретно 20000 (А) и 40000 (Б). время нахождения минималного расстояния для одной точки увеличивается на порядки ну и количество точек которые надо проверить тоже увеличивается на порядки...

вообщем даже 32 потока не спасают так как время уменьшается только в 32 раза

вот здесь лежит мой проект (один класс класс в эекземпляр метода которого передаются входные данные как по условию соревнования) даже образцами входных данных (файл надо переименовать в "ex" если сразу запускать .exe). с вроженными тестами приложение укладывается в 15 секунд (я бы даже сказал меньше чем за секунду) а вот со следующими:

7 МБ точек уже не справляется

причем задача решаема... потому что в таблице лидеров есть люди которые писали и на шарпе...

если кто до сюда дочитал уже огромное спасибо а вот если кто еще посмотрит мельком мой проект и оценит на вскидку где можно увеличить производительность.....

Здравствуйте, ncoder, Вы писали:

N>объйсните как достигнуть результата?
N>алгоритм написан — работает правильно, но начиная с 4 теста где количество входных данных возрастает наблюдается дикий спад производительности. Не знаю в чем проблема. Работает одновременно 32 потока но не смотря на это надо пару часов что бы выполнить один из последних запросов (лимит 15 секунд)

N>дано 2 массива n-dimentional точек

N>А и В

N>надо найти каждой точке из В ближайшую из А

N>точки заданы массивом строк (одна точка — одна строка)

N>пример:
N>А[0] = "0.697344 0.949788 0.405156 0.807306 0.748683 0.063167 0.445903 0.865539 0.468755 0.670751 0.581446 0.900283 0.704465 0.470243 0.432790" ;
N>А[1] = "0.485991 0.660617 0.130041 0.402206 0.297961 0.797648 0.310834 0.694292 0.696510 0.485337 0.135352 0.408756 0.888509 0.706390 0.781251" ;

N>B[0] = "0.933437 0.432483 0.510766 0.201532 0.243190 0.773406 0.573988 0.021734 0.147825 0.297345 0.161019 0.020401 0.253313 0.108317 0.889064";
N>B[1] = "0.525418 0.892353 0.109219 0.177398 0.451098 0.337748 0.886455 0.420074 0.035418 0.509325 0.701530 0.449287 0.775009 0.012290 0.030044";

N>то есть есть А и В содержат по две точки 15D измерения

N>расстояние от B[0] до А[0] составляет Math.Sqrt(Math.Pow(X1b — X1a, 2) + Math.Pow(X2b — X2a, 2) + ... + Math.Pow(X15b-X15a, 2))

N>оргинал задания вот здесь

N>вот здесь даже можно зарегаться на competition

N>вообщем проблемы начинаются когда исходных точек в каждом массиве более 1000 а конкретно 20000 (А) и 40000 (Б). время нахождения минималного расстояния для одной точки увеличивается на порядки ну и количество точек которые надо проверить тоже увеличивается на порядки...

N>вообщем даже 32 потока не спасают так как время уменьшается только в 32 раза

N>вот здесь лежит мой проект (один класс класс в эекземпляр метода которого передаются входные данные как по условию соревнования) даже образцами входных данных (файл надо переименовать в "ex" если сразу запускать .exe). с вроженными тестами приложение укладывается в 15 секунд (я бы даже сказал меньше чем за секунду) а вот со следующими:

N>7 МБ точек уже не справляется

N>причем задача решаема... потому что в таблице лидеров есть люди которые писали и на шарпе...

N>если кто до сюда дочитал уже огромное спасибо а вот если кто еще посмотрит мельком мой проект и оценит на вскидку где можно увеличить производительность.....

up

Здравствуйте, ncoder, Вы писали:
N>объйсните как достигнуть результата?
N>если кто до сюда дочитал уже огромное спасибо а вот если кто еще посмотрит мельком мой проект и оценит на вскидку где можно увеличить производительность..... Во-первых, очевидно, что извлекать квадратный корень не нужно. Потому что это монотонная функция. Впрочем, вряд ли это сильно улучшит результат для 15 измерений (это будет только одна из 31 float операции)
Во-вторых, при таких количествах точек очевидно, что нужно построить индекс по множеству A, который позволит искать ближайшую к заданной точке быстрее, чем за O(A.Length).
Искать в гугле по словам multidimensional nearest neighbor index