[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

タグ

algorithmに関するpochi-mkのブックマーク (7)

  • 論文|snmalloc: A Message Passing Allocator (ISMM 2019)

    「snmalloc: A Message Passing Allocator」という論文を読んだのでその紹介です。論文は ISMM (International Symposium on Memory Management) 2019 に採択されており、論文とソースコードは GitHub (microsoft/snmalloc) で公開されています。リポジトリ名から分かる通り、著者の多くが Microsoft Research に所属しています。 免責 読み間違えている可能性があります。正確な情報が欲しい方は必ず論文を読んでください。誤りの指摘や補足、議論などは GitHub Issue や Twitter へお願いします。 更新履歴 2019/07/08 bump pointer と free list の next entry pointer を判定する方法について追記 2019/0

    論文|snmalloc: A Message Passing Allocator (ISMM 2019)
  • JavaScriptで大量のオブジェクトの当たり判定を効率的にとる - Subterranean Flower Blog

    ゲームなどのコンテンツにおいて、「当たり判定」から逃れることはできません。オブジェクトとオブジェクトが衝突したかどうかという判定は、インタラクティブコンテンツにおいて最も重要な部分になるからです。 当たり判定の実装自体は難しくありません。ですが、素朴な実装ですと、対象となるオブジェクトが大量である場合に、十分なパフォーマンスが出ません。これはオブジェクトの多い、現代的なゲームでしたり、弾幕シューティングなどを作るときに大きな障害となります。 この記事では、大量のオブジェクトの当たり判定を処理する、効率的な方法について紹介します。 まずは素朴に実装してみる 当たり判定の処理を語るには、ある程度ゲームの骨組みのようなものが必要になってきます。もちろんクラスなどを使わないベタ書きでもよいのですが、大変読みにくくなってしまいます。ですので、今回は、まず簡易的なゲームエンジンのようなものを作って、そ

    JavaScriptで大量のオブジェクトの当たり判定を効率的にとる - Subterranean Flower Blog
  • Microsoft PowerPoint - ppt-3.pptx

    テーマ3:凸包 凸包の定義,構成アルゴリズム 凸包の定義 凸包(convex hull)とは, 与えられた点をすべて包含する最小の凸多角形(凸多面体)のこと. 凸包の定義 凸包(convex hull)とは, 与えられた点をすべて包含する最小の凸多角形(凸多面体)のこと. 1点ずつ加えて行く. 現在の凸包の内部の点なら 何もしない. 現在の凸包の外部の点なら その点から凸包に接線をひき, 凸包を修正する. 問題1:凸包の内部/外部の判定方法 問題2:凸包への接線の求め方 凸包の定義 凸包(convex hull)とは, 与えられた点をすべて包含する最小の凸多角形(凸多面体)のこと. 全ての点を含む最小の軸平行 長方形から始め,ここから削っていく. ちょうど良い 削りすぎ 削りすぎた分をどのように 復元するか? 凸包構成アルゴリズム(1) 凸包の基的な性質1: 平面上の点集合Sの凸包の頂点

    pochi-mk
    pochi-mk 2015/07/14
    凸包
  • Clojureで学ぶデータ構造:ハッシュテーブル - HackerNews翻訳してみた

    「HackerNews翻訳してみた」が POSTD (ポスト・ディー) としてリニューアルしました!この記事はここでも公開されています。 今回の記事は、Clojureでのハッシュテーブルの実装に関する記事です。長い記事で途中までの翻訳になりますがお楽しみください。 Original article: Data Structures in Clojure: Hash Tables by Max Countryman 前回のおさらい 前回の記事では連結リストについてお話ししました。具体的には、ミュータブルな片方向リストの実装方法を検証しましたね。片方向リストを選んだ理由についても、すでに説明済みです。ここで覚えておいてほしいのは、一般的にClojureではイミュータブルなデータ構造が用いられるということです。しかしミュータブルなデータ構造を利用した方が、アルゴリズムがよりシンプルで高速になるケ

    Clojureで学ぶデータ構造:ハッシュテーブル - HackerNews翻訳してみた
  • コンピュータを進化させてきた偉大なるアルゴリズムまとめ

    By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる

    コンピュータを進化させてきた偉大なるアルゴリズムまとめ
    pochi-mk
    pochi-mk 2014/03/12
    アルゴリズムの勉強って楽しいよね。
  • 計算量のはなし - 赤い黒歴史を蓄積する

    どうも華麗なるキャッツパーです。キャットアッパーです。 この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。 私は過去に、暇に任せてこのようなスライドを作ってしまいました。 有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。 記事では「計算量ってどうやって計算するの?」みたいな話を競プロの観点からします。 計算量とはなんぞやということについては上のスライドを読んでください。 計算量の種類 競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。 最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから

    計算量のはなし - 赤い黒歴史を蓄積する
  • マルチコア時代のLock-free入門

    Please select the category that most closely reflects your concern about the presentation, so that we can review it and determine whether it violates our Terms of Use or isn't appropriate for all viewers.

  • 1