「プログラミングの常識」を時々見直す必要性について｜Rui Ueyama
自分の中のプログラミングの常識というものは、ときどき現実のハードウェアに合わせて調節しないといけない。ハードウェアが進歩し続けているので、コンピュータで簡単にできることと相対的に難しいことのバランスが変化し続けているからだ。ここでは特にストレージにフォーカスして書こうと思う。 昔はメモリが相対的にとても貴重な資源だったので多くのプログラマがメモリを節約することに血道を上げていた。例えばWindowsの初期の頃に設計されたデータ構造には、メモリをバイト単位ででもいいから節約したいという意図の痕跡がいまでも多く見受けられる。DRAMの次に速い記憶装置はHDDだったので、メモリが足りなくなればHDDにデータを保存せざるを得ないのだが、DRAMとHDDのランダムアクセスの速度差は、机の上の本の開いているページを見るのと、その本をAmazonで注文して到着するのを待つのと同じくらいのスケールで違うの
遅延評価を活用して線形時間でGoogle Code Jam 2014 Round 1AのB問題を解く - tosの日記
公式の解説で，「遅延評価を使ってもできる」と書いてくれなかったので。 注意：この記事は，Google Code Jam 2014 Round 1AのB問題 Full Binary Tree についてのネタバレを含みます。 この問題は木DPをする典型的な問題であり，公式の解説にもあるように， 木を根付き木にした後， 頂点でのスコアを，子のスコアのうち大きい方から2つを用いて計算する ことで解けます。何を根として選ぶかをすべて試すとO(N2)解法となり，すべての根の可能性について同時にDPをする*1とO(N)解法になります。だから，根の選び方によって隣接頂点のうち「親以外が子となる」ので，隣接頂点のスコアのうち大きい方から3つを保存するような構造を持つ――待ってください。 もちろん，降順ソートされたスコアのすべてを計算すると，O(N2)時間かかってしまいます。しかし，先頭3つを結果的に計算でき
【コンピュータサイエンス名言紹介 vol.1】：Linus... | DERiVE コンピュータビジョン ブログ
このサイトについて DERiVEはコンピュータビジョン、画像認識が専門のMasaki Hayashiがお送りしている、コンピュータビジョン(Computer Vision)を中心としたITエンジニア、研究向けのブログです。※「DERiVE メルマガ別館」は2015/9月で廃刊致しました、 ４月からのブログ、メルマガのリニューアルによる対象内容拡大の１つとして、「コンピュータサイエンスの名言紹介」というシリーズを始めます。 コンピュータサイエンス、IT技術というものは、まだまだ歴史が浅い、20世紀以降の技術分野です。私も含めてみなさんは「歴史」や「先人の考え」について意外と無知であったりします。しかし、我々が単独で成し遂げた技術など、絶対にありえることがなく、どれだけ新規性が高いアイデアでも、先人が積み立ててくれてきた研究開発の上に成り立っているものだと思います。別にコンピュータサイエンスに
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
