Python:如何检查项是否已添加到集合中,没有2x(散列,查找)

Question

我想知道是否有一个清晰/简洁的方法来添加一些东西,并检查它是否添加没有2x哈希和查找.

这是你可能会做的,但它有2x hash的项目

if item not in some_set:  # <-- hash & lookup
    some_set.add(item)    # <-- hash & lookup, to check the item already is in the set

    other_task()

这适用于单个散列和查找,但有点难看.

some_set_len = len(some_set)
some_set.add(item)
if some_set_len != len(some_set):

    other_task()

使用Python的set api有更好的方法吗？

Answer 1

我认为没有一种内置的方法可以做到这一点.当然,您可以编写自己的函数:

def do_add(s, x):
  l = len(s)
  s.add(x)
  return len(s) != l

s = set()
print(do_add(s, 1))
print(do_add(s, 2))
print(do_add(s, 1))
print(do_add(s, 2))
print(do_add(s, 4))

或者,如果您更喜欢神秘的单行:

def do_add(s, x):
  return len(s) != (s.add(x) or len(s))

(这取决于从左到右的评估顺序以及set.add()总是返回的事实None,这是假的.)

除此之外,如果双重哈希/查找明显是性能瓶颈并且使用功能明显更快,我只会考虑这样做.

Answer 2

字典具有很好的setdefault函数，可以避免与问题中提到的“双重查找”相关的一整类问题。因为，至少在 CPython 中，大多数集合代码与字典共享，所以我尝试在处理非常大的集合（500k+ 添加，+/- 10% 重复条目）时使用它。

此外，为了减少 Python 符号名称查找所隐含的开销，我将其包装在一个高阶函数中，以便编译器将构建一个闭包，因此将能够使用基于索引的/LOAD_FAST操作LOAD_DEREF码而不是更多基于昂贵的名称查找LOAD_ATTR/ LOAD_GLOBAL：

def cache():
  s = {}
  setdefault = s.setdefault
  n = 0

  def add(x):
    nonlocal n
    n+=1
    return setdefault(x,n) != n

  return add


# Usage
cached = cache()

for i in my_large_generator_with_duplicates():
  if not cached(i):
    do_something()

在我的特定用例中，该解决方案的运行速度比其他答案中建议的解决方案快 20% 以上。当然，您的里程可能会有所不同，因此您应该进行自己的测试。

作为参考，以下是两种解决方案的反汇编代码（在 Linux 上运行的 Python3.5）：

def do_add(s, x):
  l = len(s)
  s.add(x)
  return len(s) != l


dis.dis(do_add)

 20           0 LOAD_GLOBAL              0 (len)                                                                                                                                                                    
              3 LOAD_FAST                0 (s)                                                                                                                                                                      
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)                                                                                                                                           
              9 STORE_FAST               2 (l)                                                                                                                                                                      

 21          12 LOAD_FAST                0 (s)                                                                                                                                                                      
             15 LOAD_ATTR                1 (add)                                                                                                                                                                    
             18 LOAD_FAST                1 (x)                                                                                                                                                                      
             21 CALL_FUNCTION            1 (1 positional, 0 keyword pair)                                                                                                                                           
             24 POP_TOP                                                                                                                                                                                             

 22          25 LOAD_GLOBAL              0 (len)                                                                                                                                                                    
             28 LOAD_FAST                0 (s)                                                                                                                                                                      
             31 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             34 LOAD_FAST                2 (l)
             37 COMPARE_OP               3 (!=)

def cache():
  s = {}
  setdefault = s.setdefault
  n = 0

  def add(x):
    nonlocal n
    n+=1
    return setdefault(x,n) != n

  return add


dis.dis(cache.__code__.co_consts[2])


 13           0 LOAD_DEREF               0 (n)
              3 LOAD_CONST               1 (1)
              6 INPLACE_ADD
              7 STORE_DEREF              0 (n)

 14          10 LOAD_DEREF               1 (setdefault)
             13 LOAD_FAST                0 (x)
             16 LOAD_DEREF               0 (n)
             19 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
             22 LOAD_DEREF               0 (n)
             25 COMPARE_OP               3 (!=)