Как сделать левое соединение с вектором STL и алгоритмами STL с временной сложностью лучше, чем O (n ^ 2)?

У меня есть 2 вектора, которые содержат, скажем, объекты Person (имя, фамилия и т.д.). Я хочу взять один из векторов (назовем его "большой"), затем для каждого элемента в этом векторе найти соответствующий элемент во втором ("маленький") и объединить некоторые данные из "маленького" векторного элемента в "большой" вектор элемент. Эта операция очень похожа на левое соединение в терминах SQL, но с дополнительным слиянием данных. Самый простой способ - сделать 2 цикла, но это приведет к временной сложности O (n ^ 2). Могу ли я добиться большего успеха с алгоритмами STL?


c++ algorithm stl stl-algorithm
person fspirit    schedule 04.03.2011    source источник
comment
Возможно, вам удастся добиться большего успеха, если вы переключитесь с vector, скажем, на multiset. Используя Boost.MultiIndex, вы даже можете получить O(n).   -  person Fred Foo    schedule 04.03.2011
comment
@larsmans: или хэш-таблица (с обычными оговорками о практической и теоретической асимптотической производительности хеш-таблиц). Хеш-функция определяется определением соответствующего элемента, т. е. хэширует только те поля, к которым вы присоединяетесь.   -  person Steve Jessop    schedule 04.03.2011

Ответы (3)


arrow_upward
5
arrow_downward

Если вы сортируете небольшой вектор, вы можете получить O(n log n) для части слияния путем сканирования большой вектор и используйте binary_search для поиска элементов в маленьком векторе.

person Mark Wilkins    schedule 04.03.2011
comment
И часть sort также равна O(n lg n), поэтому всего 2×O(n lg n) = O(n lg n). +1. - person Fred Foo; 04.03.2011

arrow_upward
2
arrow_downward

Да! Вы можете сделать это с временной сложностью O (nlogn). Отсортируйте второй вектор, который занимает время O(nlogn). для каждого элемента в первом векторе найдите соответствующий элемент во втором, используя двоичный поиск (в STL есть алгоритм binary_search) и объедините данные с элементом в первом векторе. для каждого элемента в первом векторе мы тратим O(logn) времени. Таким образом, сложность времени выполнения этого подхода составляет O (nlogn).

person Srikanth    schedule 04.03.2011

arrow_upward
2
arrow_downward

Если ваши списки не меняются часто, вы можете отсортировать оба списка, а затем выполнить слияние за линейное время, просто пройдясь по обоим спискам.

Если ваши списки постоянно меняются, вам, вероятно, лучше отсортировать «маленький» контейнер, например map или set. В этом случае просто используйте find в наборе для каждого элемента в большом списке, к которому вы хотите присоединиться.

person Mark B    schedule 04.03.2011