yade-users team mailing list archive
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.
Maître de Conférences
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