On Mon, Sep 28, 2009 at 9:53 AM, John Posner <jjpos...@optimum.net> wrote:
> > If you can enumerate the language of possible inputs you could >> generate a unique binary representation. Against a language of size >> l that would only take you O(l*n) to build the repr for a dict >> and for certain repr sizes the comparison could be O(1), making >> the entire operation O(l*n+l*m) vs O(n*m). >> >> >> > Geremy, I can't comment on the *content* of your observation on > performance, but ... > > This sentence reminds me of the mid-1980s, when I was learning C in order > to program the very first font cartridge for the HP LaserJet printer. The > escape sequences seemed to consist entirely of ones and small ells and zeros > and capital ohs -- apparently designed for maximal confusion. Was it around > that time that the word "pessimal" was coined? > > -John 1) I honestly wouldn't know, seeing as how I wasn't alive ;). 2) After a brief tube hunt, I found that the word "pessimal" is originally from biology and appears to be somewhat more ancient than HP printers, although judging by the amount of dust I've seen on their insides I wouldn't place any large sums of money on that. 3) Apologies if the nomenclature was confusing, I tend to use l rather than the more standard |L| to denote the size of a language L. To rephrase, using S instead of l: Given an efficiently enumerable language L of size S, a unique binary representation of any sentence in L of size N can be generated in at most O(L*N) time. Because binary strings of reasonable bitlengths can be compared in a single machine operation, for most practical purposes we can simply say that equality testing will be O(1). As a result, the total time of generation and comparison for *two* sentences of size N (remember that we're not concerned about two sentences of unequal length) will be O(L*2N), and is likely to be quite fast in practice. Further optimizations- especially revolving around Bloom filters if a small margin of error is acceptable and S is large- are probably possible. Geremy Condra
-- http://mail.python.org/mailman/listinfo/python-list
