Saturday, October 5, 2013

Chop-down algorithm

Day today programming we need to find solutions for various logical problems. today i got a task to create a program to find triangular numbers between any given two numbers. I implemented it using python. Following code shows how i did it.

   
import math,sys

#create a list with numbers
def create_list():
    num_list=[]
    for num in range(int(input("insert start point: ")),int(input("Insert end point: "))):
        num_list.append(num)
    return num_list

#function to find triangular numbers
def get_triangles(numlist):
    triangles = []
    for i in numlist:
        if (check_triangle(i)):
            triangles.append(i)
    return triangles

#function to check number is triangular or not
def check_triangle(n):
    return math.sqrt((8*n)+1).is_integer()

#fuction main to run the process
def main():
    numlist = create_list()
    print(get_triangles(numlist))
Even though it seems like the task is completed it was not. I tried it with the range of  0 - 100000000(1*10^8) numbers . it was horrible to see the out put and time taken to complete the task. my computer was stuck for few minutes and  unable to complete the task. i was tried with 10000000 (1*10^7). then i saw that 95% of memory  was occupied by the program. Then i modified the program as follow
   
import sys,_thread,time,math

#function to create a  list with numbers
def create_list():
    num_list=[]
    for num in range(int(input("insert start point: ")),int(input("Insert end point: "))):
        num_list.append(num)
    return num_list
   

#determine 3 cutdownpoints
def cut_down_points(count):
    if(count%4==0):
        return [count*0.25,count*0.5,count*0.75]
    else:
        while(count%4!=0):
            count = count+1
            first = int(count*0.25)
            second = int(count*0.5)
            third = int(count*0.75)
        return [first,second,third]

#cutdown list to 4 peces
def cutdown(num_list,cut_points):
    return [num_list[0:cut_points[0]],num_list[cut_points[0]:cut_points[1]],
            num_list[cut_points[1]:cut_points[2]],num_list[cut_points[2]:]]

#function to find triangular numbers
def find_triangle_numbers(numlists):
    triangles=[]
    for i in numlists:
        if(check_triangle(i)):
            triangles.append(i)
    print (triangles)
    #return triangles
            
#function to check number is triangle or not
#if number x is a triangle 8x+1 need to be a perfect squre number 
def check_triangle(n):
    return math.sqrt((8*n)+1).is_integer()

#start 4 threads to find triangles
def find_all_triangles(numberlist):
    #print (numberlist)
    num_set_01= _thread.start_new_thread(find_triangle_numbers,(numberlist[0],))
    num_set_02= _thread.start_new_thread(find_triangle_numbers,(numberlist[1],))
    num_set_03= _thread.start_new_thread(find_triangle_numbers,(numberlist[2],))
    num_set_04= _thread.start_new_thread(find_triangle_numbers,(numberlist[3],))

#main function to run the process 
def main():
    numbers = create_list()
    temp_cutdown_point_list = cut_down_points(int(len(numbers)))
    cutdown_point_list=[int(i) for i in temp_cutdown_point_list]
    cut_list = cutdown(numbers,cutdown_point_list)
    find_all_triangles(cut_list)
I sow that the program was not stuck as previous and did the task smoothly with a minimum execution time. After careful consideration i defined following algorithm to accomplish this kind of tasks.

NAME : Chop-down algorithm 
TASK : increase the efficiency of searching tasks  in vary large domains
ALGORITHM :
assume Domain size is equal to M where M > 10e6
Start
   chop down the domain in to n parts where n <= M/[(M*5)/100]
   create n number of  individual threads (avoid resource killing)
   assign single sub domain to each thread
   perform searching
End



Eg:  assume that we need to find triangular numbers between 0 and 10e6
             STEP 01 :
             n = 10e6/[(10e6 * 5)/100] =  20
             so we need to break the domain in to 20 parts
             STEP 02 :
             create 20 threads
             STEP 03 :
             assign single sub domain to each thread
                               Thread_01 >>>> 0  -  5*10e4
                                Thread_02>>>> 5*10e4  -  10*10e4
                                 .
                                 .
                                 .

             STEP 04 :
             Start threads to perform search
                               EG.  Thread_03 ->
                                             Search each value in its domain and print triangular values
             End


                         
                             










No comments:

Post a Comment