|
|
Home » Community » Coffee corner » alternative to array of linked list
|
Re: alternative to array of linked list [message #46370 is a reply to message #46369] |
Mon, 02 May 2016 01:55 |
Lance
Messages: 526 Registered: March 2007
|
Contributor |
|
|
Linked list may not be a good option for this application.
In general, you will be happy with O(logN) insert,delete,search time complexity. std::set, set::map, std::unordered_set, set::unordered_map, or u++ VectorMap should all be good candidate. Maybe even Upp::InVector (I am not sure though). If class Particle is of considerable size, you can put them in either a Upp::Vector or a std::vector, and actually put its index in the vector in cell's particles container.
experiment with std::set, set::unordered_set, Upp::VectorMap etc, see which offer best performance for your application.
|
|
|
Re: alternative to array of linked list [message #46371 is a reply to message #46369] |
Mon, 02 May 2016 02:32 |
mr_ped
Messages: 825 Registered: November 2005 Location: Czech Republic - Praha
|
Experienced Contributor |
|
|
If the speed is very important, why do you bother about moving particles around?
I think the simulation itself is more computationally expensive, and the data structures should be optimized for that, not for particles movement solely (although that's part of it for sure).
For example, if the particles are of the same type, and have the completely same attributes, and the number of types is much lower than amount of particles, you may have for each cell just counters of each type, so moving particle between cells will be --, ++ operation.
Or if you process all the particles during simulation, and you don't must to process them per-cell in ordered way, you can store all particles in single array (vector), and just have "belongs_to_cell" index inside them, which is updated upon movement. And process them all the time in sequentially in the array.
Or if amount of particles per cell is quite average across all cells with no extremes, you can have some vector<int> in each cell with index into particle array, the vector with some reasonable buffer and pointer to last inserted particle, then do a move as old_cell.particle_index[x] = -1; // free slot, new_cell.particle_index[search_for_free_slot(last_insert_ind ex)] = particle_index;
Etc..
There's probably million possible ways, and to get some near-optimal advice you would have to show here the whole process and details.
|
|
|
|
|
Re: alternative to array of linked list [message #46374 is a reply to message #46372] |
Mon, 02 May 2016 08:36 |
|
forlano
Messages: 1185 Registered: March 2006 Location: Italy
|
Senior Contributor |
|
|
koldo wrote on Mon, 02 May 2016 08:22Hello Forlano
What method are you using?
I have had some experience with SPH and LBM.
Hi Koldo,
I do not know SPH and LBM. I have implemented an array of cell and each element contains a linked list of the particle id. Moreover I have an array of Particle which hold all physics stuff. But I am not satisfied by the result.
I would like to use something cleaner ans faster with find and delete.
Best regards,
Luigi
[Updated on: Mon, 02 May 2016 08:37] Report message to a moderator
|
|
|
|
|
Re: alternative to array of linked list [message #46389 is a reply to message #46382] |
Wed, 04 May 2016 09:53 |
|
koldo
Messages: 3357 Registered: August 2008
|
Senior Veteran |
|
|
Are you sure that you have one CPU with one core/thread or with more than one core/thread?. If yes, the second phase could be parallelized.
If the number of particles is almost unaltered, a simple C/C++ array (malloc/new) or a U++ Buffer<> could be used.
Best regards
Iñaki
|
|
|
Goto Forum:
Current Time: Thu Apr 25 13:59:31 CEST 2024
Total time taken to generate the page: 0.02355 seconds
|
|
|