@Anand Shastri, if tasks enter randomly in runtime,
structure needs to add a member start_time, which will be different from
reference_time (till now u been considering it as same start time of every
task). finally GOOD work!!
surender
On Fri, Aug 5, 2011 at 9:42 AM, Gaurav Menghani
<gaurav.mengh...@gmail.com>wrote:
> Then that has to be mentioned in the question. Premature optimization
> is the root of all evil, in the words of Don Knuth.
>
> On Fri, Aug 5, 2011 at 9:38 AM, Anand Shastri <anand.shastr...@gmail.com>
> wrote:
> > what if new task gets added every time.
> >
> > On Thu, Aug 4, 2011 at 8:24 PM, Gaurav Menghani <
> gaurav.mengh...@gmail.com>
> > wrote:
> >>
> >> Instead of a heap, sort the array once. Pick the first element every
> >> time, and remove it from the array, or just move the 'head pointer'
> >> ahead.
> >>
> >> On Fri, Aug 5, 2011 at 8:01 AM, Anand Shastri <
> anand.shastr...@gmail.com>
> >> wrote:
> >> > /* Create a Timer Task that takes in the running time and it's
> >> > associated
> >> > function to be called after its running time is elapsed */
> >> > #include <time.h>
> >> >
> >> > #define NUM 5
> >> > typedef void (*funcToBeCalled)(void);
> >> >
> >> > typedef struct timer TIMER;
> >> >
> >> > struct timer
> >> > {
> >> > int runningTime;
> >> > funcToBeCalled func;
> >> > };
> >> >
> >> > static TIMER timerArray[NUM];
> >> > static time_t reference;
> >> > static int count;
> >> >
> >> > int LEFT(int index)
> >> > {
> >> > if(index < NUM)
> >> > return (index * 2 + 1);
> >> > }
> >> > int RIGHT(int index)
> >> > {
> >> > if(index < NUM)
> >> > return (index * 2 + 2);
> >> > }
> >> > static void print(void)
> >> > {
> >> > printf("Timer task has been called\n");
> >> > }
> >> >
> >> > // Initialise the timer data structure
> >> > void Init()
> >> > {
> >> > int index;
> >> > count = NUM;
> >> > // Note down the reference time
> >> > reference = time(0);
> >> > printf("reference : %ld\n", reference);
> >> >
> >> > // Initialise the data structure such that associate function gets
> >> > // called after 3, 6, 9, 12, 15 seconds respectively.
> >> > for(index = 0; index < count; index++)
> >> > {
> >> > timerArray[index].runningTime = (index + 1) * 3;
> >> > timerArray[index].func = print;
> >> > }
> >> > }
> >> >
> >> > // This function check the min heap property and arrange
> >> > // the element such that at every node, root node should be
> >> > // less than its right and left child element.
> >> > Heapify(int index)
> >> > {
> >> > int left, right, minIndex;
> >> > TIMER temp;
> >> > left = LEFT(index);
> >> > right = RIGHT(index);
> >> > if(left < (count) &&
> >> > (timerArray[left].runningTime < timerArray[index].runningTime))
> >> > {
> >> > minIndex = left;
> >> > }
> >> > else
> >> > {
> >> > minIndex = index;
> >> > }
> >> > if(right < (count) &&
> >> > (timerArray[right].runningTime <
> timerArray[minIndex].runningTime))
> >> > {
> >> > minIndex = right;
> >> > }
> >> > if(minIndex != index)
> >> > {
> >> > temp.runningTime = timerArray[index].runningTime;
> >> > temp.func = timerArray[index].func;
> >> >
> >> > timerArray[index].runningTime = timerArray[minIndex].runningTime;
> >> > timerArray[index].func = timerArray[minIndex].func;
> >> >
> >> > timerArray[minIndex].runningTime = temp.runningTime;
> >> > timerArray[minIndex].func = temp.func;
> >> >
> >> > Heapify(minIndex);
> >> > }
> >> > }
> >> >
> >> > // This function builds the MIN heap data structure
> >> > void BuildHeap()
> >> > {
> >> > int len, i;
> >> > len = sizeof(timerArray)/sizeof(timerArray[0]);
> >> > i = (len - 1)/2;
> >> > while(i >= 0)
> >> > {
> >> > Heapify(i);
> >> > i--;
> >> > }
> >> > Heapify(0);
> >> > }
> >> >
> >> >
> >> > // This function extract the top element of the heap
> >> > // Min heap has the min element at the top always.
> >> > int HeapExtract()
> >> > {
> >> > TIMER temp;
> >> > // Swap the 0 the element with last element of the array
> >> > temp.runningTime = timerArray[0].runningTime;
> >> > temp.func = timerArray[0].func;
> >> >
> >> > timerArray[0].runningTime = timerArray[count-1].runningTime;
> >> > timerArray[0].func = timerArray[count-1].func;
> >> >
> >> > timerArray[count-1].runningTime = temp.runningTime;
> >> > timerArray[count-1].func = temp.func;
> >> > count--;
> >> > // Check the heap property heapify if it got violated
> >> > Heapify(0);
> >> > // return the minimum element of the heap
> >> > return (count);
> >> > }
> >> > void scheduler()
> >> > {
> >> > time_t now;
> >> > int diff_time, minIndex;
> >> > while(count >= 0)
> >> > {
> >> > now = time(0);
> >> > printf("Current Time: %ld\n", time(0));
> >> > diff_time = now- reference;
> >> > printf("diff_time : %ld\n", diff_time);
> >> > if(diff_time >= timerArray[0].runningTime)
> >> > {
> >> > minIndex = HeapExtract();
> >> > timerArray[minIndex].func();
> >> > }
> >> > else
> >> > {
> >> > sleep(timerArray[0].runningTime - diff_time);
> >> > }
> >> > }
> >> > }
> >> > main()
> >> > {
> >> > int index, minIndex;
> >> > TIMER temp;
> >> >
> >> > // Initialise the data structure
> >> > Init();
> >> >
> >> > // Build MIn heap data structure
> >> > BuildHeap(timerArray);
> >> >
> >> > // Run the scheduler
> >> > scheduler();
> >> >
> >> > return;
> >> > }
> >> > The ouput of above code is
> >> >
> >> > Timer Task is about to run
> >> > reference : 1312510772
> >> >
> >> > Current Time: 1312510775
> >> > diff_time : 3
> >> > Timer task has been called
> >> >
> >> > Current Time: 1312510778
> >> > diff_time : 6
> >> > Timer task has been called
> >> > Current Time: 1312510781
> >> > diff_time : 9
> >> > Timer task has been called
> >> >
> >> > Current Time: 1312510784
> >> > diff_time : 12
> >> > Timer task has been called
> >> >
> >> > Current Time: 1312510787
> >> > diff_time : 15
> >> > Timer task has been called
> >> >
> >> > Please share your comments
> >> >
> >> > On Thu, Aug 4, 2011 at 11:43 AM, Anand Shastri
> >> > <anand.shastr...@gmail.com>
> >> > wrote:
> >> >>
> >> >> Obviously you need to run the task that a closet running time.
> >> >>
> >> >> For Example
> >> >>
> >> >> Task 1 : running time = 2 secs
> >> >>
> >> >> Task 2: running time = 4 secs
> >> >>
> >> >> This means I want to run the task 1 after 2 secs and task 2 after 4
> >> >> second.
> >> >>
> >> >> How I hope the question is clear to you know
> >> >>
> >> >> On Thu, Aug 4, 2011 at 11:37 AM, mohit verma <mohit89m...@gmail.com>
> >> >> wrote:
> >> >>>
> >> >>> there is nothing like "search min or max time and then call
> function"
> >> >>> given . It can be the case: "call the functions in order of nodes or
> >> >>> times
> >> >>> saved in objects". M i wrong?
> >> >>>
> >> >>> On Thu, Aug 4, 2011 at 11:56 PM, Anand Shastri
> >> >>> <anand.shastr...@gmail.com> wrote:
> >> >>>>
> >> >>>> You mean to say linked to maintain all time task with its
> >> >>>> corresponding
> >> >>>> running time and associate function. In that case how will find the
> >> >>>> task
> >> >>>> which has the closed running time.
> >> >>>>
> >> >>>> If you use min heap it would be easy to find the task that has
> >> >>>> closest
> >> >>>> runing time in O(1) complexity.
> >> >>>>
> >> >>>> On Thu, Aug 4, 2011 at 10:57 AM, mohit verma <
> mohit89m...@gmail.com>
> >> >>>> wrote:
> >> >>>>>
> >> >>>>> why are u maintaining heap? can't we use link list here?
> >> >>>>>
> >> >>>>> On Thu, Aug 4, 2011 at 11:16 PM, Anand Shastri
> >> >>>>> <anand.shastr...@gmail.com> wrote:
> >> >>>>>>
> >> >>>>>> You have given a structure which has two member, One which stores
> >> >>>>>> the
> >> >>>>>> time and other stores the function pointer Your function has to
> >> >>>>>> call
> >> >>>>>> the
> >> >>>>>> function stored in the fuction poitner after the time given in
> the
> >> >>>>>> structure elapses.
> >> >>>>>> Design that function?
> >> >>>>>>
> >> >>>>>> Approach: To design this function I would use a min Heap data
> >> >>>>>> structure. Each node of a heap has
> >> >>>>>> two parameters one is the running time and other
> >> >>>>>> one
> >> >>>>>> is the function pointer.
> >> >>>>>>
> >> >>>>>> // Initialise a function pointer
> >> >>>>>> typedef void (*functionToBeCalled)(int arg1, int arg2);
> >> >>>>>>
> >> >>>>>> // Timer structure
> >> >>>>>> typedef struct timer
> >> >>>>>> {
> >> >>>>>> float runingTime; // in terms of seconds
> >> >>>>>> functionToBeCalled funcToBeCall; // function pointer
> >> >>>>>> }TIMER;
> >> >>>>>>
> >> >>>>>> void initTimer()
> >> >>>>>> {
> >> >>>>>> Initialise few nodes with running time and its corresponding
> >> >>>>>> function
> >> >>>>>> Initialise a MIN heap data structure
> >> >>>>>> }
> >> >>>>>>
> >> >>>>>> void addTimer(uint32 runingTime, functionToBeCalled func)
> >> >>>>>> {
> >> >>>>>> TIMER *temp;
> >> >>>>>> temp = (TIMER *)malloc(sizeof(TIMER));
> >> >>>>>> temp->runingTime = runningTime
> >> >>>>>> temp->funcToBeCall = func;
> >> >>>>>> HeapAdd(temp);
> >> >>>>>> Heapify();
> >> >>>>>> }
> >> >>>>>>
> >> >>>>>> void scheduler()
> >> >>>>>> {
> >> >>>>>> uint32 currentTime = ObtainCurrentTime();
> >> >>>>>> // Obtain the runing time of top most element of the
> >> >>>>>> min
> >> >>>>>> Heap
> >> >>>>>> uint32 runingTime = PeakHeap();
> >> >>>>>> // if the runningTime is equal to current time then
> >> >>>>>> extract the top most
> >> >>>>>> // element of the heap and execute the function
> >> >>>>>> associate
> >> >>>>>> with it
> >> >>>>>> // Heapify the MIN heap data structure
> >> >>>>>> // Obtain the runing time of top most element of the
> >> >>>>>> min
> >> >>>>>> heap
> >> >>>>>> // scheduler sleep for that much amount of time.
> >> >>>>>> if(runingTime == currentTime)
> >> >>>>>> {
> >> >>>>>> TIMER * node = ExtractMinHeap();
> >> >>>>>> CreateThread(node->func, Thread);
> >> >>>>>> Heapify();
> >> >>>>>> runingTime = PeakHeap();
> >> >>>>>> sleep(runningTime);
> >> >>>>>> }
> >> >>>>>> else
> >> >>>>>> {
> >> >>>>>> // scheduler updates its sleep time
> >> >>>>>> // if runing time is not equal to current time
> >> >>>>>> sleep(runningTime);
> >> >>>>>> }
> >> >>>>>>
> >> >>>>>> }
> >> >>>>>>
> >> >>>>>> Let me know your comments
> >> >>>>>>
> >> >>>>>> --
> >> >>>>>> You received this message because you are subscribed to the
> Google
> >> >>>>>> Groups "Algorithm Geeks" group.
> >> >>>>>> To post to this group, send email to algogeeks@googlegroups.com.
> >> >>>>>> To unsubscribe from this group, send email to
> >> >>>>>> algogeeks+unsubscr...@googlegroups.com.
> >> >>>>>> For more options, visit this group at
> >> >>>>>> http://groups.google.com/group/algogeeks?hl=en.
> >> >>>>>
> >> >>>>>
> >> >>>>>
> >> >>>>> --
> >> >>>>> ........................
> >> >>>>> MOHIT VERMA
> >> >>>>>
> >> >>>>> --
> >> >>>>> You received this message because you are subscribed to the Google
> >> >>>>> Groups "Algorithm Geeks" group.
> >> >>>>> To post to this group, send email to algogeeks@googlegroups.com.
> >> >>>>> To unsubscribe from this group, send email to
> >> >>>>> algogeeks+unsubscr...@googlegroups.com.
> >> >>>>> For more options, visit this group at
> >> >>>>> http://groups.google.com/group/algogeeks?hl=en.
> >> >>>>
> >> >>>> --
> >> >>>> You received this message because you are subscribed to the Google
> >> >>>> Groups "Algorithm Geeks" group.
> >> >>>> To post to this group, send email to algogeeks@googlegroups.com.
> >> >>>> To unsubscribe from this group, send email to
> >> >>>> algogeeks+unsubscr...@googlegroups.com.
> >> >>>> For more options, visit this group at
> >> >>>> http://groups.google.com/group/algogeeks?hl=en.
> >> >>>
> >> >>>
> >> >>>
> >> >>> --
> >> >>> ........................
> >> >>> MOHIT VERMA
> >> >>>
> >> >>> --
> >> >>> You received this message because you are subscribed to the Google
> >> >>> Groups
> >> >>> "Algorithm Geeks" group.
> >> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >> >>> To unsubscribe from this group, send email to
> >> >>> algogeeks+unsubscr...@googlegroups.com.
> >> >>> For more options, visit this group at
> >> >>> http://groups.google.com/group/algogeeks?hl=en.
> >> >>
> >> >
> >> > --
> >> > You received this message because you are subscribed to the Google
> >> > Groups
> >> > "Algorithm Geeks" group.
> >> > To post to this group, send email to algogeeks@googlegroups.com.
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+unsubscr...@googlegroups.com.
> >> > For more options, visit this group at
> >> > http://groups.google.com/group/algogeeks?hl=en.
> >> >
> >>
> >>
> >>
> >> --
> >> Gaurav Menghani
> >>
> >> --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >> http://groups.google.com/group/algogeeks?hl=en.
> >>
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> > http://groups.google.com/group/algogeeks?hl=en.
> >
>
>
>
> --
> Gaurav Menghani
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
