4

引数として渡す特定の値よりも大きい並べ替えられたリストの最初の数値を見つける関数を Python で作成しようとしています。これを達成するために単純なリスト内包表記を使用する例をオンラインで見つけましたが、私の目的のためには、この操作を頻繁に大きなリストで実行する必要があるため、線形時間で実行される検索はコストがかかりすぎます。

これを達成するために反復二分探索のような関数を書くことにクラックがありましたが、それが正しく機能しないいくつかのエッジケースに出くわしています。ちなみに、リストに大きな項目がない場合は、この関数は必要ありません。ここに私の既存の機能があります：

def findFirstLarger(num, sortedList):
    low = 0; 
    high = len(sortedList) - 1

    mid = -1
    while True:
        print("low: " + str(low) + "\t high: " + str(high))
        if (low > high):
            print("Ah geez, low is " + str(low) + " and high is " + str(high))
            return # debugging, don't want this to happen
        if low == high:
            return sortedList[low]
        else:
            mid = (low + high) / 2;
            if num == sortedList[mid]:
                return sortedList[mid]
            elif num > sortedList[mid]:
                low = mid + 1
            else:
                high = mid - 1

この関数が機能しない 1 つのケースは次のとおりです。

>>> somenumbers=[n*2 for n in range(131072)]
>>> somenumbers[-5:]
[262134, 262136, 262138, 262140, 262142]


>>> binsearch.findFirstLarger(262139,somenumbers)
low: 0   high: 131071
low: 65536   high: 131071
low: 98304   high: 131071
low: 114688  high: 131071
low: 122880  high: 131071
low: 126976  high: 131071
low: 129024  high: 131071
low: 130048  high: 131071
low: 130560  high: 131071
low: 130816  high: 131071
low: 130944  high: 131071
low: 131008  high: 131071
low: 131040  high: 131071
low: 131056  high: 131071
low: 131064  high: 131071
low: 131068  high: 131071
low: 131070  high: 131071
low: 131070  high: 131069
Ah geez, low is 131070 and high is 131069

ここで正しい結果は になります262140。これは、リスト内の より大きい最初の数値だから262139です。

実際に機能するこれのよりクリーンな実装を推奨できる人はいますか? これがそれほど難解な問題になるとは思いませんでしたが、まだ解決策を見つけることができませんでした。

4

2 に答える 2

21

bisectモジュールを試しましたか？

def find_ge(a, key):
    '''Find smallest item greater-than or equal to key.
    Raise ValueError if no such item exists.
    If multiple keys are equal, return the leftmost.

    '''
    i = bisect_left(a, key)
    if i == len(a):
        raise ValueError('No item found with key at or above: %r' % (key,))
    return a[i]

find_ge(somenumbers, 262139)

low > high（1）が有効な終了ケースであるというコードは間違っています。(2) で停止しないでください。low == highたとえば、 の場合に間違ったインデックスが返さnum == 3れますsomenumbers。

于 2010-08-24T12:46:11.240 に答える
0

bisect 関数を使用しない実装が必要な場合は、次のコードを試すことができます。

def findFirstLargerOrEqual(num, sortedList):
    '''Finds the smallest index in the sortedList
    of the element which is greater-than or equal to num'''

    slen = len(sortedList)
    start = 0

    while slen > 0:
        m = start + slen//2

        if sortedList[m] < num:
            slen = slen - (m+1 - start)
            start = m+1
            continue

        if start < m and sortedList[m-1] >= num:
            slen = m - start
            continue

        return somenumbers[m]

    raise ValueError('Not found')

somenumbers=[n*2 for n in range(131072)]
print(findFirstLargerOrEqual(262139, somenumbers)) #output: 262140
于 2014-12-12T23:32:50.193 に答える