On Fri, Sep 20, 2019 at 6:19 AM Richard Higginbotham <higgi...@gmail.com> wrote: > >c = [val for val in a if val in filterset] > This is the crux I think. The complexity is the number of elements in > filterset. Since filterset has to be check for every value in a its O(len(a) > * len(b) * filter search time). You wrote O(n+m) but I think that is > incorrect. >
Yes, this IS the crux. If filterset were a Python list, you would be correct, but if (as the name suggests) it's a Python set, then checking "val in filterset" takes constant time, meaning that the entire process takes linear time. That is the entire point of using a hashtable for a set. ChrisA _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/QFEILZQP3UDALVODOBGNHPM6IW6JGTG4/ Code of Conduct: http://python.org/psf/codeofconduct/
