3

いくつかの並べ替えられたリストがあり、それらを 1 つの大きな並べ替えられたリストに追加したいと考えています。これを行う最も効率的な方法は何ですか?

これが私がすることですが、それはあまりにも非効率的です:

big_list=[]
for slist in sorted_lists: # sorted_lists is a generator, so lists have to be added one by one
    big_list.extend(slist)
big_list.sort()

以下は sorted_lists の例です:

sorted_lists のサイズ = 200

sorted_lists=1668 の最初の要素のサイズ

sorted_lists=[
['000008.htm_181_0040_0009', '000008.htm_181_0040_0037', '000008.htm_201_0041_0031', '000008.htm_213_0029_0004', '000008.htm_263_0015_0011', '000018.htm_116_0071_0002', '000018.htm_147_0046_0002', '000018.htm_153_0038_0015', '000018.htm_160_0060_0001', '000018.htm_205_0016_0002', '000031.htm_4_0003_0001', '000032.htm_4_0003_0001', '000065.htm_5_0013_0005', '000065.htm_8_0008_0006', '000065.htm_14_0038_0036', '000065.htm_127_0016_0006', '000065.htm_168_0111_0056', '000072.htm_97_0016_0012', '000072.htm_175_0028_0020', '000072.htm_188_0035_0004'….],
['000018.htm_68_0039_0030', '000018.htm_173_0038_0029', '000018.htm_179_0042_0040', '000018.htm_180_0054_0021', '000018.htm_180_0054_0031', '000018.htm_182_0025_0023', '000018.htm_191_0041_0010', '000065.htm_5_0013_0007', '000072.htm_11_0008_0002', '000072.htm_14_0015_0002', '000072.htm_75_0040_0021', '000079.htm_11_0005_0000', '000079.htm_14_0006_0000', '000079.htm_16_0054_0006', '000079.htm_61_0018_0012', '000079.htm_154_0027_0011', '000086.htm_8_0003_0000', '000086.htm_9_0030_0005', '000086.htm_11_0038_0004', '000086.htm_34_0031_0024'….],
['000001.htm_13_0037_0004', '000008.htm_48_0025_0006', '000008.htm_68_0025_0008', '000008.htm_73_0024_0014', '000008.htm_122_0034_0026', '000008.htm_124_0016_0005', '000008.htm_144_0046_0030', '000059.htm_99_0022_0012', '000065.htm_69_0045_0017', '000065.htm_383_0026_0020', '000072.htm_164_0030_0002', '000079.htm_122_0030_0009', '000079.htm_123_0049_0015', '000086.htm_13_0037_0004', '000109.htm_71_0054_0029', '000109.htm_73_0035_0005', '000109.htm_75_0018_0004', '000109.htm_76_0027_0013', '000109.htm_101_0030_0008', '000109.htm_134_0036_0030']]

編集

回答ありがとうございます。並べ替えられたリストがシミュレートされていないことをより明確にする必要があったと思いますが、それらを取得するためにいくつかの大きなファイルを繰り返し処理しています。したがって、上記の大まかなコードで示しているように、それらを 1 つずつ追加する必要があります。

4

3 に答える 3

6

標準ライブラリはheapq.merge、この目的のために以下を提供します。

>>> a=[1,3,5,6]
>>> b=[2,4,6,8]
>>> c=[2.5,4.5]
>>> list(heapq.merge(a,b,c))
[1, 2, 2.5, 3, 4, 4.5, 5, 6, 6, 8]
>>>

または、あなたの場合：

big_list = list(heapq.merge(*sorted_lists))

heapq.mergeiterable を返すため、リストを作成する必要がないことに注意してください。

for item in heapq.merge(*sorted_lists):

ドキュメントの引用：

に似てsorted(itertools.chain(*iterables))いますが、イテラブルを返します。データを一度にすべてメモリにプルするのではなく、各入力ストリームが既に並べ替えられていると想定します (最小から最大)。

于 2013-10-30T15:56:53.983 に答える
3

heapqモジュールを使用して、次にソートされた値を選択するリストを追跡します。

import heapq

def merge(*iterables):
    h = []
    for it in map(iter, iterables):
        try:
            next = it.next
            h.append([next(), next])
        except StopIteration:
            pass
    heapq.heapify(h)

    while True:
        try:
            while True:
                v, next = s = h[0]
                yield v
                s[0] = next()
                heapq._siftup(h, 0)
        except StopIteration:
            heapq.heappop(h)
        except IndexError:
            return

これにより、すべてのリストがヒープにプッシュされ、次の値でソートされたままになります。これが最小値を生成するたびに、使用された iterable からの次の値でヒープが更新され、ヒープが再度並べ替えられます。

これは本質的にリストの[next_value, iterable]リストを保持し、これらは によって効率的にソートされnext_valueます。

使用法：

for value in merge(*sorted_lists):
    # loops over all values in `sorted_lists` in sorted order

また

big_list = list(merge(*sorted_lists))

すべての値が効率的に並べ替えられた新しい大きなリストを作成します。

この正確な実装が関数heapqとしてモジュールに追加されたため、次のことができます。heapq.merge()

from heapq import merge

big_list = list(merge(*sorted_lists))
于 2013-10-30T15:34:10.570 に答える