タグ

algorithmに関するkoda3のブックマーク (15)

  • javascript-algorithms/README.ja-JP.md at master · trekhleb/javascript-algorithms

    数学 B ビット操作 - set/get/update/clear bits, 2つの乗算/除算, 否定的にする. 等 B 因果関係 B フィボナッチ数 - クラシックとクローズドフォームのバージョン B 素数性テスト (trial division 方法) B ユークリッドアルゴリズム - 最大公約数を計算する (GCD) B 最小公倍数 (LCM) B エラトステネスのふるい - 与えられた限度まですべての素数を見つける B Is Power of Two - 数値が2の累乗であるかどうかを調べる(単純なアルゴリズムとビットごとのアルゴリズム) B パスカルの三角形 B 複素数 - 複素数とその基演算 B ラジアン&度 - 度数と逆方向の変換に対するラジアン B 高速電力供給 A 整数パーティション A Liu Hui π アルゴリズム - N-gonsに基づく近似π計算 A 離散フ

    javascript-algorithms/README.ja-JP.md at master · trekhleb/javascript-algorithms
  • プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD

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

    プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD
  • Yahoo!の異常検知フレームワーク"EGADS"

    Yahoo!がOSSとして開発している異常検知フレームワーク "EGADS" (Extensible Generic Anomaly Detection System) について書いた次の論文を読んだ: Generic and Scalable Framework for Automated Time-series Anomaly Detection (KDD 2015) リアルタイムなデータをモデリングする種のアルゴリズムの実装とはどうあるべきなのか、という話は難しい。 僕も異常検知や情報推薦のためのアルゴリズムをパッケージ化してみてはいるものの、 時系列データの入力、モデリング、予測、出力といったコンポーネントをいかに切り分けて実装するか バッチとオンラインアルゴリズムのバランスをいかに取るか どこまで自動化して、どこにヒューリスティクスを取り入れる余地を残すか といった点は当に悩ま

    Yahoo!の異常検知フレームワーク"EGADS"
  • 高次元ベクトルデータ検索技術「NGT」の性能と使い方の紹介

    この結果を見て単語ベクトルが変わるとNGTの性能が変わってしまうように感じた方がいるかもしれません。しかし、実はこれらの単語ベクトルはデータの次元数や件数が違っているため、それぞれの条件をあわせてみる必要があります。興味がある方は論文を読んで見比べて欲しいと思いますが、ここで重要なことは、NGTが高い精度にも関わらず、せいぜい100ミリ秒程度で検索できるという規模感であるということです。その規模感を感じてもらうために、これらの実験結果をご紹介しました。この実験以外にも論文の中では単語ベクトルの応用としてアナロジーと呼ばれる合成ベクトルでの実験やその他の比較手法の比較、実験結果の考察などもありますが今回は割愛します。 これまで紹介した内容と同じような実験はLinux系のサーバーであれば公開しているExperimental softwareという実験プログラムを使うと簡単に試すことができます。

    高次元ベクトルデータ検索技術「NGT」の性能と使い方の紹介
  • 巡回セールスマン問題における最短経路をpgRoutingで探索する

    先日、PostgreSQLアンカンファレンスを開催した際、「pgRoutingを使って巡回セールスマン問題を解く」という発表を国府田さんがされていました。 第8回 PostgreSQLアンカンファレンス@東京(2016/9/10) - connpass http://pgunconf.connpass.com/event/37285/ 第8回 PostgreSQLアンカンファレンス ツイートまとめ - Togetterまとめ http://togetter.com/li/1023030 非常に面白そうな機能で、私も少し使ってみましたので、今回はその使い方や使用例などを含めてご紹介します。 ■「巡回セールスマン問題」とは何か 「巡回セールスマン問題」というのは、以下のようなものです。 巡回セールスマン問題(じゅんかいセールスマンもんだい、英: traveling salesman probl

    巡回セールスマン問題における最短経路をpgRoutingで探索する
  • 動的配列について – JavaのLinkedListとArrayListを分析・比較する | POSTD

    私はSkienaの『Algorithm Design Manual』 (訳注:『アルゴリズム設計マニュアル』 上巻 ・ 下巻 ) を読んでいました。ところでこのは素晴らしいで、連結リストと配列についてこんな比較をしていました(chapter 3.1.3)。 連結リストが静的配列に勝る相対的な長所には以下のものがあります。: • メモリが当にいっぱいにならない限り、連結構造にオーバーフローが生じない。 • 連続的な(配列)リストに比べて、挿入と削除が単純である。 • 大きなレコードを扱う場合、要素自体を動かすよりもポインタを動かすほうが容易かつ高速である。 一方で、配列の相対的な長所には以下のものがあります。 • 連結構造には、ポインタのフィールドを格納するための余計な領域が必要となる。 • 連結リストでは、要素に対する効率的なランダムアクセスができない。 • 配列は、ランダムなポイン

    動的配列について – JavaのLinkedListとArrayListを分析・比較する | POSTD
  • JavaScript開発に役立つ重要なランダムの数式まとめ - ICS MEDIA

    プログラムで使うことの多い「乱数」。ゲーム開発やビジュアルアート、ウェブサイトのアニメーションにおいて乱数は非常に重要で、さまざまな用途で利用されています。プログラムで一般に乱数と聞くと、すべての数値が同じ頻度(分布)で出現する「一様乱数」と呼ばれる乱数をイメージする方が多いと思います。 多くの場合はこの「一様乱数」で取得した乱数を用いれば十分でしょう。しかし、場合によっては「一様乱数」ではなく、偏りのある乱数を用いることでコンテンツの見た目や現象の「自然さ」を演出することが可能です。 実は「一様乱数」に一手間加えることで、乱数の分布の偏りを制御できます。今回は乱数を使用して好みの分布を得るためのパターンをいくつか紹介します。 乱数分布のシミュレーションデモ (HTML5製) 次のデモはリアルタイムで乱数の出現頻度を計算し、グラフに可視化するコンテンツです。画面下のプルダウンで乱数の種類を

    JavaScript開発に役立つ重要なランダムの数式まとめ - ICS MEDIA
  • MIT、マルコフ連鎖モンテカルロ法を高速化するアルゴリズムを発表

    印刷する メールで送る テキスト HTML 電子書籍 PDF ダウンロード テキスト 電子書籍 PDF クリップした記事をMyページから読むことができます マサチューセッツ工科大学(MIT)の研究者らは、マルコフ連鎖モンテカルロ法(MCMC)を現在よりも最大で200倍高速化できるアルゴリズムを開発したと発表した。 MITのこのアルゴリズムは、ほとんどすべての計算モデルに適用できる。このアルゴリズムの目的は、問題中に存在する未知のパラメータの値を局所近似から推定することで、対象となる解を絞り込むというものだ。 発表のなかで、MITはこのアルゴリズムについて以下のように述べている。 このアルゴリズムは、モデルを複数回実行するなかで、いくつかの適切なデータ点を組み合わせていくことにより解、すなわち未知のパラメータそれぞれの確率分布をインクリメンタルなかたちで絞り込んでいくものだ。そういった点で、

    MIT、マルコフ連鎖モンテカルロ法を高速化するアルゴリズムを発表
  • 初心者でもアルゴリズムの学習ができる入門本とサイト一覧 -

    Photo by VFS Digital Design 皆さんはアルゴリズムやデータ構造について知っているでしょうか。情報系の学部出身の人は学校の授業でやったかもしれません。一方で学校で情報系の勉強をせずにITエンジニアになったという方は、アルゴリズムやデータ構造について一度は「勉強したほうが良いんだろうな」と思いつつも、実際の業務であんまり必要なさそうだし、難しそうだし、DevOpsやオブジェクト指向やフレームワークについて学ぶので手一杯で未着手、という人も多いのではないでしょうか。 今回はそんな方に向けて、アルゴリズム、データ構造を学ぶ意義と、それらを学ぶときに役立つとサイトについてまとめました。 ■アルゴリズム、データ構造を学ぶ意味 アルゴリズムやデータ構造について語られるときに、非常に良く言われる事として「そんなものは実務に役立たたないので必要ない」という意見があります。当にア

    初心者でもアルゴリズムの学習ができる入門本とサイト一覧 -
  • グーグルのバグ予測アルゴリズムを実装したツール「bugspots」について - Qiita

    3.結果を見てみる このHotspotsの下に出力されている左の数値がバグが起こりやすい度合いを表すスコア、右が対象のファイルになる。 メチャクチャ簡単に導入できるので、 リファクタやコードレビューなどで目星をつけるという意味では有用なツールな気がしました。 背景の説明 googleでは、チェックイン前にユニットテストやコードレビューが行われているが、コードが大量になってくると、ユニットテストやコードレビューをすり抜けたバグも少なからず発生してします。 googleではこの問題に対処するために、独自の「バグ予測アルゴリズム」を採用して、コードの品質向上を図っているらしいので、そのアルゴリズムについて調べてみました。 ソフトウェアなどのバグ発見手法には、「ソフトウェアメトリクス」というものがあります。 ソフトウェアメトリクスの特徴 ソースコードを静的に分析 モジュールや関数の行数、ネストの深

    グーグルのバグ予測アルゴリズムを実装したツール「bugspots」について - Qiita
  • #JJUG - Java で最速のハッシュアルゴリズムを求めて

    【東京】【聴講者募集】JJUG ナイト・セミナー 「ビール片手にLT&納涼会」の発表資料です。 https://jjug.doorkeeper.jp/events/28182

    #JJUG - Java で最速のハッシュアルゴリズムを求めて
  • ハクビシンにもわかる全文検索 - Qiita

    高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha

    ハクビシンにもわかる全文検索 - Qiita
  • sorting algorithms in javascript

    Sorting Algorithms in Javascript This is just for quick reference does not really talk about CS theory for now. Bubble Sort: let compare = (n1, n2) => n1 - n2; let bubbleSort = (arr, cmp = compare) => { for (let i = 0; i < arr.length; i++) { for (let j = i; j > 0; j--) { if (cmp(arr[j], arr[j - 1]) < 0) { [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; } } } return arr; }; Insertion Sort: let inserti

  • Sign in - Google Accounts

    Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode

  • 【累積和、しゃくとり法】初級者でも解るアルゴリズム図解 -

    2014年12月3日より2015年1月7日まで開催した、paizaオンラインハッカソンVol.4Lite「エンジニアでも恋したい」は、トータルで3問有りましたが全て解けましたでしょうか? 各問題の成否によりストーリーが変わるのであえて間違えて解いた方もいらっしゃると思いますがw (プレゼント対象期間は終了しましたが、問題チャレンジは可能なので、未チャレンジの方は是非チャレンジください!) 問題1、問題2は解説するほどのむずかしさでもないので省きますが、問題3は多少工夫が必要なので、問題3について今回もPOH恒例の「図解解説」をしてみたいと思います。既に解けた方もそうでない方も、今回の解説を読んで、それぞれの方法すべてを実装してみると勉強になると思いますので、是非試してみてください。 ■どのような高速化ステップがあるのか? 今回の問題ですが、解法の大きなパターンとしては、1.全てのパターンを

    【累積和、しゃくとり法】初級者でも解るアルゴリズム図解 -
  • 1