61006


以下の2つの関数をより少ない行数に、または実行効率を改善する方法はあるでしょうか。  
よろしくおねがいします。

  * `findNextLessEqual()`  
リストの各要素に対して、同じかより小さい次の要素のインデックスを取得する

  * `findLastLessThan()`  
リストの各要素に対して、より小さい直前の要素のインデックスを取得する

[code]

    L = [100, 101, 102, 100, 103, 104, 104, 102, 104, 101, 102]
    print('L=', L)
    
    # リストの各要素に対して、同じかより小さい次の要素のインデックスを取得する
    def findNextLessEqual(L):
    
        result = [len(L)]*len(L)
        stack = []  # [(level,pos), ...]
    
        for i,lv in enumerate(L):
    
            while stack and stack[-1][0]>=lv:
                _,pos = stack.pop()
                result[pos] = i
    
            stack += [(lv, i)]
    
        return result
    A = findNextLessEqual(L)
    
    print('findNextLessEqual(L):', A)
    
    # リストの各要素に対して、より小さい直前の要素のインデックスを取得する
    def findLastLessThan(L):
        result = [-1]*len(L)
        stack = []  # [(level,pos), ...]
    
        for i,lv in enumerate(L):
            while stack and stack[-1][0]>=lv:
                _,pos = stack.pop()
            result[i] = stack[-1][1] if stack else i
            stack += [(lv, i)]
    
        return result
    P = findLastLessThan(L)
    print('findLastLessThan(L) :', P)
    
    
[/code]

出力:

[code]

    L= [100, 101, 102, 100, 103, 104, 104, 102, 104, 101, 102]
    findNextLessEqual(L): [3, 3, 3, 11, 7, 6, 7, 9, 9, 11, 11]
    findLastLessThan(L) : [0, 0, 1, 3, 3, 4, 4, 3, 7, 3, 9]
    
[/code]


CC BY-SA 4.0
2019-12-02T02:47:21.730
61000
2019-12-02T05:31:30.940
2019-12-02T02:58:41.283
28998
28998
question
python python3 アルゴリズム
リストのある要素より小さい直前(直後)の要素を取得する


以下、「より少ない行数に」という点では list conprehension を使っているので(実質的には) 1
行ではありますが、「実行効率を改善」という点ではあまり…でしょうか。まぁ、参考までにどうぞ(`Numpy.array`
を利用するなどした方が良いのではないかと思います)。

なお、条件に合う要素が見つからない場合には比較元の要素のインデックスを使っています。例えば、`findNextLessEqual(L)`
において、`L[3]` は `100` ですが、`L[4:]` においては 100 以下の要素が存在しません。

[code]

    def findNextLessEqual(L):
      return [
        next(
          filter(
            lambda x: x[1] <= v, enumerate(L[idx+1:])
          ), (-1, idx))[0] + (idx + 1)
        for idx, v in enumerate(L)
      ]
    
    def findLastLessThan(L):
      return [0] + [
        (idx - 1) -
        next(
          filter(
            lambda x: x[1] < v, enumerate(L[idx-1::-1])
          ), (-1, idx))[0]
        for idx, v in enumerate(L) if idx > 0
      ]
    
    L = [100, 101, 102, 100, 103, 104, 104, 102, 104, 101, 102]
    
    print(findNextLessEqual(L))
    print(findLastLessThan(L))
    
    ## 実行結果
    [3, 3, 3, 3, 7, 6, 7, 9, 9, 9, 10]
    [0, 0, 1, 3, 3, 4, 4, 3, 7, 3, 9]
    
[/code]


CC BY-SA 4.0
2019-12-02T05:31:30.940
61006
2019-12-02T05:31:30.940
61000
answer