[fpc-devel] Re: enumerators

[Hans-Peter Diettrich]

Alexander Klenin schrieb:

>> The total order will be something between O(n^1) and O(n^2), depending on
>> many factors (what is "n"?...).
> 
> Huh? O(f(n)) has a precise definition, and of course we are talking worst-case
> complexity here (although average complexity would be the same in this case).
> n is the string length, measured in whatever units you choose.

For matrix multiplication there exist algorithms from O(N^3) downto 
O(N^2.807) [Strassen] and even O(N^2.378) [Coppersmith-Winograd]. 
Similarly for other problems (hash tables...), where the *amortized 
cost* can differ from the agnostic "worst case" assumptions.

A "worst case" IMO applies to concrete procedures only, while algorithms 
or problems only have an upper limit, that can be lowered by further 
research. Applied to procedures, the coder *establishes* a certain 
complexity of his implementation, that may be far away from the 
complexity of the problem to solve.

In any case it's essential to verify the determined complexity, in order 
to detect inappropriate definitions of N or other factors, that show up 
as deviations from the assumed formula.


>> I also doubt that UTF8char is a reasonable type for the loop variable - IMO
>> UTF32char were a much better choice...
> 
> I think I meant exactly the same thing (an integer holding the codepoint value),
> but just named the type carelessly. In fact, I think the best name would be
> something like "UnicodeChar" or even "Codepoint", to avoid association
> with any particular encoding.

As outlined in another message, (Unicode) string handling IMO should be 
based entirely on substrings, so that a special single-character data 
type is not required anywhere. Wirth may have anticipated the problems 
with character sets in his Pascal design, and did not distinguish 
between string and character literals.

DoDi