| 条件 | コード |
|---|---|
| xより大きい | v.end() - upper_bound(v.begin(), v.end(), x) |
| x以上 | v.end() - lower_bound(v.begin(), v.end(), x) |
| xである | upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x) |
| x以下 | upper_bound(v.begin(), v.end(), x) - v.begin() |
| x未満 | lower_bound(v.begin(), v.end(), x) - v.begin() |
書いておいてなんですが、「xより小さい」個数と「ちょうどxである」個数が求まれば、引き算と足し算で残りは求められるので表にするほどではないですね。
Symbolの使い方として、たとえば独自の特殊値を持ちたいと言うものがあります。
// myFind: 配列と関数を受け取り、 // 関数を満たす要素が見つかればその要素、 // 見つからなければnullを返す const myFind = (arr, f) => { for (let i = 0; i < arr.length; i++) { if (f[arr[i]]) return arr[i]; } return null; // 見つからなかった }; const res = myFind(arr, n => n % 2 === 0); // ではnullを探したいときはどうする？ myFind(arr, n => n === null); // nullが見つかったのかどうかわからない
このようなケースではSymbolが有効です。たとえばNOT_FOUND = Symbol('not found')として、見つからなければこれを返すようにすれば先程の関数は完璧になります。
const NOT_FOUND = Symbol('not found'); const myFind2 = (arr, f) => { for (let i = 0; i < arr.length; i++) { if (f[arr[i]]) return arr[i]; } return NOT_FOUND; }; const res = myFind2([1, 2, 3], n => n === null); assert(res === NOT_FOUND);
実はこのとき、Symbolの代わりに単にNOT_FOUND = {}としても同等のことができます。なぜなら{} !== {}だからです。
もちろん細かいところは全然違っているので完全には代用できませんが、ES5でも使えるテクなので覚えておいて損はないと思います。
const NOT_FOUND = {}; const myFind3 = (arr, f) => { for (let i = 0; i < arr.length; i++) { if (f[arr[i]]) return arr[i]; } return NOT_FOUND; }; const res = myFind3([1, 2, 3], n => n === null); assert(res !== {}); assert(res === NOT_FOUND);
実は先程のNOT_FOUNDを使う手法は厳密にはまだ不十分です。なぜなら、NOT_FOUNDを探したくなったときにnullのときと同じ問題が起こるからです。
厳格にするならばmyFindの返り値は以下のようになります。
myFind(arr, n => n % 2 === 0); // 見つかった場合 {status: 'found', value: found_value} // 見つからなかった場合 {status: 'not found'}
とはいうものの、実際には利便性と厳密さをトレードオフしてNOT_FOUNDで実装することも多いです。
ちなみにHaskellではこういうときにMaybeが使われます。とても便利です。JavaScriptにもパターンマッチがあればMaybeでガリガリと書けるのですが…
その名の通り、差分(difference)リストです。差分リストはListのappendのパフォーマンスが結合に依存する問題を解消します。
appendは結合順を変えても意味としては同じです。しかし、cons listではappendの結合順によりパフォーマンスがかなり異なります。
たとえば以下のコードのlist1とlist2では、圧倒的にlist2のほうが早いです。
list1 = foldl (++) [] $ replicate 10000 $ replicate 10 0 list2 = foldr (++) [] $ replicate 10000 $ replicate 10 0 main = do print $ take 1000 list1 -- 遅い print $ take 1000 list2 -- 早い
これは両者の結合順が異なることに由来しています。
(([0,0,0] ++ [0,0,0]) ++ [0,0,0]) ++ [0,0,0][0,0,0] ++ ([0,0,0] ++ ([0,0,0] ++ [0,0,0]))Cons listはappendする際に左のリストの中身をひとつずつ右へ移します。そのため、左辺を伸ばす結合をしているlist1はかなり遅くなります。
計算量を見てみます。list1はappendするたびに左辺の長さが10ずつ増え、10000回結合しています。そのため、計算量は5*(10000)*(10000+1)になっています。結合回数をNとするとO(N2)かかります。
対して、list2は左辺のリストの長さは固定で10です。そのため、10000回結合しても10*(10000)しかかかりません。結合回数をNとすればO(N)しかかかりません。
このように appendするときは原則右結合で書く必要があります。しかし、appendしたいだけなのに結合を気にするのはひどく辛いです。また、左結合が避けられないケースもあります。
このappendの結合性の問題を解消したのが差分リストです。
差分リストは関数合成を用いることで結合を変換します。よくわからないと思うので、コードを見てください。
list3 = ((([0] ++ [0]) ++ [0]) ++ [0]) ++ [0] diff_list = (((([0] ++) . ([0] ++)) . ([0] ++)) . ([0] ++)) . ([0] ++) $ []
こんな感じに、「[0] ++」という関数を合成していくことでappendを表現しています。この関数に[]を適用すると通常のリストへ変換できます。
見やすさのために補助関数や型を導入します。
type DiffList a = [a] -> [a] -- abs: 受け取ったDiffListをListへ変換する abs :: DiffList a -> [a] abs l = l [] -- rep: 受け取ったListをDiffListへ変換する rep :: [a] -> DiffList a rep = (++) -- ++の代わりに+++を用いて結合する (+++) :: DiffList a -> DiffList a -> DiffList a (+++) = (.)
これで結合性が解消できます。テストしてみます。
main = do print $ take 10000 $ Main.abs $ foldl (+++) (rep []) $ replicate 10000 $ rep $ replicate 10 0 print $ take 10000 $ Main.abs $ foldr (+++) (rep []) $ replicate 10000 $ rep $ replicate 10 0
どちらもかなり高速で動作します！
ただ、差分リストにもデメリットはあります。それが変換をしなければならないという点です。例として、差分リストを用いてキューを実装することを考えます。
type DiffList a = [a] -> [a] type Queue a = DiffList a abs :: DiffList a -> [a] abs l = l [] rep :: [a] -> DiffList a rep = (++) (+++) :: DiffList a -> DiffList a -> DiffList a (+++) = (.) push x l = l +++ rep [x] pop = rep . tail . Main.abs main = do print $ Main.abs (pop $ pop $ push 3 $ push 2 $ push 1 (rep []))
popを見るとわかりますが、1回popするたびにrepとabsが呼ばれてDiffList -> List -> DiffListという変換が行われています。この変換のうち、DiffList -> Listの部分が差分リストの長さぶんだけコストがかかってしまいます(diff_list ++ []を実行しているため)。1回popするたびに長さぶんコストがかかってしまうのはつらいので、差分リストをリストへ変換したくなりますよね？しかし、一度リストへ変換してしまうと、今度はpushができなくなります。そのため、pushしたくなったらまた差分リストへ変換する必要があります。
(まあそもそもqueueの実装に使わなければ良いだけの話ですが)
まとめると、pushしたあとにpopと、差分リストの長さだけコストがかかってしまいます。しかし、キューを使いたいとき、pushする箇所とpopする箇所がまとまっていることのほうが少ないです。困りましたね…
他にもあります。それが、差分リストはheadするのが容易でないという点です。差分リストの実態はただの関数です。そのため、差分リストの先頭を見るには、一度リストへ変換する必要があります。この変換には差分リストの長さ分コストがかかります。通常のリストへのheadが定数時間でできることを考えるとかなり大きなデメリットです。
さらに言うと、「差分リストが空かどうか」の判定でさえ一度普通のリストへ変換しなければできません。驚きですね。
と、そこで登場するのがType Aligned Sequenceです。詳しくは論文を読んでください。
ES2015でMapが追加されました。パッと見Objectっぽいですよね。本記事ではどこが違い、どういう用途で使うのか解説したいと思います。
続きを読むrefとはReference(参照)のことです。ミュータブルな値を管理するときに使います。
refの使いみちの最たるものはDOMへのアクセスです。たとえばinput要素が持つfocusメソッドを呼びたいときにrefを使います。
const App = () => { const ref = useRef(); useEffect(() => ref.current.focus(), []); // レンダー後、inputにフォーカスする return <input ref={ref}/>; };
上記の例では、refはDOMへの参照となっています。もちろん、refを使えばinputのvalueを変更したり、focusする以外にも様々なことを命令的にできます。しかし、DOMを命令的に操作するのはReactのやり方に相反します。そのため、できる限りrefを使わず宣言的に書く方法を考えるべきです。
refは単にミュータブルなオブジェクトです。そのため、生DOMへのアクセス以外にも使うことができます。ただし、そこまで用途はありません。というより、他の手法で十分なことがほとんどです。refを使いたくなったら一旦落ち着いて他の方法を考えましょう。
通常、関数コンポーネントはrefを受け取ることができません。たとえば下のMyInputのようなことはできません。
// ダメな例(関数コンポーネントはrefを受け取れない) const MyInput = ({ref}) => ( <input ref={ref}/> ); const App = () => { const ref = useRef(); const onClick = () => { ref.current.focus() }; // MyInputにrefは渡せない！ return ( <div> <MyInput ref={ref}/> <button onClick={onClick}>focus</button> </div> ); }
refは特殊なpropなので、そのままでは受け取れません。forwardRefを使ってやると関数コンポーネントでもrefを受け取れます。
// forwardRefを使えば関数コンポーネントでもrefを受け取れる const MyInput = React.forwardRef((prop, ref) => ( <input ref={ref}/> ));
useImperativeHandleを使うと、string refを使っていたクラスコンポーネントを関数コンポーネントへ書き直すことができます。
以下のChildコンポーネントはstring refを使って複数のinputへのrefを親コンポーネントへ提供しています。
// string refはclass componentでしか扱えない class Child extends React.Component { render() { return ( <form> <input type="email" ref="email"/> <input type="password" ref="password"/> <input type="text" ref="username"/> </form> ); } } class App extends React.Component { focusOnEmail() { // Child内のinput[type=email]へアクセスできる this.refs.form.refs.email.focus(); } render() { return ( <div> <Child ref="form"/> <button onClick={this.focusOnEmail.bind(this)}>focus on email</button> </div> ) } }
Childコンポーネントをhooksを用いて関数コンポーネントへ書き直します。
const Child = React.forwardRef((prop, ref) => { const emailRef = useRef(), passwordRef = useRef(), usernameRef = useRef(); useImperativeHandle(ref, () => { return { refs: { get email() { return emailRef.current; }, get password() { return passwordRef.current; }, get username() { return usernameRef.current; }, } }; }) return ( <form> <input type="email" ref={emailRef}/> <input type="password" ref={passwordRef}/> <input type="text" ref={usernameRef}/> </form> ); });
これで従来のstring refでできたことが再現できます。
(型をつけるのが非常に困難なので、こんな方法するくらいなら、素直にリファクタリングしましょう)
ただし、そもそもこれはstring refからhooksへ置き換えられるだけです。古いクラスコンポーネントを書き直すとき以外、こんな方法しなくて十分です。というのも幾つか理由があります。
そのため、個人的にこの方法は好きではありません。
いちから作るのであれば、まずApp側でrefを作り、Childはそれを受け取って紐付けるだけにするとシンプルになります。以下はChildをSFCにしてrefを受け取る例です。
const Child = ({ emailRef, passwordRef, usernameRef }) => ( // useImperativeHandleのようなことをする必要がない！ <form> <input type="email" ref={emailRef} /> <input type="password" ref={passwordRef} /> <input type="text" ref={usernameRef} /> </form> ); const App = () => { const emailRef = useRef(), passwordRef = useRef(), usernameRef = useRef(); // どういうrefがあるのかApp側が明示的に持てる const focusOnEmail = () => emailRef.current.focus(); return ( <div> <Child emailRef={emailRef} passwordRef={passwordRef} usernameRef={usernameRef} /> <button onClick={focusOnEmail}>focus on email</button> </div> ); };
TypeScriptでの型付け的にもこちらのほうが筋が通っています。
もちろん、下のほうの実装を隠蔽したいときはuseImperativeHandleが活躍します。
