月: 2023年3月
してみた、というのが本記事の趣旨ですが、この記事はtwitterにフィードとして流れる予定です。ややこしいな。
このブログの投稿はwordpressの連携機能でtwitterに流していたし、そこ経由で読みたい人もたくさんいると思うしまぁそれはいいか、とは思ってた。んだけど、なにか反応があったりするとそのために読むのはかったるいし、あんまり考えたくないなという気持ちになってきた。なのでいったん止めることにします。というか前回の投稿で止めてたのでシェアされてないんだけど、止めたことをお知らせする必要はあるんじゃないかと改めて思ってこんな記事を書いています。
twitterで出てきたときだけ読んでいたという奇特なお方は、RSSリーダなどで読むか、またはmastodonではシェアしたりするかもしれないのでそっちをご覧ください。あるいはなんだろうな……wordpress.comがactivitypubに対応してくれたらいいんですけど。Automatticがんばれ。というかtumblrがActivitypub対応するって話はどうなったんだ。
3月14日に嵐がサウスベイを襲った。雨はそれほどでもなかったが風が強くてどうかなあと思っていたら家のインターネットが落ちてしまった。数時間で復旧するかなと思っていたら、24時間たってもまだ落ちている。
調べてみたら偶然うちは大丈夫だったが近所に停電が広がっているらしい。その停電も続いていて、たぶんインターネットの設備が停電エリアにあるので落ちたままなんではないか、という気がする。なかなかのおおごとである。今回はベイエリア全体で15万世帯とか停電しているらしい。
停電しなかったのはよかったがしかし、インターネットがないと本当の意味で仕事にならないので、今日は回線を探し求めて外出した。ノマドワーカーだ。
最初に向かったのは図書館で、ここはけっこうよかった。同じような境遇の人々がいて混雑していたがなんとか空き席を確保して仕事ができた。インターネット回線も速くはないがふつうに安定している。ありがたい。
昼食を食べるために離席して、ついでに移動もするかとRed Rockカフェに行ったが、ここは停電で閉店していた。ダウンタウンはおおむね停電の影響がなくてみな営業していたけど、ここの区画だけ停電があったらしい。
そこからは新しい場所をさがしてすこしさまよい、カフェに行ったりして仕事をしていた。図書館もカフェもどこもそれなりに賑わっていた。平日ふだんどれくらいの賑わいなのかは知らんけど、やはり自分と同じような境遇の人が多いからだと思う。
学校も閉鎖していたりするので子連れの人たちもよくみかけた。子供を座らせて宿題をやらせているな……という母親をみかけたりした。
ちなみに台風一過かどうなのか、今日は素晴らしい天気で青空が広がり、すこし暑いくらい。ぽかぽかとしたいい一日だった。これほどいい天気だがしかし停電トラブル、という対比はなかなかにシュールであった。
それにしても停電もインターネット断もなかなかのおおごとである。強風や大雨で落ちるのはめずらしいが、このへんだとまあ、たまにあるなという感じ（こんなに長期なのははじめて体験したけど）。一方、これくらいの強風は日本のほうがおおそうなものだが、倒木やそれにまつわる停電とかはあまり聞いたことがない。なんでなんだろうな、というのは気にはなる。
首都圏はそこまで木が多くなくよく管理されているので、強風で被害がおきそうなやつは切っちゃったりするが、このへんはそういうのを放置しがちだし巨木も多くてそういう管理が大変だからではないか、というのが妻の説。このへんは人口が東京みたいに密ではないので送電網もsparseになっていてresilienceが低いんじゃないか、というのが友人の説。どっちもありそう。両方の組み合わせだったりするのかもね。
明日もまだ断線していそうだ。明日はどこに出かけるかな……
前回の記事を書いてから、考えてるだけじゃだめだなとすこし書いてみたところいろいろわかった。
Rcはリファレンスカウントで管理できる。RcはWeakをつくれるので、たとえばnext方向にRcをつなげておき(先頭ノードはリスト本体が保持)、prev方向へはWeakを持たせればいいのではないか？ と考えてみたのだった。
やってみたところこの方針では書けないということがわかった。Rcの参照先は基本的には更新ができない。ノードを追加したらprevやnextを書き換えないといけないけど、書き換えができない。書き換えをするには mutable なリファレンスを一時的に獲得する必要があるが、weakも含めたリファレンスカウンタが1でないといけない(これは安全性のためだろう)。prevとnextで基本的にノードにはstrongが1つとweakが1つ常にあるので、mutableなリファレンスを獲得できない。
なのでこの方針で書くことはできないのだった。マジで？
ArcはRcのようなリファレンスカウンタだが非同期でアクセスできるようになっている。mutexと組み合わせると一時的に書き換えができたりする。どう考えてもオーバーヘッドが大きいから現実的じゃないけど、これならRcの問題は解決されるんじゃないだろうか？
解決される、というふうには思う。だが問題があった。要素の参照を返せないのだ。
たとえば、先頭要素を返す front() メソッドを書いてみたとする。こんな感じになる。
pub fn front(&self) -> Option<T> {
if let Some(n) = &self.head {
let node = n.lock().unwrap();
Some(node.element.clone())
} else {
None
}
}このコードでは結果の値を clone して返している。単純に&node.elementとする場合、そのライフタイムはnodeのライフタイムに縛られる(Mutexのlockというのはそういうものだ)。なので返される値はifの中が終わった瞬間に無効になるのでコンパイルできない。
こういうインタフェースを実装していくのは可能だが、cloneできるものに限定するのもイマイチだし、要素アクセスのたびにcloneされるのはまったく現実的ではなさそうだし、要素を書き換えたいときのイディオムが変わってしまう(front_mutみたいなものは書けない)。イテレータのインタフェースも標準的なものとは変わってしまう。
というわけで、やはり現実的ではなさそうだ。
ノード間でオーナーシップを持つのはおかしいんじゃないかという気がする。ノードのオーナーはリスト本体であってそいつが所有していればいい。あとは適当にリファレンスを持てばいいんじゃないか。こんな感じ。
struct Node<'a, T> {
element: T,
next: Option<&'a Node<'a, T>>,
prev: Option<&'a Node<'a, T>>,
}
struct LinkedListVec<'a, T> {
nodes: Vec<Node<'a, T>>,
head: Option<&'a Node<'a, T>>,
tail: Option<&'a Node<'a, T>>,
}ノードをベクタで管理していて連結リストとは……という気持になるが、適切にreservedなサイズを増やしていけば追記するだけならamortized costはO(1)なのでいいんじゃないか。本気でやるなら削除したノードを管理しないといけないが……。
だがどうもライフタイム解析で失敗してしまい、うまくいかない。リストがノードを保有していてその生存範囲では有効ではあるが、そのようなことをうまく表現できていないような気がする。
というわけでこの方向性もうまくいかなさそうだ。
ちなみにだが、next/prevをusizeにしてしまい、nodesの中の場所をインデックスで指定する、という方法ならたぶん大丈夫だと思う。しかしそれはなんというかもはや、nodesをメモリ領域にしてインデックスをポインタがわりにしているのとほぼ同じことである。そりゃまぁ unsafe という言語機能は使わないが、インデックスの先がほんとうに生きているものかの保証があやういので(途中でノードを破棄したときとか)、ぜんぜん安全な感じがしない。さすがにアホっぽい気がするのでこれは試していません。
というわけで、double-linked-listをsafe Rustの範囲内で作るのはどうも無理っぽいというので正解という気がする。raw pointerとunsafeバリバリなstdのリスト実装が一番現実的なのであった。そこまで複雑じゃないからね、という話なのかもしれない。
しかし、linked listていどのことすら適切に表現できないような言語仕様というのはどうなんだろうか。どうも自分は不思議な気持ちになるんだよな。なにかもっとうまい仕組みがあったりしないんだろうか？
ところで single-linked-list なら、まぁ Box とかを使えばいけそうな気がする。双方向イテレータも zipper とかを使えば実現できるんじゃないかな。でも実際にやってみたらいろいろ罠があるんだろうか。
なんかそろそろまた入門してみるか、という気持ちになったので勉強してみることに。
なにかしらちょっとしたものを作ってみるぐらいがいいかなと思うが、プロジェクトアイディアをさがしていても進まないのでまずなにかを読んでみることにした。とりあえず std にある linked list のコードを読んでみた。あと deque と binary heap。このへんは単純。 B-tree も読んでみようかなという気がするが格段に複雑になるね。
linked list はつくりは単純なので理解はできるが、わからないこともあったので疑問を書いておく。
linked list は基本的に NotNil (ほぼ raw pointer のラッパ)を使っていて、unsafeだらけだ。なぜだろうか？
第一に std の linked list は double-linked list で、各ノードはバックリンクを持つ(リスト本体も先頭と同時に末尾へのポインタをもち、push backがO(1)でできるようになっている)。single-linked listならオーナーシップを連結させればよさそうな気がする。
2つのオブジェクトが相互にリファレンスを持っているというのは単純な循環リンクなので、たとえば単純なリファレンスカウント (Rcなど)では適切に管理できない。drop時に適切にリファレンスカウントを減らすようなコードを書かないといけないが、それならraw pointerを開放していっても手間がいっしょ。ただRcからweakをつくれるようだ。それならできる？
そもそも単純に、あるノードが次のノードの所有権を持つとすると、そのノードのライフタイムは確定できるので、次のノードが前のノードへのポインタを持っていても安全性は保証できそうな気がする。安全なweakポインタというか。そういうのってないんだっけ？ あったらこんな仕組みになってないとおもうので、ないんじゃないかという気がするけど、どうして存在しないんだろう。こんな単純な例ならいいけど現実的にうまく解析できないとか、そういう理由なんだろうけども……。
疑問の2。raw pointerを使えばいいような気もするけど Option と NonNil を組み合わせているのはなぜ？
これは単純で、raw pointerはnilかどうかをチェックするのもunsafeになってしまうから、かなぁ。
Jun Mukai's blog 