diff = list(set(map(tuple, paths1)) - set(map(tuple, paths2)))
куда paths1
а также paths2
список списка пар.
Пример:
paths1 = [[(1,2),(2,3),(3,4)],[(1,3),(3,5)]]
paths2 = [[(5,2),(2,3),(3,4)],[(1,3),(3,5)]]
print(list(set(map(tuple, paths1)) - set(map(tuple, paths2))))
Должен выводить [((1, 2), (2, 3), (3, 4))]
, Внутренний список должен быть сначала преобразован в кортеж, потому что этот тип списка нельзя хешировать в набор.
В приведенном ниже коде C ++ я попытался использовать функцию set_difference из стандартной библиотеки:
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
int main () {
std::vector < std::pair < int, int >>v1 =
{ std::make_pair (1, 2), std::make_pair (2, 3), std::make_pair (3, 4) };
std::vector < std::pair < int, int >>v2 =
{ std::make_pair (5, 2), std::make_pair (2, 3), std::make_pair (3, 4) };
std::vector < std::pair < int, int >>v3 =
{ std::make_pair (1, 3), std::make_pair (3, 5) };
std::vector < std::vector < std::pair < int, int >>>V1 = { v1, v3 };
std::vector < std::vector < std::pair < int, int >>>V2 = { v2, v3 };
std::vector < std::vector < std::pair < int, int >>>diff;
std::set_difference (V1.begin (), V1.end (), V2.begin (), V2.end (),
std::inserter (diff, diff.begin ()));
std::cout << "[";
for (auto v : diff) {
std::cout << "[";
for (auto p : v)
std::cout << "(" << p.first << "," << p.second << ")";
std::cout << "]";
}
std::cout << "]\n";
}
Этот код напечатан [[(1,2)(2,3)(3,4)][(1,3)(3,5)]]
, Почему второй внутренний список не удаляется, когда это должно быть?
Наборы Python основаны на хешировании. Таким образом, разница наборов Python работает путем итерации левого набора, поиска каждого элемента в хэш-карте правого набора и пропуска соответствующих элементов.
Наборы C ++ основаны на сортировке (фактически, бинарных деревьях поиска), а не на хешировании. Тот же алгоритм будет работать, но это займет (логарифмическое вместо линейного времени. Таким образом, они используют другой алгоритм, который делает работать в линейном времени: предполагая, что оба диапазона отсортированы, вы можете просто пройти два параллельно.
Соответственно С ++ set_difference
работает только на отсортированных диапазонах:
Копирует элементы из отсортированного диапазона
[first1, last1)
которые не найдены в отсортированном диапазоне[first2, last2)
к диапазону, начинающемуся вd_first
,
Когда вы даете ему несортированные диапазоны, он не знает, что вы сделали это, и пытается пройти их параллельно, и запутывается. После того, как левый список проходит (5, 2)
, он уже прошел все остальные элементы, поэтому больше ничего не пропускается.
Других решений пока нет …