四十三庵

蔀の雑記帳

四十三庵からnoteにアウトプット拠点を移しています

はてなブログ側に告知出すのを忘れていました。 2020年に入ってから週一更新してたんですが、アクセスが伸びないので、方向修正することにしました。 四十三庵を更新することは今後ない予定です。 その思いは↓に書きました。 note.com はてな側で購読されて…

Amazonプライムやめました

タイトルの通りなんですが、Amazonプライムをやめました。 目次 目次 Amazonプライムのサービスがだんだん悪くなっていった サイトがだんだんごちゃごちゃしてきた 「なぜ俺はプライム会員なんだろう?」 Amazonプライムやめて困ったこと ヨドバシ.comが思っ…

WWDC2020 Keynoteメモ

IT

自分用メモですが公開します。 動画はこちら。 WWDC Special Event Keynote — June 22, 2020 – Apple 目次 目次 iOS 14 メイン Siri Message Map CarPlay App Store iPadOS Native AppのiPad特化 Apple Pencil Airpods Pro WatchOS App Security Homekit tvO…

三島由紀夫の作家としての成長を追いかけてみた〜「花ざかりの森」から「豊饒の海」まで〜

画像はこちらから 個人的に尊敬する人間が三人いて、三島由紀夫とKurt CobainとSteve Jobsなんだけども、アメリカ人二人は伝記読んで、 それなりに生涯を追ったんだけど、三島に関してはそこまで細かく追っていなくて、 小説を何個か読んで、その人となりは…

Notionを活用するためのTips

移行してから一週間ほどたちましたが、使えば使うほどに感動するツールです、Notion。 前回の移行記事に続いて、今回は活用術を書いてみたいと思います。 1から説明すると、たくさん書きたいことがあって書ききれないので、Tipsとしてポイントだけ書いてい…

EvernoteからNotionに移行したのでやったことと感想書きます

EvernoteはEvernoteでいいツールでしたが、Notionに乗り換えました。 目次 目次 移行作業でやったこと いいとこ なんといってもカンバンでも見れる柔軟なView アイコンやカバーを設定することを想定したUI Markdownが効く 複数ウィンドウで開く 悪いとこ シ…

自粛生活を充実させるためにお取り寄せした食べ物の感想を淡々と書いていく記事

ぼちぼち5月も終わりますね。 (この記事を書いているのは5月ですが、多分公開している頃は6月になっているでしょう) 日本の緊急事態宣言は解除となりましたが、依然として世界的には感染拡大は止まってないですし、 日本も第二波があるかもしれません。…

心と体が長期休暇を求めている

画像はこちらから さて。 この一週間は仕事的には谷間だった。 けど久しぶりにメンタル面で強い焦燥感が生じた一週間になった。 仕事で嫌なことがあった、という訳でもなかった。 以前もそうだったが、何か明確な原因がないまま、メンタルが動揺するのは、解…

どうしたらやるべきことに集中できるか

きりみんちゃんの下記のブログ記事を読んで。 kirimin.hatenablog.com 要するに、4ヶ月丸々空けて、スキルアップしまくったり、 趣味のレベルアップしようと思ったら、2ヶ月目くらいでゲームめっちゃやって堕落しちゃったぜ! という経験談なんだけども、…

カーシェアとマイカーの損益分岐点を考えてみた

カーシェアとマイカーの損益分岐点って月何時間乗るところなんやろな。コンパクトカー買った想定で— 蔀(しとみ) (@0si43) May 8, 2020 というわけで、損益分岐点が一日何時間乗ることなのかシミュレートしてみます。 画像出典 目次 目次 カーシェアのコスト …

最悪の人格から、最高の成果物が生まれることもある

2020年も4月が終わり、まもなく1/3が終わろうとしていますね。 進捗いかがですか ここ最近ブログに勉強ノートを大量投下したせいで、スパム攻撃受けたブログみたいに人間感がなくなってしまったので、 生活感のある、日記風の記事を書こうかなと思います。 …

アルゴリズム設計法

目次 目次 brute force solution Dynamic Programming Solution(動的計画法) 分類 Divide and conquer solution (分割統治法) Greedy Method(欲張り法) brute force solution 日本語の訳語がない セキュリティの文脈ではよくブルートフォースアタック…

Boyer-Moore String Search

理想的な場合はO(N/M)で探索できる 検索対象のワードの右から順に探索することで、スキップ量を大きくする

Knuth-Morris-Pratt String Search

単純な文字列検索は検索対象の文章の長さNと検索ワードの長さMのO(MN)になる KMPアルゴリズムを使うとO(N)でいける ただし検索ワードのスキップ量があらかじめ設定されている場合 発想としては、検索対象の文字を一文字ずつ照合していくと、 実は明らかにス…

Kruskal's Algorithm

実装 func minimumSpanningTreeKruskal<T>(graph: Graph<T>) -> (cost: Int, tree: Graph<T>) { var cost: Int = 0 var tree = Graph<T>() let sortedEdgeListByWeight = graph.edgeList.sorted(by: { $0.weight < $1.weight }) var unionFind = UnionFind<T>() for vertex </t></t></t></t></t>…

Prim’s Algorithm

計算量はO(n2) 解説はここがわかりやすかった 実装 func minimumSpanningTreePrim<T>(graph: Graph<T>) -> (cost: Int, tree: Graph<T>) { var cost: Int = 0 var tree = Graph<T>() guard let start = graph.vertices.first else { return (cost: cost, tree: tree) } v</t></t></t></t>…

Minimum Spanning Tree

重み付けのあるグラフに対して、コストが最小となるスパニングツリーを求めるアルゴリズム。 Prim’s Algorithm / Kruskal's Algorithmが二大解法

BFSとDFS

Breadth-First Search: 幅優先探索 Depth-First Search: 深さ優先探索 BFSは開始するNodeをキューに入れ、一度デキューしてから、隣接するNodeをキューイングする。 そしてDequeueしたNodeの隣接しているNodeをenqueueする…… (一度enqueueしたNodeはもうenq…

Dijkstra Algorithm

有向グラフの最短経路を見つけるためのアルゴリズム 計算コストはO(N2) 経路コストの計算にヒープを使うと、約O(2NlogN)までパフォーマンスが改善する 節点と辺の数が同程度の時に限るらしい 辺が多くなる(例えば全ての節点がつながれた完全グラフの時)は…

Warshall–Floyd Algorithm

ダイクストラと発想は同じだが、出発点が存在せず、全ての節点と全ての接点のコストテーブルを更新する コストテーブルのサイズはN*N 計算量はO(N3) 計算量はダイクストラよりN回倍多いが、実装が楽で、接点を結ぶ辺が多い際は有効 実装 import Foundation l…

グラフ理論

前提 本を読んだだけだと、グラフ理論そのものがよくわらかなかったので、前提を調べた。 内容 最終的なアウトプットが表になるかTreeになるかでわかれる グラフ理論では頂点のことをVertex、辺のことをEdgeと呼ぶ慣習があるよう。 Vertex = Node, Edge = li…

Bucket Sort

要素のとりうる値の範囲(バケット)に応じて挿入して、最後にmapするようなSort方法 特定の条件では計算効率がよい場合がある バケットがm個のとき、m < NならO(N)になる。

Heap Sort(ヒープソート)

Heapを使ってSortする Performance of heap sort is O(n log n) in best, worst, and average case 実装 Heapの実装にどっかバグがあって、上手くソートできなかった。 一日格闘してダメだったので、SACの模範解答見てお茶を濁した。 import Foundation stru…

Merge Sort(マージソート)

最悪計算量でもO(NlogN) メモリ領域はO(N)分食う フォンノイマンが考えたアルゴリズムらしいが、考え方はシンプルだし、計算効率いいし実用的 配列の真ん中から要素を分けて、それを繰り替えして、要素二つにしたらmerge() mergeされた配列は再帰的にどんど…

Quick Sort(クイックソート)

配列の最初の要素と二番目の要素の大きい方をpivotとして、その値との大小関係を使ってSortする 計算量は平均でO(NlogN) 最悪の場合はO(N2) 本の通り実装しようとしたら、Arrayはstructなので再帰ができなくて、 しかも引数のArrayはimmutabelで直接操作でき…

Bubble Sort(バブルソート)

小さな泡が水から浮き上がるようにソートすることから 「配列の最後からその一個前の要素を大小比較して、逆だったら要素を入れ替える」という操作を最初の要素の一個前まで行うことで最小の要素が配列の最初になる その操作を次は最初の要素の二個前まで行…

Hash

ハッシュ値を使うとO(1)で値を求められる 衝突という問題がある 衝突を回避するためには二つ方法がある チェイン法(chaining mechanism) 衝突した値はリスト構造でenqueして格納する 開番地法(open addressing) 衝突したら再ハッシュを行い、空いている…

B Tree(B木)

ノート balanced treeの例 A B-Tree of order n satisfies the following properties: Every node has at most 2n keys. Every node (except root) has at least n keys. Every non-leaf node with k keys has k+1 children. The keys in all nodes are sort…

AVL Tree

ノート ソビエト連邦時代のロシア人が論文書いたデータ構造。 平衡木の例 回転処理で計算量の効率性を保つ 実装例までは追えず

2-3 Tree(2-3木)

ノート balanced tree(平衡木)の例として2-3木が紹介されている 二分探索木はあくまで平均の計算量がO(logN)となるだけで、操作の結果によっては最悪の計算量O(N)になりうる そこでbalanced treeは常に計算量がO(logN)となるように要素を挿入・削除するた…