Re: initialization time?

From: David B Ring (dbring_at_pacbell.net)
Date: 10/23/03 

Date: Thu, 23 Oct 2003 18:00:38 GMT

I understand your point and agree. I've been playing with BurstSort, a
complex algorithm for sorting very large numbers of strings. In many
situations, it runs faster than competing algorithms like MSD RadixSort
or Multikey QuickSort, but the latter are simpler and show less of the
first/second interation slowdown. If a server is going to grind thru
sort after sort, that may be irrelevant, but if it's going to sort a
very long list once a day, it may be very relevant.

Dave

Roedy Green wrote:
> On Wed, 22 Oct 2003 21:04:11 GMT, David B Ring <dbring@pacbell.net>
> wrote or quoted :
>
>
>>Regarding your first response, there's no way to guarantee that gc()
>>happens before a block of code is executed?
>
>
> I think the BEA jvm has a way of doing that. I don't think there is a
> way in Sun's.
>
> The GC problem will show up with one in N iterations after you run
> this a while taking longer than most.
>
> In a modern machine there are scores of other tasks running the
> background you are normally unaware of, many of which you would nuke
> if you knew what they were. These too can upset your measurement.
>
> Yet I repeat WHAT ARE YOU MEASURING and why? These fluctuations are
> part of the truth of how apps behave in the real world.
>
> Let me give an example. Let's say that you horse raced two
> algorithms, on which was 5% faster after 20 iterations, but was 10
> times slower in the first 2. Does it really make sense to pick that
> algorithm unless in real life you run this code 20+ times per run?
>
> --
> Canadian Mind Products, Roedy Green.
> Coaching, problem solving, economical contract programming.
> See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Relevant Pages

  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... I would tailor which algorithm to start with by how the student thinks ... If you only learn the beautiful side of programming, ...
    (comp.programming)
  • Re: puzzle
    ... >> Christopher Barber wrote: ... >> or understanding among programming professionals. ... > algorithm "close to" O. ... bubble sort, it is almost always acceptable to use an interchange sort: ...
    (comp.programming)
  • Re: The ultimate luxury ?
    ... >>My definition in terms of imposing a linear order on a set is abstract ... >>and corresponds not to the algorithm of sorting, ... > that the CS dudes of today would not know what sort means. ... Jesse Hughes ...
    (sci.physics)
  • Re: Help me with references
    ... I can't think of any situation in which bubble sort is ... > best choice for a sorting algorithm in a real machine. ... Quicksort is optimized for large Ns. ... I picked Bubblesort because your original post implied something along ...
    (comp.lang.java.help)
  • Re: Educated guesses for efficiency?
    ... it is comparatively rare for a program to run too slowly because an algorithm with the wrong big-O analysis was chosen. ... of things tended to be stored in lists). ... built-in sort function. ... Programmers *will* use algorithms with high complexities. ...
    (comp.lang.c)