A java list randomizer
This week I came across what seemed like a simple programming problem. From a large list of items I wanted to create a smaller list with random items copied from the larger list. The real world equivalent of would be something like bring me four random records from your CD collection. Sounds simple? Well, there was an additional requirement on that I put on the solution, and that was that the smaller list should contain no duplicates.
There is a Random class in java that returns pseudorandom numbers. However, there is no guarantee that when calling Random.nextInt() a number of times the same number will not be returned twice. In other words, the simple strategy filling a small list with elements from the large list picked at random with the help of Random.nextInt() will probably produce a result list when the same element is added twice. Not good enough.
One defense against that problem could be to keep track of which numbers the random generator has returned and simply discard any duplicates. For most cases that strategy is probably efficient, but sometimes it could lead to having to discard a whole bunch of random numbers. Moreover, execution times of such a solution would differ a lot depending on which numbers Random.nextInt() returned.
Another solution would be to copy all of the large list to a temporary list and remove each element taken to the smaller list from the temporary list. That way, no item would be added twice to the result list. However, if the source list is long, say a million entries, creating a temporary list to fetch holding all the million entries just to extract 100 random entries would be inefficient.
The elegant solution to this problem in my mind would instead be to create a list of offsets into the large list as long as the small list. The list of offsets would then be modified to emulate the effect of having a copy of the large list and removing entries from it. If the first entry of the offset list is offset 1, and the second offset also is 1, modify that to 2 instead, the element that would have been at position 1 if the original element at that position was removed.
I wrote a class implementing this solution, Randomizer.java. Feel free to use it or modify it anyway you wish.
Filed under Geeky, Programming | Comment (0)The joy of unnecessary optimizations
The overwhelming majority of all professional programming is about solving a large number of simple problems. The intellectually challenging problems are rare and in many situations solving a problem with a complicated but efficient solution is hard to justify. It is much cheaper to buy a faster computer with more memory to run your program than it is to write a smarter program that uses less resources.
However, I really enjoy the challenge of writing efficient and elegant code that solve a particular problem, so sometimes when I get a bit of free time and want to do something relaxing I spend time writing solutions to small programming puzzles that I run across in my day job working for Voxbiblia.
The next post contains the solution to one such puzzle and the solution I just wrote. It might be interesting to some.
Filed under Geeky | Comment (0)CentOS prerelease security
The CentOS Linux distribution is in many respects the optimal choice for anyone that wants a stable system that is supported over a number of years. I run it on a handful of servers and the problems are few and far between.
However, one thing has been emerging as a bit of a problem lately, and that is that security updates from Red Hat has taken quite some time to get built and released for CentOS. This is especially true in the weeks following a new point release from Red Hat. Not having security updates available for known problems for weeks a the time makes users of CentOS less secure than they would otherwise be.
To help make this problem a bit less pronounced I have started to rebuild security updates from Red Hat and installing them on the systems I administer. That's one of the beauties of open source, you can fix things. If anyone else is interested in those updated packages they can be found at http://rpm.resare.com/centos5-pre-security. If you're in the target demographic you'll know what to do.
Filed under centos | Comment (0)