On Wednesday, 11 February 2015 20:11:27 UTC, Pablo Zubieta wrote:
>
> Hi again,
>
> There were some bugs in my implementations. I updated the gist
> <https://gist.github.com/pabloferz/01675f1bf4c8be359767#file-levicivita-jl>
> with the corrected versions and added a simpler looking function (but of
> O(n²) running time).
>
> I did some tests and found (with my slow processor) that for permutations
> of length <= 5 the quadratic implementation (levicivita_simple) performs
> as fast as the (levicivita_inplace_check). For lengths from 5 to 15,
> levicivita_inplace_check
> is the fastest, followed by levicivita_simple. For lengths from 15 to 25
> levicivita_simple
> and levicivita perform the same (but slower than levicivita_inplace_check).
> For more than 25 elements levicivita_inplace_check is always the fastest,
> 2x faster than levicivita and n times faster than levicivita_simple.
>
> For people wanting the 3D Levi-Civita tensor, levicivita_simple and
> levicivita_inplace_check
> should be the same. For people wanting the parity of a permutation for long
> permutations levicivita_inplace_check should work the best.
>
For small n I would have expected a lookup-table (LUT) approach to be the
best approach. Obviously there is a memory-cpu trade-off, but for n=3
there would only need to be 6 table entries! My suggestion would be to
employ memoisation and build up the LUT on the fly. Also, I would suggest
only caching the results for inputs that are actually permutations. I think
a slower code path for inputs that do not represent permutations would be
acceptable.
