Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

差分リスト(Difference List)について

Difference Listとは？

その名の通り、差分(difference)リストです。差分リストはListのappendのパフォーマンスが結合に依存する問題を解消します。

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 -- 早い

これは両者の結合順が異なることに由来しています。

  • list1は左結合(([0,0,0] ++ [0,0,0]) ++ [0,0,0]) ++ [0,0,0]
  • list2は右結合[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するのが容易でないという点です。差分リストの実態はただの関数です。そのため、差分リストの先頭を見るには、一度リストへ変換する必要があります。この変換には差分リストの長さ分コストがかかります。通常のリストへのheadが定数時間でできることを考えるとかなり大きなデメリットです。

さらに言うと、「差分リストが空かどうか」の判定でさえ一度普通のリストへ変換しなければできません。驚きですね。

Type Aligned Sequenceなら解決できる

と、そこで登場するのがType Aligned Sequenceです。詳しくは論文を読んでください。

React ref解説

React JavaScript Hooks

refとは？

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を使いたくなったら一旦落ち着いて他の方法を考えましょう。

forwardRef

通常、関数コンポーネントは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}/>
));

String refを使っていたコンポーネントをhooksで書き直す

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コンポーネント側からrefs以下に何があるか分からない
  • 下のコンポーネントでhookを使いたくない

そのため、個人的にこの方法は好きではありません。

いちから作るのであれば、まず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が活躍します。

イトーキF レビュー

中古でイトーキのFというオフィスチェアを購入したのでレビューです。

感想

すごくいいです。座椅子でずっと作業してたのですが、苦労が全てなくなりました。

ヘッドレストがないモデルですが、あまり気になりません。ディスプレイを買ったので下を向いて作業することがなくなったのも、おそらくはヘッドレストが要らない要因の一つです。

肘掛けは絶対にあったほうがいいと思いました。肘掛けあるとすごく楽に作業できます。試しに肘掛けを外に向けて肘が宙にある状態で作業してみましたが、圧倒的にやりづらいです。可動式の肘掛け、これは本当にオススメです。写真ではあまり内側への角度調整ができなそうに見えましたが、十分でした。めっちゃいいです。

座り心地もいいですね。「わー高級！」みたいにはなりませんが、疲れません。若干背もたれとの間に隙間があるのが気になりますが、疲れないので問題ないです。

結構背が高い(180cm弱)ですが、十分ゆったりと使えます。いい椅子です。

プロフィール

お問い合わせは @le_panda_noir まで

SNS