14

私は口述のリストを持っています、このようなもの：

test_data = [
    { 'offset':0, 'data':1500 },
    { 'offset':1270, 'data':120 },
    { 'offset':2117, 'data':30 },
    { 'offset':4055, 'data':30000 },
]

dictアイテムは、データに従ってリスト内でソートされ'offset'ます。実際のデータははるかに長くなる可能性があります。

私がやりたいのは、特定のオフセット値を指定してリスト内のアイテムを検索することです。これは、正確にはそれらの値の1つではありませんが、その範囲内です。だから、二分探索は私がやりたいことです。

私は今、Pythonbisectモジュールに気づきました。これは、既成の二分探索です。すばらしいですが、この場合は直接使用できません。自分のニーズに適応する最も簡単な方法は何だろうと思ってbisectいます。これが私が思いついたものです：

import bisect

class dict_list_index_get_member(object):
    def __init__(self, dict_list, member):
        self.dict_list = dict_list
        self.member = member
    def __getitem__(self, index):
        return self.dict_list[index][self.member]
    def __len__(self):
        return self.dict_list.__len__()

test_data_index_get_offset = dict_list_index_get_member(test_data, 'offset')
print bisect.bisect(test_data_index_get_offset, 1900)

それは印刷します：

2

私の質問は、これが私がやりたいことをするための最良の方法ですか、それとも他のもっと簡単でより良い方法がありますか？

4

5 に答える 5

4

できることはこれ

class OffsetWithAttributes( object ):
    def __init__( self, offset, **kw ):
        self.offset= offset
        self.attributes= kw
    def __eq__( self, other ):
        return self.offset == other.offset
    def __lt__( self, other ):
        return self.offset < other.offset
    def __le__( self, other ):
        return self.offset <= other.offset
    def __gt__( self, other ):
        return self.offset > other.offset
    def __ge__( self, other ):
        return self.offset >= other.offset
    def __ne__( self, other ):
        return self.offset != other.offset

listこれにより、単純なOffsetWithAttributesインスタンスを作成できるようになります。bisectアルゴリズムは、定義された演算子を使用することに完全に満足する必要があります。

を使用できますsomeOWA.attributes['data']。

または

    def __getattr__( self, key ):
        return self.attributes[key]

それはOffsetWithAttributesよりのようにする必要がありdictます。

于 2009-08-28T00:55:35.203 に答える
4

ここでの通常のパターンは、属性によるソート、装飾、操作、非装飾に似ています。したがって、この場合は、装飾してから呼び出すだけです。ただし、これを O(logn) にしたいのに対し、decorate は O(n) になるため、これを避ける必要があります。したがって、私はあなたの方法が最善だと思います。

于 2009-08-27T23:56:26.517 に答える
4

実際のデータはもっと長くなる可能性があると言うとき、それによってオフセット値のリストを手元に置いておくことが妨げられますか?

offset_values = [i['offset'] for i in test_data]
bisect.bisect(offset_values, 1900)

あなたの方法は私にはうまくいくようです。

于 2009-08-27T23:58:14.077 に答える