Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Tutorials
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site
Search in forums












SourceForge.net Logo
Home » Community » Coffee corner » alternative to array of linked list
alternative to array of linked list [message #46369] Mon, 02 May 2016 00:52 Go to next message
forlano is currently offline  forlano
Messages: 1110
Registered: March 2006
Location: Italy
Senior Contributor
Hello,

I am doing experiments with molecular dynamics.
The domain of simulation is divided in cells and each cell contains a number of particles.
The particle can move from a cell to another.
Usually it is used an array of linked list. I would like to replicate this structure with U++ containers.
I do not know what to use:
Vector< Vector<int> >
Vector< Index<int> >
Map< ... >
something else?
Here the speed is very important: search quickly a particle in a given cell, delete it, move in another cell.
Does anybody have suggestions? If somebody have already done similar experiment snippet code are greatly appreciated.

Thanks,
Luigi
Re: alternative to array of linked list [message #46370 is a reply to message #46369] Mon, 02 May 2016 01:55 Go to previous messageGo to next message
Lance is currently offline  Lance
Messages: 362
Registered: March 2007
Senior Member
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 Go to previous messageGo to next message
mr_ped is currently offline  mr_ped
Messages: 810
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 #46372 is a reply to message #46369] Mon, 02 May 2016 08:22 Go to previous messageGo to next message
koldo is currently offline  koldo
Messages: 3231
Registered: August 2008
Senior Veteran
Hello Forlano

What method are you using?

I have had some experience with SPH and LBM.


Best regards
Iñaki
Re: alternative to array of linked list [message #46373 is a reply to message #46371] Mon, 02 May 2016 08:30 Go to previous messageGo to next message
forlano is currently offline  forlano
Messages: 1110
Registered: March 2006
Location: Italy
Senior Contributor
mr_ped wrote on Mon, 02 May 2016 02:32

There's probably million possible ways, and to get some near-optimal advice you would have to show here the whole process and details.


Thanks both for reply!

Few more details. The particles are all the same and can be a huge number for example 1000 (and more if one has a super computer!). In principle the particle interacts with all others (particle i exerts a force on j and viceversa). As result of this interactions the particle can freely move around the domain.
However the interaction range of such force is just a fraction of the whole dimension of the simulation domain (you may think a square DxD). To save a lot of computation time then come up the concept of cell. Each has dimension d=D/n, where d a bit gretear than the force range.
In this way you can scan the domain by cell, pick a particle inside it and look for other particles that stay in the same cell and in its neighbour cells (https://en.wikipedia.org/wiki/Cell_lists)
Each cell must have a container of the particle they belong to. During the upgrade process I must pick a particle from one cell (find and delete it) and move in another one (append).

I never used std::set. Perhaps it can be a good alternative to linked list.

Thanks,
Luigi
Re: alternative to array of linked list [message #46374 is a reply to message #46372] Mon, 02 May 2016 08:36 Go to previous messageGo to next message
forlano is currently offline  forlano
Messages: 1110
Registered: March 2006
Location: Italy
Senior Contributor
koldo wrote on Mon, 02 May 2016 08:22
Hello 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 #46380 is a reply to message #46374] Tue, 03 May 2016 15:36 Go to previous messageGo to next message
koldo is currently offline  koldo
Messages: 3231
Registered: August 2008
Senior Veteran
It sounds very similar to SPH ( https://en.wikipedia.org/wiki/Smoothed-particle_hydrodynamic s), but I do not understand the role of the cells. Questions:
- Is the number of particles "almost" the same in all simulation?
- How is every solving step/iteration?. In the "explicit" case:
--- First, are computed the forces that act over every particle?
--- Second, is the movement of every particle computed depending on the forces?

If the problem is similar to this, you can:
- use a fixed list of particles.
- do a terrific parallelization Smile


Best regards
Iñaki
Re: alternative to array of linked list [message #46382 is a reply to message #46380] Tue, 03 May 2016 20:30 Go to previous messageGo to next message
forlano is currently offline  forlano
Messages: 1110
Registered: March 2006
Location: Italy
Senior Contributor
koldo wrote on Tue, 03 May 2016 15:36
It sounds very similar to SPH ( https://en.wikipedia.org/wiki/Smoothed-particle_hydrodynamic s), but I do not understand the role of the cells. Questions:
- Is the number of particles "almost" the same in all simulation?
- How is every solving step/iteration?. In the "explicit" case:
--- First, are computed the forces that act over every particle?
--- Second, is the movement of every particle computed depending on the forces?

If the problem is similar to this, you can:
- use a fixed list of particles.
- do a terrific parallelization Smile


The answer is YES.
The problem is that I have only one CPU.
Anyway I have implemented a
std::vector< std::unordered_set<int> >
and I am very happy. The code is very clean and easy to read.

Luigi
Re: alternative to array of linked list [message #46389 is a reply to message #46382] Wed, 04 May 2016 09:53 Go to previous message
koldo is currently offline  koldo
Messages: 3231
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
Previous Topic: MT opens up whole new can of worms :)
Next Topic: Outage...
Goto Forum:
  


Current Time: Sat Nov 28 17:13:16 CET 2020

Total time taken to generate the page: 0.01461 seconds