U++ forum: Welcome to the forum

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.

Report message to a moderator