Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Best way to keep track of numbers used

Eric Pascarello
author
Rancher
Posts: 15385
6
What is the best way to keep track of integers used? The integer set can be infinite and the list of used integers can be extremely long.

Eric

David Newton
Author
Rancher
Posts: 12617
Bitmap?

fred rosenberger
lowercase baba
Bartender
Posts: 12231
36
Are they random, or are they a series of some kind?

Does the set size change - does it grow and shrink once created?

What is most important to you - speed? memory utilization?

Does the list need to be sorted? members inserted in the middle? members deleted from the middle?

Will you 'use' consecutive integers? I.e. can you keep track of the first and last you used (or a list of ranges you've used)?

David Newton
Author
Rancher
Posts: 12617
Will you 'use' consecutive integers? I.e. can you keep track of the first and last you used (or a list of ranges you've used)?

I like that one (under the right conditions); sort of RLE the set of used ints.

Lester Burnham
Rancher
Posts: 1337
The java.util.BitSet class could be useful for this, given the right usage scenario.

Eric Pascarello
author
Rancher
Posts: 15385
6
Basic stuff:
• I want to keep track of the integers and see if a number was used previously.
• There will be no other operations done on this group of integers.
• All numbers will be appended to the list as it grows.
• The size is unknown.
• The integers are basically random.
• The faster the better.

• I would like it to be fast since this is being used in an algorithm that runs through equations and it eventually starts to loop. I am trying to find the first time it starts to repeat.

I already wrote this in JavaScript, trying to find the best practice for Java in this scenario.

Basic JavaScript code is

I have limited knowledge in Java, just trying to convert some code for fun. There will be a bunch more questions in the future!

Eric

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
The Java equivalent would be to use a HashSet; it would work pretty much the same way:

Eric Pascarello
author
Rancher
Posts: 15385
6
Ernest Friedman-Hill wrote:The Java equivalent would be to use a HashSet; it would work pretty much the same way:

HashSet is what I been using. I was not sure if that was the best tool for the job. I originally started with an ArrayList and found out that was not the best idea.

Eric

David Newton
Author
Rancher
Posts: 12617
The only reason I didn't suggest a map implementation is because of the potentially large size you mentioned.

David O'Meara
Rancher
Posts: 13459
With a HashSet you would be limited to Integer.MAX_INT entries (due to the backing array) and the performance would depend on the size - too large would be a memory hog, too small would have too many collisions.
As stated, BitSet could be useful if you want to move into extraordinarily large numbers.
I once wrote a bitwise operation that was an array of ints where each bit represented a boolean state for a couple of billion numbers.

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
It has good performance and is easy to code, and it's almost certainly the best solution if your set of numbers is reasonably sparse (i.e., below about 10 million or so.) If you actually expect more than that, then the other solution is to actually make an array with 4 billion bits (one bit for every integer, say 6.25M longs) and then check/set the presence of an integer by looking at the corresponding bit. This is more complicated code (it could be hidden inside some functions, of course) but it uses just one huge 500M block of memory.

As DOM points out, BitSet implements this for you.

David O'Meara
Rancher
Posts: 13459
Ernest Friedman-Hill wrote:...but it uses just one huge 500M block of memory.

Yeah I've been there, but it isn't as much as a problem as it once was.
Ernest Friedman-Hill wrote:As DOM points out, BitSet implements this for you.

Mr Newton went there first (mostly), straight out of the blocks, even.

David O'Meara
Rancher
Posts: 13459
and BitSet is still 'limited' to 2^31 bits, but if you feel like writing your own bitwise operation based on an array of int or longs you can get to 2^63 ie more than you have available memory, fingers and toes included.

Campbell Ritchie
Sheriff
Posts: 50687
83
How do you get 2^63 into an array of (2^31 - 1) * 64 bits?

Eric Pascarello
author
Rancher
Posts: 15385
6
If you are interested with what I am playing with and have a topcoder account: http://cotm.topcoder.com/?module=ViewProblemStatement&compid=9042&rd=13674

I am attacking the problem 100% wrong. Brute force will not win over some fancy algorithm that Math Geeks can whip out.

I just wanted to play around with it as an excuse to write code in a different language.

Eric

Campbell Ritchie
Sheriff
Posts: 50687
83
Don't have a topcoder account, I am afraid.

Eric Pascarello
author
Rancher
Posts: 15385
6
Campbell Ritchie wrote:Don't have a topcoder account, I am afraid.

You can always create a throw away one.

Eric

Campbell Ritchie
Sheriff
Posts: 50687
83
Sounds a good idea, but I need to go and do some cooking now

Eric Pascarello
author
Rancher
Posts: 15385
6
Campbell Ritchie wrote:Sounds a good idea, but I need to go and do some cooking now

Cooking is overrated when there are algorithms to code. lol

Campbell Ritchie
Sheriff
Posts: 50687
83
When the wife wants her dinner and there's nothing to eat, I would have to work out an algorithm for getting out alive

Eric Pascarello
author
Rancher
Posts: 15385
6
Campbell Ritchie wrote:When the wife wants her dinner and there's nothing to eat, I would have to work out an algorithm for getting out alive

Eric