- It wastes memory as there is another list in memory
- It wastes CPU cycles. Objects coordinates are updated every frame, meaning that the second linked list has to be destroyed and recreated each frame. Major problem
Rapid sorting of linked-list
Author
Here''s the problem I''m facing. All my sprites are stored in a linked list. because it is an isometric game, what I''m doing at the moment is going through the list and drawing the sprites with the highest Y coordinate value first, followed by those with lower Y coordinate values.
The problem with this approach is that it requires many passes. One way I''ve managed to solve this is to create a seperate linke d-list that does an insertion sort. This brings about 2 major problems.
One approach would be to have an array of pointers to you linked list node type. Walk through the linked lists adding them to the array, then quick sort that array.
This means you never actually sort you linked list only the temporary array.
Another approach is when adding to the linked list insert the node at the correct place, but if you change the depth order of the sprite you would have to cut then re-add it.
[The views stated herein do not necessarily represent the view of the company Eurocom ]
Eurocom Entertainment Software
www.Eurocom.co.uk
The Jackal
This means you never actually sort you linked list only the temporary array.
Another approach is when adding to the linked list insert the node at the correct place, but if you change the depth order of the sprite you would have to cut then re-add it.
[The views stated herein do not necessarily represent the view of the company Eurocom ]
Eurocom Entertainment Software
www.Eurocom.co.uk
The Jackal
Author
The array approach sounds more plausible than the remove and reinsert method. I might take a look into it, but my original question still stands. Is there a way to apply a quick sort to a linked list?
It may also be an idea to adapt your list node insertion code to walk the list and place the node in a sorted position.
Also depending on the operations and how nodes are created you another idea is to put the nodes themselves into a pre-allocated array (aka pool) i.e. if you know that every frame you always have between 80 and 158 nodes per frame rather than using a normal memory allocator, just make an array of nodes with 158 entries - this can (with smallish nodes) do wonders for your cache coherency compared to using malloc/new to allocate nodes.
We do something similar to handle texture changes - although we use multiple lists (all within an array though) one for each unique texture encountered, and also a list of lists for fast lookups.
--
Simon O''''Connor
Creative Asylum Ltd
www.creative-asylum.com
Also depending on the operations and how nodes are created you another idea is to put the nodes themselves into a pre-allocated array (aka pool) i.e. if you know that every frame you always have between 80 and 158 nodes per frame rather than using a normal memory allocator, just make an array of nodes with 158 entries - this can (with smallish nodes) do wonders for your cache coherency compared to using malloc/new to allocate nodes.
We do something similar to handle texture changes - although we use multiple lists (all within an array though) one for each unique texture encountered, and also a list of lists for fast lookups.
--
Simon O''''Connor
Creative Asylum Ltd
www.creative-asylum.com
Nuffsaid,
If you know how many elements are in the linked list (which would be pretty easy), then, yes, you could do a quicksort or merge sort. Just set the high, middle, and low pointers to the right place, and start the algorithm. The implementation would be a bit more complex than using an array, but if you have good list manipulation functions, then it shouldn''t be a big problem.
Nutts
If you know how many elements are in the linked list (which would be pretty easy), then, yes, you could do a quicksort or merge sort. Just set the high, middle, and low pointers to the right place, and start the algorithm. The implementation would be a bit more complex than using an array, but if you have good list manipulation functions, then it shouldn''t be a big problem.
Nutts
You can perform merge sort on a linked list rather easily.. The trick is how you break the list in half. Because it''s a linked list, just taking the first half and the second half isn''t really a good idea. Instead, it''s better to divide the list into elements at even positions and elements at odd positions, mergesort those smaller lists, then join them.
Because I''ve got it sitting around, I''ll post some code for doing that in OCaml.
I don''t expect you''ve ever seen any variant of ML before, so that''s probably useless... But it does show that sorting a linked list can be done in place, in O(n lg n) time.
Because I''ve got it sitting around, I''ll post some code for doing that in OCaml.
let rec mergeSort lst = let rec split ls = match ls with [] -> ([], []) | [hd] -> ([hd], []) | first :: second :: rest -> let l1, l2 = split rest in (first :: l1, second :: l2) and merge tup = match tup with [], [] -> [] | ls, [] -> ls | [], ls -> ls | h1 :: t1, h2 :: t2 -> if h1 <= h2 then h1 :: (merge (t1, h2 :: t2)) else h2 :: (merge (h1 :: t1, t2)) in match lst with [] -> [] | [hd] -> [hd] | _ -> let l1, l2 = split lst in merge (mergeSort l1, mergeSort l2);; I don''t expect you''ve ever seen any variant of ML before, so that''s probably useless... But it does show that sorting a linked list can be done in place, in O(n lg n) time.
I know there is an "optimized" sort for linked lists, because STL provides a container-specific "sort" method for lists, but I don''t know what that method is. Generally, "sort" and "linked list" shouldn''t be mentioned in the same breath. Sounds like you''re trying to have your cake and eat it too. If I were you I''d keep with the two-container method and just eat the memory waste, but it depends on the size of your containers.
Author
Just had a look at the STL headers and man, I don''t understand a thing. It is all way too cryptic for me.
I''m using a double linked list, so I presume, using a quicksort isn''t going to be much of a problem(huh?). I''ve got no idea how to do that. I''ll try figure out c_wraith''s code later. Mind is too fuzzy now to do anything...
Thanks a lot for the info.
I''m using a double linked list, so I presume, using a quicksort isn''t going to be much of a problem(huh?). I''ve got no idea how to do that. I''ll try figure out c_wraith''s code later. Mind is too fuzzy now to do anything...
Thanks a lot for the info.
quicksort is a problem in linked lists because in order for quicksort to be efficient, it requires efficient random access to the container. Linked lists--even double-linked lists--have linear random access times, the worst you can get. This is why I said it looked like you''re trying to "have your cake & eat it too": linked lists buy you fast insertion at any point at the cost of slow random access. It''s what we call in the biz a "tradeoff".
You could keep a fixed size array of pointers to your nodes just make it far bigger then you''ll ever need. Or each node could have multible links (like next1,next2) so that the list could be gone through in two different ways one could be sorted with out fucking up the other.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
