0

質問は次のとおりです。

まず、Pythonでコーディングしています。ソートされた自然数「givenY」の配列（Numpy配列ですが、何か助けになる場合はリストに変更できます）があります。a=Y[i]2つの指定された値との間にある最初と最後の要素を見つけてポイントしたいと思いますb=Y[i+1]。私はコードを書きましたが、可能な限り厄介な方法の1つで書いたと思います。また、コードが時間的に効率的かどうかはわかりません。ですから、コメントや提案を一から書いていただければ幸いです。Y[i]重要なことは、との間にgivenYの要素がない場合Y[i+1]（startに割り当てることによって処理される） 、多くの例外的な状況があることです-1。私のコードは次のとおりです。

startRes=binSearch(givenY,Y[i]);
endRes=binSearch(givenY,Y[i+1]);        
start=startRes[1]
end=endRes[1];        
if(givenY.size==0 or (givenY.size>0 and givenY[start]<=Y[i])):
    start=startRes[1]+1;
if(endRes[0]):
    end=endRes[1]-1;
if end<start or (givenY.size>0 and (givenY[end]>Y[i+1] or givenY[start]>=Y[i+1])) or givenY[end]<=Y[i]:
    start=-1;


startRes=binSearch(givenY,a);
endRes=binSearch(givenY,b);        
start=startRes[1]
if startRes[0]:
    start=start+1;
end=endRes[1]-1;

そしてこれはbinSearchの実装です：

def binSearch(arr,element):
left=0
right=arr.size;
mid=(left+right)/2
while left<right:
    mid=(left+right)/2
    if(arr[mid]<element):
        left=mid+1;
    elif (arr[mid]>element):
        right=mid;
    else: 
        return True,mid;
return False,left;

いくつかの簡単な入力と出力：

与えられたY=[2,5,8,10]の場合：

  • a = 3、b = 4、出力：値の間にありません（私のコードではstart = -1）
  • a = 2、b = 5、出力：値の間にありません（私のコードではstart = -1）
  • a = 2、b = 9出力：start = 1、end = 2
  • a = 1、b = 10、出力：start = 0、end = 2
  • a = 1、b = 11、出力：start = 0、end = 3
  • a = 11、b = 12、出力：値の間にありません（私のコードではstart = -1）
  • a = 0、b = 2、出力：値の間にありません（私のコードではstart = -1）
  • a = 3、b = 3、出力：値の間にありません（私のコードではstart = -1）
  • a = 5、b = 5、出力：値の間にありません（私のコードではstart = -1）

私が現在働いている場合、bは常にaよりも大きくなります。

どうもありがとう。

4

2 に答える 2

3

返されたインデックスがよくわかりません。たとえば、givenYisと空のリストの場合、とは両方ともstart-1endになります。また、投稿したコードはリスト内の重複する値を処理しません。

手作業でコーディングされた二分探索の代わりに、bisectモジュールを使用できます。詳細については、APIドキュメントを参照してください。

  1. Python3.3-8.6。bisect —配列二分アルゴリズム
  2. Python2.7.3-8.5。bisect —配列二分アルゴリズム

start以下は、とを返す実装でありend、次のプロパティが保持されます。

  1. end-start指定された境界の間にある要素の数に等しい。
  2. list[start:end]指定された境界間のすべての値を含むスライスを返します。
  3. end-start見つかった要素の数に等しい
  4. 値が見つからない場合start==end。

コード：

import unittest

from bisect import bisect_left, bisect_right


def find_range(array, a, b):
    start = bisect_right(array,a)
    end = bisect_left(array,b)
    return (start, end)


class TestCase(unittest.TestCase):
    Y = [1, 3, 5, 10, 15]
    givenY = [3, 4, 5, 6, 7, 8, 9, 10, 11]

    def test_empty_array(self):
        self.assertEqual( (0, 0), find_range([], 1, 2) )

    def test_all_values_larger(self):
        self.assertEqual( (0, 0), find_range([4,5,6], 1, 3) )

    def test_all_values_larger_or_equal(self):
        self.assertEqual( (0, 0), find_range(self.givenY, self.Y[0], self.Y[1]) )

    def test_both_endpoints_inside_list(self):
        self.assertEqual( (1, 2), find_range(self.givenY, self.Y[1], self.Y[2]))
        self.assertEqual( [4], self.givenY[1:2])

    def test_2(self):
        self.assertEqual( (3, 7), find_range(self.givenY, self.Y[2], self.Y[3]) )
        self.assertEqual( [6, 7, 8, 9], self.givenY[3:7])

    def test_no_values_larger_or_equal_to_upper_limit(self):
        self.assertEqual( (8, 9), find_range(self.givenY, self.Y[3], self.Y[4]) )
        self.assertEqual( [11], self.givenY[8:9])


if __name__=="__main__":
    unittest.main()

注：返される開始位置と終了位置は、必要に応じて現在の値に簡単に調整する必要があります。一貫性があることを確認してください。

編集

以下は、与えられたサンプルから理解できる限り、要求された値を返すコードです。ロジックはfind_range()docstringで説明されています。元のコードは、PythonでプログラミングするときにIMHOがより自然に感じるため、保持されます。

import unittest

from bisect import bisect_left, bisect_right


def find_range(array, a, b):
    """Find elements that are greater than a and less than b.
    Returns a tuple (start,end) where array[start] is the first
    value and array[end] is the last value.
    If no value is found, returns start=end=-1.
    """
    start = bisect_right(array,a)
    end = bisect_left(array,b)
    if start==end:
        return (-1,-1)
    else:
        return (start, end-1)


class TestCase(unittest.TestCase):
    Y = [1, 3, 5, 10, 15]
    givenY = [3, 4, 5, 6, 7, 8, 9, 10, 11]

    def test_empty_array(self):
        self.assertEqual( (-1, -1), find_range([], 1, 2) )

    def test_all_values_larger(self):
        self.assertEqual( (-1, -1), find_range([4,5,6], 1, 3) )

    def test_all_values_larger_or_equal(self):
        self.assertEqual( (-1, -1), find_range(self.givenY, self.Y[0], self.Y[1]) )

    def test_both_endpoints_inside_list(self):
        self.assertEqual( (1, 1), find_range(self.givenY, self.Y[1], self.Y[2]))

    def test_2(self):
        self.assertEqual( (3, 6), find_range(self.givenY, self.Y[2], self.Y[3]) )

    def test_no_values_larger_or_equal_to_upper_limit(self):
        self.assertEqual( (8, 8), find_range(self.givenY, self.Y[3], self.Y[4]) )

    def test_sample(self):
        self.assertEqual( (3,3), find_range([1,3,5,7], 5, 8)  )
        self.assertEqual( (3,3), find_range([1,3,5,7], 6, 8)  )


if __name__=="__main__":
    unittest.main()
于 2013-02-26T20:14:53.997 に答える
0

最初にリストを並べ替えてから、線形検索を実行します。

セミコロンを削除します。セミコロンは不要であり、不要です...

于 2013-02-26T17:16:48.200 に答える