Прилагане на ефективен алгоритъм за съпоставяне на двойки

Да предположим, че имам два списъка с обекти и бих искал да съпоставя всеки обект в списък едно с всеки обект в списък две.

Това вероятно ще бъде алгоритъмът, който човек веднага ще измисли.

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 цикли е много по-сложно от това. Но идеята е същата, тоест съпоставяне на всеки обект в List1 с всеки в List 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. net/2009/11/   -  person Gigamegs    schedule 10.07.2012


Отговори (1)


Тук можете да използвате многопоточна обработка, като разделите list1 на 2 или 3 части в зависимост от размера и ефективността, които търсите, и изпълните алгоритъма за съвпадение във всяка нишка със list2 и съпоставяте резултатите обратно към повикващия.

Вижте дали помага..

person javanx    schedule 10.07.2012