Re: [Haskell] Lista bez powtórzeń.

Article View: pl.comp.lang.funkcyjne

Article #361

Back to pl.comp.lang.funkcyjne Previous Next

#361

From: Marcin Gajda
Date: Sun, 15 Jun 2003 21:35

18 lines
1771 bytes

> Przeczytałem ten kod i nie bardzo rozumiem, po co wyznaczasz tam medianę
> ze środkowego i skrajnych elementów listy. Quicksort działa dla 
> dowolnego, wybranego do podziału elementu - niekoniecznie środkowego.
> W ten sposób parę razy niepotrzebnie biegasz po liście (drop,
> reverse). Być może bredzę (czegoś nie zrozumiałem), ale wydaje mi się,
> że takie coś również zadziała i to pewnie szybciej:

Wyznaczam medianę, gdyż w Twoim przypadku QuickSort robi się kwadratowy
dla posortowanego ciągu. A akurat listy, które potem przeglądam mają w
przeważnie postać [a..b] ++ [c..d], b < c.

QuickSort z glibca też tak działa, więc jest to chyba spoko. Oczywiście
takiego też można ukwadracić, ale to już raczej ciężkie jest.

Pozdrawiam,
-- 
Marcin Gajda ________________________
Dieu me pardonerra - c'est son metier

Technical Details

Message-ID: <bciorh$8jv$1@kenny.mimuw.edu.pl>

Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!mimuw.edu.pl!news.mimuw.edu.pl!not-for-mail

References: <bcijpt$1s1$1@kenny.mimuw.edu.pl> <bcinv9$s2g$1@pasza.io.waw.pl>

Show Full Headers

Complete Article Headers

Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!mimuw.edu.pl!news.mimuw.edu.pl!not-for-mail
From: Marcin Gajda <marcin.gajda@kicha.zagrycha.pl>
Newsgroups: pl.comp.lang.funkcyjne
Subject: Re: [Haskell] Lista bez powtórzeń.
Date: Sun, 15 Jun 2003 21:35:45 +0000 (UTC)
Organization: MIMUW
Lines: 18
Sender: Marcin Gajda <mg174717@zodiac.mimuw.edu.pl>
Message-ID: <bciorh$8jv$1@kenny.mimuw.edu.pl>
References: <bcijpt$1s1$1@kenny.mimuw.edu.pl> <bcinv9$s2g$1@pasza.io.waw.pl>
NNTP-Posting-Host: zodiac.mimuw.edu.pl
Mime-Version: 1.0
X-Trace: kenny.mimuw.edu.pl 1055712945 8831 10.1.1.1 (15 Jun 2003 21:35:45 GMT)
X-Complaints-To: abuse@news.mimuw.edu.pl
NNTP-Posting-Date: Sun, 15 Jun 2003 21:35:45 +0000 (UTC)
User-Agent: tin/1.5.10-20011117 ("Darkcell") (UNIX) (Linux/2.4.20 (i686))
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Reply to Parent Message