nDiki : アルゴリズム

アルゴリズム論 第5回

本日の内容

ヒープソート。

学生から受けた質問等

• うまくソートされない: どこがおかしいかまで、こちらで調べてあげると本人のためならず。printf 文挿入で問題部分をしぼりこむ方法を説明。

今日の質問は1人のみ。 もう、やる気のない学生の方が多い。 現状では、現場サポートの副手もこれだけいるのは無駄な気がする。

ハッシュとは

新人に Perl のハッシュの話をしていて、ふと隣にいた5年選手のプログラマに「ハッシュって何ですか」と質問してみた。

「キーと…」と連想配列としての使い方は理解していたが、「もしや」と思った通りハッシュ表、ハッシュ関数、チェイン法、開番地法といったことはまったく知らず。 当然、自分で書いたこともなし。

「クラスとかあるから…」

まぁ Java でも C++ でも Perl でも基本的なデータ構造はだいたい何らかの方法で提供されており多くのケースではそれらを使うのがよいのは事実。

しかしハッシュ・リンクリストや各種ツリーは1度は実装した事があるべき。 そもそも原理を理解していないと適切にデータ構造を使い分けられないし、速度・メモリ効率とかの検討もできない。

データ構造とアルゴリズムの基本は(当然)押さえとけ。

「○○についてのお薦めの本、ありますか?」

たまに

「○○についてのお薦めの本、ありますか?」

と問われることがある。 ○○には C++ とか、C# とか Perl とかその他もろもろのコンピュータ関連キーワードが入る。

正直この質問は辛い。

コンピュータ関連の書籍は、今や大量に出版されているし陳腐化も激しいので相当マメにチェックしていないと人に紹介できるもんじゃない。

もちろん古典・定番もあることはあるが、こういう質問の時はたいがいこれには当てはまらない。 言語や開発環境なんかの本の質問はあるけれど、計算機数学とかアルゴリズムとかそういうのを求めてくる人などいないのである (大体そういうのに興味がある人は自分で探している)。

たまたま自分が詳してかつ最近リサーチをかけた分野については良書と呼べるものを知っている場合があるが、良いと思ったら自分でも買っているから既にその人に貸していたりする。

安直にコンピュータ書籍を紹介して欲しいという人は、よくわからないというのを理由に自分で探さず、しかもハズレを引いて金を払うことを非常に嫌っている。

一応質問されると Amazon.co.jp とかのぞいてみるのだが、その人のスキル・その人が求めているものまで理解していないので、結局徒労に終わるのである。 だいたいその程度なら、本人ができるはずなのだが。

ま、ようはケチらずどんどん読んで「この本はウンコだ」と言えるようになるのが一番ということだ。

で、なんかお薦めの本ありませんか?

• Naney お薦めの本

今日のさえずり - ささやかな気持ちDES

2008年11月06日

• 08:12 アルゴリズムこうしんマスターしたい。[mb]
• 09:37 向かいの女の人が「消化器now」読んでる。[mb]
• 09:39 まずい。もう腹減ってる。[mb]
• 09:39 消化済みnow。[mb]
• 09:56 信号赤なのでファミリーマートに寄って R25 入手。[mb]
• 11:04 あ、そうだ。PostgreSQL 入れてた PC テスト環境用として供出したんだっけ。開発機にまたインストールしなくては。
• 11:17 メール受信がうまくいかないというので「telnet メールサーバ 110」した。久しぶりだけれど、USER と PASS と QUIT ぐらいは覚えていた。
• 12:08 今日は向日葵という弁当屋にチャレンジ。[mb]
• 12:29 弁当屋でもらったスクラッチカード、上に大きく「ささやかな気持ちDES」って書いてある。新しい暗号っぽい。スクラッチ結果は 10YEN。
• 12:38 粗大ごみ収集申し込み完了。11月19日(水)。
• 12:46 P3_fan follow。
• 13:40 ん? SO905iCS がソフトウェアダウンロードしている。
• 13:42 SO905iCS、2008年11月5日にソフトウェア更新が出たのか。手動更新実行。
• 18:37 公募公告「スパムメール対策装置 エネルギー充填サービス更新」ってすごい件名だな。
• 19:12 昨日帰り人身事故運転見合わせくらったが、今日もまた京浜東北線一時運転見合わせていたのか。もう大丈夫かな? 明日ロング残業会社飯なので今日はもう帰るよ。
• 19:40 ヨドバシカメラでデジカメプリント受け取り。[mb]
• 19:51 京浜東北線ぜんぜん来ないじゃん。L:秋葉原駅[mb]
• 19:56 ようやく京浜東北線南行くる。L:秋葉原駅[mb]
• 20:13 MovaTwitter に「つぶやき検索」があったのか(以前に見たの忘れていただけかも)。[mb]

2008年11月07日

• 08:54 今日のヨドバシカメラ前販促はエボルタとインディ・ジョーンズ。L:秋葉原[mb]
• 11:11 きた、窓ガラス清掃。車止まっていたもんなー。
• 12:11 ヨドバシカメラ。[mb]
• 12:26 「こうすれば必ず人は動く」購入。みんな動かしちゃる。[mb]
• 12:32 過去データを考えて筆まめ購入。DVD-ROM ドライブないので CD 版。コンテンツ少ないから安くして欲しいところ。[mb]
• 12:38 @lynmock デール・カーネギーだけど別著書です。人を動かすは学生時代からマイバイブルの一つですが、まだこちらは読んでなかったので。[mb]
• 12:39 昼はハッピーセットね。たまごっち。[mb]
• 12:42 @lynmock ラジャー。[mb]
• 12:48 東京にはマクドはありません。
• 17:56 コーディングモードから抜けた。
• 19:09 今日は食って帰るデー。
• 19:16 @zakwa ピザ1週間に2回食べたからもういい。
• 20:13 鉄鍋ラーメン食べた。ずっと熱々。[mb]
• 20:28 説明書の ZIP ファイルアイコンが象になっている。パオーン。ってこれ何のツールだろ。
• 20:40 象のアイコン、bash0C7 さんが教えてくれた「LHAユーティリティ32」でビンゴでした。
• 20:50 明日雨降らないといいな。焼き芋大会。
• 21:21 睡眠不足もありちょっと限界。帰る。[mb]
• 21:28 頭にピンクのカツラのせて歩くのやめれ(男)。L:秋葉原[mb]
• 21:55 粗大ごみ処理券品切れってどういう事だよ、ローソン。みんな捨てまくってるとでもいうのか?[mb]
• 22:35 Life-X の存在忘れてた。

今日のさえずり: 満員電車のなかでもげて落ちた。さようなら。

2009年07月22日

• 08:12 QRIO のアルゴリズム体操やるなあ。 [mb]
• 08:38 バッグにさげていたミニルービックキューブが満員電車のなかでもげて落ちた。さようなら。 [mb]
• 08:49 コンコースの電気街口側、工事カバー取れてきた。地味な結末。 #Akihabara L:秋葉原駅 [mb]
• 09:46 給与引き下げ。 *P3
• 09:51 日食はタイムラインで雰囲気だけ楽しむ。 *P3
• 11:02 本社の人は部分日食見られているらしい。生意気。 *P3
• 13:12 今日のさえずえり - YEBICHU じゃなくなっていたのが非常に残念 (2009-07-20) http://ff.im/-5xEtn
• 16:25 「さえずり」って「さえずえり」って typo すると芸名っぽい。 *P3
• 17:54 「廃トナー容器がいっぱいです」 *P3
• 18:09 Joel がいうところの「アーキテクチャ宇宙飛行士」ばりに抽象化したいという衝動と闘った。 *P3
• 18:43 @train_kanto 18:43 京浜東北線南行東京駅付近ゆっくり走行。前詰まってる。 [mb]
• 18:50 このちんたらカクカク制動は三半器官的にイライラする。そんな京浜東北線の中。 [mb]
• 19:04 LABI 店頭で、ももいろクローバーのインストアライブやってる。人だかりで見えないけど。 L:大井町 [mb]
• 19:07 ももいろクローバー撮影禁止。この間きていたピカチュウは OK だったのに。 [mb]
• 25:10 browse-url の設定が古いままでうまく Iceweasel で開けなかった問題をようやく修正した。 *P3

今日のさえずり: ココス貸切状態になった

2010年05月17日

• 08:44 アルゴリズムこうしんMAXだと?
• 09:40 京浜東北線安全確認で止まってる。
• 11:02 今日ガラス清掃の日か。
• 12:04 弁当 350円。 (@ 向日葵 和泉町店・カレー食堂) http://4sq.com/9oazrC
• 12:10 ついにホワイトボードから名前が無くなっていた。
• 15:51 昨晩から 3G 不調。Xperia 再起動して対応。タイムラインみていると回線側の問題っぽいな。mopera U?
• 17:05 あ、ガラス清掃明日だった。17日と18日間違えるのこれで2回目。なんでだろー。
• 18:07 缶コーヒー 100円。
• 18:13 第5回TEP代表主催ランチ TXアントレプレナーパートナーズ http://bit.ly/9zP8B6
• 19:11 やばい。また分類したい病。
• 20:01 勘違い。まだあった。 RT @Naney: ついにホワイトボードから名前が無くなっていた。
• 20:26 ルイーダの酒場跡地また人が増えてきている。あれドラゴンクエスト?
• 21:24 IKEA FAMILY LIVE 届いた。
• 21:41 freeml のフォト共有についていちおうチェックしてみている。
• 21:57 「一度にアップできる画像容量は、合計で100メガバイトまで。画像1枚の容量は10メガバイトまで」と。合計容量がわからん。
• 24:04 青色ダイエットめがね「掛けるだけでお腹が減らない！さらにリラックスもできる」。そういえばデイリーポータルZで食用色素青をいろいろいれてたな。 http://bit.ly/axda2u

2010年05月18日

• 07:39 本日有給休暇。
• 14:03 デニーズカード払い戻しにきた。電話問い合わせするから待てとのこと。 (@ デニーズ東大井店) http://4sq.com/dyL18X
• 14:04 @as_tone 自分の席のところも拭いてくれた?
• 14:07 508円戻ってきた。
• 15:13 イマココココス。
• 15:43 ココス貸切状態になった。
• 16:45 賽銭 10円。 (@ 梶原稲荷神社) http://4sq.com/8WWVfg

mixi Engineers' Seminar #3

データマイニングがテーマ。

高村大也氏(東京工業大学)	「機械学習の基礎と評判分析」
神嶌敏弘氏(産業技術総合研究所)	「推薦システムのアルゴリズム」
石川有氏(株式会社ミクシィ)	「Big Data Analysis at mixi」

今日のさえずり: 「労務からのお・ね・が・い☆」とかにすればいいのに

2012年02月02日

• 06:41 Timely 登録してみた。00:10 に enqueue したこの Tweet はいつ投稿されるかな?
• 07:01 Buffer も久しぶりに使ってみよう。 http://t.co/jWfyMGs1
• 09:19 @mushikabu レシピ通りの分量でやったら成形できないぐらいドロドロ生地だったらしいです。
• 09:31 今日は生足キツいわ。
• 10:40 「ツイてる」って即効性があるのでヤバい。今日もツイてる。
• 11:20 RT @shima__shima: 本日 mixi さんのセミナー http://t.co/7pVafJxX で2番目にお話をさせていただく神嶌です．拡張版資料を http://t.co/oKlg55Jj の「推薦システムに関する講演・講義資料」にて配布しています． #mixi_engineers
• 11:20 RT @shima__shima: 前半は推薦システムのアルゴリズムについて，メモリベース型手法，行列分解，確率モデルと，どういった拡張があるかということについて概念的な話させていただきます．アルゴリズムの詳細までは時間的に無理なので，そのあたりは資料をご覧下さい． #mixi_engineers
• 11:20 RT @shima__shima: 後半は，推薦システムの研究トピックについて，一般のニュースサイトなどではみかけないようなものをいくつか紹介させていただきます：サクラ攻撃，ソーシャル推薦，バンドワゴン効果・人気バイアス，Webコンテンツ最適化，フィルターバブル など #mixi_engineers
• 11:54 今日の mixi Engineers’ Seminar #3 は「データマイニング」! Ustream 配信予定あり。 http://t.co/Ced5hghA #mixi_engineers
• 12:32 「労務からのおねがい」っていう張り紙、「労務からのお・ね・が・い☆」とかにすればいいのに。
• 13:13 はてなOne招待ありがとうございました!
• 13:23 mixiの友人で招待されたはてなOneアカウントって、ふつうのはてなアカウントと別になっちゃうの?
• 13:33 @yuzuemon え、気がつきませんでした……。
• 13:36 @yuzuemon mixi の方にいったん認証がきて、それで「id:数字列@mixi」が割り当てられて新規作成されたっぽかったです。
• 14:07 削除できないはてなOneアカウントが1つできてしまった……。
• 16:56 はてなOne、mixi 経由で新規作成されたIDで投稿したコメントが、別のはてなIDで書き込んだように見えてる。なんか ID 間の関連付けがおかしいな。
• 18:11 イヤー! RT @yuji0602: 【速報】花粉症の症状が出ました＞＜
• 18:54 データマイニングがテーマの mixi Engineers' Seminar #3 そろそろ。 Ustream もぼちぼちかな? http://t.co/M6YnzVWF #mixi_engineers
• 19:02 mixi Engineers' Seminar #3 #mixi_engineers @ 株式会社ミクシィ(mixi, Inc.)にタッチ！ http://t.co/VzhgdwYQ
• 19:07 mixi Engineers' Seminar #3 始まってます。席埋まって盛況です! #mixi_engineers http://t.co/M6YnzVWF

C MAGAZINE 電子書籍で復刻と、ビギナーの出発点としてのコンピュータ雑誌

C MAGAZINE と言えば1989年から2006年まで出版されていたプログラミング雑誌。その C MAGAZINE が電子書籍で復刻というトピックがSBクリエイティブがで出ていた。

• http://www.sbcr.jp/topics/11895/

高校生の時に読み始めて、付録として収録されていた LSI C-86 試食版で C の世界に足を踏み入れた(それまでは BASIC 中心だった)。初めて Perl というものを知ったのも C MAGAZINE (記事)。

C MAGAZINE はオブジェクト指向などのパラダイムやいろいろなアルゴリズムなどのプログラミングについてのいろいろな事を知るきっかけとなっていた雑誌だった。当時はまだ World Wide Web にも触れておらず、プログラミングついての情報は雑誌・書籍が中心だった。

その後 UNIX Magazine や Software Design なんかで UNIX 系に触れていくことになったり。

コンピュータ雑誌を定期購読しなくなってから久しく、情報は Web から得られる時代にはなったけれど、やはり雑誌を通していろいろなきっかけを得るというのはまだまだ悪くないと思うんだよね。

ソフトウェアエンジニアビギナーのための推薦図書とかの話とか定期的にでるけれど、そういう層は特にコンピュータ雑誌を定期的に読むといいと思うんだよね。そこでいろいろなことに触れて面白そうなことを見つけて出発点とすれば良いと思う。

• C MAGAZINE 1989年10月号 Kindle 版

PC でのワンタイムパスワードのシークレットキー管理に KeePassXC を使う

TOTP アルゴリズムを使っている2段階認証のシークレットキーの管理・ワンタイムパスワード生成はスマートフォンアプリの Google Authenticator とIIJ SmartKey を両用している。メインのスマートフォンが使えなくなった時のために、使っていない古いスマートフォン残しておいてそこにもシークレットキーを登録しているのだけれどこれ面倒。バックアップは PC (Mac)で管理したい。

そう思って調べたところ、普段パスワード管理に使っている KeePassX のフォーク版 KeePassXC が TOTP 生成機能をもっているということを知った。

KeePassX の開発保守が停滞していることもあり KeePassXC にこのタイミングで乗り換えつつ KeePassXC で 2段階認証のシークレットキーの管理をしてみることにした。

• https://keepassxc.org/

クロスプラットフォームで公式サイトでは Linux 用・macOS 用・Windows 用のパッケージが配布されている。

シークレットキーの登録

IIJ SmartKey に登録しているキーについてそれぞれ QRコード生成をし別のカメラで読み取り、その中の secret の値を KeePassXC のエントリに登録していく。エントリを作成し(あるいは既存のエントリを選択し) TOTP の設定でキーを入力し保存すれば OK。

ワンタイムパスワードの生成

もちろんワンタイムパスワードの生成にも対応している。これがあればスマートフォンが手元に無くても要 TOTP 認証のネットサービスにログインできる。便利。

パスワードデータベースファイルの管理

KeePass パスワードデータベースファイル (kdbx) に保存されるので、あとは好きな方法でバックアップ。

[ Mac アプリケーション ]

今日のさえずり: 買い物から帰ってきてからのアクエリアスうまーい

• 11:55 買い物から帰ってきてからのアクエリアスうまーい。
• 12:10 Rainbow Bridge #photography RICOH GR III #GR #GRIII #GR3 https://t.co/KThvwfRJ6U
• 16:45 Omnisearch for Obsidian を入れてみた。BM25 ベースのアルゴリズムでスコアリングする全文検索プラグイン。インメモリなので速いのが良い。
• 16:45 日本語検索した時の recall は低め。自分が書いたノートを検索した時はファイル名の Z to A 順で検索結果を見ていくことが多い。自分の使い方には合ってなさそう。
• 17:26 Android デバイスを Chromecast with Google TV の仮想リモコンとして使う方法を覚えた。テキスト入力する時に使おう。
• 17:37 Chromecast with Google TV で Google アカウント PIN が使えるようになっていた。これなら複数アカウントを追加しておけるね。
• 20:35 明日が8月の最終日曜日なので、そろそろ月録の下書きを始めとこ。
• 24:42 2022年8月27日(土) したこと - 食材を買い出しする - AR カメラ SNOW の最近を知る - Omnisearch for Obsidian を試す - Chromecast with Google TV の仮想リモコンを試す - 弁当を買ってくる - 『響け!ユーフォニアム』第四回を視聴する

Rainbow Bridge#photography
RICOH GR III #GR #GRIII #GR3 pic.twitter.com/KThvwfRJ6U

— Naney (@Naney) August 27, 2022