10

特異値を a のキーとしてハッシュできることを知っていますdict。たとえば5、 のキーの 1 つとしてハッシュできますdict。

現在、値の範囲をハッシュする必要があるという問題に直面しています。

基本的に、これを行うにはより高速な方法が必要です。

if 0 <= x <= 0.1:
    # f(A)
elif 0.1 <= x <= 0.2:
    # f(B)
elif 0.2 <= x <= 0.3:
    # f(C)
elif 0.3 <= x <= 0.4:
    # f(D)
elif 0.4 <= x <= 0.5:
    # f(E)
elif 0.5 <= x <= 0.6:
    # f(F)

ここで、xはfloat任意精度のパラメータです。

私が考えることができる最速の方法はハッシュですが、ここに問題があります:(0.1, 0.2)キーとして使用できますが、それでも O(n) ランタイムがかかり、最終的にはelifs のスルーよりも良くありません (私はキーを反復し、確認するかどうかを確認しますkey[0] <= x <= key[1])。

ハッシュテーブルをチェックして取得できるように、値の範囲をハッシュする方法はあり0.15ます#execute Bか?

そのようなハッシュが不可能な場合、これの実行時間を改善するにはどうすればよいでしょうか? 線形ランタイムが十分に速くないほど大きなデータセットを扱っています。

編集:チーケンの答えに応えて、間隔が規則的であると想定できないことに注意する必要があります。実際のところ、そうではないことはほぼ保証できます。

コメントでのリクエストに応えて、遺伝的アルゴリズムでフィットネスベースの選択を実装しようとしてこれを行っていることを言及する必要があります。アルゴリズム自体は宿題ですが、具体的な実装は実験データを生成するための実行時間を改善することだけです。

4

4 に答える 4

12

他の人が指摘したように、これに対して得られる最良のアルゴリズムは、O(1) ではなく O(log N) であり、ソートされたリストを介した二分探索のラインに沿ったものです。

Python でこれを行う最も簡単な方法は、bisect標準モジュールhttp://docs.python.org/library/bisect.htmlを使用することです。特に、セクション 8.5.2 の数値テーブルの検索に関する例に注意してください。これは、まさにあなたが行っていることです。

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

grades文字列を関数のリストに置き換え、breakpointsリストを下限しきい値のリストに置き換えます。

于 2012-01-28T06:21:16.133 に答える
4

必ずしも値の範囲全体をハッシュする必要はありません。たとえば、上記のスケールで 0.15 が与えられた場合、それを 0.2 (小数点以下の最初の桁) に切り上げ、代わりに 0.2 をハッシュすることができます。

これはどの程度効率的でなければなりませんか？試すことができる代替手段は、二分探索です。間隔値をリストに並べ替えて格納し、それに対してバイナリ検索を実行します。例えば：

sorted_list = [ (0.1, function1), (0.2, function2), ....(0.6, function6) ]

次に、バイナリ検索を実行して、x よりも大きい最小の要素を見つけます。これにより、O(log(n)) が生成されます。

于 2012-01-28T05:43:41.937 に答える
3

ランタイムを改善するために、二分探索を実装できます。

それ以外の場合は、間隔のしきい値を試行することができます。

編集:実装を提案させてください:

class IntervalHash():
    def __init__(self,SortedList):
        #check it's sorted 
        self.MyList = []
        self.MyList.extend(SortedList) 
        self.lenlist = len(self.MyList)
    def get_interval(self,a):
        mylen = self.lenlist 
        mypos = 0
        while mylen > 1:
            mylen = (mylen/2 + mylen % 2)
            if mypos + mylen > self.lenlist - 1:
                if self.MyList[self.lenlist - 1] < a:
                    mypos = self.lenlist - 1
                break
            if self.MyList[mypos + mylen] < a:
                mypos += mylen
        if mypos == 0:
            if self.MyList[0] > a: 
                return ("-infty",self.MyList[0],0)
        if mypos == self.lenlist - 1:
            return (self.MyList[mypos],"infty",0)
        return (self.MyList[mypos],self.MyList[mypos+1],0)

A = [0.32,0.70,1.13]
MyHasher = IntervalHash(A)
print "Intervals are:",A
print 0.9 ," is in ",MyHasher.get_interval(0.9)
print 0.1 ," is in ",MyHasher.get_interval(0.1)
print 1.8 ," is in ",MyHasher.get_interval(1.8)

さらなる編集と改善を歓迎します！トライ アプローチはもっと複雑で、私の意見では、低レベル言語により適しています。

于 2012-01-28T05:48:17.977 に答える
3

間隔が規則的である場合は、オペランドを各範囲の最小値にスケーリングしてから、その結果を適切なハンドラーにそれらの下限をマッピングするfloorことに直接渡すことができます。dict

指定した範囲を使用した実装例。

# Integerize our 0.1 width intervals; scale by x10
handlerDict = {}
handlerDict[0] = lambda x: ... # 0.1
handlerDict[1] = lambda x: ... # 0.2
handlerDict[2] = lambda x: ... # 0.3
...

# Get the right handler, scaling x by x10; handle
handlerDict[int(10*x)](x, ...)
于 2012-01-28T05:34:52.097 に答える