3

I have a Tuple object that holds 3 primitives: Tuple(double, long, long). To avoid creating a huge amount of Tuple, I'm thinking using Trove library's primitive MAP, which would take two primitive as key and value. In my case, it would be Map<double, some primitive>.

My question: is it possible efficiently to encode the two long into a single primitive that I can store in the map, and later decode them?

2
  • Perhaps you can store you data as double[], long[], long[] for all your Tuples. Aug 1, 2011 at 18:38
  • The tuples are sorted by double, and longs are just associated information.
    – Wei Shi
    Aug 1, 2011 at 18:43

4 Answers 4

7

is it possible efficiently to encode the two long into a single primitive

No, simply because longs are 64-bit, and no Java primitive is longer than that. You would need a 128-bit primitive to encode two longs into it.

1

It's right, you cannot pack two 64-bit primitives into another primitive, which is at most 64 bits of size. Both, double and long by standard are mapped by 64 binary digits.

The question is, whether you can impose some restrictions on the numbers you are dealing with. If you know, you will always have even numbers or uneven numbers or the first component will have integer range or you are dealing with multitudes of 1000, you can win some bits here.

Practically speaking, you will never make use of all

2^64 x 2^64 combinations

of pairs of long values.

On the other hand, it's no big deal to handle maps on pairs of values. That was the whole effort to make object-oriented languages like Java to not only deal with data types like struct in C, but also to bind methods to the data. You can find good implementations of a Pair class in the web, e.g. angelikalanger.com. Or you can easily code an implementation yourself, especially, since you only need a pair of Long values.
Also consider to use Pair<Double, Pair<Long, Long>> or implement a Tuple<M,N,T> class right away instead of a Map, i.e. key-value combination, following the outline of the Pair<M,N> implementation.

Finally, you could even employ an in-memory database like H2 to hold your Tuple(double, long, long) entries. It is enough to enclose it in your project as a Java library and configure it properly.

By the way, a 3-tuple is called a triple. Therefore, you could correctly call your class Triple(double, long, long) or better Triple(Double, Long, Long).

3
  • What if I know the two long are both positive (0~2^63-1)?
    – Wei Shi
    Aug 2, 2011 at 15:28
  • If both numbers are positive, you win two bits, one each. (You could store both in 126 bits then.) That would only matter, if you pack both into a BigInteger or use a native (machine) data structure. Aug 3, 2011 at 19:31
  • Your statement is very naïve. In information-theoretical fields like chaos theory or crptography, all bits in a (primitive) value will be used, Even if you don't use 2^65 different values, the handful of values that you do use have full 128-bit entropy, meaning all 128 bits should be accounted for and are incompressible. The latter statement also implies that even given 127 bits, the 128th bit is unpredictable (unless the entropy is 127 bits or less) Mar 15, 2016 at 20:02
1

You could use Trove's double-Object map and encode the two longs into a BigInteger, but if your objective is to stay strictly with primitive types, that obviously isn't any help.

0

As Joonas says, there is no single primitive that will hold 128 bits. What might meet your need is to use an array to hold the two longs: Map<Double, long[]>. While Double and long[] are not strictly primitives that might suit. Remember that you cannot put double (small-d) into a Map as Maps can only contain reference types, not primitives.

Alternatively, how about Map(Double, Pair), where Pair is a small class to hold two longs? Most libraries have something like that lying around somewhere.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.