assoutの日記スマートフォン用の表示で見るassoutの日記この広告は、90日以上更新していないブログに表示しています。見るCleanCodeなど今までの技術書とは毛色が異なり、特定の言語に限らない、アルゴリズムとデータ構造について論じている。第1部から第3部の全15のコラムに分かれている。真珠貝を開いて重複のない単純なデータのソートを、ビット列というデータ構造を用いて実現する。入力ファイルには、重複のない7桁の正の整数が記録されている。入力された整数を昇順にソートした一覧を出力したい。メモリには1MB程度の余裕しかない。問題定義をきちんとする。アルゴリズム、データ構造を考える上で、問題の前提条件などきちんと整理する。ビット列というデータ構造ビット列は、「限られた範囲内にあり、密で、重複が無く、付随する情報もないようなデータのセット」を表すのに有効です。「ああ(そうか)!」アルゴリズムひらめきが大事。例題1最大40億個の32ビット整数がでたらめな順に入っているファイルから、このファイルに含まれていない整数を探し出す。例題2要素がn個の配列を左方向にi要素分回転させる。例題3英語の辞書が与えられたときに、すべてのアナグラムを見つける。解2分探索、(まとめるための)ソート、印付け(値を同値クラスに振り分ける)原則ソートソートの用途は、整列された出力を作るだけではない。2分探索ソートされたデータの探索方法として非常に有効。あらゆる場面で使われる。印(シグネチャ、署名)ある値を決まったルールでグループにわけ、印をつけておく。その印で、ソートするなどして効率的に処理できる。ここでは、アナグラムの検索を実現している。英語学習メモVimとVrapperとVichromeでキーマッピングを揃えたい月別アーカイブはてなブログをはじめよう!assoutさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。