文章来自《Python cookbook》.

翻译仅仅是为了个人学习,其它商业版权纠纷与此无关!

-- Zoom.Quiet [2004-08-11 17:18:39]

在一个嵌入的序列中发现一个条目的深度索引

2.11 Finding the Deep Index of an Item in an Embedded Sequence 在一个嵌入的序列中发现一个条目的深度索引

Credit: Brett Cannon

问题 Problem

You need to find the deep index of an item in an embedded sequence (i.e., the sequence of indexes that will reach the item when applied one after the other to peel off successive layers of nesting). For example, the 6 in 1,2],[3,[4,[5,6],7,[8,9]] has the deep index of [1,1,1,1].

你需要在一个嵌入的序列中发现一个条目的深度索引(也就是, 在其他的剥离了嵌套的连续的层次以后, 当应用一个的时候, 获得条目的索引的序列)。 例如,6在1,2],[3,[4,[5,6],7,[8,9]]有[1,1,1,1]的深度索引。

解决 Solution

Lists can be nested (i.e., items of lists can, in turn, be lists), but it takes some care to unnest them when we need to reach for an item:

List能够被嵌套(也就是说,list的条目能一次被列出),但是当我们需要伸手获得一个条目的时 候,它需要关注解开嵌套。

   1 import sys, types
   2 
   3 class Found(Exception): pass
   4 
   5 _indices = xrange(sys.maxint)
   6 
   7 def _is_sequence(obj):
   8     return isinstance(obj, types.ListType) or isinstance(obj, types.TupleType)
   9 
  10 def deepindex(sequence, goal, is_subsequence=_is_sequence):
  11     """ deepindex(sequence, goal) -> index list """
  12     def helper(sequence, index_list, goal=goal):
  13         for item, index in zip(sequence, _indices):
  14             if item==goal:
  15                 raise Found, index_list+[index]
  16             elif is_subsequence(item):
  17                 helper(item, index_list+[index])
  18 
  19     try: helper(sequence, [])
  20     except Found, index_list: return index_list
  21     else: return -1
  22 
  23 if _ _name_ _=='_ _main_ _':
  24     print deepindex([[1,2],[3,[4,[5,6]]],7,[8,9]], 6)
  25     print deepindex([[1,2],[3,[4,[5,6]]],7,[8,9]], 66)

讨论 Discussion

This recipe is handy when you have deeply nested sequences and thus need something better than somelist.index(item) to get the index with which an item can be retrieved from the list. It also works as a way to determine if an item is in a deep sequence, regardless of the item's location within the nested sequence. The recipe is coded to work with Python 2.0 or later.

当有有深度的嵌套序列并且需要一些比somelist.index(item)好的东西去得到从list中能够获取一 个条目的索引的时候,这个配方是便利的。它的工作方式也有为一种去决定是否一个条目是在一个 深度的序列中,而不管条目的位置在嵌套的序列中。配方的代码工作在python2.0或者以后。

The nested helper function is recursive. helper iterates on its argument sequence, examining each item. When the current item equals goal, the search is finished, and helper breaks out of whatever number of levels of recursion it's in, using the following statement:

嵌套的helper函数是递归的。 Helper在它的参数序列上迭代,检查每一个条目。当当前的条目等于目标时,查找结束。并且help er使用下面的句子来跳出它所在的不管多少级的递归:

raise Found, index_list+[index] 

When the current item is a nested sequence, helper calls itself recursively on the subsequence, with an updated index_list. If the recursive call returns normally, that branch of the search has proved fruitless (successful searches don't return normally, but rather raise a Found exception), so helper keeps looking. Note that helper checks for nested sequences via type tests for tuples and lists specifically; see Recipe 1.13 for alternative ways to perform this check.

当当前的条目是一个嵌套的序列,helper在带有一个更新的index_list的子序列上递归的调用它自 己。如果递归调用正常返回,查找的分支证明没有结果(成功的查找不正常返回,而是引发一个Fo und的异常),所以helper保持原样。注意,helper通过测试特定的tuple和list来检查嵌套的序列 。为了可选的方法去执行这个检查,请看配方1.13 。

This recipe is an interesting, although controversial, show-off for the concept of raising an exception as a way to return a value from deeply nested recursive calls. If using exceptions as building blocks for alternative control structures is ever appropriate, this case for their application surely would be. We avoid having to arrange some artificial means of signaling "found" versus "not found," and, even better, we avoid having to arrange for the complexity of returning from a deep stack of calls when the item has been found. In any case, this usage surely underscores how, in Python, exceptions can be used for conditions that are not errors, and indeed not even truly exceptional.

这个配方尽管是有争议的,但对于把引发一个异常作为一种途径从深度的嵌套递归调用中返回值的 概念来说,它是有趣的,可以炫耀的。如果为 可选择的控制结构来使用异常作为一个构建的块是合适的。这个案例对他们的应用来说的确是。我 们避免了不得不安排一些人工的“找到”对“没找到”的引号方法,并且,更好的是,我们避免了 不得不为当一个条目被发现的时候,从一个深度调用堆栈返回的复杂性。在任何情况下,在python 里,这个用法的确强调对于不是错误的条件,异常怎样能被使用,并且甚至不是一个真正的异常。

参考 See Also

PyCkBk-1-13--Recipe 1.13; documentation for the range built-in function in the Library Reference