在元组集中的运算符中使用 python
Use in operator in set of tuples python
我在尝试检查某个元素是否属于 Python 中的集合时遇到问题。 （我的集合包含大约 60 万个字符串元组。）
我正在寻找一种解决方案，该解决方案利用 in 运算符的优势来检查某个值是否是集合中元组的元素。
我找到了如下解决方案：
# S set of tuples, I'm checking if v is the second element of a tuple
any( y == v for (_, y) in S )
但这有一个 O(n) 复杂度。
Python 文档说 IN 运算符的平均复杂度是 O(1)。
编辑
我的问题是：如何使用[的速度检查一个元素是否是集合中至少一个元组的first/second/...元素=12=]运算符。
容器测试的复杂性取决于对象类型，而不是操作员，因为操作委托给了容器。测试列表中的包含是 O(n)，集合中的包含是 O(1)。
但是，您不是在测试集合中的包容性，而是在一堆元组中测试包容性（元组的容器 无能为力 ）。如果不进一步处理，你不能比这里的 O(n) 做得更好。
您可以创建和维护单独的数据结构，例如，跟踪元组中包含的单独值以及元组本身，然后针对这些单独的数据结构进行测试。这会增加内存需求，但会降低计算成本。
您将在程序的整个生命周期内分摊保持该结构最新的成本（只会稍微增加构建数据结构的恒定成本），并且在 return 中您得到 O (1) 对您的收容测试的操作。仅当您需要针对不同的值多次执行此测试时才执行此操作。
average complexity of the IN operator is O(1)
这对于集合中的成员资格检查或任何使用散列 table 来存储它的项目（如字典）的容器都是正确的。
而且它的操作与以下 in:
完全不同
for (_, y) in S
in 只是 for 循环语法的一部分。
此外，如果您想获取包含特定字符串的元组，您可以使用列表理解而不是 any:
[item for item in S if my_str in item]
如果您想利用 set 的成员资格检查，您应该使用集合而不是元组，但由于它们不可散列，因此您不能在 [=17] 中使用它们=] 在这种情况下，您可以使用 frozenset() 代替。
如果您只想检查满足特定条件的项目是否存在，您可以在 any 中使用以下生成器表达式：
any(my_str in item for item in S)
毕竟，由于您的集合完全有可能成为字典，因此您可以创建字典而不是集合，然后只需使用 my_str in my_dict 检查成员资格。你的字典应该是这样的：{'luca': 1, 'mario': 2 , 'franco': 3}
回答所提出的问题（注意：这不是您通常想要解决它的方式，因为它保证了 O(n) 行为，因为 in 运算符没有保证 O(1)，在这种情况下，永远不会）。
您可以使用 in 运算符，将每个 tuple 中的无关值映射掉。使用 C 级内置函数完成后，对于足够大的输入，这将 运行 比您的 any 表达式快，但差异很小（对于足够大的输入，值可能加快 10%在那里）：
# At top of file
from future_builtins import map # Only on Py2, to get lazy map
from operator import itemgetter
v in map(itemgetter(1), S)
这是有效的，因为 in 运算符是为任意迭代器实现的，类似于 any 的惰性检查，一次提取一个值，与 v 进行比较，并且短-如果发现命中，则退出。
就像我说的，这是 O(n)；在现实世界中，如果你可能不止一次地做这个测试，你可能只想做一个 set 的目标并重用它，或者 dict 将目标映射到关联的值如果需要，获取 O(1) 支票。其他答案已经充分涵盖了这一点。
我在尝试检查某个元素是否属于 Python 中的集合时遇到问题。 （我的集合包含大约 60 万个字符串元组。）
我正在寻找一种解决方案，该解决方案利用 in 运算符的优势来检查某个值是否是集合中元组的元素。
我找到了如下解决方案：
# S set of tuples, I'm checking if v is the second element of a tuple
any( y == v for (_, y) in S )
但这有一个 O(n) 复杂度。
Python 文档说 IN 运算符的平均复杂度是 O(1)。
编辑
我的问题是：如何使用[的速度检查一个元素是否是集合中至少一个元组的first/second/...元素=12=]运算符。
容器测试的复杂性取决于对象类型，而不是操作员，因为操作委托给了容器。测试列表中的包含是 O(n)，集合中的包含是 O(1)。
但是，您不是在测试集合中的包容性，而是在一堆元组中测试包容性（元组的容器 无能为力 ）。如果不进一步处理，你不能比这里的 O(n) 做得更好。
您可以创建和维护单独的数据结构，例如，跟踪元组中包含的单独值以及元组本身，然后针对这些单独的数据结构进行测试。这会增加内存需求，但会降低计算成本。
您将在程序的整个生命周期内分摊保持该结构最新的成本（只会稍微增加构建数据结构的恒定成本），并且在 return 中您得到 O (1) 对您的收容测试的操作。仅当您需要针对不同的值多次执行此测试时才执行此操作。
average complexity of the IN operator is O(1)
这对于集合中的成员资格检查或任何使用散列 table 来存储它的项目（如字典）的容器都是正确的。
而且它的操作与以下 in:
for (_, y) in S
in 只是 for 循环语法的一部分。
此外，如果您想获取包含特定字符串的元组，您可以使用列表理解而不是 any:
[item for item in S if my_str in item]
如果您想利用 set 的成员资格检查，您应该使用集合而不是元组，但由于它们不可散列，因此您不能在 [=17] 中使用它们=] 在这种情况下，您可以使用 frozenset() 代替。
如果您只想检查满足特定条件的项目是否存在，您可以在 any 中使用以下生成器表达式：
any(my_str in item for item in S)
毕竟，由于您的集合完全有可能成为字典，因此您可以创建字典而不是集合，然后只需使用 my_str in my_dict 检查成员资格。你的字典应该是这样的：{'luca': 1, 'mario': 2 , 'franco': 3}
回答所提出的问题（注意：这不是您通常想要解决它的方式，因为它保证了 O(n) 行为，因为 in 运算符没有保证 O(1)，在这种情况下，永远不会）。
您可以使用 in 运算符，将每个 tuple 中的无关值映射掉。使用 C 级内置函数完成后，对于足够大的输入，这将 运行 比您的 any 表达式快，但差异很小（对于足够大的输入，值可能加快 10%在那里）：
# At top of file
from future_builtins import map # Only on Py2, to get lazy map
from operator import itemgetter
v in map(itemgetter(1), S)
这是有效的，因为 in 运算符是为任意迭代器实现的，类似于 any 的惰性检查，一次提取一个值，与 v 进行比较，并且短-如果发现命中，则退出。
就像我说的，这是 O(n)；在现实世界中，如果你可能不止一次地做这个测试，你可能只想做一个 set 的目标并重用它，或者 dict 将目标映射到关联的值如果需要，获取 O(1) 支票。其他答案已经充分涵盖了这一点。