「Scala で diff を書いてみた」[1] という記事に触発されて [2] の論文や [3] の解説を読んで diff のアルゴリズムを勉強して自分なりに Scala で実装してみました。 これは [2] で "An O((M+N)D) Greedy Algorithm" と呼ばれているほうの実装で、論文の後半では改良についても書いてあるけどそちらは読んでいません。 私なりに工夫をした部分は全体的に副作用を排除した所とエディットグラフの格子点をオブジェクトとして表現した点です。 元論文の擬似コードで "a number of simple optimizations are employed" とされている部分は可読性の観点から取り入れませんでした。ただ元論文が「D回の編集で到達する（対角線 k 毎の）最遠点の集合」を配列で管理しているのを Set で管理するようにしたのは本当はよろ
タグ
- すべて
- .net (526)
- 2ch (1611)
- aa (121)
- actionscript (95)
- adobe (190)
- agile (563)
- ai (43)
- air (228)
- ajax (357)
- algorithm (84)
- amazon (521)
- amazon ec2 (163)
- amazon ecs (119)
- amazon rds (34)
- amazon s3 (89)
- android (1625)
- anime (561)
- ansible (123)
- apache (270)
- api (40)
- apple (694)
- apple watch (77)
- appstore (53)
- ar (88)
- architecture (511)
- asp.net (90)
- async (60)
- au (90)
- authentication (156)
- aws (1079)
- aws lambda (133)
- backup (131)
- battery (39)
- bdd (58)
- benchmark (169)
- blog (156)
- book (633)
- boost (37)
- browser (515)
- bts (65)
- build (34)
- business (755)
- c (169)
- c# (131)
- c++ (552)
- c++11 (33)
- calendar (52)
- camera (587)
- canvas (39)
- capistrano (42)
- capture (38)
- career (35)
- catalyst (167)
- cdn (61)
- centos (103)
- cheatsheet (42)
- chef (225)
- chrome os (48)
- ci (415)
- circleci (33)
- citrix (43)
- closure (33)
- cloudcomputing (580)
- cms (78)
- cocoa (57)
- codereview (59)
- collaboration (51)
- comic (88)
- communication (163)
- community (39)
- compiler (65)
- configuration (36)
- container (393)
- coreos (38)
- cpan (95)
- cpu (50)
- css (503)
- dart (39)
- database (1299)
- dbic (40)
- ddd (61)
- debug (211)
- dell (48)
- deploy (292)
- design (288)
- development (939)
- devops (266)
- devtool (33)
- di (66)
- display (73)
- django (45)
- dns (46)
- docker (693)
- docomo (228)
- document (111)
- documentation (77)
- dojo (38)
- dom (33)
- drawing (63)
- dropbox (122)
- dsl (57)
- dvcs (198)
- eclipse (229)
- ecmascript (34)
- editor (259)
- education (58)
- elasticsearch (42)
- elixir (32)
- emacs (56)
- engineer (173)
- english (49)
- epub (33)
- erlang (187)
- event (260)
- evernote (105)
- excel (134)
- ext (33)
- extension (318)
- eye-fi (42)
- facebook (118)
- feed (33)
- filesystem (79)
- firebug (76)
- firefox (586)
- flash (330)
- flex (94)
- flickr (44)
- fluentd (123)
- flutter (34)
- font (97)
- food (160)
- framework (458)
- frontend (408)
- functional (101)
- gadget (799)
- game (771)
- gc (45)
- gears (52)
- generator (66)
- git (824)
- github (348)
- gitlab (58)
- gmail (123)
- golang (305)
- goods (92)
- google (1401)
- google app engine (179)
- google calendar (39)
- google chrome (301)
- google docs (52)
- google reader (45)
- googlemaps (53)
- gps (104)
- grails (62)
- graph (80)
- graphql (70)
- greasemonkey (39)
- groovy (194)
- grpc (36)
- gtd (46)
- hack (38)
- hadoop (52)
- hardware (189)
- hashicorp (45)
- haskell (52)
- hatena (142)
- hdd (39)
- health (103)
- heroku (49)
- hosting (38)
- html (403)
- html5 (261)
- http (112)
- httpd (47)
- https (38)
- hudson (122)
- hyper-v (83)
- iOS (530)
- iaas (54)
- icloud (37)
- icon (56)
- ide (225)
- ie (202)
- illust (105)
- image (66)
- infrastructure (66)
- install (144)
- ipad (628)
- iphone (3795)
- ipod (32)
- it (413)
- itunes (51)
- jailbreak (52)
- java (1675)
- java8 (34)
- javaee (55)
- javafx (52)
- javascript (2582)
- jenkins (217)
- jquery (306)
- jruby (104)
- json (138)
- jsonp (33)
- jvm (57)
- k8s (73)
- kernel (67)
- kindle (185)
- knowledge (63)
- kotlin (40)
- kubernetes (223)
- kvm (42)
- kvs (67)
- language (306)
- library (909)
- license (42)
- life (155)
- lifehack (444)
- lifestyle (50)
- linq (42)
- linux (1026)
- lisp (34)
- llvm (50)
- log (158)
- mac (592)
- macosx (33)
- mail (129)
- management (184)
- map (87)
- mapreduce (65)
- markdown (54)
- marketing (70)
- mashup (87)
- maven (41)
- media (96)
- memcached (74)
- memory (103)
- memoryleak (36)
- mercurial (136)
- microservice (109)
- microsoft (878)
- mindmap (58)
- mmorpg (32)
- mobile (649)
- modeling (88)
- module (54)
- mongodb (41)
- monitor (58)
- movie (34)
- mozilla (56)
- music (500)
- mvc (50)
- mysql (343)
- netbeans (42)
- netbook (59)
- network (397)
- nginx (58)
- node.js (302)
- nosql (145)
- notepc (193)
- o'reilly (105)
- oauth (42)
- objective-c (121)
- office (202)
- offshore (46)
- oop (84)
- openid (46)
- openoffice (44)
- opera (35)
- oracle (206)
- orm (84)
- os (181)
- oss (399)
- paas (198)
- packer (42)
- parallel (36)
- pattern (51)
- pc (263)
- pdf (146)
- performance (734)
- perl (934)
- photo (202)
- php (498)
- plack (59)
- plugin (128)
- postgresql (183)
- presentation (52)
- privacy (97)
- programmer (117)
- programming (2014)
- protocol (60)
- prototype.js (56)
- prototyping (47)
- proxy (33)
- psgi (43)
- puppet (32)
- python (356)
- rails (905)
- react (310)
- react native (61)
- redhat (63)
- redmine (173)
- redux (62)
- refactoring (58)
- regexp (46)
- rest (133)
- review (46)
- ria (82)
- rspec (61)
- rss (99)
- rssreader (37)
- ruby (1521)
- rust (87)
- saas (72)
- safari (68)
- salesforce (48)
- sbm (69)
- scala (109)
- scalability (193)
- scm (37)
- scraping (33)
- script (32)
- scrum (125)
- seasar (57)
- security (965)
- selenium (79)
- server (296)
- serverless (118)
- serverspec (35)
- shell (57)
- shopping (61)
- si (97)
- silverlight (123)
- smartphone (650)
- sns (84)
- social (41)
- softbank (140)
- software (605)
- sony (423)
- sourcecode (36)
- spring (58)
- sql (135)
- sqlite (53)
- sqlserver (43)
- ssd (42)
- ssh (76)
- ssl (41)
- storage (363)
- streaming (45)
- study (47)
- subversion (336)
- sun (54)
- swift (40)
- tablet (350)
- tag (32)
- tdd (94)
- team (70)
- techno (53)
- technology (76)
- template (42)
- terminal (56)
- terraform (104)
- test (645)
- thread (71)
- tidd (69)
- tips (637)
- titanium (83)
- todo (87)
- tomcat (39)
- tool (596)
- trac (201)
- travel (175)
- trouble (169)
- tuning (220)
- tutorial (99)
- tv (122)
- twitter (446)
- typescript (209)
- ubuntu (172)
- ui (131)
- uml (81)
- umpc (34)
- unicode (71)
- unittest (205)
- unix (34)
- url (41)
- usability (83)
- utility (123)
- vagrant (153)
- vaio (55)
- vcs (188)
- vim (46)
- virtualbox (65)
- virtualization (585)
- vista (45)
- visual studio code (72)
- visualization (80)
- visualstudio (243)
- vmware (171)
- vocaloid (60)
- vscode (59)
- vue.js (60)
- vulnerability (72)
- web (241)
- web2.0 (60)
- webapi (279)
- webassembly (49)
- webdesign (577)
- webpack (54)
- webservice (75)
- websocket (34)
- webアプリ (192)
- webサービス (1492)
- web制作 (602)
- web開発 (746)
- wifi (126)
- wiki (103)
- wimax (68)
- windows (1164)
- windows 10 (57)
- windows 7 (111)
- windows 8 (75)
- windows azure (59)
- windows phone (85)
- word (39)
- wsl (38)
- xcode (41)
- xen (97)
- xml (132)
- xpath (32)
- xss (54)
- yahoo (102)
- youtube (111)
- yui (45)
- zsh (35)
- あとで (2183)
- けいおん！ (84)
- これはすごい (33)
- これはひどい (64)
- ねこ (33)
- ねんどろいど (111)
- はてブ (86)
- まとめ (113)
- まどか☆マギカ (88)
- アメリカ (50)
- ケータイ (205)
- サーバ監視 (32)
- サーバ管理 (72)
- システム監視 (72)
- システム管理 (61)
- システム運用 (74)
- システム開発 (325)
- ソフトウェア開発 (65)
- タスク管理 (165)
- テザリング (38)
- ドラクエ (37)
- ニコニコ動画 (157)
- ネタ (1050)
- ネタ政治 (113)
- フィギュア (394)
- プロジェクト管理 (397)
- マスコミ (35)
- モバイルルータ (46)
- 並列処理 (47)
- 中国 (152)
- 交通 (71)
- 仕事 (448)
- 仕事術 (195)
- 企業 (65)
- 位置情報 (50)
- 便利 (127)
- 健康 (56)
- 写真 (249)
- 初音ミク (95)
- 動画 (278)
- 地デジ (34)
- 地図 (49)
- 地方 (36)
- 壁紙 (68)
- 広告 (42)
- 情報共有 (84)
- 情報整理 (38)
- 政治 (185)
- 教育 (47)
- 文字コード (37)
- 新聞 (47)
- 旅行 (140)
- 検索 (121)
- 検索エンジン (33)
- 民主党 (108)
- 決済 (33)
- 海外 (165)
- 無線lan (37)
- 生活 (47)
- 画像 (212)
- 画像処理 (78)
- 社会 (112)
- 素材 (38)
- 組織 (41)
- 経済 (57)
- 考え方 (48)
- 自動化 (60)
- 艦これ (50)
- 著作権 (37)
- 読み物 (37)
- 通信 (239)
- 鉄道 (46)
- 開発プロセス (178)
- 開発環境 (406)
- 電子マネー (35)
- 電子書籍 (436)
- 静的解析 (37)
- 韓国 (156)
- iphone (3795)
- javascript (2582)
- あとで (2183)
- programming (2014)
- java (1675)
- android (1625)
- 2ch (1611)
- ruby (1521)
- webサービス (1492)
- google (1401)
scalaとalgorithmに関するlizyのブックマーク (1)
-
lizy 2008/03/01
- scala
- algorithm
- diff
リンク -
1
公式Twitter
- @HatenaBookmark
リリース、障害情報などのサービスのお知らせ
- @hatebu
最新の人気エントリーの配信
処理を実行中です
キーボードショートカット一覧
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
設定を変更しましたx