Thread: is there a better way to optimise this?

  1. #1
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85

    is there a better way to optimise this?

    I have written an in_order_list function, was just wondering if there is a better way to do it, mine seems to work fine through testing. It just looks a bit long, what do you think:
    Code:
    list_t
    *insert_in_order (list_t *list, data_t value) 
    {
    node_t *new, *curr, *prev;
    	
    new = (node_t *) malloc (sizeof (node_t));
    	
    new->next = NULL;
    new->data = value;
    	
    curr = list->head;
    if (curr == NULL)		/*We have the first entry*/
    {
    	list->foot = list-> head = new;
    	return list;
    }
    	if (curr->data > value)
    { 
    	new->next = curr;
    	list->head = new;
    	return list;	
    }
    else 
    	while (curr->next !=NULL)
    	{
    		if (curr->data < value)
    		{
    		prev = curr;
    		curr = curr->next;
    		}
    		if (curr->data > value)
    		{
    		new->next = curr;
    		prev->next = new;
    		greturn list;
    		}
    	}
    	curr->next = new;
    	return list;	
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > greturn list;
    I think it doesn't compile, and is badly indented.

    You're also casting the result of malloc in C - see the FAQ

    > if (curr->data > value)
    You should be able to combine this test with the while loop which follows, which also contains in effect the same condition.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    If it was made to compile, it is buggy because inserting a data_t that is equal to another in the list and is not at the end, will cause an infinite loop.

    You're spot on thinking it is a bit longer than it shoule be. If it is longer than 15 lines all up (including lines with just a curly bracket) then it is definitely too long.

    Start by removing both "if (curr->data > value)" statements (keeping the body of the else part).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    i changed it a bit and but im still confused about getting ascending order...
    Code:
    list_t
    *insert_in_order (list_t *list, data_t value) 
    {
    	node_t *new, *curr, *prev;
    	
    	new = (node_t *) malloc (sizeof (node_t));
    	
    	new->next = NULL;
    	new->data = value;
    	
    	curr = list->head;
    	if (curr == NULL)		/*We have the first entry*/
    	{
    		list->foot = list-> head = new;
    		return list;
    	}
    	else 
    	{
    		prev = curr;
    		while (curr->next != NULL && curr->data > value)
    		{
    			if (curr->data <= value)
    			{
    				new->next = prev->next;
    				prev->next = new;
    				return list;
    			}
    			else
    			{
    			prev = curr;
    			curr = curr->next;
    			}
    		}
    		new->next = curr->next;
    		curr->next = new;
    	}
    	
    	return list;	
    }

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    While this statement is true
    curr->data > value
    this will always be false
    curr->data <= value

    So really, all you need inside this while loop are the two statements which advance through the list.


    > curr->next = new;
    This should be prev->next = new;
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If you ever want to move this list-handling to C++ instead of C, you probably want to rename your "new" variable to some other name, as "new" is a keyword in C++.

    In straight C, you shouldn't cast malloc - it hides problems with including stdlib.h.

    As far as I can tell, new->next is ALWAYS set to something during te insertion, so new->next = NULL is not needed. (Except when list is empty).

    I would move the "curr = list->head" down inside the "else" branch of the first if, and use "if(list->head == NULL)" to check if the list is empty. It won't change the code much, but it connects better with the code inside the if that uses list->head.

    Not sure what "list->foot" does - if you are using it as "the end of the list", then you probably need to update it when you insert at the end of the list. If you aren't using it, remove it completely.

    Is there a particular purpose to returning the list? are you calling using something like this?
    Code:
    list = insert_in_order (insert_in_order (memset(malloc(sizeof(list_t)), 0, sizeof(list_t)), value1), value2);
    (I wouldn't want to debug that line, if it ever started going wrong!).

    If you aren't using the return value, then make the function void - it simplifies the code for the compiler, which makes it faster (and that's what you asked for in the first place) - it may not make MUCH of a difference, but it forces the compiler to store list in a particular register, which may be better used for something else (or to shuffle what list is in to get to the right register at the return-point - again, unneccessarily if the function return value isn't being used).

    --
    Mats

  7. #7
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    what about when the case is for insert at the head when the value is smaller than the head, I dont understand how to write it so that this is looked after as well at the end case (value is larger than the end). Putting it into the middle is understood : new->next = prev->next; prev->next = new;

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So, if we have a list where you want to insert before the head (because the value is less than head), the following (red) code will be run:

    Code:
    list_t
    *insert_in_order (list_t *list, data_t value) 
    {
    	node_t *new, *curr, *prev;
    	
    	new = (node_t *) malloc (sizeof (node_t));
    	
    	new->next = NULL;
    	new->data = value;
    	
    	curr = list->head;
    	if (curr == NULL)		/*We have the first entry*/
    	{
    		list->foot = list-> head = new;
    		return list;
    	}
    	else 
    	{
    		prev = curr;
    		while (curr->next != NULL && curr->data > value)[/COLOR]
    We do not enter the loop, because curr->data > value is false
    		{
    			if (curr->data <= value)
    			{
    				new->next = prev->next;
    				prev->next = new;
    				return list;
    			}
    			else
    			{
    			prev = curr;
    			curr = curr->next;
    			}
    		}
    		new->next = curr->next;
    		curr->next = new;
    	}
    	
    	return list;
    }
    --
    Mats

  9. #9
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    thank you guys firtsly, matsp, I will change the cast to malloc and try some of the changes you mentioned esp. the void changes, I am not using the function like you mentioned.

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    By the way, I think you need to update head to if you insert at the head of the list - otherwise head will point to somewhere after the first element - I may be wrong on that, but I don't think I'm wrong.

    --
    Mats

  11. #11
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    "We do not enter the loop, because curr->data > value is false" wouldn't this be true for the head (ascending order?)

  12. #12
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    so far i have
    Code:
    list_t
    *insert_in_order (list_t *list, data_t value) 
    {
    	node_t *new, *curr, *prev;
    	
    	new = malloc (sizeof (node_t));
    	
    	new->next = NULL;
    	new->data = value;
    	
    	curr = list->head;
    	if (curr == NULL)		/*We have the first entry*/
    	{
    		list->foot = list-> head = new;
    		return list;
    	}
    	else 
    	{
    		prev = curr;
    		while (curr->next != NULL && curr->data < value)
    		{
    			prev = curr;
    			curr = curr->next;
    		}
    		
    		new->next = curr->next;
    		prev->next = new;
    	}
    	
    	return list;	
    }
    without success...
    this list_t return for the function being run over a scanf loop

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by qubit67 View Post
    "We do not enter the loop, because curr->data > value is false" wouldn't this be true for the head (ascending order?)
    Yes, my point was more to the fact that if you have list->head is a separate variable to curr and new and prev, right?

    So let's pretend that we do this (I've shortened your function name a bit):
    list->head = NULL
    insert(list, 7);
    list->head was null, so we just set list->head = new;
    list->head is now (say) 0x12345
    insert(list, 5)
    curr = list->head = 0x12345
    curr->data = 7, 5 is less than 7, so we insert at the head of the list, but list->head isn't changed! [This is assuming the rest of the list insertion is correct].

    So you will never find 5 in the list, because you start at list->head, which is 7.

    If you start by verifying that your current code works for inserting values 10, 15, 20, 25, 22, 12, 35 or some such - print the entire list after each new value.

    Then start looking at what happens if you insert 7, 5, 3 or such. I think you'll find that the list doesn't have those values - but if you print the list from prev inside your function, it WILL list the 7, 5 and 3 values. [Although I'm not 100% sure]

    --
    Mats

  14. #14
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    so after trying many different models, I found a solution though again, rather length. any improvements over it?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    typedef int data_t;
    typedef struct node node_t;
    
    struct node
    {
    	data_t data;
    	node_t *next;
    } ;
    
    typedef struct 
    {
    	node_t *head;
    	node_t *foot;
    } list_t;
    
    list_t
    *make_empty_list(void) {
    	list_t *list;
    	
    	list = malloc(sizeof(list_t));
    	assert(list!=NULL);
    	
    	list->head = list->foot = NULL;
    	
    	return list;
    }
    
    
    list_t
    *insert_in_order (list_t *list, data_t value) 
    {
    	node_t *new, *curr, *prev;
    	
    	new = malloc (sizeof (node_t));
    	
    	new->next = NULL;
    	new->data = value;
    	
    	if (list->head == NULL)		/*First in*/
    	{
    		list->foot = list->head = new;
    		return list;
    	}
    	else
    	{	
    		if (value <= list->head->data) /*Smaller than the head, so insert there*/
    		{
    			new->next = list->head;
    			list->head = new;
    			return list;
    		}
    		else
    		{
    			if (value > list->foot->data)/*Larger than the foot so insert there*/
    			{
    				list->foot->next = new;
    				list->foot = new;
    				return list;
    			}	
    			else
    			{					/*we are somewhere between H & F, find the right place*/
    				prev = list->head;
    				curr = list->head->next;
    		
    				while (curr->data < value)
    				{/*Move through list, stop when the curr node data is larger than value*/
    					prev = curr;	
    					curr = curr->next;
    				}
    /*Now at the right spot in the body of the list, insert*/
    			new->next = curr;
    			prev->next = new;
    			return list;
    			}
    		}
    	}		
    }
    
    list_t 
    *read_into_list (void)
    {
    	list_t *list;
    	int value;
    	
    	list = make_empty_list ();
    	
    	while ((scanf("&#37;d", &value)) != EOF)
    	{
    		list = insert_in_order (list, value);
    	}
    	return list;
    	
    }
    
    void
    print_list(list_t *list) 
    {
    	node_t *ptr;
    	ptr = list->head;
    	while (ptr != NULL)
    	{ 
    		printf("%d ", ptr->data);
    		ptr = ptr->next;
    	}
    }
    
    void
    free_list(list_t *list)
    {
    	node_t *curr, *prev;
    	assert(list!=NULL);
    	curr = list->head;
    	while (curr) {
    		prev = curr;
    		curr = curr->next;
    		free(prev);
    	}
    	free(list);
    }
    
    int 
    main (int argc, char **argv)
    {
    	list_t *list;
    	
    	list = read_into_list ();
    	
    	print_list (list);
    	free_list (list);
    	
    	return 0;
    }

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Oh no it's just getting worse - I can't stand it any longer!
    This is how to do it, the way you've defined things:
    Code:
    list_t* Insert(list_t *list, data_t value)
    {
    	node_t *prev = NULL, *curr = list->head, *ins = malloc(sizeof(node_t));
    	while (curr != NULL)
    	{
    		if (value < curr->data) break;
    		prev = curr;
    		curr = curr->next;
    	}
    	if (prev == NULL)
    		list->head = ins;
    	else
    		prev->next = ins;
    	if (list->foot == NULL)
    		list->foot = ins;
    	ins->next = curr;
    	ins->data = value;
    	return list;
    }
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Optimise?
    By rtan3005 in forum C Programming
    Replies: 17
    Last Post: 11-14-2006, 03:10 PM
  2. Will 'static' optimise my code?
    By samGwilliam in forum C++ Programming
    Replies: 3
    Last Post: 03-29-2005, 11:28 AM
  3. optimise algorithm
    By cyberCLoWn in forum C++ Programming
    Replies: 10
    Last Post: 01-18-2005, 02:27 PM
  4. Optimise FindFiles.
    By anonytmouse in forum Windows Programming
    Replies: 0
    Last Post: 01-14-2004, 02:41 AM
  5. How to optimise this c program?
    By megablue in forum C Programming
    Replies: 5
    Last Post: 06-28-2003, 04:20 AM