在Python中查找嵌套元组中是否存在字符串

Question

在Python 2.7.x中，最好（也是最快）的方式是什么，用于检查嵌套元组中是否存在字符串（或任何其他数据类型）？

例如：

RECIPES = (
    ('apple', 'sugar', 'extreme_Force'),
    ('banana', 'syrup', 'magical_ends'),
    ('caramel', 'chocolate', 'pancake_MONSTER'),
    ('banana',('someAnother','banana'))
)

需要检查这个元组是否包含 banana，并返回其位置索引，此时应返回 1,0。

同时，这些元组的嵌套深度可以是任意的。

- Nandeep Mali

---

当你说“最快”时，每个元组中可能有多少项（在顶级RECIPES中有多少项，平均有多少项配料）？ - dbr

我猜这个位置是“1,0”？ - Ashwini Chaudhary

嵌套到任意深度是什么意思？你的例子是一个扁平列表 - 如果你想要一个能处理它的解决方案，你应该提供一个数据结构和期望的嵌套食谱返回值。 - Dave

@Dave -- 这不是一个平面的列表。它是一个包含元组的元组。 - mgilson

你能详细说明一下“嵌套”的部分吗？当一个元组包含其他元组时，它是否仅包含元组还是字符串也包括在内？ - Martijn Pieters

@MartijnPieters 在我的情况下，只有元组。否则混合起来会太复杂了。 - Nandeep Mali

Answer 1

递归多位置索引：

import sys
from collections import Sequence,defaultdict

#making code python3-compatible
if sys.version_info[0] == 3:
    basestring = str

def buildLocator(tree):
    locator = defaultdict(list)
    def fillLocator(tree, locator,location):
        for index,item in enumerate(tree):            
            if isinstance(item,basestring):
                locator[item].append(location+(index,))
            elif isinstance(item,Sequence):
                fillLocator(item,locator, location+(index,))
    fillLocator(tree,locator,())
    return locator

RECIPES = (
    ('apple', 'sugar', 'extreme_Force'),
    ('banana', 'syrup', 'magical_ends'),
    ('caramel', 'chocolate', 'pancake_MONSTER'),
    ('banana',('someAnother','banana'))
)
locator = buildLocator(RECIPES)

print(locator['banana'])

打印输出

[(1, 0), (3, 0), (3, 1, 1)]

- Odomontois

---

最好使用basestring，因为它被标记为Python2.7。 - mgilson

我曾以为只有我会加入多余的 if sys.version_info[0] >= 3 来保持向后兼容性 :) - mgilson

Answer 2

如果您只需要第一个匹配项，生成器可以很好地完成这项任务。

def find_location(text):
    try:
        return next((i, j) 
            for i, t in enumerate(RECIPES)
            for j, v in enumerate(t)
            if v == text)
    except StopIteration:
        return (None, None)  # not found

使用方法：

>>> find_location('banana')
(1, 0)
>>> find_location('apple')
(0, 0)
>>> find_location('chocolate')
(2, 1)
>>> find_location('spam')
(None, None)

注意，第一个值是指向整个RECIPES序列的索引，第二个值是指向单个元组的索引；RECIPES[1][0] == 'banana'

- Martijn Pieters

---

这很棒，也很干净。但多位置解决方案是所期望的。 :) 谢谢！ - Nandeep Mali

Answer 3

使用for循环查找项目是否存在，一旦找到就立即退出循环。

In [48]: RECIPES = (
   ....:     ('apple', 'sugar', 'extreme_Force'),
   ....:     ('banana', 'syrup', 'magical_ends'),
   ....:     ('caramel', 'chocolate', 'pancake_MONSTER'),
   ....: )

In [49]: for i,x in enumerate(RECIPES):
   ....:     if 'banana' in x:
   ....:         print i,x.index('banana')
   ....:         break
   ....:         
   ....:         
1 0

- Ashwini Chaudhary

---

你会两次搜索每一行；首先使用 in 测试，然后使用 .index()。 - Martijn Pieters

这也仅在配方嵌套1级深度时起作用。对于任意嵌套，您需要更多的工作。 - mgilson

@MartijnPieters，没错，但是由于我相信in和index都经过了高度优化，所以它可能仍然很快。与您的解决方案进行比较将会很有趣。 - Mark Ransom

@MarkRansom -- 你可以通过尝试使用index，然后捕获如果未找到该值而引发的ValueError来避免检查两次... 当然，except可能会很耗费时间，所以这可能不会使它更快... - mgilson

@mgilson 我正要写同样的东西（try-except）。 - Ashwini Chaudhary

Answer 4

为什么不尝试使用numpy呢？

import numpy as np
RECIPES = (
    ('apple', 'sugar', 'extreme_Force'),
    ('banana', 'syrup', 'magical_ends'),
    ('caramel', 'chocolate', 'pancake_MONSTER'),
)
np_recipes = np.array(recipes)
indices = zip(*np.where( np_recipes == 'banana' ) ) #[(1, 0)]

这适用于您的示例，因为数据有很好的排序。我想应该注意到，这不适用于您所要求的任意嵌套（但我会把它放在这里，以防其他人发现类似但更受限制的问题）。

- mgilson

---

这很不错。但是这里的数据稍微有些随意。我会为将来的参考做个要点。你可以创建一个问题并自己回答以供参考。 - Nandeep Mali