Send Beginners mailing list submissions to
beginners@haskell.org
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
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Removing the biggest element from a list - maybe slow?
(Markus L?ll)
2. Re: Removing the biggest element from a list - maybe slow?
(Daniel Fischer)
3. Re: Removing the biggest element from a list - maybe slow?
(Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Mon, 24 May 2010 17:15:32 +0300
From: Markus L?ll <markus.l...@gmail.com>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: beginners@haskell.org
Message-ID:
<aanlktil7k7-09qpiusoehzwn88rmatdydamsia4_s...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
On a list, that is internally too a list, the complexity of the
operation is always at least O(n), because to find the maximum, you
have to look through all the list -- i.e do n comparisons.
If you don't have any other variables like pointers to the previous
and next elements of the maximum, when you are going trough the list
to find it, then after finding the maximum value, you have to go
through the list again, to find its position and remove it...
For
> delete (maximum xs) xs
the complexity is O(n + m), where m is the index of the maximum. This
goes through the list to find the maximum, and then goes through it
again up until it finds the first occurrance of it.
For
> init $ sort xs
it is (n log n) + n, where (n log n) is the complexity of the sorting
algorithm (it might be something else depending on the algorithm), and
(+ n) is because the init funcion has to go through the list again to
find its last element and remove it.
Although Haskell is lazy, and when sorting a list, it might not get
fully sorted until you request the last element from the sorted list,
the init function still forces it to do so.
I don't know how one would do the removing of the maximum by going
through the list and whenever finding a bigger element, then saving
the positions of its predecessor and successor, so it could reassemble
the list in the middle, when it has done looking through it. Anyone
have ideas?
------------------------------
Message: 2
Date: Mon, 24 May 2010 16:47:50 +0200
From: Daniel Fischer <daniel.is.fisc...@web.de>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: beginners@haskell.org
Message-ID: <201005241647.50271.daniel.is.fisc...@web.de>
Content-Type: text/plain; charset="iso-8859-1"
On Monday 24 May 2010 16:15:32, Markus Läll wrote:
> On a list, that is internally too a list, the complexity of the
> operation is always at least O(n), because to find the maximum, you
> have to look through all the list -- i.e do n comparisons.
>
> If you don't have any other variables like pointers to the previous
> and next elements of the maximum, when you are going trough the list
> to find it, then after finding the maximum value, you have to go
> through the list again, to find its position and remove it...
>
> For
>
> > delete (maximum xs) xs
>
> the complexity is O(n + m), where m is the index of the maximum. This
> goes through the list to find the maximum, and then goes through it
> again up until it finds the first occurrance of it.
>
> For
>
> > init $ sort xs
>
> it is (n log n) + n, where (n log n) is the complexity of the sorting
> algorithm (it might be something else depending on the algorithm), and
> (+ n) is because the init funcion has to go through the list again to
> find its last element and remove it.
And since we changed the order of elements anyway,
drop 1 $ sortBy (flip compare) xs
saves us the last traversal. But if the order is changed, it can be done in
O(n).
>
> Although Haskell is lazy, and when sorting a list, it might not get
> fully sorted until you request the last element from the sorted list,
> the init function still forces it to do so.
>
> I don't know how one would do the removing of the maximum by going
> through the list and whenever finding a bigger element, then saving
> the positions of its predecessor and successor, so it could reassemble
> the list in the middle, when it has done looking through it. Anyone
> have ideas?
remLargest :: Ord a => [a] -> [a]
remLargest [] = []
remLargest [_] = []
remLargest (x:xs) = go [] x xs
where
go post _ [] = reverse post
go post mx (y:ys)
| mx < y = mx : reverse post ++ go [] y ys
| otherwise = go (y:post) mx ys
Not as ugly as I feared, and not as inefficient for descending lists as I
feared.
------------------------------
Message: 3
Date: Mon, 24 May 2010 16:53:42 +0200
From: Daniel Fischer <daniel.is.fisc...@web.de>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: beginners@haskell.org
Message-ID: <201005241653.42259.daniel.is.fisc...@web.de>
Content-Type: text/plain; charset="iso-8859-1"
On Monday 24 May 2010 16:47:50, Daniel Fischer wrote:
> But if the order is changed, it can be done in O(n).
And by that I meant
"in O(n) time with one traversal and in constant space", since
delete (maximum xs) xs
is O(n) time too and doesn't change the order.
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 23, Issue 37
*****************************************
