0

のような並べ替えられたリストの辞書で、d=={1:[1,6,16],2:[1],7:[6]}リスト内のすべての数値 (したがって、リストが空になるキーと値のペアも) をk 効率的に削除するには、指定された値よりも少ないものを使用します。私の場合、d大きくなります。

たとえば、もしそうならk = 15、最終的にはd == {1:[16]}.

を使用して、最初に辞書を初期化しましたd = defaultdict(list)。

私はそれをスピードアップするために使用しようとしbisectましたが、間違いを犯したに違いありません.

リストがソートされているという事実を利用して高速化することは可能ですか?

4

5 に答える 5

3 
>>> d = {1:[1,6,16],2:[1],7:[6]}
>>> for lst in d.values(): lst[:] = [x for x in lst if x >= 16]
... 
>>> d
{1: [16], 2: [], 7: []}
>>> for k in list(d):
...     if not d[k]:
...         del d[k]
... 
>>> d
{1: [16]}

>>> d = {1:[1,6,16],2:[1],7:[6]}
>>> tmp = [(k, [x for x in lst if x >= 16]) for k, lst in d.items()]
>>> d = {k: v for k, v in tmp if v}
>>> d
{1: [16]}

bisect.bisect_left の使用

>>> d = {1:[1,6,16],2:[1],7:[6]}
>>> for k in list(d):
...     d[k] = d[k][bisect.bisect_left(d[k], 16):]
...     if not d[k]:
...         del d[k]
... 
>>> d
{1: [16]}
于 2013-07-26T07:07:29.310 に答える
2

できるよ：

from collections import defaultdict
from bisect import bisect_left
d = {1:[1,6,16],2:[1],7:[6]}
d1 = defaultdict(list)
k = 15
for key, value in d.iteritems():
    temp = value[bisect_left(value, 16):]
    if temp:
        d1[key] = temp

print d1.items()

版画:

[(1, [16])]
于 2013-07-26T07:02:23.693 に答える
1

私は私のこの回答と同じ気持ちを持っています。私が読んだすべての回答は、新しいオブジェクトを作成するように思えます。
私はリストをその場で変更することを好みます。

次のコードでは、各リストの不要なセクションを適切に削除し (リストはソートされているため、簡単です)、EADPコーディング スタイルを尊重します (許可よりも許しを求める方が簡単です) 。

d={1:[1,6,16,32,50],2:[1,5,15],7:[6,7,9],13:[10,12,23,55]}

k = 15
for ki,li in d.items():
    try:
        x = next(x for x in li if x>=k)
    except:
        del d[ki]
    else:
        i = li.index(x)
        li[0:i] = []

print d
# {1: [16, 32, 50], 2: [15], 13: [23, 55]}

.

編集 1

コードを変更しました。d.items()の代わりに反復する義務があるため、あまり良くありませんd.iteritems()。この最後のケースでは、反復中に辞書を変更できません。

.

編集 2

私は試してみましたがbisect_left()、それは確かに最速のソリューションです。この下の 3 番目のコードです。2枚目はRussWのものを修正。最初のものは私の以前のコードです

k = 15

te = clock()
for jj in xrange(10000):
    d={1:[1,6,16,32,50],2:[1,5,15],7:[6,7,9],13:[10,12,23,55]}
    for ki,li in d.items():
        try:
            x = next(x for x in li if x>=k)
        except:
            del d[ki]
        else:
            i = li.index(x)
            li[0:i] = []
print clock() - te
print d
            
print '------------------------------------------'

d={1:[1,6,16,32,50],2:[1,5,15],7:[6,7,9],13:[10,12,23,55]}
te = clock()
for jj in xrange(10000):
    dct={1:[1,6,16,32,50],2:[1,5,15],7:[6,7,9],13:[10,12,23,55]}
    for key, lst in dct.items():
        gn = None
        for i, x in enumerate(lst):
            if x >= k:
                gn = i
                break
        if gn is None:
            del dct[key]
        else:
            dct[key] = lst[gn:]
print clock() - te
print dct
print '------------------------------------------'

te = clock()
for jj in xrange(10000):
    d={1:[1,6,16,32,50],2:[1,5,15],7:[6,7,9],13:[10,12,23,55]}
    for ki,li in d.items():

    i = bisect_left(li,15)
    if i==len(li):
        del d[ki]
    else:
        li[0:i] = []
print clock() - te
print d

結果

0.22918869577
{1: [16, 32, 50], 2: [15], 13: [23, 55]}
------------------------------------------
0.163871665254
{1: [16, 32, 50], 2: [15], 13: [23, 55]}
------------------------------------------
0.100142057161
{1: [16, 32, 50], 2: [15], 13: [23, 55]}
于 2013-07-26T08:02:50.580 に答える
0 
>>> import bisect
>>> d = {1: [1,6,16], 2: [1], 7: [6]}
>>> for k in d.keys():
...     d[k] = d[k][bisect.bisect_left(d[k], 16):]
...     if not d[k]:
...             del d[k]
...
>>> d
{1: [16]}
于 2013-07-26T07:23:04.233 に答える
0 
>>> def sieve(dct, n):
    for key, lst in dct.iteritems():
        gn = None
        for i, x in enumerate(lst):
            if x >= n:
                gn = i
                            break
        if gn is None:
            del dct[key]
        else:
            dct[key] = lst[gn:]


>>> d = {1:[1, 6, 16], 2:[1], 7:[6]}
>>> sieve(d, 15)
>>> d
{1: [16]}
>>>
于 2013-07-26T07:19:22.207 に答える