Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Agile forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Best way to keep track of numbers used

 
Eric Pascarello
author
Rancher
Posts: 15385
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Bitmap?
 
fred rosenberger
lowercase baba
Bartender
Posts: 12086
29
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The java.util.BitSet class could be useful for this, given the right usage scenario.
 
Eric Pascarello
author
Rancher
Posts: 15385
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
    Pie
    Posts: 24208
    35
    Chrome Eclipse IDE Mac OS X
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    The Java equivalent would be to use a HashSet; it would work pretty much the same way:

     
    Eric Pascarello
    author
    Rancher
    Posts: 15385
    6
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    IntelliJ IDE Ruby
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Android Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Pie
    Posts: 24208
    35
    Chrome Eclipse IDE Mac OS X
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Android Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Android Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 48402
    56
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    How do you get 2^63 into an array of (2^31 - 1) * 64 bits?
     
    Eric Pascarello
    author
    Rancher
    Posts: 15385
    6
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 48402
    56
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Don't have a topcoder account, I am afraid.
     
    Eric Pascarello
    author
    Rancher
    Posts: 15385
    6
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 48402
    56
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Sounds a good idea, but I need to go and do some cooking now
     
    Eric Pascarello
    author
    Rancher
    Posts: 15385
    6
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 48402
    56
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
     
    • Post Reply
    • Bookmark Topic Watch Topic
    • New Topic