0

I have a Set of BigInteger that I want to cache. This Set can go up to ~100K size.

The application i'm using is quite light : it does not have a lot of memory (heap about 256mb) and does not use a database (the team is considering it for later, but now it is not possible).

Upon initialization, it receives a big array of BigInteger that needs to be stored in a File for future use.

The application then needs to check if a particular BigInteger is stored into the given file.

Considering the memory implications, what would i need to do in order to store efficiently these values then check if a given value is present in the file ?

Jordi Castilla
  • 26,609
  • 8
  • 70
  • 109
Laurent B
  • 2,200
  • 19
  • 29

2 Answers2

1

Let's assume each BigInt takes up 20 bytes. Then 100k of them take up ~2MB, less than 1% of heap size. Hopefully it's something you can afford to just keep in RAM.

I'd sort them and put into an array, then use binary search to efficiently check if a particular value is in the array.

Update: an array is most compact representation; a tree would waste 12 to 24 bytes per item just on three pointers.

9000
  • 39,899
  • 9
  • 66
  • 104
  • 20 bytes is a lot less than I'd expect for a typical `BigInteger`. In fact, I'm not even sure the smallest `BigInteger` fits in 20 bytes. – Louis Wasserman May 25 '15 at 21:16
  • @LouisWasserman: still it could be a noticeable percent. The payload of a reasonably small `BigInteger` is probably 16 bytes (two 64-bit words), plus 4-8 bytes of object header (think 'VMT pointer'). – 9000 May 26 '15 at 03:21
0

The size of a BigInt is variable, but you can assume that 100K BigInt object won't use more than 10MB. The easiest way to store them in order to search anyone quickly is using a TreeSet, which is a implementation of a SortedSet.

Community
  • 1
  • 1
Pablo Lozano
  • 10,122
  • 2
  • 38
  • 59