2

I have a small set of positive integers (roughly 10 numbers), each of which is a power of two.

How can I map each number to some other number as quickly as possible?

Here are two solutions that would work but, considering the simplicity of the problem (and how few keys I have), they both seem needlessly sluggish (am I wrong?):

Avoiding the mapping problem altogether by, e.g., replacing my integers with a struct that carries the pairs together would probably be the fastest solution but it would complicate much of my code, so I'm not willing to do this.

Community
  • 1
  • 1
lemon
  • 188
  • 6
  • Could you paste up the transformation table (assuming the mapping is not arbitrary)? There might be a clever bit twiddle trick. – Bathsheba Jun 06 '16 at 09:56
  • @Bathsheba Unfortunately the values that the keys map to were randomly generated numbers. – lemon Jun 06 '16 at 09:57

1 Answers1

6

Don't compute anything. You can't do better than 10 int comparisons from low-level cache.

Just have a vector with your values and run a loop to find the index of the number you want and use the index to lookup in another vector the reset of the data.

For performance it's better if the key ints are close together so that you get the most out of the processor cache. However it's not going to be a lot slower if you have a vector of pairs or something like that. You should try to do a benchmark and see if you really need the last drop of performance or if you can sacrifice a bit of performance for simplifying the data structure.

Sorin
  • 11,863
  • 22
  • 26