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

追加するすべてのリストは、2 番目の要素 (コンストラクターの引数でpush制御します) に関して順番に並べられます。key=lambda x:x[1]を呼び出して、要素を 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 に答える