Home | Blog | Software | Reviews and Features | Forum | Help | Donate | About us
topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • December 11, 2016, 12:12:26 AM
  • Proudly celebrating 10 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.
  • donate

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

kartal

  • Supporting Member
  • Joined in 2008
  • **
  • Posts: 1,529
    • View Profile
    • Donate to Member
Functional programming test in Python. Finding the smallest item
« on: February 22, 2010, 03:06:43 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:04 PM by kartal »

CWuestefeld

  • Supporting Member
  • Joined in 2006
  • **
  • Posts: 1,002
    • View Profile
    • Donate to Member
Re: Functional programming test in Python. Finding the smallest item
« Reply #1 on: February 23, 2010, 11:53:49 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
    • View Profile
    • Donate to Member
Re: Functional programming test in Python. Finding the smallest item
« Reply #2 on: February 23, 2010, 12:14:49 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
    • View Profile
    • Donate to Member
Re: Functional programming test in Python. Finding the smallest item
« Reply #3 on: February 23, 2010, 02:09:41 PM »
There is also some good introductory material on functional programming in python in chapter one of Text Processing in Python.