按顺序将项目插入到嵌套列表中

Question

假设我有一个嵌套的列表如下：

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

当前列表（按照中间值的字母顺序）已经排好序，我希望将值"insert_me"插入到嵌套列表的正确位置。为了保持字母顺序，需要在包含'Bob'和'John'的列表之间添加。我知道通常使用bisect来处理此类列表，但不知道如何处理嵌套列表。

- user1789376

---

最终，如果你要执行大量插入操作，树可能是更好的数据结构。 - mgilson

Answer 1

请看Python文档中bisect的示例：

bisect()函数与sorted()函数不同，因为对于bisect()函数来说，使用key或reversed参数是没有意义的，因为这会导致设计效率低下（连续调用bisect()函数时将无法“记住”所有先前的key查找）。

相反，更好的方法是搜索预先计算好的键列表以找到所需记录的索引：

>>> 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])

---

更新：

进行了插入/二分、追加/排序和堆解决方案的性能比较：

# 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

- isedev

---

这样做的问题在于，每次插入新元素时都需要重新构建键，这将破坏你的O(logn)效率。（当然，insert本身就是O(n)，所以......它已经比你想要的更糟糕了......） - mgilson

但是，键列表不可以被重新构建时缓存起来以保持O(nlogn)效率吗？ - user1789376

您可以随后使用bisect_left插入键，因此2O(n)。但我同意mgilson的观点-如果有许多插入，则树结构可能更适合。 - isedev

@isedev -- 你提到更新键列表是个好主意。不知为何我之前没有想到过。但如果最终列表非常大，我仍然认为列表不是适当的数据结构。使用某种形式的AVL树可能更好。 - mgilson

Answer 2

我建议您针对您的问题使用堆的特化版本。可以从此答案中获取堆类，您的代码将如下所示：

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一个接一个地按顺序获取元素。

- halex

Answer 3

你可以使用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])

Sorted()

- Jroosterman

---

这样做非常低效 - 每次插入后都要对列表进行排序... 另外，使用operator.getitem(1)而不是lambda更清晰（在我看来）。 - isedev

是的，我确实考虑过这个。然而，意图是要重复地将新子列表插入到嵌套列表中，如果每次插入后都必须对列表进行排序，那么它将极大地影响效率。 - user1789376

是的，这可能会变得有些繁琐。如果只在需要查看列表内容时进行操作，那会更好。 - Jroosterman