From: Arthur Schwarz <aschwarz1309@ve...>  20051218 17:44:23

On approximately 12/17/2005 6:46 AM, came the following characters from the keyboard of Arthur Schwarz: > Robert; "... For example, my last email just suggested doing a form of linear searching, because it would allow space to be saved.... but this can be fully optimal in certain circumstances... what circumstances? FWIW (I really hate these acronyms, only because I rarely know what they mean, so, for what it's worth) linear searching is 'optimal' in only a few cases, to wit: 1. The locale of reference is small. 2. It is possible to load all of the list into primary cache. 3. Predictive loads load data not in primary cache into secondary cache before use (and then into primary cache before use). 4. Dynamic instruction code optimization does not intefere with the search by putting in latencies. In terms of just looking at code and operation, a binary search should be faster in most (but not all) cases. In particular, conditions based on a small locale of reference are violated for a binary search. See, for example, Selforganizing Linear Search J.H. Hester, D. S. Hirschberg ACM Computing Surveys, V17N3 for another look at linear searching. > It does several things that have ne'er before seen > the light of day. Assuming a keyword list of ASCII words (not strictly > necessary): > 1. Given a list of keywords, it selects the optimum set of columns to use > to get a minimum height search tree. I've never heard this idea codified before, but I did, in fact, attempt to manually approximate that a few times in the past when I was generating mph polynomials. Computers might be fast enough now to make it practical to calculate this automatically. Calculation of an optimal parameter set from an arbitrarily large set does not take long on average (I suspect). Worst case performance can be really bad and depends on tree depth. If at most a single keyword is removed from the keyword list at every level then the worst case is bounded by: Iterations = O((# keyword) * (maximum # parameters) * (# keywords)) O == big O (upper bound of computation) and depth == (maximum # parameters) The algorithm has nothing to do with MPH, it is merely useful as a prepass optimization step. Since the solution is deterministic (finiteness guaranteed) and not a branchandbound problem it doesn't suffer from some of the search issues. > 2. Given the results of the prepass, it will generate a polynomial whose > return value is an integer, 0 <= i < # keywords for each input keyword. I've heard this one discussed, of course without the results of the prepass. But in the codes I've seen, it was never stated as a guaranteed achievement; the operational instructions said you could try for that, but if it didn't find one, then you might increase the size of the max integer, which would result in some gaps in the sequence of possible return values, which would "help" the polynomial generator find a solution. There are a number of polynomial and nonpolynomial solutions given in the literature (that I've looked at). All of them that I have so far seen depend on a search technique of some sort. One such solution which is readily available is 'gperf' in Cygwin. My proposed solution does not depend on a search and is deterministic. I'll be interested to see the Arthur Schwarz mph generator when it is published. Me to :). That doesn't mean that I necessarily think that it will be the right solution for Win32::GUI::Constant ... my thinking is quite the opposite at the moment. Not my decision. If used I am sure it will be analyzed for performance and used if it performs well. 