DouKaku?beta

Comment detail

アレイのuniq (Nested Flatten)
こんなのでいいのか。 (import Data.List が必要) 
1
nub xs

nub だと最悪のケースでO(n^2) になる。以下のuniqなら要素がOrd(順序)クラス
という条件のもとで最悪ケースでO(n log n)にできる。

最悪ケースのベンチマークは以下のとおり

*Main> length $ uniq [1..10000]
10000
(0.13 secs, 11539780 bytes)
*Main> length $ uniq [1..100000]
100000
(1.00 secs, 121637004 bytes)
*Main> length $ nub [1..10000]
10000
(0.98 secs, 1045976 bytes)
*Main> length $ nub [1..100000]
100000
(95.85 secs, 8910200 bytes)



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import Data.List

app o f x y = f x `o` f y
cmpapp = app compare
eqapp  = app eq

uniq :: Ord a => [a] -> [a]
uniq  = map snd  . sort . map head . groupBy (eqapp snd) . sortBy (cmpapp snd) . zip [1..]

uniq' :: Eq a => [a] -> [a]
uniq' = nub

あれあれコードを写しそこねてる。ごめんなさい。
eq なんて関数ないし、型宣言を文脈をつけて書くのが正しい。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import Data.List

app :: (b -> b -> c) -> (a -> b) -> (a -> a -> c)
app o f x y = f x `o` f y

cmpapp :: Ord b => (a -> b) -> (a -> a -> Ordering)
cmpapp = app compare

eqapp :: Eq b => (a -> b) -> (a -> a -> Bool)
eqapp  = app (==)

uniq :: Ord a => [a] -> [a]
uniq  = map snd  . sort . map head . groupBy (eqapp snd) . sortBy (cmpapp snd) . zip [1..]

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]