← Back to team overview

yade-users team mailing list archive

Re: Contact detection

 



InsertionSortCollider is typically over O(N*log N) depending on number
of inversions (optimal O(N), worst case O(N^2)); bad enough given that
there are algos which are _always_ O(N).

1000xN is worst than 0.0001xN^2 for practical problems, right? ;)

For instance : TriangulationCollider is O(N), but I never use it, because it is the slowest collider in Yade currently.

QuickSort collider is much slower than InsertionSortCollider, since
quicksort is optimal in the general case, but not for substantially
pre-ordered lists... see http://yade.wikia.com/wiki/Colliders_performace
(insertionsort is about 5x faster for non-initial steps).

Yes, sorry, I was thinking about InsertionSort (the new one), not QuickSort.


Bruno

--

_______________
Chareyre Bruno
Maître de Conférences

Grenoble INP
Laboratoire 3SR - bureau E145
BP 53 - 38041, Grenoble cedex 9 - France
Tél : 33 4 56 52 86 21
Fax : 33 4 76 82 70 43
________________




References