假设我有一个嵌套的列表如下:
nested_list=[[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me=[122,'George','AL']
当前列表(按照中间值的字母顺序)已经排好序,我希望将值"insert_me"插入到嵌套列表的正确位置。为了保持字母顺序,需要在包含'Bob'和'John'的列表之间添加。我知道通常使用bisect来处理此类列表,但不知道如何处理嵌套列表。
假设我有一个嵌套的列表如下:
nested_list=[[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me=[122,'George','AL']
当前列表(按照中间值的字母顺序)已经排好序,我希望将值"insert_me"插入到嵌套列表的正确位置。为了保持字母顺序,需要在包含'Bob'和'John'的列表之间添加。我知道通常使用bisect来处理此类列表,但不知道如何处理嵌套列表。
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
insert
本身就是O(n),所以......它已经比你想要的更糟糕了......) - mgilsonimport 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
一个接一个地按顺序获取元素。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])
operator.getitem(1)
而不是lambda更清晰(在我看来)。 - isedev