2

Pythonでmin/max関数を使用せずに、リストの最小値と最大値を見つける方法があるかどうか疑問に思いました。そこで、再帰を使用して同じコードを作成しました。私のロジックは非常に単純です。再帰呼び出しごとに最小値と最大値を追跡する2つのスタック（min_stackと）を作成します。max_stack2つの質問があります：

  1. 誰かが私のコードの複雑さを見積もるのを手伝ってもらえますか？
  2. これを行うためのより良い方法はありますか？マージソート/クイックソートを使用してリストを並べ替え、最初と最後の要素を取得すると、パフォーマンスが向上しますか？

これがPythonでの私の試みです：

minimum = []
maximum = []

# Defining Stack Class
class Stack:
    def __init__(self) :
        self.items = []

    def push(self, item) :
        self.items.append(item)

    def pop(self) :
        return self.items.pop()

    def access(self, index):
        return self.items[index]

    def isEmpty(self) :
        return (self.items == [])

    def length(self):
        return len(self.items)

def minmax(input_list):
    # make two stacks, one for min and one for max
    min_stack = Stack()
    max_stack = Stack()
    # comparing the first two elements of the list and putting them in appropriate stack
    if input_list[0]<input_list[1]:
        min_stack.push(input_list[0])
        max_stack.push(input_list[1])
    else:
        max_stack.push(input_list[0])
        min_stack.push(input_list[1])

    # Pushing remaining elements of the list into appropriate stacks. 
    for i in range(2, len(input_list)):
        if input_list[i] < min_stack.access(-1):
            min_stack.push(input_list[i])
        else:
            max_stack.push(input_list[i])

    # to find minimum
    minlist = []
    while min_stack.length() > 0:
        minlist.append(min_stack.pop())

    # to find maximum
    maxlist = []
    while max_stack.length() > 0:
        maxlist.append(max_stack.pop())

    if len(minlist) > 1:
        minmax(minlist)
    else:
        minimum.append(minlist)


    if len(maxlist) > 1:
        minmax(maxlist)
    else:
        maximum.append(maxlist)

def main():
    input_list = [2, 0, 2, 7, 5, -1, -2]
    print 'Input List is: ', input_list
    minmax(input_list)

print 'Global Minimum is: ', minimum[0]
print 'Global Maximum is: ', maximum[len(maximum)-1]

if __name__ == "__main__":
    main()
4

9 に答える 9

9

もちろん、これを使用sorted()すると、組み込みであるため、信頼性が高く、書き込みが速く、適度なサイズのリストに対して高いパフォーマンスが得られます。大きなリストの場合、O(n) アルゴリズムの方が高速です。例:

def minmax1 (x):
    # this function fails if the list length is 0 
    minimum = maximum = x[0]
    for i in x[1:]:
        if i < minimum: 
            minimum = i 
        else: 
            if i > maximum: maximum = i
    return (minimum,maximum)

print(minmax1([9,8,7,6,5,4,3,2,1,11,12,13,14,15,16,17,18,19]))
print(minmax1([1]))
print(minmax1([2, 0, 2, 7, 5, -1, -2]))

...出力は次のとおりです。

(1, 19)
(1, 1)
(-2, 7)

2 つの選択肢のパフォーマンスを確認することに興味がありました。Windows XP と Python 3.2.3 を実行している私の PC では、minmax1()要素数が 500 未満のリストの場合、上で定義した関数よりも並べ替えアプローチの方が高速ですが、リストが長い場合は O(n) のminmax1()方が高速であることがわかりました。私のタイミングテストコードは次のとおりです。

def minmax_sort(x):
    x = sorted(x)
    return (x[0],x[-1])

import timeit

aa = list(range(0,100))
a = aa
while (1):
    stime = min(timeit.repeat('minmax_sort(a)', "from __main__ import minmax_sort,a",number=1000))
    mtime = min(timeit.repeat('minmax1(a)', "from __main__ import minmax,a",number=1000))
    if (stime > mtime):
        break
    else:
        a = a + aa
print(len(a))
于 2013-03-01T04:59:16.570 に答える
0

これは、再帰関数を使用した簡単なソリューションです。arrあなたの数字のリストをしましょう。最小/最大は、リストの最後に到達し、一度に最後の 2 つの数値を比較し、結果を最初の要素まで前の関数呼び出しに伝播することで確認できます。

def get_min_max(arr):
    min = find_peak(arr, peak = "minimum")
    max = find_peak(arr, peak = "maximum")
    return {"minimum": min, "maximum": max}

def find_peak(arr, peak):
    if len(arr) == 1: # base condition
        return arr[0]    
    n1 = arr[0]
    n2 = find_peak(arr[1:], peak) # first element removed for each call
    if peak == "maximum":
        if n1 > n2: 
            return n1
        else:
            return n2
    else:
        if n1 < n2: 
            return n1
        else:
            return n2
于 2022-01-05T07:40:44.723 に答える