3

假设我有一个这样的嵌套列表：

nested_list=[[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me=[122,'George','AL']

该列表当前按每个子列表的中间值排序（按字母顺序），我想将值 insert_me 添加到嵌套列表中的正确位置。为了保持字母顺序，需要在其中包含“Bob”和“John”的列表之间添加它。我知道 bisect 通常会用于这样的任务，但不明白如何将 bisect 用于这样的嵌套列表。

4

3 回答 3

5

请参阅 Python 文档中的示例bisect：

与 sorted() 函数不同，bisect() 函数具有键或反转参数是没有意义的，因为这会导致设计效率低下（对 bisect 函数的连续调用不会“记住”所有先前的键查找） .

相反，最好搜索预先计算的键列表以找到相关记录的索引：

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)

所以在你的情况下：

nested_list = [[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me = [122,'George','AL']                                
keys = [r[1] for r in nested_list]
nested_list.insert(bisect.bisect_left(keys,insert_me[1]),insert_me)
[[123, 'Aaron', 'CA'],
 [124, 'Bob', 'WY'],
 [122, 'George', 'AL'],
 [125, 'John', 'TX']]

为避免keys每次都重新构建，请在其中插入新值keys：

keys.insert(bisect_left(keys,insert_me[1]),insert_me[1])

更新：

在 insert/bisect、append/sorted 和 heapq 解决方案之间进行了一些性能比较：

# elements  heapq   insert/bisect  append/sorted
10,000      0.01s   0.08s           2.43s         
20,000      0.03s   0.28s          10.06s
30,000      0.04s   0.60s          22.81s
于 2013-03-22T19:47:17.793 回答
4

我会为您的问题使用堆的专门化。从此答案中获取堆类，您的代码将是：

import heapq

class MyHeap(object):
    def __init__(self, initial=None, key=lambda x:x):
        self.key = key
        if initial:
            self._data = [(key(item), item) for item in initial]
            heapq.heapify(self._data)
        else:
            self._data = []

    def push(self, item):
        heapq.heappush(self._data, (self.key(item), item))

    def pop(self):
        return heapq.heappop(self._data)[1]

h = MyHeap([[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']], key=lambda x:x[1])
h.push([122,'George','AL'])
for _ in xrange(4):
    print h.pop()

您添加的每个列表都push将相对于第二个元素（我们使用key=lambda x:x[1]构造函数中的参数控制）按顺序排列。您可以通过调用来按顺序获取元素pop。

于 2013-03-22T20:05:16.697 回答
2

您可以使用按字母顺序排列列表sorted()。

nested_list=[[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me=[122,'George','AL']

nested_list.append(insert_me)
nested_list=sorted(nested_list, key=lambda x:x[1])

排序（）

于 2013-03-22T19:50:47.917 回答