タグ

関連タグで絞り込む (12)

タグの絞り込みを解除

algorithmとprogrammingに関するt2y-1979のブックマーク (13)

  • Human sorting

  • 浮動小数点数の表現と誤差 - Floating Point Number

    はじめに デジタル計算機におけるデータは、全て有限の bit によって表現されています。 ですから、 ある値を表現するために仮に N bit 使っているとするならば、 その値とは高々 2 N の状態しか取りえないわけです。 しかし、 数学における実数とは無限の値を取りうるものであり、 どんなに狭い区間だけを対象とすることにしても、 その区間内に無限個の値が存在するような代物です。 では、 そんな実数を、 高々数十とか百数十のビット数でどのように表現するのでしょうか。 そのことで、 どんな事態が起るのでしょうか。 浮動小数点形式 デジタル計算機を使って数値を表現する場合、 まず、 私たちは数値を『整数』と『実数』とに区別します。 デジタル計算機で用いる整数とは、 零を中心にプラス側とマイナス側にほぼ同じ拡がりを持つ変域を持ち、 その絶対値の最大値は整数表現に用いるビット数で決まります。 一方

  • 赤黒木の本質 - Qiita

    Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思い

    赤黒木の本質 - Qiita

  • ２つのことを同時に学ばない

    こんにちは、ある人のところてんです。プロシンという情報処理学会の<s>新年会</s>学会にかれこれ15年くらい参加しているわけですが、本稿はそこで水島さんと話をした「2つのことを同時に学ばない」という考え方についてのまとめになります。 初手レイトレーシング「２つのことを同時に学ばない」というのは私が発した言葉ですが、この言葉には私の友人の影響があります。 私の友人に「新しいプログラミング言語を覚える際には、とりあえずレイトレーシングを書いてみる」と言うやつがいます。 彼にとってはレイトレーシングのコードは、資料を何も調べずとも書けるそこそこに複雑なコードという位置づけのようです。 そのため、彼にとってはレイトレーシングを新しい言語で書くことで、言語仕様にのみ問題を絞って勉強することができるわけです。仮に実行結果がマズかったとしても、それは言語仕様の理解の問題であり、アルゴリズム自体に問題な

    ２つのことを同時に学ばない

  • プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD

    情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。

    プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD

  • Purely Functional Left-Leaning Red-Black Trees

    We show that the idea of left-leaning reduces one pattern matching in the insertion operation of Okasaki's purely functional red-black trees. We proved in Coq that the invariants of left-leaning red-black trees stand for our purely functional algorithm of the insertion operation. Our benchmark shows that our algorithm is slightly faster than Okasaki's algorithm in some cases. History In 1979, Guib

  • 「プログラミングの常識」を時々見直す必要性について｜Rui Ueyama

    自分の中のプログラミングの常識というものは、ときどき現実のハードウェアに合わせて調節しないといけない。ハードウェアが進歩し続けているので、コンピュータで簡単にできることと相対的に難しいことのバランスが変化し続けているからだ。ここでは特にストレージにフォーカスして書こうと思う。 昔はメモリが相対的にとても貴重な資源だったので多くのプログラマがメモリを節約することに血道を上げていた。例えばWindowsの初期の頃に設計されたデータ構造には、メモリをバイト単位ででもいいから節約したいという意図の痕跡がいまでも多く見受けられる。DRAMの次に速い記憶装置はHDDだったので、メモリが足りなくなればHDDにデータを保存せざるを得ないのだが、DRAMとHDDのランダムアクセスの速度差は、机の上の本の開いているページを見るのと、その本をAmazonで注文して到着するのを待つのと同じくらいのスケールで違うの

    「プログラミングの常識」を時々見直す必要性について｜Rui Ueyama

  • [初心者向け] プログラムの計算量を求める方法 - Qiita

    はじめに この記事では、プログラムの計算量を求める方法を説明します。プログラミングの初心者向けに、厳密さよりも分かりやすさを優先して説明していきます。 サンプルコードについて この記事のサンプルコードは、C言語（C99）で記述しています。 計算量とは？ 計算量とは、 「そのプログラムがどれくらい速いかを大雑把に表す指標」 です。 もう少し正確に言うと、 「入力サイズの増加に対して、実行時間がどれくらいの割合で増加するかを表す指標」 です。 グラフによる計算量の表現 計算量をグラフで表すと、以下のようになります。 これは、**「入力サイズ $n$ が増加するにつれて、実行時間が $n$ に比例して増加する」**ということを表しています。 別のグラフも見てみましょう。 これは、**「入力サイズ $n$ が増加するにつれて、実行時間が $n^2$ に比例して増加する」**ということを表しています

    [初心者向け] プログラムの計算量を求める方法 - Qiita

  • カルドセプトサーガの乱数問題 | 月と燃素と、ひと匙の砂糖

    「カルドセプトサーガ」というゲームで、サイコロが常に「偶数・奇数」のパターンを繰り返す、というバグがあって一時期祭りがありました。 痛いニュース(ﾉ∀`):【Xbox360】「カルドセプトサーガ」で、プログラマーがランダムなサイコロを作れなかったことが発覚 「カルドセプトサーガ」にダイス目が偶数と奇数を繰り返すバグ(slashdot)http://lovelove.rabi-en-rose.net/blog.php?n=256 カルドセプトサーガ不具合情報 以上を参考にしてもらえば大体分かると思います。 ■自称「正しいコード」も間違っていた ２ちゃんのスレでどうも自称「正しいコード」が張られたらしい。今チェックしてきたんですが、見つからない。もう遥か昔に消えたか・・・。 これに関するうさだBlogのls氏のコメントが興味深いです。 やがてそのような書き込みの中に、Cコードを示して「サイコロ

  • 書籍編集局ブログ｜Ohmsha

    2月15日(木)に開催された「Developers Summit 2018(デブサミ)」（主催：翔泳社）にて「ITエンジニアに読んでほしい！ 技術書・ビジネス書大賞2018」のプレゼン大会と投票が行われ、大関真之先生の著書『機械学習入門 ボルツマン機械学習から深層学習まで』がみごと技術書部門の大賞の栄冠に輝きました！ プレゼン大会では大関先生自ら本書に関する熱い熱い思いを披露していただました。このプレゼンによって「読んでみたい！」「数式が苦手だけどこの本なら読める！」と惹きつけられるオーディエンスが続出！みごと大賞に選ばれることとなりました。ブラボー！ 本書は、おとぎ話の白雪姫に登場するお妃様と鏡の関係をなぞらえ、その問答により「機械学習とは何か」「何ができるのか」を楽しいストーリーと可愛らしくしかも的確なイラスト、そして数式をまったく用いることなく解説している画期的な内容です。 登場する

    書籍編集局ブログ｜Ohmsha

  • Obfuscating "Hello world!" – Ben Kurtovic

  • How-To: OpenCV and Python K-Means Color Clustering

    Take a second to look at the Jurassic Park movie poster above. What are the dominant colors? (i.e. the colors that are represented most in the image) Well, we see that the background is largely black. There is some red around the T-Rex. And there is some yellow surrounding the actual logo. It’s pretty simple for the human mind to pick out these colors. But what if we wanted to create an algorithm

    How-To: OpenCV and Python K-Means Color Clustering

  • スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤

    魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、（「数」を求めるだけだとしても）GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します（Xeon Phiなら簡単なのでしょうか→追記参照）。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します（schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します）。変数iは上の図の緑の部分（カンで5個にしました）を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います（1つのマスに入る数を1バイトで表現

    スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤
  • 1

お知らせ

もっと読む

公式Twitter

  • @HatenaBookmark

    リリース、障害情報などのサービスのお知らせ

  • @hatebu

    最新の人気エントリーの配信

はてなブックマーク

公式Twitter

はてなのサービス

  • App Storeからダウンロード
  • Google Playで手に入れよう
Copyright © 2005-2025 Hatena. All Rights Reserved.