in reply to Re^2: Fastest way to lookup a point in a set
in thread Fastest way to lookup a point in a set

You did not answer his question though. Can you batch the queries or do you need to run them one by one?

If batching is allowed, then LanX has more or less revealed the solution. The problem is then very similar to sorting, and the fastest way to sort is probably the usual radix sort. (Maybe with AVX512 the balance has tipped in favor of merge sort; but I haven't tested that.)

Once you have binned/sorted the queries, the lookup is essentially a linear pass over the (sorted) dataset. Don't loop over queries, map them.

  • Comment on Re^3: Fastest way to lookup a point in a set

Replies are listed 'Best First'.
Re^4: Fastest way to lookup a point in a set
by eyepopslikeamosquito (Archbishop) on Aug 07, 2017 at 21:42 UTC

    Thanks for the tip. There is some scope for batching, I believe, and I hadn't thought of sorting. I'll write a new root node in the next day or so with details on the full problem.

    Update: the new root node: High Performance Game of Life

[reply]

In Section Seekers of Perl Wisdom