Trying to make this run faster

This is a discussion on Trying to make this run faster within the C Programming forums, part of the General Programming Boards category; Originally Posted by iMalc Don't let the fact that you've crammed all that into one line confuse you into thinking ...

  1. #31
    Registered User
    Join Date
    Jun 2009
    Posts
    5
    Quote Originally Posted by iMalc View Post
    Don't let the fact that you've crammed all that into one line confuse you into thinking that it's not still a loop over (on average) half of the items in a linked list each time.
    When you're talking about easily over a million items to iterate over each time, after a little while, don't you think that's going to take a long time?!
    It's where your code becomes O(n*n) and that's what makes it slow.

    The rule here is: Don't repeatedly use a linear search - ever!
    I think you're right. But, in this case, what's the alternative approach?

    Is there another way of searching the linked list faster? I can't think of another approach especially with the way the structure is built now. Maybe I need to change it, but that will require major changes in the code.

  2. #32
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If you don't want to change the linked list's structure, change how you hold the list. Instead of using one pointer to hold the list, use an array of pointers. Basically, make a hash table. Super simple version:
    Code:
    /* super lazy mode, use the last digit as what list you end up in */
    #define HASHSIZE 10
    struct node *dc_head[ HASHSIZE ]; /* instead of just one pointer, an array... */
    ...
    double is_dependent(unsigned long long which_inst, enum stall_reason *where)
    {
    	struct dependency *temp, *prev;
    	double ret_val = 0;
    	size_t which_bucket = which_inst % HASHSIZE;
    
    	// Scan the chain for the dependent line
    	for(prev=NULL, temp=dc_head[ which_bucket ]; temp && temp->which_inst != which_inst; prev=temp, temp=temp->next);
    
    	// Found. Unlink node and return when_satisfied
    	if(temp)
    	{
    		if(prev)
    		{
    			prev->next = temp->next;
    		}
    		else
    		{
    			dc_head[ which_bucket ] = temp->next;
    		}
    
    		ret_val = temp->when_satisfied;
    		*where = temp->reason;
    		free(temp);
    	}
    
    	return ret_val;
    }
    Pretty much all you've done is split your list into HASHSIZE smaller lists. Now everything that ends in a 1 goes in array[ 1 ], everything that ends in a 9 goes in array[ 9 ], etc.

    This is just an extremely simplified example. That's not the best number to use for hashing, but it's easy to understand, which is why I use it for examples. Now, you've cut your search time by 10.

    Either way, if you use this, a tree, or something better, you're going to end up putting some work in. I think this would probably require the least amount of work, because really all you have to do is find everywhere you use dc_head and make it use an array instead. It's not the fastest method, but it's really simple.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #33
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by wkohlani View Post
    I think you're right. But, in this case, what's the alternative approach?

    Is there another way of searching the linked list faster? I can't think of another approach especially with the way the structure is built now. Maybe I need to change it, but that will require major changes in the code.
    I would probably do those "major changes" if it were me. I'm sure they can't be that bad.
    However an alternative approach is to insert the address of every node (as the data to store) into a binary tree of some kind (perhaps a splay tree), or into a hash table.
    quzah's suggestion could be thought of as a kind of primitive hash-table.
    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"

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Some help with make my programs faster
    By Sshakey6791 in forum C++ Programming
    Replies: 11
    Last Post: 12-11-2008, 12:41 PM
  2. What to make?
    By Caldus in forum C++ Programming
    Replies: 4
    Last Post: 04-06-2005, 01:12 PM
  3. A few questions on programs and when they can run...
    By Junior89 in forum Windows Programming
    Replies: 2
    Last Post: 04-05-2005, 07:47 PM
  4. Making standalone APP run in background
    By hart in forum Windows Programming
    Replies: 3
    Last Post: 02-27-2005, 10:20 AM
  5. plz help me run this program!!!
    By galmca in forum C Programming
    Replies: 8
    Last Post: 02-01-2005, 12:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21