四十三庵

蔀の雑記帳

ITについての記事

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…

アルゴリズム設計法

目次 目次 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)となるように要素を挿入・削除するた…

Binary Search Tree(二分探索木)

BSTとは 任意の要素の取得がO(logN)で済む構造 計算量がO(logN)ですむ証明が難しかった 実装 最初Structでやろうとしたら、再帰にできなくて死んだ ただ再帰でやることを思いついてしまうと、実装時間としてはそんなにかかんなかった if文2回ネスト(2×2)す…

Heap

基本教科書を読んでわかることは書かなくて、読んでいてわからなかった点や、 実際に手動かして書いてみたコードなんかを書いています。 Heapとは www.raywenderlich.com ここの説明がわかりやすい。 英語の意味 英語のHeapの意味は積み重ね heap of moneyな…

なぜデータ構造とアルゴリズムを学ぶか

2020/2〜3月にデータ構造とアルゴリズムを勉強したので、その勉強ノートをブログで公開して行こうと思う。 下記の本を使いました。 目次 目次 方法と期間 目的 技術力とは? フレームワークがあれば不要だよ論 次回予告 方法と期間 五十嵐健夫さんの…

データ構造とアルゴリズムノート 目次

2020/2〜3月にデータ構造とアルゴリズムを勉強したので、その勉強ノートをブログで公開する。 全体 はじめに データ構造とアルゴリズムノート 目次 なぜデータ構造とアルゴリズムを学ぶか データ構造 Heap Binary Search Tree(二分探索木) 2-3 Tree…

みずほ銀行のシステム統合の本読んで思ったこと

みずほ銀行の新システムMINORI稼働に至るまでを追った本を読んだので、それに関連することを書く。 記事のレベル感はちょっと迷うところなのだが、ある程度リテラシーが高い読者を前提にするので、用語の解説などは行わない。 みずほ銀行システム統合、苦闘…

ブログのデザインを変えました2020

IT

ブログのデザインは定期的に気になってイジっていたが、2015年に大幅にCSSカスタムしてしばらく満足していた。 blog.stm43.com その後Google Adsense導入、2017年にはブログ用のデザインを組んだり、カスタマイズしまくった。 ただ僕自身の思想として、 優れ…

自分がはてなスターをつけた一覧が見たい!!!!!!!!!!!!!!

IT

最近真面目にブログを書いています。 自分が真剣に書いたものにスターがつくと嬉しいです。 だから人が書いたものにも、気軽にスターをつけるようになりました。 noteのスキもかなりカジュアルに押します。 最近はもう読んだら押す、くらいのレベル。 (内容…

EaseUS MobiMoverを試してみました

IT

EaseUS(イーザス)という会社から、 TwitterのDMで「ウチの会社の製品レビュー書きませんか???」という依頼が来て、試すことにしました。 EaseUSとは EaseUS MobiMoverとは 機能 お値段 使ってみた感じ メリット デメリット まとめ EaseUSとは 2004年設…

iPhone XsからPixel 3aへ機種変更しました

掲題の件、感想を書く。 もし同じ移行をしようとしている人がいれば、参考になったら嬉しい。 なぜ機種変更したか iPhone Xsを売った顛末 データ移行自体は簡単 モバイルSuicaが一番手間取った LINEはトーク履歴移行諦めた Google Photoが無制限ではない ウ…

ライフハック:ポモドーロテクニックを導入して、ゆるく運用して1ヶ月が経ちました

ポモドーロテクニックとは 使うツール マイルール どうだったか 課題について ポモドーロテクニックとは 1つのタスク管理法。 詳細は下記。 ポモドーロ・テクニック:世界が実践する時間管理術はこうして生まれた | キャリア | 最新記事 | ニューズウィーク…