Dr. Dobb's Journal January 2000
Dear DDJ,
I enjoyed Al Stevens treatise on Brief-compatible editors in the October, 1999 issue of DDJ. I, too was a Brief addict in my DOS days and have since moved to Windows. The editor I swear by, mostly because of its stupendous Brief compatibility is Rimstar (http://www.rimstar.com/). Unlike Al's description of Boxer, Rimstar is complete with a C-like macro language that lets you automate just about every task. It also has a great source browsing system and a utility for generating skeleton classes with properly defined operator overloads and such. Brian Smith, the sole programmer and owner of Rimstar Inc., actually worked on Brief back when Underware sold it to Solution Systems.
Andrew Tucker
andrewt@bsquare.com
Dear DDJ,
I greatly enjoyed Evan Easton's October 1999 "Java Q&A" column on Java and enums. I had often used inner classes for enumerations but I didn't know of the jdk1.2 serialization "trick" for limiting the instances and letting clients use the operator for equality. Very useful!
Since Evan mentioned that editor's code-completion features help in using idioms like the one he presented, I'd like to tell you about another idiom that is very enjoyable in a code-completion IDE.
Say you have an interface for which you like to provide a default implementation that does nothing (the "Null Object Pattern" of one of the PLOPD books). You can implement that with an external class of course, but using a class inner to the interface itself is meaningful to me. I always call it Null and implement it as a Singleton. So clients use it calling:
IMyInterface.Null.instance();
public interface IMyInterface
{
public Object aMethod(Object args);
//... other methods
public class Null implements IMyInterface
{
private static Null instance =3D new Null();
public static Null instance() { return in stance; }
public Object aMethod(Object args) {}
//... other methods
}
}
Edoardo Comar
e.comar@go.nettuino.it
Dear DDJ,
I am not a lawyer, but I have just about finished a Ph.D. comprehensive reading field in Labor History, and I do know a little about the subject. It would would seem that, as Jonathan Erickson described in his August 1999 "Editorial," IATSE Local 16 was in violation of assorted labor laws. Since you do not employ their members, and your people have not signed union cards, the union has no standing to interfere. You can get a lawyer, go to court, and get an injunction. If the union still persists, they can be fined for contempt of court, and their officers imprisoned, pretty well at the discretion of the judge. They were gambling on you not knowing the law, and naturally they are now saying nothing, declining to incriminate themselves.
Andrew D. Todd
u46a8@wvnvm.wvnet.edu
Dear DDJ,
In my article "Implementing Operator->* for Smart Pointers" (DDJ, October 1999), the correct URL for Kevin S. Van Horn's Smart Pointer Web Site is http://www .xmission.com/~ksvhsoft/code/index.html.
Scott Meyers
smeyers@aristeia.com
Dear DDJ,
In response to Peter Roth's letter in DDJ, August 1999: While I agree with his advice "don't calculate unnecessarily," I won't follow him in his application to the traveling salesman problem. Comparing distances or square of distances produce the same result. However, the sum of squares is usually not the same as the square of a sum; e.g., 32+42!=(3+4)2. When comparing the total distance of different travels of the salesman, you cannot afford to skip the square root operation.
As a simple example I've found by writing a small program for SysQuake, let's consider the four towns at (7;3), (10;7), (8;9), and (6;1). The optimal travel visits towns 1, 2, 3, 4, and back to 1, for a total distance of 18.31 and a sum of squares of 106; comparing the sums of the squares of the distances gives the order 1, 3, 2, 4, and back to 1, for a suboptimal total distance of 18.36 and a smaller sum of squares of 102.
Best regards, and thanks for one of the last computing magazines with articles which make you think.
Yves Piguet
yves.piguet@calerga.com
Dear DDJ,
The algorithm presented by Ron Verbruggen ("Letters," DDJ, October 1999) describes the most direct method to solve the Traveling Salesman Problem (TSP) -- complete enumeration. His algorithm would generate all possible TSP tours and choose the shortest. However, his analysis of the run time for this algorithm is flawed. The correct run time is O((n-1)!). Consider N cities labeled 0,1,...,N-1. Arbitrarily choose 0 as the starting city. Each tour is now a permutation of the N-1 remaining cities.
It is true that for any fixed k, finding the shortest cycle visiting exactly k of N (N>=k) cities is polynomial in N of degree k. However, the TSP is proven to be NP (nondeterministic polynomial run time). Unless there is a fundamental breakthrough in computing theory, every algorithm that solves the TSP will experience super-polynomial growth in run time.
Programmers should look beyond simple speedups such as reducing multiplies, using look-up tables, efficient allocation of memory, and so on, and be able to recognize when they are facing NP problems. At this time, it is the programmer's duty to manage customer expectations for performance, determine alternative models which scale better, or be satisfied with heuristic solution.
Kevin Ruland
kevin@rodin.wustl.edu
Dear DDJ,
In his letter to the editor (DDJ, October 1999), Ron Verbruggen is "pretty sure" that a simple program can be worked out to list the possible circuits of a graph.
He is, of course, correct. However, consider the worst case scenario, one where every vertex is connected to every other vertex. His algorithm involves finding all circuits, and eliminating duplicates. In this worst case scenario, there are N! possible circuits, and eliminating duplicates merely divides by N (each circuit has N possible starting points), giving a total number of circuits equal to (N-1)!.
So, while his algorithm is simple to implement, it still proves the problem to be intractable in the worst case circumstances.
Scott Neugroschl
scottn@alumni.cse.ucsc.edu
Dear DDJ,
I take issue with Jonathan Erickson's "Editorial" in the October 1999 issue of DDJ, in which he describes a "community development block grant," which "made it possible for the village to purchase land and construct a building tailored for MI."
He states, "In the end, everyone won -- the village, the company, the employees, and MI's customers." However, this list does not include everyone involved. In fact, it leaves out some very important people -- the ones who paid for the building! I'm sure many projects would seem like a good deal if no accounting was made for the cost of the project. But, in fact, someone does have to pay for the project and for them a project such as this is likely not to be a good deal. After all, the people that know the most about the situation -- the owner and his management team -- decided it was not a financially viable project.
Finally, you state that "To stay competitive, innovative ideas...are important...," which is undeniably true, however, I don't think that taking money from someone else to pay for something for yourself qualifies as an innovative idea.
Greg Hadaller
greg.hadaller@iname.com
Jonathan responds: Thanks for your note, Greg. Actually, everyone did win in the MI-Assistant project. The local economy was strengthened, the company made a long-term commitment to the area, and it is apparently prospering and therefore paying more taxes. If the company had moved, it would have deducted its moving expenses (meaning that you and I would have paid for the move), and would have likely ended up paying more in rent (and related expenses), higher salaries, and the like. In short, MI-Assistant might have been less profitable and paid less in taxes. Granted, you can pick up any newspaper and see an abuse of the grant block programs, but this isn't one of them. It was an honest, upfront deal that doesn't hurt the environment or health of the community, and that leads to a better quality of life for the participants. If my tax dollars go to those ends, that's fine with me.
Dear DDJ,
I've just read the article "Porting Communication Software to Windows CE" (DDJ, August 1999) and I'd like to say not all things are so bad as described. For example, Oliver said that there are problems with debugging because of slow link between desktop station and CE device. Yes, I agree speed of serial link isn't agreeable for debugging even with 115 Kbits/sec., but you can use Ethernet adapter. This way is much more fast. And moreover, while you're using Ethernet to transfer debug information, you can use COM port in your application under debugger. But despite my comments, the article is very interesting. Thank you.
Mike Zhilin
mzhilin@epiphan.com
Dear DDJ,
I enjoyed Jon Bentley's article "Code Tuning In Context" (DDJ, May 1999). While his optimization using distarr works well, another more generic optimization works for most problems with distance calculations. Simply ignore the sqrt. Most algorithms compare distances to each other and for that purpose sqrt is not required. It seems this would work well for the Traveling Salesman Problem. After finding the optimal path without sqrt one will have to go back and calculate the real distance of course, but this is trivial.
Todd Stephan
tstephan@genscan.com
DDJ