Pythonのアレイeffiency

Question

私はcoderfightsから小さな問題に取り組んでいます：

注：配列は[1,1,1,2,3-]それが重複しているので、そのまたFalseの場合。

私のプログラムは完全に動作していますが、5,000個のエントリを持つテストアレイ上では、4秒間のウィンドウに収まらないので終了します。

私のコード：私は何

def almostIncreasingSequence(s): 
l = len(s); 
R1 = [] #RESULT AFTER 1st test 
R2 = [] #RESULT AFTER 2nd test 
T2 = [] #All true, to remove false positives 

     #TEST ONE 1 BY 1 
for n in range(0,l): 
    one = s[:]; 
    one.pop(n)   
    k = one[:]; 
    if sorted(k)==k: 
     R1.append("T") 
     T2.append(k) 
    #else: 
     R1.append("F") 

     #TEST 2, REMOVE FALSE POSITIVE DUPLICATES 
if "T" in R1: 
    # print("will go throught",T2) 

    secondTEST = len(T2) 
    for n in range(0,secondTEST): 
     #print("Running False Positive test for array # ",n) 
     duplicates = [] 
     duplicates = T2[n] 
     if (len(duplicates) != len(set(duplicates))): 
      # print("DUPLICATE FOUND IN",T2[n]) 
      #if found add F to R2 
      R2.append("F") 
     else: 
      # print("no duplicate found in, so TRUE ",T2[n]) 
      R2.append("T") 
     #tf.append("F") 
if "T" in R2: 
    return True 
else: 
    return False 

は次のとおりです。すべての場合に、その真の場合 最初のループでは、チェックを1つの要素を削除しました。 Trueの場合、2番目のテストを実行するために配列を保存します。ループが終了すると、Trueとして渡された配列がある場合、2番目のテストで重複数があ​​るかどうかを調べて誤検出を排除します。彼らはその偽陽性を行う場合、その真でない場合。

最後に、Tが含まれている場合、[T、F、F]などの2番目のテストの後に配列を取得します。

私のアプローチでパフォーマンスを改善するにはどうすればよいですか？私はfalseにすると配列に "F"を書き込まないようにしましたが、それでも4秒未満で5.000配列を渡すためにパフォーマンスが向上しません。

Answer 1

パフォーマンスを向上させる最も効果的なアプローチは、より良いアルゴリズムを使用することです。問題は、あなたかどうかを判断するだけであるので、実際に要素を削除する必要がないことに注意してください

# If a sequence is not strictly increasing then there will be a point at 
# which a[n] >= a[n+1]. We'll call that a reversal. 
Scan the array for a reversal 
If you find a reversal, 
    # At this point you have an option of removing element n, 
    # or removing element n+1. Try them one at a time: 
    if a[n-1] < a[n+1] then check the results of removing element n 
    call another method that checks for strict ordering for the rest 
     of the array. [i.e. n+1 .. array.size] 
    If that method returns true, then return true 
       else fall thru to next check 

# if you get here, removing element n won't work: 
    if a[n] < a[n+2] then check the results of removing element n+1 
     call the method that checks for strict ordering for the rest 
     of the array. [i.e. n+2 .. array.size] 
     return whatever value it returns 
    else removing element n+1 won't work either 
    return false 

# if you get here, you didn't find any reversals. 
return true 

[これは擬似コードで、あなたは実際のPythonを自分で記述する必要がありますこのような何かを試してみてくださいあなたがしたい場合はそれを削除することができます。入力を不変として処理すると、パフォーマンスが向上し、「試用除去」を実行してバグを導入する可能性が排除されます。

非常に慎重にコードを書いて、配列の端の境界条件を避ける必要があります。