【実践】エンジニアの基礎教養-アルゴリズムを学べる本筆者は新卒エンジニア時代に社内でアルゴリズム勉強会を主催していました。 その内容を本形式に書き起こしたものになります。 【この本の特徴】 📗問題演習形式でアルゴリズムの基礎が身に付く構成となっています。 📗分かりにくい概念は丁寧に図解で解説しています。 📗基礎的なアルゴリズムがどのように世の中に役立っているのかを言及しています。 アルゴリズムに関して、皆さんの理解を深めるお手伝いができれば幸いです。
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
DeepMind、AIで人間考案のものより優秀なソートアルゴリズムを発見 最大70％高速化
米Google傘下のAI企業Google DeepMindは6月7日（現地時間）、アルゴリズムを開発するAI「AlphaDev」が、人間が考えたものより高速なソートアルゴリズムを発見したと発表した。 ソートアルゴリズムは、入力されたデータを一定のルールに基づいて並べ替えるもの。ネット検索結果の並べ替えやランキング制作などIT技術の根幹を担う技術の一つ。今回AlphaDevが考案したアルゴリズムは既存のものに比べて、少量のデータなら最大70％、数十万規模の大量のデータなら約1.7％速く処理できた。 DeepMindはAlphaDevに新しいアルゴリズムを発見させるため、ソートの作業を「組み立てゲーム」としてプレイさせた。「正確にソートできる」「既存のアルゴリズムより高速である」という2点を満たせばクリアとした。 関連記事 OpenAIやDeepMindのCEOやトップ研究者ら、「AIによる人
AES-256 GCMに渡すkeyに、パスワードそのものではなく、鍵導出関数（PBKDF2など）で生成したハッシュ値を指定する理由は？
以前書いた、「あるデータをパスフレーズで暗号化し、公開ストレージ（URLが判明すれば誰でも読み取り可能）に暗号化ファイルの形式で保存し（期間は無期限）、あとからパスフレーズで復号して読み取るためのコード」を改修するため、「AES-256 GCM、または、ChaCha20-Poly1305を用いて、データを1つのパスフレーズを用いて暗号化するライブラリ」をTypeScriptで書こうと考えています。 この場合の要件は： 暗号化したデータは、第三者が自由に読み取り可能であり、その場合でも安全性を保つ必要がある 暗号化したデータは、無期限で利用される場合がある。したがって、短期間のみ用いるものではない 暗号化したデータには、パスフレーズを除く、復号に必要な情報がすべて含まれる。暗号化と複合に必要な秘密情報はパスフレーズのみ になります。例えるなら、Gitリポジトリ内で特定のファイルを暗号化するよ
メルセンヌツイスタはそんなに衝突しない - Qiita
κeenです。こちらのスライドが話題になっているようです。 10秒で衝突するUUIDの作り方 - Speaker Deck 笑い話としても乱数の難しさの側面としても面白いのですが、これを見た人たちの反応がちょっと勘違いしてそうだったので補足します。 別に私は暗号とか乱数とかの専門家ではないです。 発表者の方のコードは読みましたか？ 少し速度が必要になるのでRustに移植します。 [package] name = "genuuidv4" version = "0.1.0" edition = "2018" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] rand = "0.7.2" sfmt = "0.6.0" use
ハッシュ値の使い方について - クックパッド開発者ブログ
モバイル基盤グループのヴァンサン(@vincentisambart)です。 先日以下のツイートを拝見しました。 Swift's stdlib moves to randomly seeded hashing: https://t.co/2T5oRYtD8B— ericasadun (@ericasadun) 2018年3月10日 この変更はSwift 4.1にはまだ入りませんが、4.2か5.0に入るはずです。コードレビューでこの変更が問題を起こそうなコードを指摘したことあるので、ハッシュ値のおさらいをする良いタイミングではないでしょうか。 Swiftのことを考えて書いていますが、多くのプログラミング言語にも当てはまります。ハッシュ値はSwiftではhashValueというプロパティが返しますが、多くの言語では単にhashというメソッド・関数が返します。 ハッシュマップ ハッシュ値はハッシュ
観察日記 2018-02-14 - なるせにっき
配列の全ての要素が等しいか否か mrkn 配列の全ての要素が等しいことはどう確認したら良いんだろう。 `ary.all? {|e| e == ary[0] }` これかな usa ary.uniq.size == 1 mrkn なるほど > uniq usa all?でブロック引数より速そうな予感 いやでもaryがでかくてかつ全然要素が等しくなかったらそうでもないか。 mrkn `ary.all? {|e| e.foo == ary[0].foo }` の場合はどうでしょう。map.uniq.size がいいかな usa all?は全て等しい時に遅いが、序盤で違うとわかったら速い mrkn 確かに > 序盤で違うとわかったら速い usa この辺は予想される集合の傾向で判断するしかないですかねえ。 map.uniq.sizeはmapの結果としての一時配列を作らないようにするには、えーと En
画像処理の数式を見て石になった時のための、金の針 - Qiita
画像処理は難しい。 Instagramのキレイなフィルタ、GoogleのPhoto Sphere、そうしたサービスを見て画像は面白そうだ！と心躍らせて開いた画像処理の本。そこに山と羅列される数式を前に石化せざるを得なかった俺たちが、耳にささやかれる「難しいことはOpenCVがやってくれるわ。そうでしょ？」という声に身をゆだねる以外に何ができただろう。 本稿は石化せざるを得なかったあの頃を克服し、OpenCVを使いながらも基礎的な理論を理解したいと願う方へ、その道筋(アイテム的には金の針)を示すものになればと思います。 扱う範囲としては、あらゆる処理の基礎となる「画像の特徴点検出」を対象とします(実践 コンピュータビジョンの2章に相当)。なお、本記事自体、初心者である私が理解しながら書いているため、上級画像処理冒険者の方は誤りなどあれば指摘していただければ幸いです。 画像の特徴点とは 人間が
Knuth multiplicative hash が最小完全ハッシュ関数であることの証明 | メルカリエンジニアリング
こんにちは！サーチチームの @metal_unk です。普段はサーバーサイドエンジニアとして、メルカリの検索を改善する仕事をしています。 メルカリには Be Professional Day という「普段できないことをやろう」をテーマとする日があり、その日は業務に直接関係のないことや、普段は手をつけられないリファクタリングなどがされます。Be Professional Day の様子はこちらで紹介されています。 tech.mercari.com わたしは今回の Be Professional Day で、Knuth multiplicative hash が最小完全ハッシュであることを証明しました。このブログはその証明についての記事です。 「普段できないことをやろう」という Be Professional Day では、証明もアリです。 Knuth multiplicative hash
Amazonの推薦システムの20年
IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も
rubyでdfsでメモ化再帰 - 会者定離で(ダイアリーから)以降
いや、早くなるのは分かってたけどめちゃくちゃ早かった*1のでｗ− P.S. チーター本の７章「動的計画法、メモ化」のサンプルのrubyでのベンチ結果です。 dfs $ ruby -v ruby 2.1.5p273 (2014-11-13) [arm-linux-gnueabihf] $ time ruby hello_dfs.rb 119759850 real 13m50.176s user 13m50.080s sys 0m0.050s hello_dfs.rb $h = 13 $w = 17 def dfs(nowh, noww) return 0 if nowh > $h || noww > $w return 1 if nowh == $h && noww == $w dfs(nowh+1, noww) + dfs(nowh, noww+1) end puts dfs(0, 0)
私たちはいかにして環状線で”悪さをする列車”を捕まえたか | プログラミング | POSTD
文：Daniel Sim 分析：Lee Shangqian、Daniel Sim、Clarence Ng ここ数ヶ月、シンガポールのMRT環状線では列車が何度も止まるものの、その原因が分からないため、通勤客の大きな混乱や心配の種となっていました。 私も多くの同僚と同じように環状線を使ってワンノースのオフィスに通っています。そのため、11月5日に列車が止まる原因を調査する依頼がチームに来た時は、ためらうことなく業務に携わることを志願しました。 鉄道運営会社SMRTと陸上交通庁（LTA）による事前調査から、いくつかの電車の信号を消失させる信号の干渉があり、それがインシデントを引き起こすことが既に分かっていました。信号が消失すると列車の安全機能である緊急ブレーキが作動するため、不規則に電車が止まる原因となります。 しかし8月に初めて発生した今回のインシデントは、不規則に起こっているように見えるた
珍しいSHA1ハッシュを追い求めて - プログラムモグモグ
「SHA1ハッシュってあるだろう？」 放課後、いつものように情報処理室に行くと、高山先輩が嬉しそうな顔でそう言った。 「ええ、SHA1、ありますね」 「SHA1って何桁か覚えているかい？」 「えっと…」 一年下の後輩、岡村が口を開いた。 「50桁くらいはありましたっけ…？」 先輩はパソコンに向かって何かを打ちはじめた。 現在、情報部の部員は三人しかいない。部長の高山先輩と、二年の自分と、後輩の岡村だ。いや、正確に言うと、先輩の学年にはもう少しいたのだが、もうほとんど部室に来ることはなくなってしまった。無理もない、この季節になると先輩たちは受験勉強で忙しくなる。 「例えば、こういうふうに… 適当なSHA1の長さを…」 echo -n | openssl sha1 | awk '{print length}' 部長だけは今も部活に来てこうやって色々なことを教えてくれている。本人曰く、普通に勉強
PHP の壊れた mt_rand の品質を統計的に検証した - iwiwiの日記
メルセンヌ・ツイスターと似て非なるアルゴリズムが実装されていたことが発覚して話題の PHP の mt_rand 関数の品質を統計的に検証しました．果たして，PHP の「壊れた」mt_rand は安心して使うことができるのでしょうか……？ ちなみに，結論から言うと，PHP の壊れた mt_rand は，（少なくともこのテストの範囲では）本家メルセンヌ・ツイスターと遜色ない品質を持っているようです．ただし，最後に PHP の乱数の別の懸念点についても紹介します． 壊れた mt_rand とは PHP の mt_rand は，ドキュメントによると，有名な乱数生成アルゴリズム「メルセンヌ・ツイスター」を利用して高品質の乱数を生成する関数です．ところが，どうやら一部では知られていたこととして，PHP の mt_rand の実装にはバグがあり，本家メルセンヌ・ツイスターと挙動が一致していませんでした．
JavaのTimSortがバグってる件について | さにあらず
Python で実装され、その後 Java にも移植されたソートアルゴリズムである TimSort が盛大にバグっていることが発見されました。 このバグがどのようにして発生するのかについては、以下のドキュメントを精査して下さい。 TimSort fails with ArrayIndexOutOfBoundsException on worst case long arraysOpenJDK’s java.utils.Collection.sort() is broken: The good, the bad and the worst caseどんなことが起こるのか#通常の利用では想定しえない場所でArrayIndexOutOfBoundsExceptionが発生します。 例えば、以下のようなスタックトレースになります。 Exception in thread "main" java.l
[KMP77] を読んでみた - d.y.d.
17:53 14/12/22 ソートの逆流れ クイックソートってあるじゃないですか、クイックソート。 配列、たとえば [4,2,1,7,0,6,5,3] があったときに、 小さい方を左に、大きい方を右にまず適当に集める。 この「小さい方」と「大きい方」への二分割を、いわゆる再帰的に、 分かれたブロック両方で同じ事を繰り返していくと… なんと、小さい順に並んだ配列 [0,1,2,3,4,5,6,7] が出来上がるというアルゴリズムです。 逆向き！ このデータの流れを「逆向きに」見てみたい。つまり、ソートが終わった最終状態から話が始まります。 しかも、さっきから説明なしで意味ありげにくっついていた、 「入力配列で元々どの位置にあったか」を表す値に注目していきます。 0の上に[4]がくっついているのは、最初は値0は配列のインデックス[4]の位置にあった、 ということを意味しています。（上のソート
![[KMP77] を読んでみた - d.y.d.](https://cdn-ak-scissors.b.st-hatena.com/image/square/e6fe840dfdcca31b69f48171e0de96a69b93595b/height=288;version=1;width=512/http%3A%2F%2Fwww.kmonos.net%2Fwlog%2Fsub%2Fdual%2F8.png)
書籍編集局ブログ｜Ohmsha
2月15日(木)に開催された「Developers Summit 2018(デブサミ)」（主催：翔泳社）にて「ITエンジニアに読んでほしい！ 技術書・ビジネス書大賞2018」のプレゼン大会と投票が行われ、大関真之先生の著書『機械学習入門 ボルツマン機械学習から深層学習まで』がみごと技術書部門の大賞の栄冠に輝きました！ プレゼン大会では大関先生自ら本書に関する熱い熱い思いを披露していただました。このプレゼンによって「読んでみたい！」「数式が苦手だけどこの本なら読める！」と惹きつけられるオーディエンスが続出！みごと大賞に選ばれることとなりました。ブラボー！ 本書は、おとぎ話の白雪姫に登場するお妃様と鏡の関係をなぞらえ、その問答により「機械学習とは何か」「何ができるのか」を楽しいストーリーと可愛らしくしかも的確なイラスト、そして数式をまったく用いることなく解説している画期的な内容です。 登場する
GNU grep 2.18リリース: 10倍速くなったと思ったら今度は200倍遅くなっていた | はむかず！
先日の記事 いまさらgrepが10倍高速化したのはなぜか が思わぬ閲覧数を稼いでしまい、トルコ語の知識を日本に広めるのに大きな貢献をしたような気がしますが、みなさんいかがお過ごしでしょうか。 実は先日の記事を書いた時にはすでに2.18がリリースされてたのだが、今回は2.17のときと違って日本の大手メディアが取り上げてなかったので、ついつい見落としていた。しかし実は2.18でも大きな変更が！！ リリースノート抜粋： grep -i in a multibyte, non-UTF8 locale could be up to 200 times slower than in 2.16. [bug introduced in grep-2.17] なんということでしょう。-iオプションでUTF8のときは2.17で10倍速くなっていたのだが、それ以外のマルチバイトロケールのときは200倍遅くなって
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
Adobeサイトから漏えいした暗号化パスワードはなぜ解読されたか
Adobe社のサイトの不正アクセス（参照、参照）によって、少なくとも3800万人のIDと暗号化されたパスワードが漏えいしたと言われています。既に報告したように、私のアカウントも漏えいしていました。 その後、『Adobeの情報流出で判明した安易なパスワードの実態、190万人が「123456」使用』というニュースが流れてきました。安易なパスワードが使われている統計は今までもあり、「パスワードの実態」に関しては「そんなものだろうな」と思いましたが、問題は、どうやって「暗号化パスワード」を解読したかです。 別の報道では、Adobeサイトがパスワードの暗号化に用いていたアルゴリズムはトリプルDESだったということです。トリプルDESは電子政府推奨暗号リストの今年の改訂でもしぶとく生き残り広く使われている暗号化アルゴリズムです。そんなに簡単に解読されたのでは問題ですが、実際には、「トリプルDESが解読
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
