Did you miss your activation email?

• November 15, 2018, 07:14 AM
• Proudly celebrating 13 years online.
• Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.

### Author Topic: Functional programming test in Python. Finding the smallest item  (Read 3214 times)

#### kartal

• Supporting Member
• Joined in 2008
• Posts: 1,529
##### Functional programming test in Python. Finding the smallest item
« on: February 22, 2010, 03:06 PM »
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)
« Last Edit: February 22, 2010, 03:10 PM by kartal »

#### CWuestefeld

• Supporting Member
• Joined in 2006
• Posts: 1,009
##### Re: Functional programming test in Python. Finding the smallest item
« Reply #1 on: February 23, 2010, 11:53 AM »
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

• Supporting Member
• Joined in 2008
• Posts: 1,529
##### Re: Functional programming test in Python. Finding the smallest item
« Reply #2 on: February 23, 2010, 12:14 PM »
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

• Supporting Member
• Joined in 2006
• Posts: 1,927
##### Re: Functional programming test in Python. Finding the smallest item
« Reply #3 on: February 23, 2010, 02:09 PM »
There is also some good introductory material on functional programming in python in chapter one of Text Processing in Python.