Jump to content
  • Advertisement


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


Is this a new way to search?

This topic is 6185 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!