Czy zestaw python s.difference_update (t) O (m X n) oświadczenie

Question

Problem:

Pracuję na problem gdzie mam bazę danych z ogromną listę plików z systemu plików. Jeśli kilka plików zostanie usuniętych z systemu, to samo powinno zostać zaktualizowane w bazie danych.

Podejście:

lista zapytań plików z db i listy plików z systemu plików. Następnie porównaj, czy każdy z plików z db znajduje się na drugiej liście. Usuń jeśli nie znaleziono Aby uniknąć odnośnika każdego pliku z listy wielokrotnie, Mam zamiar korzystać z zestawów w Pythonie i (metoda difference_update)

Pytanie:

Wewnętrznie, to będzie znowu mieć złożoność O (m X n), podobnie jak inne podejście do wielokrotnego przeszukiwania czy jest zoptymalizowana pod kątem zmniejszenia złożoności?

Answer 1

To będzie O(len(t)), jak podano w komentarzu, ze względu na ustawiony stały czas wyszukiwania.
Również potwierdzone w http://python-reference.readthedocs.org/en/latest/docs/sets/difference_update.html