Dear DDJ,
In the January 1998 issue of DDJ, John Boyer discusses resizable data structures in "Algorithm Alley." Under the heading "Java and the STL," he discusses the Java hash table and the C++ STL Vector class.
I would like to add that Java in the java.util package also has a Vector class available. This Java Vector class is a fully resizable data structure. Its elements can be any object, including other vectors.
Using the constructor Vector(0);, this data structure uses array doubling as a capacity strategy, but any other strategy can be used by setting the initialCapacity and capacityIncrement parameters.
Using the trimToSize method of this class trims the capacity to the vector's current size, thus allowing for the shrinkage of the data structure that John is looking for.
More flexible shrinkage strategies, like shrinking the array to half size when it's one-quarter full, as John proposes, can be obtained by using Vector's trimToSize method followed by calling the ensureCapacity method with an appropriate argument. For the "one-quarter full" strategy, this argument would be two times the current vector size. This would look something like Example 1.
The availability of a fully resizable data structure (growing, shrinkage, different strategies) in Java puts the possibilities of this language in the right perspective.
Alexander G. Vandervoort
University of Groningen
a.g.van.der.voort@bdk.rug.nl
Dear DDJ,
In his excellent "Algorithm Alley" (DDJ, January 1998), John Boyer pointed out that resizable arrays should always be grown or shrunk by a factor of two. There are two additional comments which I would like to make:
Surprisingly, this powerful yet simple technique is very much underused. The number of programs that resize their arrays using fixed increments is staggering. As I found out recently, it even happens to the software giants. I wrote a Win32 program that tries to create as many windows as possible. Under Windows NT 4.0, the elapsed time increases quadratically with the number of windows created; it is fairly safe to conclude that this is caused by an array that is being grown by fixed amounts. (If anyone at Microsoft is reading this, please fix this in the next release.) Interestingly, the supposedly less powerful Windows 95 does not have this problem.
Martin Boehme
boehme@informatik.mu-luebeck.de
Dear DDJ,
It was interesting to see the letter from Quinn, Emanuel, Urquhart, & Oliver, LLP in the "Letters" section of DDJ, March 1998. To add to the lore, according to the Trademark & Copyright Journal, Vol. 55 No.1353 (pp. 82), Lockheed Martin sued Network Solutions Inc. (the domain name registrar) for issuing domain names such as "skunkworks.com," "skunkworks.net," "skunkwrks.com," and "skunkwerks.com." In a nutshell, "Lockheed sued NSI for trademark infringement, unfair competition, dilution, and contributory trademark infringement." Unfortunately for Lockheed, the "court granted NSI's motion for summary judgement on all claims."
Jeff Clausius
iometrics@iometrics.com
Dear DDJ,
I really liked Al Stevens' column about PTL in DDJ, March 1998. I felt compelled to suggest that a namespace name that no one else would dream of using might be "AlStevensPTL" because if Microsoft or AT&T can do it, so can he. Besides, I like the way it looks and I always enjoy Al's articles. In my opinion, he deserves it.
John O. Viesselman, M.D.
doctorv@doctorv.com
Dear DDJ,
Although the VerCheck utility presented by John Graham-Cumming in DDJ, March 1998 is certainly very useful, I think a few, but important, comments are in order.
I also had to deal with this problem in the past and spent a few hours modifying Jeffrey Richter's well-known Vershow utility. I could notice a few problems with the way some programmers (especially at Microsoft) use VERSIONINFO. When you open the Properties dialog box in the Explorer by right clicking a filename, you get a Version tab that gives you the file version number. Like the VerCheck utility and unlike Vershow, this file version number is the "string" version number, not the "real" version number found in the VS_FIXEDFILEINFO data structure.
So what? Well, I have noticed that it happens more often than expected that the string version number doesn't match the actual (numerical) version number, especially for system files distributed by Microsoft. It seems that the developers there often forget to keep both entries in synch (this is done automatically in the the Visual Studio Resource Editor but not necessarily in all other development environments). So far as I know, installation utilities use the numerical version number, not the string value. At least, I hope so. Therefore, I think that any utility giving access to the file version number (including the Explorer itself), should also use the numerical file version number. Otherwise, this may lead to problems like replacing a newer file with an older file. Using the string version number is easier, but from far less reliable.
By the way, another problem with version stamping at Microsoft: The vast majority of the Win32 SDK include files don't contain any version information. I thought that Visual SourceSafe macros where able to maintain this automatically. This is surprising. Any professional developer will add version information in the include file headers he writes, even for small programs. I can't imagine what good reason they have for not including version information in such important files. Since these include files may come with various products (Win32 SDK, VC++, Borland C++, and so on), it is often very difficult to determine which file is the latest and greatest when you install several of these products on your system. You absolutely can't rely on the time stamp. About two years ago (95/96), I received a new version of the Win32 SDK where all include files were dated 1993! Since then, I don't even look at the time stamp when comparing include files from Microsoft.
Patrick Philippot
patrick.philippot@iname.com
John responds: Thanks for your note, Patrick. My intent was to replace the long and arduous task of gathering the version numbers from Properties over the phone. I agree with your analysis concerning the string versus numeric version numbers and VerCheck could be improved to gather both quite easily. Also, I use the $History$ macro for automatic maintenance. This gives the full file history as well (as long as the developer bothers to write it).
Dear DDJ,
In reading DDJ, February 1998, I noticed the "News & Views" item on MOSS, the program that provides a statistical comparison of source code, so that professors can detect cheating among programming students.
While I agree that this program could be useful, and that academic fraud should not be allowed, I know from personal experience that such similarities should not automatically be construed as fraud.
My freshman year in college, I was taking a Pascal course, and doing quite well. The day after submitting a project, I was summoned into an office with the Dean, my professor, and a classmate. The professor placed our respective projects side by side, and asked us to explain ourselves. Our code was virtually identical, with only minor differences in comments and variable names. We both admitted that the programs looked identical, and I think the Dean was ready to expel us both. Fortunately, we were both fairly meticulous notekeepers, and could fully document our development progress. Combined with an impromptu coding quiz in the Dean's office, we both managed to stay in school, although she and I were required never to be in the programming lab together or to send e-mail to one another, and we both got more than the average stares during tests. Eventually, I think the professor was fully convinced that our identical code was just a fluke.
For small projects, with programmers of similar training and experience, the likelihood of running across very similar code is higher than most people seem to think.
Byron Jones
byronj@fdpcorp.com
Dear DDJ,
Embedded in the Watcom C/C++ 11.0 compiler is a second profiler not mentioned by Ron van der Wal in his article "Source-Code Profilers for Win32" (DDJ, March 1998). When you compile the source code with the "-et" switch on the command line, the compiler inserts timing code at the start and exit of all functions, and it creates a LOG file for each program and DLL after each run. I have found this option to be more convenient and giving more accurate results than the stand-alone profiler that comes with Watcom.
Thiadmer
CompuPhase@compuserve.com
DDJ