Реализация эффективного алгоритма сопоставления пар

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

Вероятно, это был бы алгоритм, который можно было бы сразу же придумать.

for( it_1=list_1.begin() ; it_1!=list_1.end() ; it_1++ )
  {
      for( it_2=list_2.begin() ; it_2!=list_2.end() ; it_2++ )
      {
          //now match 
           match(*it_1,*it_2);
      }

  }

Интересно, есть ли лучший способ сделать это. Для этого требуется O(n1*n2), где n1 и n2 — длина list_1 и list_2 соответственно.


person cpp_noname    schedule 10.07.2012    source источник
comment
Что делает ваша функция match?   -  person Fred Foo    schedule 10.07.2012
comment
Фактический алгоритм, с которым я имею дело, не совсем такой, как этот. Таким образом, тело внутри этих вложенных циклов for намного сложнее, чем это. Но идея та же, то есть сопоставление каждого объекта в списке 1 с каждым в списке 2. Функция сопоставления может быть просто простым добавлением или чем-то еще. Просто игнорируйте это. Основное внимание должно быть уделено петлям и их сочетанию.   -  person cpp_noname    schedule 10.07.2012
comment
Если match может быть чем угодно, то этот алгоритм (без учета опечаток в приращении внешнего цикла) асимптотически оптимален. Чтобы улучшить его, вам нужно знать, что делает код внутри цикла.   -  person Fred Foo    schedule 10.07.2012
comment
Я понимаю. Единственный способ улучшить это — распараллелить циклы. Спасибо за ответ, larsmans.   -  person cpp_noname    schedule 10.07.2012
comment
std::for_each и универсальный функтор могут помочь?   -  person linello    schedule 10.07.2012
comment
еще один способ ускорить этот алгоритм - предварительно упорядочить элементы с заданной функцией, а затем использовать порядок для уменьшения итераций цикла...   -  person linello    schedule 10.07.2012
comment
@linello, почему так? Я думаю, что он также должен иметь сложность O (n1 * n2). Каждый элемент в списке 1 должен соответствовать каждому элементу в списке 2. Я не вижу никакой пользы от переупорядочения элементов.   -  person cpp_noname    schedule 10.07.2012
comment
@takwing: вы можете уменьшить 2d до 1d с помощью кривых заполнения пространства. Это изменение порядка элементов и может помочь функции сопоставления.   -  person Gigamegs    schedule 10.07.2012
comment
@Chiyou, не могли бы вы указать мне, где я могу узнать больше об этой трансформации?   -  person cpp_noname    schedule 10.07.2012
comment
blog.notdot. нетто/2009/11/   -  person Gigamegs    schedule 10.07.2012


Ответы (1)


Здесь вы можете использовать многопоточность, разделив list1 на 2 или 3 части в зависимости от размера и эффективности, которые вы ищете, и запустить алгоритм сопоставления в каждом потоке со списком2 и сопоставить результаты обратно вызывающей стороне.

Посмотрим поможет ли..

person javanx    schedule 10.07.2012