Re: VMs: For this MONKEY: Help, pointers, etc. please:Unicode,TrueType fonts, kerning

[Jacques Guy <jguy@xxxxxxxxxxxxxxxx>]

10/09/2003 10:50:48 PM, Mart Vabar <mesinik@xxxxxx> wrote:

\
>... but adding more criteria about how meaningful the text should look like
>will IMO slow the generator down. Plus - it seems me, two tasks 
>(a) to check a text for n qualities and
>(b) to generate a text which has n qualities

The texts generated by MONKEY have one, and only one,
quality: for any n, all the substrings n-characters long
(of n-words long) of the output text are substrings
of the input text.

>are badly elliptic in favor of checking
>and if n comes bigger, the difference is growing exponentially,

as n becomes bigger, the number of substrings becomes smaller.
Given an input text 100-characters long, and n = 1, you have
100 substrings. With n = 2, 99, with n=3, 98, and so on.

Since MONKEY generates text using a binary search on a sorted
list of pointers to  all the substrings in the input text,
the greater n, the shorter the list. On even a not-so-modern
computer the search for and the generation of any substring
take only a tiny fraction of the time spent displaying it
on the screen. The other bottlenecks are:

1. reading the input text from disk -- proportional to the
   its length, and independent from n
2. sorting the list of pointers to the n-long substrings, which
   is dependent on the algorithm. Since I use a Shell sort, 
   it is proportional to N*log(N) where N is number of n-long
   substrings, i.e. N -n +1
3. the search; being a binary search, it is proportional to
   log(N); it can be made faster.
4. memory allocation and de-allocation but ONLY if you make 
   heavy use of dynamic arrays; there is not need for that,
   since the maximum size of the substring list is known: it is 
   the size of the input text, in bytes.

So, as is often the case with computer programs, all the bottlenecks 
are in the I/O: disk access, screen access.

>this is why I
>remembered the quantum algorithms which can solve such things 
>w/o the "dirty work".

As far as I know quantum algorithms rely on:

1. massive parallel processing
2. an untested theory
3. quantum processor chips, currently manufactured
   only by Cloud Cuckoo Land Inc.



______________________________________________________________________
To unsubscribe, send mail to majordomo@xxxxxxxxxxx with a body saying:
unsubscribe vms-list