Archived

This topic is now archived and is closed to further replies.

RolandofGilead

Is this a new way to search?

Recommended Posts

First, thanks to everyone who read or responded to my last post. Judging by its name, what I have in mind might be a skip list. Anyway, I thought of it before I posted my last thread and I''d like to think I''m able to come up with a good idea even if someone has beaten me to the punch. Suppose we have a linked list(currently single, lol). That was a bad joke/pun I know. As nodes are added to the list, each one is sorted and put into its proper place. There is another pointer which points to the middle of the list. /* // We(good thread) compare the middle of the list with // whatever we''re searching for and if it''s lower we start // searching from the beginning, if it''s higher we search // from that point forward, and if we''ve found it then that''s // great. */ Also, this can can be expanded to any number of indices, but dividing the list into quarters is plenty for me, as updating the indices grows more complex as more indices are added. A counter could be used to keep track of nodes added, and when two nodes have been added or deleted, the index moves up or down as needed(for a single index). When searching with multiple indices, a compare to the middle just bumps you up to either a higher or lower index. (If I''m not mistaken, kind of like a binary search.) It doesn''t add much complexity and can significantly shave off search times, sorting doesn''t add too much hassle because you can utilize the search algorithm to find where it needs to go. Save gamedev.net! http://www.gamedev.net/donate.asp I think there''s a thread on it somewhere. Create.

Share this post


Link to post
Share on other sites
No, it''s not new, just a bad way of doing something old

I''m too busy to search for the other thread to see exactly why you''re using a list for this, but I personally would find something a bit more appropriate than a list if search time is important. If nodes are sorted, I would use an STL set. This gives you automatic insert sorting and search speed roughly equivalent to a binary search. But it depends on how you are going to manipulate the elements.

Your method does work, to a small degree, providing you can keep the ''middle'' node in a decent place. You could achieve similar sorts of optimisation by comparing the search value with the values at the start and end, and depending on which was closest, search forward from the the start or backwards from the end. You can combine that method with the one you mentioned already, if you liked.

Share this post


Link to post
Share on other sites