Yitz writes (in the Haskell Cafe):
This gives O(log k * (n + k)) execution in constant memory.
I guess that should be O(k) memory.
Cheers,
Ronny Wichers Schreur
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
G'day all.
I wrote:
O(log(n! / (n-k)!))
= O(n log n - (n-k) log (n-k))
= O(n log (n/(n-k)) + k log (n-k))
That looks right to me. If k n, then this simplifies to
O(n + k log n), and if k is close to n, it simplifies to
O(n log n + k).
Quoting Ian Lynagh [EMAIL PROTECTED]:
You may be missing a few recursive calls there :-)
Indeed.
I'm confused.
Is this a legitimate stable quicksort, or not? (My guess is, it is
indeed legit as written.)
This was also the first I have heard of stability as a sort property.
http://perldoc.perl.org/sort.html may shed some light
And for reference, here is again stefan's stable quicksort from his
earlier post.
sort [] = []
sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l
(A stable quicksort, btw)
This is the code whose legitimacy I am requesting confirmation of.
2007/4/13, Thomas Hartman [EMAIL
Trying to understand this better I also came across
http://groups.google.de/group/fa.haskell/browse_thread/thread/1345c49faff85926/8f675bd2aeaa02ba?lnk=stq=%22I+assume+that+you+want+to+find+the+k%27th+smallest+element%22rnum=1hl=en#8f675bd2aeaa02ba
where apfulmus gives an implementation of
Rereading this, I see in fact apfelmus explains this is
O(n + k*log n) for the first k elements, which this discussion also
maintains is the best case. So, there's no discrepancy.
I think this is a very valuable post to read for the explanation.
2007/4/13, Thomas Hartman [EMAIL PROTECTED]:
G'day all.
Quoting Thomas Hartman [EMAIL PROTECTED]:
Does that mean you can have the k minima in O(n) time, where n is
length of list, which would seem to be an improvement?
It's worth considering what the theoretical minimum is.
You have n elements, and you need to locate a specific
Hello,
My Hugs tells me this:
Prelude let sort [] = []; sort l@(x:_) = filter (x) l ++ filter (==x) l ++
filter (x) l in sort [1,3,2]
[1,3,2]
Prelude
So, no, this is not a working sorting function. Inserting the few missing
recursive calls:
Prelude let sort [] = []; sort l@(x:_) = sort (
On Fri, Apr 13, 2007 at 07:32:20AM -0400, [EMAIL PROTECTED] wrote:
Quoting Thomas Hartman [EMAIL PROTECTED]:
Does that mean you can have the k minima in O(n) time, where n is
length of list, which would seem to be an improvement?
It's worth considering what the theoretical minimum is.
On 4/13/07, Ian Lynagh [EMAIL PROTECTED] wrote:
Tuple each element with its position: O(n)
Find kth smallest element in linear time, as per [1]: O(n)
Filter list for elements = kth smallest: O(n)
Sort filtered list by position: O(k log k)
map
G'day all.
Quoting raghu vardhan [EMAIL PROTECTED]:
So, any algorithm that sorts is no good (think of n as huge, and k small).
The essence of all the answers that you've received is that it doesn't
matter if k is small, sorting is still the most elegant answer in Haskell.
The reason is that
[sorry for the double, ajb]
Since there seemed to be a disconnect between the expectation and
the previous answers, I thought an alternative suggestion might help
out. This sort of thing (haha) usually isn't my cup o' tea, so please
point out any blunders.
RM, is this more like what you had in
On Thu, 12 Apr 2007, raghu vardhan wrote:
What's the best way to implement the following function in haskell:
Given a list and an integer k as input return the indices of the least k
elements in the list. The code should be elegant and also, more importantly,
must not make more than the
On 4/12/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
To get the indices, use the Schwartzian transform:
sortWith :: (Ord b) = (a - b) - [a] - [a]
sortWith f = mergeRuns . runs
where
runs = map (:[])
mergeRuns [] = []
mergeRuns [xs] = xs
mergeRuns xss = mergeRuns (mergeRun
Kurt Hutchinson wrote:
On 4/12/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
To get the indices, use the Schwartzian transform:
sortWith :: (Ord b) = (a - b) - [a] - [a]
sortWith f = mergeRuns . runs
where
runs = map (:[])
mergeRuns [] = []
mergeRuns [xs] = xs
The link pretty much answers my question, though you probably require a
little bit more book keeping to get the indices out. Compared to the
iterative version or the matlab version, this definitely is more elegant,
but also is trickier.
apfelmus wrote:
raghu vardhan [EMAIL PROTECTED]:
So,
\begin{code}
kmin :: Ord a = Int - [a] - [Int]
kmin k x = map snd $ Set.toList $ foldl' insertIfSmall (Set.fromList h) t
where
(h, t) = splitAt k $ zip x [0..]
insertIfSmall :: Ord a = Set.Set a - a - Set.Set a
insertIfSmall s e
| e mx= Set.insert e s'
| otherwise = s
where
(mx, s')
\begin{code}
kmin :: Ord a = Int - [a] - [Int]
kmin k x = map snd $ Set.toList $ foldl' insertIfSmall (Set.fromList h) t
where
(h, t) = splitAt k $ zip x [0..]
insertIfSmall :: Ord a = Set.Set a - a - Set.Set a
insertIfSmall s e
| e mx= Set.insert e s'
| otherwise = s
where
(mx, s')
G'day all.
Quoting Kurt Hutchinson [EMAIL PROTECTED]:
For my own edification, what is the benefit of this sortWith over sortBy?
None. I wanted to write my own sort, illustrating how the lazy
evaluation thing works, and I didn't want a name clash with an
existing library function.
Cheers,
What's the best way to implement the following function in haskell:
Given a list and an integer k as input return the indices of the least k
elements in the list. The code should be elegant and also, more importantly,
must not make more than the minimum O(k*length(list)) number of operations.
R
mrvr84:
What's the best way to implement the following function in
haskell: Given a list and an integer k as input return the
indices of the least k elements in the list. The code should
be elegant and also, more importantly, must not make more
than the minimum
On Thu, Apr 12, 2007 at 08:58:33AM +0530, raghu vardhan wrote:
What's the best way to implement the following function in haskell:
Given a list and an integer k as input return the indices of the least
k elements in the list. The code should be elegant and also, more
importantly, must not make
On Wed, Apr 11, 2007 at 08:38:48PM -0700, Stefan O'Rear wrote:
On Thu, Apr 12, 2007 at 08:58:33AM +0530, raghu vardhan wrote:
What's the best way to implement the following function in haskell:
Given a list and an integer k as input return the indices of the least
k elements in the list.
On Wed, Apr 11, 2007 at 09:20:12PM -0700, Tim Chevalier wrote:
On 4/11/07, Stefan O'Rear [EMAIL PROTECTED] wrote:
If you want to be really explicit about it, here is a sort that will
work:
sort [] = []
sort l@(x:_) = filter (x) l ++ filter (==x) l ++ filter (x) l
(A stable quicksort,
April, 2007 11:17:15 PM
Subject: Re: [Haskell-cafe] k-minima in Haskell
On Thu, Apr 12, 2007 at 09:30:22AM +0530, raghu vardhan wrote:
Hmmm. That's not something I was looking for. I'm not sure the
running time is good enough (think of k as being 2 - then you should
not make more than 2n
G'day all.
Quoting raghu vardhan [EMAIL PROTECTED]:
What's the best way to implement the following function in haskell:
Given a list and an integer k as input return the indices of the least k
elements in the list. The code should be elegant and also, more importantly,
must not make more
this).
- Original Message
From: Stefan O'Rear [EMAIL PROTECTED]
To: raghu vardhan [EMAIL PROTECTED]
Cc: [EMAIL PROTECTED]
Sent: Wednesday, 11 April, 2007 10:47:08 PM
Subject: Re: [Haskell-cafe] k-minima in Haskell
On Wed, Apr 11, 2007 at 08:38:48PM -0700, Stefan O'Rear wrote:
On Thu
27 matches
Mail list logo
