Removed Areas > Python

Functional programming test in Python. Finding the smallest item

(1/1)

kartal:
I have been using Python for a while but never delved into functional programming( http://docs.python.org/dev/howto/functional.html ). Here is my first try.  I am using a recursive function to slice the array into 2 pieces, smaller and bigger than average in given pass until the lenght achieves 1. In the past for practice I used loops for this stuff but functional+recursive makes more sense to me now.

This will find the smallest item in the array


--- Code: Python ---import random, timeprint random.seed(time.time())myarray=[random.randrange(1,100) for a in range(0,10)]  #this creates a random list array  print myarray def findSmallest(array):     if len(array)<2: return     array_sum=reduce(lambda x,y:x+y,array) #Calculate the sum of all the elements inside the array by using the "reduce" function    array_avg=array_sum/len(array)     smallers=filter(lambda x:x<array_avg,array) #This line filters the array items based on their size compared to the average of the array #----------------------------------------->Debug       #print " sum: ",array_sum,    #print " average: ",array_avg    #print "\n"    print smallers#----------------------------------------->Debug        findSmallest(smallers)  if __name__=="__main__":#    pass    findSmallest(myarray)

CWuestefeld:
That's similar to the QuickSort algorithm. Recursively break the set into pairs, with one pair having everything < a given value, the other having those >=.

One difference is that QS assumes that the first item in a given (sub)set is a good representative of the median value. Thus, QS is O(N log(N)) on average (typical with random data), but if you're data is already sorted it falls to O(N^2) like a Bubble Sort.

Anyway, you're still stuck with O(N log(N)) complexity on something that's theoretically possible in O(N) for any input dataset.

But I'm still learning functional programming myself, and don't know how to do any better than your proposal.

kartal:
You are right but I was not trying to come up with a fast method, rather I just wanted to entertain the basic functional programming methods in Python. The method would work faster if I can make the summing faster I think since LogN is not that terrible. Python has a built in array sum mehtod probably faster than using reduce to sumup the array, but again that would only effect the speed of the calculation not the number of steps :)

One another way I can think of without going through the recursion way is using "map", "filters" and "lamda" in the same line. I need to see if that is doable

tinjaw:
There is also some good introductory material on functional programming in python in chapter one of Text Processing in Python.

Navigation

[0] Message Index