Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

Re: Puzzle: The Ham Cheese Sandwich cut.

by robin (Chaplain)
on Nov 21, 2005 at 19:08 UTC ( #510525=note: print w/replies, xml ) Need Help??

in reply to Puzzle: The Ham Cheese Sandwich cut.

As ambrus said, even the warm-up problem is pretty damned hard. I too cheated by looking in Cormen, Leiserson and Rivest. Here is a Perl implementation of the linear-time algorithm they give.
sub naive_median { (sort {$a <=> $b} @_)[@_/2]; } sub nth_largest { my ($n, @a) = @_; die "You can't find the ${n}th-largest element of an ".@a."-element +array!" if $n > $#a || $n < 0; #warn "Looking for ${n}th element of (@a)\n"; return $a[0] if $n == 0; my @medians; for(my $i=0; $i < @a; $i += 5) { push @medians, naive_median(@a[$i..($i+4 > $#a ? $#a : $i+4)]); } my $median = median(@medians); my @smaller = grep {$_ < $median} @a; return nth_largest($n, @smaller) if $n < @smaller; my @larger = grep {$_ >= $median} @a; return nth_largest($n - @smaller, @larger); } sub median { unshift @_, int(@_/2); goto &nth_largest; }
In practice it's pretty inefficient, and even proving that it runs in linear time is not entirely trivial!

Replies are listed 'Best First'.
Re^2: Puzzle: The Ham Cheese Sandwich cut.
by Roy Johnson (Monsignor) on Nov 21, 2005 at 19:17 UTC
    That goto is not helpful.

    Caution: Contents may have been coded under pressure.
      Hmm, that's interesting. But I bet the goto is faster if @_ has, say a million elements. You're saving an awful lot of copying. Update: I lost this bet :-)

      It also saves a fair amount of stack space.

        It isn't the goto that saves the copying. It's the use of & without parentheses to call the function. As far as I can tell, the goto is a useless relic.

        Update: Ok, not entirely useless: if you want a routine not to return to where you called it from, goto is the way to do it. In other words, use it when you want to do weird control flow (which is what goto is all about). Example:

        sub one { print "In one\n"; goto &two; print "never print this if you goto\n"; } sub two { print "In two\n"; } one();
        It's like exec for the subroutine domain.

        Caution: Contents may have been coded under pressure.
Re^2: Puzzle: The Ham Cheese Sandwich cut.
by hv (Parson) on Nov 22, 2005 at 13:19 UTC

    I suspect that a proof of the running time order will concentrate on the expected depth of recursion.

    However I believe it will be much harder to prove that the push is O(1) - indeed I suspect it is not - and without that the algorithm as a whole cannot be O(n).


      No, the proof doesn't need an expected running time. The running time T(N) is expressed as:
      T(N) = T(N/5) + T(7N/10 + 10) + Ο(N);
      which has T(N) = Ο(N) as a solution.
      However I believe it will be much harder to prove that the push is O(1) - indeed I suspect it is not - and without that the algorithm as a whole cannot be O(n).
      It doesn't have to be. What's needed is that the push has an amortized running time of Ο(1) - that is, if we perform N pushes, the total running time is still bounded by Ο(N). And from what I understand of how allocation of array sizes work (an addition extra 20% memory is being claimed), a push has an amortized Ο(1) performance. A single push may take Θ(N) running time, but N pushes average it out.
      Perl --((8:>*

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://510525]
[ambrus]: level where people can more easily write as good mathematical papers in them as the people who write bad LaTeX papers usually write.
[ambrus]: Yes, for like the first twenty of its years, TeX was basically the only system that allowed you to write decent maths papers, and C++ and PHP were programming languages that sucked, etc. But times change and people have to accept that.
Discipulus bad people + good tool < normal people + decent tool
[Discipulus]: php does not suck anymore?
[ambrus]: Discipulus: I'm not sure, but it certainly doesn't suck as much as it's used to. it's like C++, it sucks because people still recursively learn from twenty year old PHP examples,
[ambrus]: and they try to use the obsolete features that PHP has to support only for compatibility with old scripts. C++ and PHP both have the problem that people can't forget the past, because when they google "PHP" plus the problme they want to solve, they find b
[ambrus]: ad code examples.
[ambrus]: I'm not trying to recommend PHP, but I think it has way too bad a name because of its past.
[ambrus]: This is different from MS Word, which was already a good editor in the pre-unicode days (in word for windows versions 2 and 6, which ran on windows 3 but also on windows 95), only it wasn't trying to solve the task of writing maths papers back then.
[Discipulus]: ah ok, sounds reasonable; with no fear: Perl all life long

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (10)
As of 2017-09-26 11:08 GMT
Find Nodes?
    Voting Booth?
    During the recent solar eclipse, I:

    Results (293 votes). Check out past polls.