aspose file tools*
The moose likes Beginning Java and the fly likes Best way to keep track of numbers used Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Best way to keep track of numbers used" Watch "Best way to keep track of numbers used" New topic
Author

Best way to keep track of numbers used

Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    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

Joined: Sep 29, 2008
Posts: 12617

Bitmap?
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11402
    
  16

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)?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
David Newton
Author
Rancher

Joined: Sep 29, 2008
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

Joined: Oct 14, 2008
Posts: 1337
The java.util.BitSet class could be useful for this, given the right usage scenario.
Eric Pascarello
author
Rancher

Joined: Nov 08, 2001
Posts: 15376
    
    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

    Joined: Jul 08, 2003
    Posts: 24187
        
      34

    The Java equivalent would be to use a HashSet; it would work pretty much the same way:



    [Jess in Action][AskingGoodQuestions]
    Eric Pascarello
    author
    Rancher

    Joined: Nov 08, 2001
    Posts: 15376
        
        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

    Joined: Sep 29, 2008
    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

    Joined: Mar 06, 2001
    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

    Joined: Jul 08, 2003
    Posts: 24187
        
      34

    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

    Joined: Mar 06, 2001
    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

    Joined: Mar 06, 2001
    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

    Joined: Oct 13, 2005
    Posts: 39393
        
      28
    How do you get 2^63 into an array of (2^31 - 1) * 64 bits?
    Eric Pascarello
    author
    Rancher

    Joined: Nov 08, 2001
    Posts: 15376
        
        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

    Joined: Oct 13, 2005
    Posts: 39393
        
      28
    Don't have a topcoder account, I am afraid.
    Eric Pascarello
    author
    Rancher

    Joined: Nov 08, 2001
    Posts: 15376
        
        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

    Joined: Oct 13, 2005
    Posts: 39393
        
      28
    Sounds a good idea, but I need to go and do some cooking now
    Eric Pascarello
    author
    Rancher

    Joined: Nov 08, 2001
    Posts: 15376
        
        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

    Joined: Oct 13, 2005
    Posts: 39393
        
      28
    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

    Joined: Nov 08, 2001
    Posts: 15376
        
        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
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Best way to keep track of numbers used