はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
/0 » diff(3)
そんなわけでO(NP)のお話とか。 まず、処理を最適化するためにO(ND)の無駄を考えてみる。 O(ND)では編集回数Dを0…nと変化させて順次処理を行うわけだけど、仮に集合A(0…M)とB(0…N)の間で、M!=Nの関係が有る場合、D<|M-N|の間は決して終端にたどり着かない期間の計算となる。 また、編集回数Dの時に、零距離直線kを-D…0…Dまで計算するが、この際も実際には結構無駄な計算を行っている。 というのも、編集回数Dで終点にたどり着ける場合、実際に経路として使用されるkの範囲は-D…0…Dと一致しない。 集合Aと集合Bの関係をN>=Mと仮定して、Δ=N-Mとした場合、この未知の集合において最も少ない編集回数はΔとなるが、その場合のkの範囲は0…Δとなる（上図の緑色の範囲）。 以降Dが2増える毎(移動距離1の往復分)に-1…Δ+1、-2…Δ+2とkの範囲が広がっていくこ
/0 » diff(2)
diff続き。 今回はO(ND)アルゴリズムと一般的に呼ばれている方法のまとめ。 O(Nなんちゃら)とか表記する場合、本当は処理時間の指標の筈で、元々O(ND)もこのアルゴリズムにはO(ND)掛かりますよってダケの筈なんだけどなぁ・・・。 何処を覗いてもMyers氏のアルゴリズムをO(ND)アルゴリズムと呼ぶ不思議。 diff(1)と同様に 集合 A(0…M) = { a b d e f a b c e d } 集合 B(0…N) = { d a b a b c b c b a e d } のdiffを取る事を考える。 （エディットグラフは前回参照で） エディットグラフ上の最短距離を考えるにあたり、如何に効率よく斜線部分を通るかを考える（最短距離＝最も効率よく斜線部分を通過した経路）。 ここで、斜線斜線と呼ぶのも、原文diagonal直訳の対角線もちょっとアレなので、あえて
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
