Second largest

[Eric Sosman]

Keith Thompson wrote On 08/09/07 13:17,:

Um, do you know what "ein Gift" means in German?

Ja. Ich schrieb es, um die Mehrdeutigkeit von
Wörtern zu zeigen. (Beachten Sie das Lächeln.)

 

[Richard Bos]

No, no. Use a bubble sort, just one with a small constant overhead per
item.

You know what? If I ever found a bubble sort that had a smaller K than
the equivalent insertion sort, I _would_ use it.

Richard

 

[Richard Tobin]

If you're talking of *real* cards, that's unlikely, given that the
equivalent of memmove() can be done in O(1).

Really? How fast can you move 10^10 cards?

-- Richard

 

[Army1987]

You know what? If I ever found a bubble sort that had a smaller K than
the equivalent insertion sort, I _would_ use it.

If you're talking of *real* cards, that's unlikely, given that the
equivalent of memmove() can be done in O(1).

 

[Army1987]

Really? How fast can you move 10^10 cards?

It depends on the speed of the truck they're contained in.
If it is traveling at 50 km/h (14 m/s), it takes me 7e-5 seconds
to move them by one millimeter.
No, you didn't mean this...
Well, if I have 10 billion cards, and insert a card in position
3, the third card becomes the fourth card, the fourth card becomes
the fifth card and so on. It doesn't take much longer than if the
cards were ten.

 

[Richard Tobin]

Really? How fast can you move 10^10 cards?

It depends on the speed of the truck they're contained in.
If it is traveling at 50 km/h (14 m/s), it takes me 7e-5 seconds
to move them by one millimeter.[/QUOTE]

That's thoughput; consider latency: if a card weighs a gram, 10^10
weigh 10,000 tons. How fast can you accelerate that lot?

Well, if I have 10 billion cards, and insert a card in position
3, the third card becomes the fourth card, the fourth card becomes
the fifth card and so on. It doesn't take much longer than if the
cards were ten.

Consider the force needed to insert a card at the 5-billionth position.

-- Richard

 

[Richard Bos]

Really? How fast can you move 10^10 cards?

The largest deck I own is a tarot deck of 73 cards; I've used double
normal decks of /in toto/ 104 cards; but I've never seen a deck of
10**10 cards.

Which was kinda my point all along, really. Yes, Big-O notation is all
about big numbers; but how often do you really encounter datasets of
10**10 members in practice? I know I never have. Hundreds of thousands,
yes, although usually safely packed away inside a database. Dozens or
hundreds is much, much more likely. Therefore, although Big-O notation
is a good tool for information _science_, in the reality of computing
_practice_ the constant factors are often at least as important as the
asymptotical behaviour.

Richard

 

[Army1987]

It depends on the speed of the truck they're contained in.
If it is traveling at 50 km/h (14 m/s), it takes me 7e-5 seconds
to move them by one millimeter.

That's thoughput; consider latency: if a card weighs a gram, 10^10
weigh 10,000 tons. How fast can you accelerate that lot?[/QUOTE]
Good point. Maybe O(1) was too optimistic, but of course it
doesn't take one billion times longer than to move ten cards.
Maybe O(log N)?
Anyway, I don't think this could ever cause a bubble sort to be
faster than insertion sort. Also because swapping the 321495013th
card with the 6138274597th one can take a nontrivial amount of
time...

Consider the force needed to insert a card at the 5-billionth position.

It depends on how tightly packed they are. If they are loosely
packed enough, it will not be excessive. Only that just a few
cards are physically moved; but the indices of five billion cards
change very quickly.
(More seriously, whilst *notationally* the big-O notation is for
asymptotic growth as N approaches infinity, *in practice* it just
means "as N becomes large enough that additive constants can be
neglected". For example, when N becomes larger than (size_t)(-1),
a C implementation of a sorting algorithm becomes *very* tricky,
but this isn't usually an issue, even when considering the big-O
notation.)

 

[CBFalconer]

. snip ...


If you're talking of *real* cards, that's unlikely, given that
the equivalent of memmove() can be done in O(1).

memmove has O(N) performance. Considerably different than O(1).

 

[user923005]

The largest deck I own is a tarot deck of 73 cards; I've used double
normal decks of /in toto/ 104 cards; but I've never seen a deck of
10**10 cards.

Which was kinda my point all along, really. Yes, Big-O notation is all
about big numbers; but how often do you really encounter datasets of
10**10 members in practice? I know I never have. Hundreds of thousands,
yes, although usually safely packed away inside a database. Dozens or
hundreds is much, much more likely. Therefore, although Big-O notation
is a good tool for information _science_, in the reality of computing
_practice_ the constant factors are often at least as important as the
asymptotical behaviour.

I see sets in hundreds of millions and billions all the time.
For instance, all registered products of a large software company.
For instance, all individual tolls taken on toll roads in New Jersey
over the last decade.
For instance, DNA sequences for the human genome.
Database work often entails many terabytes of data. So we had better
care about big-O.

On the other hand (as you say) a hybrid algorithm is usually the best,
because it can have the best of all worlds.

 

[Kelsey Bjarnason]

[snips]

Which was kinda my point all along, really. Yes, Big-O notation is all
about big numbers; but how often do you really encounter datasets of
10**10 members in practice? I know I never have. Hundreds of thousands,
yes, although usually safely packed away inside a database.

For a lot of stuff I do, hundreds of thousands of items might qualify as
a quick-and-dirty test set, but real data sets are a _tad_ larger. Like,
oh, three orders of magnitude larger than that.

 

[Army1987]

memmove has O(N) performance. Considerably different than O(1).

Re-read the fifth (or sixth, depending on how you count) word in
my post (the one between asterisks). Also, look at the last three
non-whitespace characters in my post before the signature.