[fpc-devel] Re: enumerators
DrDiettrich1 at aol.com
Sun Nov 14 21:39:01 CET 2010
>> The comparison in the UTF-8 string example is very questionable. First
>> ch(i) is not equivalent to ch, not even closely related, and the claim
>> of O(N^2) operations deserves an proof - IMO it's simply wrong.
> Yes, this caught my eye as well: O(N^2) seems only the case if "length"
> would be evaluated every time.
This would apply to zero-terminated C strings, but not to counted Pascal
strings. Most probably the text was copied from a C site, and that
essential difference was not taken into account in the Pascal adaptation.
> Since you should not modify the index
> (although this is possible with some tricks in Delphi) the compiler
> should optimize it away.
> If you look at the algorithm, however, the statement is correct: it
> implies/reads: "evaluate length every iteration", whereas "for..in"
> evaluates the index value only once.
This also is a weak argument, since the behaviour of the iterator is not
taken into account. When the iterator checks the length before moving to
the next element, and the determination of the length would be O(N),
then the order of the iterated loop still is O(N^2).
But you spot an essential pro of iterators: the user does not have to
know about the implementation of the container, and can not choose a
wrong function for the loop termination condition.
More information about the fpc-devel