Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. sorting almost sorted list (Dennis Raddle)
2. Re: sorting almost sorted list (David Place)
3. Re: sorting almost sorted list (Yitzchak Gale)
4. Re: sorting almost sorted list (Yitzchak Gale)
----------------------------------------------------------------------
Message: 1
Date: Mon, 26 Sep 2011 19:46:29 -0700
From: Dennis Raddle <[email protected]>
Subject: [Haskell-beginners] sorting almost sorted list
To: Haskell Beginners <[email protected]>
Message-ID:
<CAKxLvopJmFJmn0foqSBrdYcwN=Y1AhiYsOKHhgQGmvZ18Jq=d...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
I have a problem from music. I have a list of notes sorted by begin
time. I want to sort them by end time.
Notes that are sorted by begin time are usually close to sorted by end
time, because notes tend to cluster within a small range of durations.
What algorithms are available to me (hopefully in a library) that are
good with this kind of thing?
Dennis
------------------------------
Message: 2
Date: Mon, 26 Sep 2011 23:21:09 -0400
From: David Place <[email protected]>
Subject: Re: [Haskell-beginners] sorting almost sorted list
To: Dennis Raddle <[email protected]>
Cc: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
There are probably to few notes in a piece of music to worry about algorithm
complexity. The standard sort function should work just fine.
_____________________
David F. Place
Owner, Panpipes Ho!, LLC
http://panpipesho.com
On Sep 26, 2011, at 10:46 PM, Dennis Raddle <[email protected]> wrote:
> I have a problem from music. I have a list of notes sorted by begin
> time. I want to sort them by end time.
------------------------------
Message: 3
Date: Tue, 27 Sep 2011 11:08:53 +0300
From: Yitzchak Gale <[email protected]>
Subject: Re: [Haskell-beginners] sorting almost sorted list
To: Dennis Raddle <[email protected]>
Cc: Haskell Beginners <[email protected]>
Message-ID:
<CAOrUaLaqPP5AJWLTbRLr-5X70BtgV9mFMkqj_dpgfkeg=p=n...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Dennis Raddle wrote:
> I have a problem from music. I have a list of notes sorted by begin
> time. I want to sort them by end time.
>
> Notes that are sorted by begin time are usually close to sorted by end
> time, because notes tend to cluster within a small range of durations.
>
> What algorithms are available to me (hopefully in a library) that are
> good with this kind of thing?
Sorry, I don't know of any library that handles this special
case. I'm also not too familiar with the literature, so
I don't know of anyone who writes about it. (It's probably
worthwhile to have a look in Knuth.)
Anyway, it seems like this is not too hard.
Can you guarantee for some value of m that for each note N,
only the first m notes following N might end earlier than N?
If so, then the following simple algorithm is linear
and runs in constant space. You could then use:
sortAlmostBy m (comparing endTime)
sortAlmostBy :: Int -> (a -> a -> Ordering) -> [a] -> [a]
sortAlmostBy m cmp =
mergeAABy cmp . map (sortBy cmp) . chunksOf m
chunksOf :: Int -> [a] -> [[a]]
chunksOf m =
map (take m) . takeWhile (not . null) . iterate (drop m)
-- Merge a list of lists with two assumptions:
-- (1) Each list is sorted.
-- (2) The sequence of lists is "almost ascending" -
-- no element of a list is greater than any element of
-- any list following it, except possibly the list immediately
-- following it.
mergeAABy :: (a -> a -> Ordering) -> [[a]] -> [a]
mergeAABy cmp ((x:xs):xss) = y : mergeAABy cmp yss
where
(y, yss) = pickLeast x xs xss
pickLeast p ps pss@((q:qs):qss) = case cmp p q of
GT -> (q, (p : ps) : qs : qss)
_ -> (p, ps : pss)
pickLeast p ps (_:pss) = pickLeast p ps pss
pickLeast p ps _ = (p, [ps])
mergeAABy cmp (_:xss) = mergeAABy cmp xss
mergeAABy _ _ = []
You might be able to do a little better than this.
Here is one way: GHC would probably optimize this
better if you make pickLeast non-recursive by
arranging for lists that become empty to be eliminated
from the calculation earlier.
But as David points out, this is probably good enough
for your application, even if you are processing a
full orchestra score of a Mahler symphony that lasts
for hours. (Whereas just using sortBy for that case might
be slow.)
Regards,
Yitz
------------------------------
Message: 4
Date: Tue, 27 Sep 2011 12:32:35 +0300
From: Yitzchak Gale <[email protected]>
Subject: Re: [Haskell-beginners] sorting almost sorted list
To: Daniel Fischer <[email protected]>
Cc: Haskell Beginners <[email protected]>
Message-ID:
<CAOrUaLYNUh-8h5jMjTSrqnDzT96YKEw5gs+mPDtd-kg=bqy...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
I wrote:
> Can you guarantee for some value of m that for each note N,
> only the first m notes following N might end earlier than N?
> If so, then the following simple algorithm is linear
> and runs in constant space. You could then use:
> sortAlmostBy m (comparing endTime)
> ...You might be able to do a little better than this.
After running some tests, it seems empirically that
you can use m `div` 2 instead of m for lists of even
length, which gives you a nice speedup for larger
values of m. For lists of prime length, the best
you can do seems to be m-1. It's more complicated
for lists of non-prime odd length.
I can't immediately see why any of that is true.
Daniel to the rescue perhaps?
test n k = fmap (all isSorted . map (sortAlmostBy n compare)) $ rands k
isSorted xs = and . zipWith (<=) xs $ drop 1 xs
rands d = fmap (take 100 . map (concat . zipWith (map . (+)) [0,d ..]
. chunksOf d) . chunksOf 1000 . randomRs (0, d-1)) newStdGen
Thanks,
Yitz
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 39, Issue 34
*****************************************
