Python：如何检查某个项目是否已添加到集合中，无需 2x（哈希、查找）

Question

我想知道是否有一种清晰/简洁的方法可以将某些内容添加到集合中，并检查是否在没有 2x 哈希和查找的情况下添加了它。

这就是你可能会做的，但它有 2x 的项目哈希值

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 (!=)

Answer 3

@Sylvain Leroux 的答案版本确保用于添加的标记是唯一的（不与添加的任何值冲突）。

def cache():
  s = {}
  setdefault = s.setdefault
  sentinel = object()

  def add(x):
    return setdefault(x, sentinel) is not sentinel

  return add