Functional programming test in Python. Finding the smallest item

[kartal]

I have been using Python for a while but never delved into functional programming( http://docs.python.o...owto/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 [Select]

1. import random, time
2. print random.seed(time.time())
3. myarray=[random.randrange(1,100) for a in range(0,10)]  #this creates a random list array
4.  
5.  
6. print myarray
7.  
8. def findSmallest(array):
9.  
10.     if len(array)<2: return
11.  
12.     array_sum=reduce(lambda x,y:x+y,array) #Calculate the sum of all the elements inside the array by using the "reduce" function
13.     array_avg=array_sum/len(array)
14.  
15.     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
16.  
17. #----------------------------------------->Debug  
18.     #print " sum: ",array_sum,
19.     #print " average: ",array_avg
20.     #print "\n"
21.     print smallers
22. #----------------------------------------->Debug  
23.  
24.     findSmallest(smallers)
25.  
26.  
27. if __name__=="__main__":
28. #    pass
29.     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.