{{ message }}

Instantly share code, notes, and snippets.

# banacorn/summary-week-1.md

Last active May 2, 2018
# Summary of Week 1 - Implementing nub

# Summary of Week 1 - Implementing nub

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

## Solutions

• 時間複雜度皆為 `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)```
• 時間複雜度皆為 `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```
• 時間複雜度為 `O(nlog n)`
• 運用 `Int` 可比較大小的性質（`Ord`
```qsnub [] = []
qsnub (a:xs) = compo (<a) xs ++ [a] ++ compo (>a) xs
where compo f = qsnub. filter f```
• 時間複雜度為 `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]
-}```
• 時間複雜度皆為 `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..]```
• 時間複雜度為 `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
dedup xs ytail
else
• 時間複雜度為 `O(n²)`
• `nub` 是 stable 的
```import Data.List

nub xs = [ x | (x, p) <- zip xs (inits xs), x `notElem` p]```
• 時間複雜度為 `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```
• 時間複雜度為 `O(n²)`
• `nub` 是 stable 的
```nub' :: [Int] -> [Int]
nub' (x:xs) | elem x xs = nub' xs
| otherwise = x:(nub' xs)
nub' [] = []

nub = reverse . nub' . reverse```
• 時間複雜度為 `O(n)` 或者 `O(nlog n)` （端看實作，在舊版 `unordered-containers``HashSet.insert` 曾經是 `O(min(n,W))`，現在改為 `O(log n)`
• 運用 `Int``Hashable` 的性質
• 有一定機率會把東西變不見
• `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```
• 時間複雜度為 `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).```
• 時間複雜度為 `O(n²)`
• `nub` 是 stable 的
```nub :: [Int] -> [Int]
nub [] = []
nub (x:xs) = x:(nub \$ filter (/= x) xs)```
• 時間複雜度為 `O(n²)`
• `nub` 是 stable 的
```import Data.List
nub xs = map fst . filter (uncurry notElem) \$ zip xs (inits xs)```
• 時間複雜度為 `O(n²)`
```nub :: [Int] -> [Int]
nub []     = []
nub [x]    = [x]
nub (x:xs) = if x `elem` xs then nub xs else x : nub xs```