У меня есть список из нескольких тысяч наименований.Каждый элемент имеет атрибут под названием «диапазон адресов».У меня есть функция, которая проверяет правильность элементов в списке, следя за тем, чтобы ни один из их диапазонов адресов не перекрывался с диапазонами адресов любых других элементов в списке (каждый элемент имеет ровно один диапазон адресов).Если N - это количество записей в списке, я, по сути, должен выполнить ( N -1) * ( N / 2) проверки перекрытия диапазона адресов.Другими словами, если число элементов в списке удваивается, количество проверок перекрытия увеличивается в четыре раза.
Несколько месяцев назад в таком списке было бы всего несколько тысяч элементов, и вся операция завершалась бы относительно быстро,но с течением времени количество элементов выросло, и теперь для выполнения всех перекрестных проверок требуется несколько минут.
Я пытался распараллелить перекрестные проверки, но мне еще предстоит подумать овыполнимый подход.Моя проблема в том, что если я хочу распределить перекрестные проверки для выполнения, скажем, 8 потоков (чтобы полностью использовать процессоры на компьютере), мне придется разделить возможные комбинации перекрестных проверок на 8 независимых блоков.
Чтобы использовать пример, скажем, у нас есть 5 пунктов в нашем списке: (A, B, C, D, E).Используя формулу ( N -1) * ( N / 2), мы можем видеть, что это требует (5-1)* (5/2) = 10 перекрестных проверок:
A vs B
A vs C
A vs D
A vs E
B vs C
B vs D
B vs E
C vs D
C vs E
D vs E
Единственный способ распределить комбинации перекрестных проверок по заданному количеству потоков - это сначала создать список всех перекрестных проверок.проверьте пары комбинаций, а затем разбейте этот список на куски одинакового размера.Это будет работать в принципе, но даже для всего 20 000 элементов в этом списке уже будет (20 000-1) * (20 000/2) = 199 990 000 записей !!
Так что мой вопрос, есть ли какие-то сверхсложныеалгоритм, который позволил бы мне передать весь список элементов каждому потоку, а затем заставить каждый отдельный поток сам определять, какие перекрестные проверки должны выполняться, чтобы никакие два потока не повторяли одинаковые перекрестные проверки?
Я программирую это на Perl, но на самом деле проблема не зависит от какого-либо конкретного языка программирования.
РЕДАКТИРОВАТЬ: Хммм, теперь мне интересно, если я вообще поступил об этом неправильно.Если бы я мог отсортировать элементы по диапазонам адресов, я мог бы просто просмотреть отсортированный список и проверить, не перекрывается ли какой-либо элемент с его последующим элементом.Я попробую это и посмотрю, не ускорит ли это все.
ОБНОВЛЕНИЕ: Боже мой, это действительно работает !!!: D Используя предварительно отсортированный список, вся операция занимает 0,7 секунды для 11 700 элементов, в то время как моя предыдущая наивная реализация заняла бы от 2 до 3 минут!
ОБНОВЛЕНИЕ ПОСЛЕ комментария пользователя usr: Как заметил пользователь usr, просто проверяя каждыйпредмет против его непосредственного преемника не достаточно.Проходя по отсортированному списку, я перетаскиваю дополнительный (изначально пустой) список, в котором я отслеживаю все элементы, связанные с текущим перекрытием.Каждый раз, когда обнаруживается, что элемент перекрывается с его элементом-преемником, элемент-преемник добавляется в список (если список ранее был пустым, сам текущий элемент также добавляется).Как только элемент НЕ пересекается с его последующим элементом, я локально сверяю все элементы в моем дополнительном списке друг с другом и затем очищаю этот список (та же операция выполняется, если в моем дополнительном списке все еще есть какие-либо элементы после того, как яя прошел список всех предметов).
Мои модульные тесты подтверждают, что этот алгоритм работает;по крайней мере, со всеми примерами, которые я до сих пор кормил.