Powisss Powisss - 1 year ago 73
Python Question

Python Array effiency

I'm working on a small problem from coderfights:
Problem Description

NOTE: if array is [1,1,1,2,3] its also False, since it has duplicate.

My program is working fully, BUT on the test array with 5,000 entries it doesn't fit into 4second window to finish.

my code:

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


What I did is:
First loop removed 1 element, checks if its true to all cases. If it True it saves the array to run 2nd test on it. When loop finishes, if there is Arrays that passed as True, second test eliminates False Positives by checking if any of them have duplicate numbers. If they do its false positive, if no its True.

Finally I get array after second test e.g.[T,F,F] if it contains T then one of the arrays is not false positive.

My question is how can I improve performance in my approach? I tried not writing "F" into array if false, but it still doesnt increase performance to pass 5.000 array in less than 4 seconds.

Answer Source

The most effective approach to improving performance is to use a better algorithm. Try something like this [this is pseudo-code, you'll have to write the actual Python yourself]

# 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.  
     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.
       return whatever value it returns

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

Note that there is no need to actually remove the element since the problem is simply to determine whether you could remove it if you wanted to. Treating the input as immutable both improves performance and eliminates the chances of introducing a bug by doing a "trial removal."

You will have to code very carefully to avoid boundary conditions at the ends of the array.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download