[off-topic] Pessimal (was: Detecting changes to a dict)

[geremy condra]

Aaagh! Did it without thinking. Should be O(S*N) and O(S*2N).

On Sep 28, 2009 12:09 PM, "geremy condra" <debatem1 at gmail.com> wrote:



On Mon, Sep 28, 2009 at 9:53 AM, John Posner <jjposner at optimum.net> wrote: >
> >> If you can enumera...
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20090928/0cd7ca39/attachment-0001.html>