Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# Summary of Week 1 - Implementing nub

Summary of Week 1 - Implementing nub

  • 14 位參與者
  • 18 種解法(外加一種使用 Prolog XD)
  • 大部分時間複雜度為 O(n²),少數運用 IntOrdHashable 性質將複雜度壓到 O(nlog n) 甚至 O(n)
  • 大部分實作是 stable 的(在這裡定義為保持輸入資料從前面往後枚舉的順序)
    • 多數利用 foldr 搭配 reverse
    • 少部分利用 zip 維護資料順序

Solutions

  1. 王韋勝 https://gist.github.com/wilson8507/f81f2eb0e63824e1a8e8fc42f4dd1cc4
  • 時間複雜度皆為 O(n²)
  • nub3 是 stable 的
nub1 :: [Int] -> [Int]
nub1 xs = foldr isntElement [] xs
  where isntElement x xs | length [y | y <- xs, y == x] == 0 = x:xs
                         | otherwise = xs

nub2 :: [Int] -> [Int]
nub2 [] = []
nub2 (x:xs) | length [y | y <- nub2 xs , y == x] /= 0 = nub2 xs
            | otherwise = x : nub2 xs

nub3 :: [Int] -> [Int]
nub3 [] = []
nub3 (x:xs) = x : nub3 (filter (/= x) xs)
  1. Tai An Su https://gist.github.com/taiansu/3c041a7b972701c4154e651b4bcc4693
  • 時間複雜度皆為 O(n²)
nub' :: [Int] -> [Int]
nub' = foldr f [] where
  f x xs
    | x `elem` xs = xs
    | otherwise   = x:xs

-- without using `elem`
nub'' :: [Int] -> [Int]
nub'' = foldr f [] where
 f x xs
  | length (filter (x ==) xs) > 0 = xs
  | otherwise                     = x:xs
  1. 葉柏宏 https://gist.github.com/rareone/cd7db3d7ac4a4fbadd48d1b4ab472f1a
  • 時間複雜度為 O(nlog n)
  • 運用 Int 可比較大小的性質(Ord
qsnub [] = []
qsnub (a:xs) = compo (<a) xs ++ [a] ++ compo (>a) xs
  where compo f = qsnub. filter f
  1. 潘廣霖 https://gist.github.com/andy0130tw/528bec01bbfff96a1244c46c61d9db00
  • 時間複雜度為 O(n²)
  • nub 是 stable 的
nub' :: [Int] -> [Int] -> [Int]

nub' rs []     = reverse rs
nub' rs (x:xs) | elem x rs = nub'    rs  xs
               | otherwise = nub' (x:rs) xs

nub :: [Int] -> [Int]

nub = nub' []

{-
some test cases:
  * nub [] == []
  * nub [1, 2, 3, 4] == [1, 2, 3, 4]
  * nub [1, 1, 1, 2] == [1, 2]
  * nub [1, 2, 2, 5, 3, 5] == [1, 2, 5, 3]
  * nub [1, 2, 3, 4, 2, 3, 1, 5, 4, 3] == [1, 2, 3, 4, 5]
-}
  1. Shin-Cheng Mu https://gist.github.com/scmu/900cc6b30972d2b55bf9cfc8803d8c3c
  • 時間複雜度皆為 O(nlog n)
  • 運用 Int 可比較大小的性質(Ord
  • nubStable 是 stable 的
import Data.Ord
import Data.List

nubSimple :: [Int] -> [Int]
nubSimple = map head . group . sort

nubStable :: [Int] -> [Int]
nubStable = map fst . sortBy (comparing snd). map head .
              groupBy ((. fst).(==).fst) . sort . flip zip [0..]
  1. 郭宗霆 https://gist.github.com/jc99kuo/05d0728b3b479465b0b1d62fa7c03aeb
  • 時間複雜度為 O(n²)
  • nub 是 stable 的
--  FLOLAC 2018 Week 1 -- nub: filter out duplicating integers on a list

nub :: [Int] -> [Int]

nub ix = dedup [] ix
  where
    dedup = \xs ys ->
      case ys of
        [] -> xs
        (yhead:ytail) ->
           if (elem yhead xs) then
             dedup xs ytail
           else
             dedup (xs ++ [yhead]) ytail
  1. 江宗儒 https://gist.github.com/ray851107/afc8c9c82a56403667e3896e7b0cde4d
  • 時間複雜度為 O(n²)
  • nub 是 stable 的
import Data.List

nub xs = [ x | (x, p) <- zip xs (inits xs), x `notElem` p]
  1. 陳昱維 https://gist.github.com/akira02/1ae4c0cce5d3941bce00813fcca4bbd1
  • 時間複雜度為 O(nlog n)
  • 運用 Int 可比較大小的性質(Ord
  • 偷用別人寫好的 Data.Set XD
  • nub 是 stable 的
import qualified Data.Set as S

nub = go S.empty
  where go _ [] = []
        go s (x:xs) | S.member x s = go s xs
                    | otherwise    = x : go (S.insert x s) xs
  1. Terry Cheong https://gist.github.com/terry182/3f31de2b19c66db208d84afafa539ec9
  • 時間複雜度為 O(n²)
  • nub 是 stable 的
nub' :: [Int] -> [Int]
nub' (x:xs) | elem x xs = nub' xs
            | otherwise = x:(nub' xs)
nub' [] = []

nub = reverse . nub' . reverse
  1. 許恆與 https://gist.github.com/m80126colin/0852fa76bf741c4a258840f892033aae
  • 時間複雜度為 O(n) 或者 O(nlog n) (端看實作,在舊版 unordered-containersHashSet.insert 曾經是 O(min(n,W)),現在改為 O(log n)
  • 運用 IntHashable 的性質
  • 有一定機率會把東西變不見
  • nub 是 stable 的
import Data.Hashable
import Data.HashSet

-- Amortised linear-time by hashing
uniqhs :: (Hashable a, Eq a) => HashSet a -> [a] -> [a]
uniqhs _ []     = []
uniqhs h (x:xs) = if member x h then uniqhs h xs else x:uniqhs (insert x h) xs

nub :: [Int] -> [Int]
nub = uniqhs empty
  1. Jensen Holder https://gist.github.com/shhyou/cffcaafe0fe6bb410a60a0f8aaf44701
  • 時間複雜度為 O(n²)
  • nub 是 stable 的
bun []                   = []
bun (x:xs) | x `elem` xs =     bun xs
           | otherwise   = x : bun xs

nub :: Eq a => [a] -> [a]
nub = reverse . bun . reverse
  • 出來面對啦!! XD
append3(XS, YS, ZS, OS) :- append(XS, WS, OS), append(YS, ZS, WS).

% nub(PS ++ (Q:QS) ++ (Q:RS)) = nub(PS ++ (Q:QS) ++ RS)
nub(XS, OS) :- append3(PS, [Q|QS], [Q|RS], XS), !,
               append3(PS, [Q|QS], RS, YS),
               nub(YS, OS).
nub(XS, XS).
  1. Yu-Ren Pan https://gist.github.com/YuRen-tw/9c24e474f8ab46f5d1edba2b46be0904
  • 時間複雜度為 O(n²)
  • nub 是 stable 的
nub :: [Int] -> [Int]
nub [] = []
nub (x:xs) = x:(nub $ filter (/= x) xs)
  1. 林子期 https://gist.github.com/Zekt/7eaefa0f142b20569664a8460fd5da81
  • 時間複雜度為 O(n²)
  • nub 是 stable 的
import Data.List
nub xs = map fst . filter (uncurry notElem) $ zip xs (inits xs)
  1. 洪崇凱 https://gist.github.com/RedBug312/ed954151416c3293f271d0e6f46e5494
  • 時間複雜度為 O(n²)
nub :: [Int] -> [Int]
nub []     = []
nub [x]    = [x]
nub (x:xs) = if x `elem` xs then nub xs else x : nub xs
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment