Surprising (for me) benchmark results...

[Rainer Deyke]

"Daniel Berln" <dan at cgsoftware.com> wrote in message
news:mailman.988787824.17942.python-list at python.org...
> First, let's be clear on what Rainer did.
> He said: Disk access are O(n). (Where n is the number of bytes). Sorting
> is O(n log n) (Where n is the number of items to sort). Therefore,
> sorting is more expensive algorithmically.
> This is clearly incorrect, you are comparing apples and oranges. The n's
> aren't representing the same things.
>
> The number of bytes is the absolute upper bound on the number of items
> to sort, and would only be the case for single byte items, in which
> case, there are better sorting algorithms, and you could make disk
> accesses dominate again.

I did say that this only only applies when "larger file" means "more
entries", not "longer entries".  In other words, there is a definite finite
average entry length which remains constant.  Given that, O(number of bytes)
and O(number of entries) are equal.


--
Rainer Deyke (root at rainerdeyke.com)
Shareware computer games           -           http://rainerdeyke.com
"In ihren Reihen zu stehen heisst unter Feinden zu kaempfen" - Abigor