yade-users team mailing list archive
Mailing list archive
Re: Contact detection
> In an arbitrary step of Yade (not the first one), you have an ordered
> list with just a few elements to move, and you will only compare
> coordinates that are close to each other.
> I'm not claiming that the algorithm is perfect and I'm all for
> improvement (and actually, I don't even know if it is still used in the
> latest QuickSort collider), but at least it is not a N^2 algorithm.
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).
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).