← Back to team overview

yade-users team mailing list archive

[Fwd: Re: Contact detection]


(happens to everybody)
--- Begin Message ---

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.



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

--- End Message ---