Surprising (for me) benchmark results...

Rainer Deyke root at rainerdeyke.com
Tue May 1 22:37:46 EDT 2001


"Courageous" <jkraska1 at san.rr.com> wrote in message
news:rrouet0f4un3h3eo8pq6nlk5idgkmhhhca at 4ax.com...
> On Wed, 02 May 2001 01:11:50 GMT, "Rainer Deyke" <root at rainerdeyke.com>
wrote:
>
> >"Daniel Berlin" <dan at www.cgsoftware.com> wrote in message
> >news:mailman.988762570.8591.python-list at python.org...
> >> Actually, the sort is probably not the bottleneck.
> >> As the file gets larger, the bottleneck becomes disk time, not sort
time.
> >
> >Disk access is O(N); sorting is typically O(N log N).  Therefore as the
> >number of entries in the file size increases, the time taken by the sort
> >becomes more significant and the time taken by disk access becomes less
> >significant.  This is assuming that the file fits into memory (as was the
> >case here).
>
> Disregarding the algorithm and this specific situation in question, you
are
> both correct; this is because while disk access may scale O(N), this
> scaling is multiplied by a huge constant factor that can in many cases
> dwarf the sorting algorithm, depending on the number of entries and
> the like.

I was responding to this: "As the file gets larger, the bottleneck becomes
disk time, not sort time."  This is just plain incorrect (assuming larger
file = more entries, not longer entries).  If disk access dominates on large
files, it dominates even more on small files.


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





More information about the Python-list mailing list