読者です 読者をやめる 読者になる 読者になる

$shibayu36->blog;

プログラミングの話や自分の考えを色々と書いています。

BM法による文字列マッチング学習メモ

grepで文字列マッチングしている時の仕組みを学ぶために、BM法などの文字列マッチングについて調べていた。調べたことをメモしておく。特にまとまってはいない。参考になった文献は以下。 コーディングに役立つ! アルゴリズムの基本(7):文字列の中から効…

問題解決のための質問群を学んだ - 「考える技術・書く技術」を読んだ

最近、自分は問題をうまく分割して解決する能力や、他の人に分かりやすく伝える能力がまだ足りていないと感じていた。そのあたりを強化するために、おすすめと言われた「考える技術・書く技術」を読んだ。考える技術・書く技術―問題解決力を伸ばすピラミッド…

ゴールを決め目標を決める・解決案ではなく質問する - コーチングの学習で学んだこと

半年前から会社でシニアエンジニアという役職で、エンジニアのメンターの役割を担っている。その役割を出来るだけうまく演じられるように、半年間はコーチングの学習を進めてきた。 目標設定の仕方を学ぶ - 「ザ・コーチ」読んだ - $shibayu36->blog; なぜ最…

Union Findアルゴリズムの様々な実装とパフォーマンス計測

CourseraにAlgorithms Part1という授業があり、これが非常に評判が良いので、会社で勉強会をしている。Week1にUnion Findというアルゴリズムが出てきて、その実装パターンがいくつかあった。それぞれ計算量が違うらしいのだけど、速度がどのように変化するか…

登場人物を分類し、振る舞いを分解して、機能を考える(企画職の人に教えてもらったこと)

本職の企画の人が優れた機能案を出してくる理由がわからなくて、どうやってやってるんですかと雑談した。新たな発見があったので、雑なメモだけ残しておく。*1 その人の企画の流れ 企画の流れは、以下の3ステップで行っているらしい。 1. 登場人物を分類する…

「検索エンジン自作入門」を読んだ

Elasticsearchが裏でどのように動いているか理解できるようにするために、「検索エンジン自作入門」を読んだ。検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏作者: 山田浩之,末永匡出版社/メーカー: 技術評論社発売日: 2014/09/25メディア: 単行…

どうやったら発見した問題をうまく放置できるようになるのか

仕事をしていると、様々な問題が発見される。問題を発見した時、とにかくすぐに対処しようとしてしまうことが多い。しかし、そうしていると、タスク量が増えてきたときに問題解決に忙殺され、もっと重要なことに取り掛かれないということが起こりがちである…

「無印良品は、仕組みが9割」を読んだ

昨夜なぜか眠れなかったので、積んであった「無印良品は、仕組みが9割」を一気読みした。無印良品は、仕組みが9割 仕事はシンプルにやりなさい作者: 松井忠三出版社/メーカー: 角川書店発売日: 2013/07/10メディア: 単行本この商品を含むブログ (15件) を見…

転置インデックスの構造から見る全文検索

全文検索エンジンについて学んでいたのだけど、転置インデックスのデータ構造という観点から見るといろいろ面白かったのでまとめてみる。 転置インデックスの具体的な構造 全文検索では、転置インデックス(Inverted index)という仕組みを使う。詳しくは第3回…

WikipediaのXMLデータから文書を1000件含むXMLファイルを作成するワンライナー

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏作者: 山田浩之,末永匡出版社/メーカー: 技術評論社発売日: 2014/09/25メディア: 単行本(ソフトカバー)この商品を含むブログ (4件) を見る検索エンジン自作入門を見ていて、WikipediaのXMLデータ…

極大部分文字列について調べた

社内の技術勉強会で極大部分文字列というワードが出てきたので、自分で調べた内容をメモ。内容があっているかは保証しない。 極大部分文字列とは何か 定義は 全ての部分文字列を考慮した文書分類 に書いてある これによると、「極大部分文字列の必要十分条件…

「数学ガール/乱択アルゴリズム」を読んだ

アルゴリズム読み物を読みたくて、いろんなところでオススメされている数学ガールの乱択アルゴリズムを読んだ。なかなか興味深かった。数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)作者: 結城浩出版社/メーカー: SBクリエイティブ発売日: 2011/03/02…

パーフェクトJavaを読んだ

最近アルゴリズムの勉強でJavaを使っていて、いい機会だしどうせならJavaの言語の詳細な機能や考え方などを知りたいと思っていた。Javaをやっている人に聞いてみると「パーフェクトJava」が良いということなので読んでみた。改訂2版 パーフェクトJava作者: …

Suffix Arrayを使った文字列マッチング

あるPatternがあるText中のどこに含まれるかという文字列マッチングの実装を最近してみている。前回、Suffix Trieでの文字列マッチングを行った。blog.shibayu36.orgSuffix Trieを利用すると、Suffix Trieを最初に構築したあと、実際にパターンを検索するの…

CircleCIでJava8 + Gradleプロジェクトのテストを行う

興味本位で自分のアルゴリズム実装repository( https://github.com/shibayu36/algorithms )のテストをCircleCIで動かしてみようと考えた。基本的にCircleCIはcircle.ymlに設定を追加したら終わりなのだけど、何を設定すればいいか少し調べる必要があったので…

冪集合を作るメソッドをジェネリクス対応する

以前 Javaで冪集合を生成する - アルゴリズム学習(その3) - $shibayu36->blog; で冪集合を作るメソッドを実装していた。しかし、以前の実装だとListでしか冪集合を作ることができなかった。最近パーフェクトJavaを読んで、ジェネリクスについて学んだので、…

Suffix Trieを使って文字列マッチングする

文字列マッチングを行うためのアルゴリズムとして、Suffix Trieを使った探索というものがある。これはテキストからSuffix Trieという構造を作り、パターンをつかってそれを辿ることで、パターンの長さmに対して、O(m)の計算量で探索できるものである。今回は…

nanobenchを使ってJavaのベンチマークを取る

アルゴリズムを学習していると、ある実装の速度がどのくらいか計測したいことがよくある。これまでは、currentTimeMillisを利用して、愚直にベンチマークを取っていたのだけど、結構だるい感じだった。調べてみると、jmh と nanobench という二つのツールが…

「世界でもっとも強力な9のアルゴリズム」読んだ

なんとなくアルゴリズム系の読み物読んでみたかったので読んだ。世界でもっとも強力な9のアルゴリズム作者: ジョン・マコーミック,長尾高弘出版社/メーカー: 日経BP社発売日: 2012/07/19メディア: 単行本購入: 15人 クリック: 437回この商品を含むブログ (21…

基礎技術の学習のモチベーションをどう保つか

最近、コンピュータサイエンスなどの基礎的な知識を学習するように心がけている。できる限り今後も長い期間役に立つ、寿命の長い技術や知識を付けておきたいためである。その一貫で アルゴリズムを学習 してみている。 学習をはじめて感じた課題 しかし、と…

文字列マッチングのためのLCP Arrayを構築する

前回のブログ記事で、文字列マッチングをするためのSuffix Arrayという構造を構築した。このSuffix Arrayという構造だけでも、テキスト長をn、パターン長をmとして、の計算量で文字列マッチングできるようになった。 suffix arrayを一番簡単なアルゴリズムで…

Chrome Developer ToolsのTimeline -> Bottom-Up -> Group by URLが便利だった

アニメーションが遅い問題を調査していて、どうやって原因を特定すれば良いかわからない状態だった。それをチャットで会話していたら同僚が「Chrome Developer ToolsのTimeline -> Bottom-Up -> Group by URL使うと良さそう」みたいなことを教えてくれた。使…

suffix array構築のメモリ効率を良くする - アルゴリズム学習(その7)

blog.shibayu36.org上の記事で、一番簡単なアルゴリズムでのsuffix arrayの構築を実装してみた。しかしこれをベンチマークしようとして、10万文字くらいの文字列に対して適応してみると、Java heap spaceというエラーが出てしまい、計算できなかった。こうな…

suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6)

文字列アルゴリズムを学んでいると、suffix array(接尾辞配列)という配列が出てくる。これは文字列の接尾辞の集合を辞書順にソートし、その順でそれぞれの接尾辞の文字列中の開始位置のindexを格納した配列のことである。以下が参考になる。 接尾辞配列 - Wi…

力づく法・分割統治法・動的計画法 - アルゴリズム学習(その5)

アルゴリズムの設計手法として、力ずく法・分割統治法・動的計画法というような考え方があった。新しいアルゴリズムを学ぶ時、どの設計手法でやっているのだろうかと意識しておくと、頭に入りやすい気がした。そこで、自分の頭を整理するためにメモを書いて…

Javaデータ構造とアルゴリズム基礎講座読んだ

Java データ構造とアルゴリズム基礎講座作者: 長尾和彦出版社/メーカー: 技術評論社発売日: 2008/12/26メディア: 大型本購入: 4人 クリック: 171回この商品を含むブログ (13件) を見る読んだ。実装しながら読んでいて、その実装は https://github.com/shibay…

Javaでスタックとキューを実装 - アルゴリズム学習(その4)

Java データ構造とアルゴリズム基礎講座作者: 長尾和彦出版社/メーカー: 技術評論社発売日: 2008/12/26メディア: 大型本購入: 4人 クリック: 171回この商品を含むブログ (13件) を見る 今回はスタックとキュー。非常に基本的なデータ構造だし、だいたい知っ…

Javaの文字列の長さを判定するには

自分の頭を整理するために書いておく。正しいかは知らない。まず前提として、Javaの内部表現としての「文字」は16ビット長のUTF-16ということがある。そうすると、普通に長さを取得すると、UTF-16のサロゲートペアで表される文字は2文字と扱われる。また、文…

Javaで冪集合を生成する - アルゴリズム学習(その3)

同僚に冪集合作ってみては、と言われたので作った。冪集合はhttp://www.geocities.jp/k27c8_math/math/set_theory/power_set.htmとかに書いてあるとおり、渡された集合の部分集合全体。 考え方 思いついたのは以下の考え方。 [ 1, 2, 3 ]と渡されたとする 冪…

Javaで組み合わせを生成する - アルゴリズム学習(その2)

Javaで順列生成アルゴリズムを実装する - アルゴリズム学習(その1) - $shibayu36->blog;で順列を作ったので、続いて組み合わせを作ってみた。 考え方 いろんな考え方があると思うけど、僕が最初に思いついたのは次の考え方。 [ 1, 2, 3, 4, 5 ]から3つ取り出…

Perl Hackers Hubで執筆した「Perl開発への動的な型制約の導入」がWebで公開されました

以前Web+DBのVol.94のPerl Hackers Hubで執筆した、「Perl開発への動的な型制約の導入」がWebで公開されていました。gihyo.jpPerlに動的な型制約を導入するのは結構簡単にできて、安全さがかなり変わると思います。興味がある人は見てください!

Javaで順列生成アルゴリズムを実装する - アルゴリズム学習(その1)

アルゴリズムを勉強しようと思って、以下の本のアルゴリズムをJavaで自分で考えて再実装するという取り組みをやっている。以下の本は基本的なアルゴリズムが簡単に説明されていて、しかも薄いのでやりやすい。アルゴリズムの勉強のしかた - きしだのはてなを…

ディレクターを経験して良かった

この記事は、はてなディレクターアドベントカレンダー2016の19日目です。昨日は id:shimobayashi の「効率的で課題解決的な態度にひそむ罠について」でした。こんにちは、はてなでアプリケーションエンジニアをやっているid:shiba_yu36です。僕は現在はエン…

はてなインターンの事前課題をJavaでやった - Java入門記(その2)

はてなインターンの事前課題で非常に簡単なltsvパーサーを作るやつがあるのだけど、Javaの勉強のためにJavaで実装してみた。ltsvパーサーは結構いろんな言語で誰かが実装しているので、これどうするのがいいのかってなったら、その実装を見に行くとやり方を…

Javaに入門している(その1)

Javaでアルゴリズムを紹介している本に書いてあるアルゴリズムを全部Javaで実装してみるというのをやってみたかったので、まずJavaに簡単に入門している。 Javaの構文を理解する まあ簡単だった。 スッキリわかるJava入門を読む まあ素直な構文なので分かっ…

「スッキリわかるJava入門」読んだ

Javaでアルゴリズム実装してみようと思って、とりあえずJavaに入門した。とりあえず書ければいいので、簡単そうな「スッキリわかるJava入門」という本を買って読んだ。スッキリわかるJava入門 第2版 スッキリわかるシリーズ作者: 中山清喬,国本大悟出版社/メ…

特定のHTML属性を追加するだけでリンククリック計測したい(Google Tag Managerを利用して)

今日はGoogle Tag Managerの設定をすることで、自分が好きなエリアのリンククリック計測を簡単にする方法について書く。 課題 クリック計測は自作で作るのは大変 Google Tag Managerで計測することもできるが、計測対象を増やすためにタグを毎回一つ増やすと…

builderscon tokyo 2016に参加しました & 発表しました

builderscon tokyo 2016に参加してきました。buildersconは「知らなかった、を聞く」をテーマにしたと書いてあるとおり、かなり尖った発表が多く、非常に楽しめました。僕は「一から始めるJavaScriptユニットテスト」という発表をしました。全体的にハックっ…

「コーチングのすべて」読んだ

なぜ最近コーチングや人間の学習モデルの勉強をしているのか - $shibayu36->blog;や、目標設定の仕方を学ぶ - 「ザ・コーチ」読んだ - $shibayu36->blog;の続きとして、コーチングという知識を体系的に学びたいと思い、「コーチングのすべて」を読んだ。コー…

エンジニア立ち居振舞い: 分かりやすく依頼する・説明する

お題「エンジニア立ち居振舞い」というお題を id:hitode909 くんが作っていたので書いてみる。 コードを書く以外にいろいろとしているのだけど、その中の一つとして「分かりやすく依頼する・説明する」ということに時間を割いているので紹介。 エンジニアと…

なぜ最近コーチングや人間の学習モデルの勉強をしているのか

最近以下のようにコーチングや人間の学習モデルの勉強をしている。 目標設定の仕方を学ぶ - 「ザ・コーチ」読んだ - $shibayu36->blog; 「リファクタリング・ウェットウェア」を再読した - $shibayu36->blog; 「コーチングのすべて」という本を今読んでいる …

AMPについてのコンテンツ消費者としての感想メモ

昨日、「AMPが導入された結果、現時点ではモバイルのブラウズ体験が大きく損なわれてるのですが、そう感じるのは僕だけでしょうか」とTwitterでつぶやいたら、いろいろ反応があり、いろんな観点を知ることが出来たのでメモしておく。なお、自分自身はまだAMP…

「やさしいコンピュータ科学」読んだ

やさしいコンピュータ科学 (Ascii books)作者: アラン・W.ビアマン,Alan W. Biermann,和田英一出版社/メーカー: ASCII発売日: 1993/06メディア: 単行本購入: 6人 クリック: 184回この商品を含むブログ (30件) を見る最近、流行りのものを勉強するより、技術…

「リファクタリング・ウェットウェア」を再読した

最近、学生時代よりも学習時間を取れなくなっていて、このままだと新しいことが身につかなくなっていっていくのではという危機感があった。またメンターをするにあたって、人の学習モデルをある程度理解しておいて、アドバイス出来るようにしたいという思い…

目標設定の仕方を学ぶ - 「ザ・コーチ」読んだ

最近コーチングという分野に興味を持って、まずは簡単でさくっと読めそうな「ザ・コーチ」という本を読んだ。ザ・コーチ作者: 谷口貴彦出版社/メーカー: プレジデント社発売日: 2012/05/31メディア: Kindle版この商品を含むブログを見るこの本は、副題も含め…

「いちばんやさしいグロースハックの教本」読んだ

サービスの成長について少しだけ理解を深めたくて読んだ。いちばんやさしいグロースハックの教本 人気講師が教える急成長マーケティング戦略 (「いちばんやさしい教本」シリーズ)作者: 金山裕樹,梶谷健人出版社/メーカー: インプレス発売日: 2016/01/22メデ…

チーム内プロジェクトが発足した時に、プロジェクトの朝会を用意すべきか

最近チーム内で少し大きめなプロジェクトが発足して取り組んでいたのだが、その時プロジェクトの朝会(デイリースクラム)をするべきなのか悩んだことがあった。自分の中ではプロジェクトごとの朝会を用意すべきという結論に至ったのだが、今回はその結論に至…

関数の仕様を正しく実装していることをどう保証するのか

静的型チェックがあったらテストはあまり書かなくて良いのか - $shibayu36->blog; で静的型チェックがあったとしても、テストをあまり書かなくて良いわけではないという話を書いた。するとブコメでいろいろ意見をもらえた。これらの意見から、関数の仕様を正…

MySQLを使って簡易的にサービスの数値を集計する

最近色んな機能を作る時に、簡単に数値を集計してみて様子を見るということがよくあった。そこで今回はその時に使ったクエリの紹介。【2016/10/18 10:28追記】 社内でHOUR関数とかGROUP BYにalias名を使ったらもっと簡単にできるよと言われたので、それぞれ…

TypeScriptを2系にアップデートした

TypeScript 2.0 is now available! | TypeScript ということで、自分のプロジェクトのTypeScriptを1.8.9から2.0.3に上げた。あんまり困ったことはなかったけど、少しだけハマったのでメモ。 コンパイルを通すための対策 readonly property対策 今のプロジェ…