徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
[Rust] 自然に見える迷路の生成
Rust でやるゲーム開発アルゴリズムシリーズ、第4弾ぐらいでしょうか？ 今回はプログラム的に迷路生成をします。 元々は、四分木による経路探索をテストするために考えたものですが、これはこれで独立した知見になりそうなので別記事にしました。 自然に見える迷路とは 何をもって自然な迷路というかは、人によると思いますが、ここでは次のような感じのものを指します。 ある程度迷路としての構造を持ちながらも、分岐やループを持ち、道幅をいくらか持つことによってエージェント同士がすれ違えるようにします。 また、壁の形状にノイズを加えて単調にならないようにしています。 総合的には、鍾乳洞のような天然の洞窟というほどは自然ぽくはありませんが、完全に人工的な環境というわけでもない、ほどほどに自然な迷路を目指します。 このような地形のプロシージャル生成については、様々な方法があります。 ここで紹介するのはごく一部で、
![[Rust] 自然に見える迷路の生成](https://cdn-ak-scissors.b.st-hatena.com/image/square/8dacf1b0b1560cad1913c4519c3f590ef6fcd12b/height=288;version=1;width=512/https%3A%2F%2Fres.cloudinary.com%2Fzenn%2Fimage%2Fupload%2Fs--nb2LL6oy--%2Fc_fit%252Cg_north_west%252Cl_text%3Anotosansjp-medium.otf_55%3A%25255BRust%25255D%252520%2525E8%252587%2525AA%2525E7%252584%2525B6%2525E3%252581%2525AB%2525E8%2525A6%25258B%2525E3%252581%252588%2525E3%252582%25258B%2525E8%2525BF%2525B7%2525E8%2525B7%2525AF%2525E3%252581%2525AE%2525E7%252594%25259F%2525E6%252588%252590%252Cw_1010%252Cx_90%252Cy_100%2Fg_south_west%252Cl_text%3Anotosansjp-medium.otf_37%3Amsakuta%252Cx_203%252Cy_121%2Fg_south_west%252Ch_90%252Cl_fetch%3AaHR0cHM6Ly9saDMuZ29vZ2xldXNlcmNvbnRlbnQuY29tL2EvQUFUWEFKeG5tZ0ZYQlJsZjJpZVh1QWlwOG9LaFdpT2FSczg2dXRzWlcwN3o9czk2LWM%3D%252Cr_max%252Cw_90%252Cx_87%252Cy_95%2Fv1627283836%2Fdefault%2Fog-base-w1200-v2.png)
優先度付きキューにも使われる二分ヒープ構造をRubyで実装してみる - $shibayu36->blog;
アルゴリズム図鑑 絵で見てわかる26のアルゴリズム 作者:石田保輝,宮崎修一翔泳社Amazon アルゴリズム図鑑を眺めていて、二分ヒープ構造は優先度付きキューに使われることを知った。面白いなーと思うと同時に、そういえば二分ヒープ構造の実装をしたことがなく、あまり理解できていないことに気づいた。そこで簡単にRubyで実装をしてみたのでメモ。簡単なテストケースを作ったので多分合ってると思うけど、もしかしたらバグっているかも... 二分ヒープの詳細は二分ヒープ - Wikipediaも参考。 【2023/01/03 14:01追記】要素数が1の時に要素が空にならないバグがあったので修正しました。コメントありがとうございます。https://github.com/shibayu36/algorithms/commit/6c2ce588f7bc7fb890c6a560c7ab062c6f531a9a
ヒープについてわかりやすく解説してみた – Yasufumi Taniguchi – Medium
基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介します。MITが講義や資料を公開しているMIT OpenCourseWareのアルゴリズムとデータ構造の講義 が非常にわかりやすかったので、その内容に沿ってまとめました。この記事ではHeaps and Heap Sortの内容を以下の順序で解説します。 ヒープの概要ヒープの表現ヒープの構築ヒープの計算量ヒープの実装ヒープソート1. ヒープの概要ヒープ (heap) は優先度付きキュー (priority queue) の実装の1つです。優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。学会のポスター発表を回るときや、旅行先での観光地巡りでは、優先度に基づいて要素を取り出すことが重要
UUID v6, v7, v8 : タイムスタンプでソートできる新しい UUID のドラフト仕様 - kakakakakku blog
ID を採番するときによく使われる UUID Version 4 の課題として「順序性がなくソートしにくい」という側面があり，ULID (Universally Unique Lexicographically Sortable Identifier) を使えばソートできるようになるという記事を前に書いた． kakakakakku.hatenablog.com 関連して調査をしていたら，標準化団体 IETF (Internet Engineering Task Force) によって，UUID Version 6, 7, 8 という新しい仕様が提案（ドラフト段階）されていることを発見した❗️UUID Version 6, 7, 8 の目的を簡単にまとめると「タイムスタンプ情報を使ってソートできる ID を採番できるようにする」となり，もしこの仕様が取り込まれると，UUID を活用する幅がさ
25歳で年商40億円の株式会社アルゴリズム、事業実体はサイト貸しを活用したアフィリエイター集団か。過激化するSEOハックの実態に迫った。
東大卒、TNK出身の勝俣社長と、慶應卒の金田氏が主要経営陣とのこと。 株主にもエアトリやトレンダーズなど上場企業が並びます。 こちらのアルゴリズム社が、年商40億円、利益率はキーエンス超えしているとのこと。。その一方で、このインタビュー記事の中身を読んでも事業は全く不明。 ベギラマくんからも、「事業内容を話さないという強い意志を感じる」と指摘されています。 話題になっていたアルゴリズムさん面白い。スポンサードで2本記事出しているけど、絶対に事業内容を話さないという強い意思を感じる。Wantedly見てもほぼ事業内容は記載がない。でも人手は欲しい。M&Aも積極的。 つまり事業モデルは一定カネがある企業であれば真似ができるので早めにEXITしたいのか。 pic.twitter.com/nkMxQ5DuT2 — ベギラマくん (@cogitopp) October 13, 2022 今回はこちら
ゲームで「壁すり抜けるバグとかどうなってんだ！？」ってよく言われるけど実際作ってみると「逆」だと分かる
なぎせ ゆうき @nagise ゲームで 「壁をすり抜けるバグどうなってんだ！？」 みたいに言われがちですけども、プログラミングやると 「すり抜けない衝突判定、どうやってんだ！？」 ってなりますからね🤔 2022-09-28 17:07:17 リンク Wikipedia 衝突判定 衝突判定（しょうとつはんてい、Collision Detection）とは、「2つ以上のオブジェクトの交差を検出する」という計算機科学上の問題であり、具体的には「ある物体が別の物体に当たったか（衝突したか）どうか」を判定するプログラム処理のことを指す。ロボット工学、計算物理学、コンピュータゲーム、コンピュータシミュレーション、計算幾何学など、さまざまなコンピューティング分野で応用されている。 衝突判定のアルゴリズムは、2Dオブジェクト同士の衝突判定と3Dオブジェクト同士の衝突判定に分けることができる。 ビ 14
はじめに - アルゴリズムとデータ構造大全
はじめに このドキュメントは，主に競技プログラミングで出題される問題を解く際に利用できるアルゴリズムやデータ構造をまとめたものです．特定の問題にはあまりフォーカスしないため，問題を解く際の考察の仕方等の内容はありません．詳しく，正確に，分かりやすく書いていこうと思っています． このドキュメントは執筆途中です． 想定する読者 C++を用いたプログラミングに慣れている方を読者として想定しており，C++言語の仕様や，文法にはあまり触れません．また，計算量という用語についても説明しません．ただし，償却計算量など，計算量の見積もりが複雑なものについては必要に応じて説明します． コードについて このドキュメントで登場するコードは，可読性向上のため，以下のようなコードがファイルの先頭に記述してあることを前提としています．また，適切な問題を用いてコードの検証がなされている場合は，コード周辺にのように，検証
6x6リバーシの神 - まめめも
絶対に勝てない6x6リバーシを作りました。あなたは黒番、AIが白番です。 絶対に勝てない6x6リバーシを作りました！ ぜひ挑戦してみてくださいhttps://t.co/Ul5n3q9jMp— Yusuke Endoh (@mametter) December 30, 2021 これは何？ 6x6の盤面のリバーシは後手必勝 *1 であることが知られています。 このAIは白番（後手）で完璧にプレイします。つまり黒番のあなたは絶対に勝てません。無力感を楽しんでください。 技術的な話 このAIはWebAssemblyになっているので、全部あなたのブラウザの上で動いてます。真のサーバーレスです。 AIのソースコードはRustで書きました。わりと堅実なゲーム木探索になってます。UIは普通にTypeScriptとthree.jsで実装しました。 github.com 作った順に説明します。 盤面の表現
エラトステネスの篩の活用法を総特集！ 〜 高速素因数分解・メビウスの反転公式 〜 - Qiita
とても久しぶりです！ 1 年ぶりの投稿となりました、大槻 (通称、けんちょん) です。 去年、『AtCoder 版！マスター・オブ・整数』と題して、プログラミングコンテストで出題される整数問題を解くときに有効な考え方を特集する記事を 2 本書きました！ AtCoder 版！マスター・オブ・整数 (素因数分解編) AtCoder 版！マスター・オブ・整数 (最大公約数編) 今回はその続編として、素数を列挙するアルゴリズムであるエラトステネスの篩を特集していきます。なお今回の記事の内容は、競プロへの応用を意識していますが、純粋に数学的興味に沿って読み進めることもできるものになっています。下図は、これから紹介するエラトステネスの篩のイメージ図です。 0. はじめに エラトステネスの篩は、$1$ 以上 $N$ 以下の素数をすべて列挙する方法です。たとえば $20$ 以下の素数を列挙すると、$2,
東京大学、量子コンピューティング入門教材が無料公開 ゼロから自習できる教材目指す | Ledge.ai
画像は公式サイトより 東京大学素粒子物理国際研究センター（ICEPP）の研究者が選定・執筆した、量子コンピューティングを手を動かして学びたい人向けの入門教材「量子コンピューティング・ワークブック」が無料公開されている。SNS上では本教材について「面白そう！」「いい時代になったなぁ」などのコメントが見られる。 本教材は、量子力学や計算科学の前提知識を極力必要とせず、大学1年程度の数学とPythonプログラミングの知識があれば、ゼロから量子コンピューティングを自習できるような教材を目指しているという。 公式サイトより 内容は「量子コンピュータに触れる」「超並列計算機としての量子コンピュータ」「量子ダイナミクスシミュレーション」「ショアのアルゴリズム」「グローバーのアルゴリズム」「変分法と変分量子固有値ソルバー」「量子・古典ハイブリッド機械学習」「補足」で成り立っている。 公式サイトでは「私たち
Python言語による実務で使える100+の最適化問題 | opt100
指針 厳密解法に対しては、解ける問題例の規模の指針を与える。数理最適化ソルバーを使う場合には、Gurobi かmypulpを用い、それぞれの限界を調べる。動的最適化の場合には、メモリの限界について調べる。 近似解法に対しては、近似誤差の指針を与える。 複数の定式化を示し、どの定式化が実務的に良いかの指針を示す。 出来るだけベンチマーク問題例を用いる。OR-Libraryなどから問題例をダウンロードし、ディレクトリごとに保管しておく。 解説ビデオもYoutubeで公開する． 主要な問題に対してはアプリを作ってデモをする． 以下，デモビデオ： 注意 基本的には，コードも公開するが， github自体はプライベート そのうち本にするかもしれない（予約はしているが， 保証はない）． プロジェクトに参加したい人は，以下の技量が必要（github, nbdev, poetry, gurobi); ペー
Tsukasa #01 (4x vaccinated) on Twitter: "真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR"
真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR
シンプルかつ高速な文字列照合アルゴリズムを紹介します - エムスリーテックブログ
こんにちは！ エンジニアリンググループ マルチデバイスチーム 新卒1年目の小林です。 エムスリーでは、2週間に1度、Tech Talkという社内LT会（現在はリモートで）が開催されています。これは、とある回の発表テーマリストです。 Tech Talkのとある回の発表テーマリスト このように、最近エムスリーでは文字列が流行っている（？）ようなので、その勢いに乗って私も文字列照合アルゴリズムについて書きたいと思います！（業務とは全然関係ない話です） Knuth-Morris-PrattやBoyer-Mooreアルゴリズムは解説記事がたくさん出ていると思うので、この記事ではシンプルかつ高速なQuick-SearchとQuite-Naiveアルゴリズムについて説明し、速度比較を行った結果についてご紹介します。 文字列照合アルゴリズムとは テキストとパターンという文字列が与えられたときに、中に出現す
アルゴリズムの基本をJava、C#、Pythonで学ぼう - データを集計し、言語ごとの違いを知る - エンジニアHub｜Webエンジニアのキャリアを考える！
今回は、以下のように指定しました。表示オプションはデフォルトのままです。 地点を選ぶ：東京 項目を選ぶ（データの種類）：時別値 項目を選ぶ（項目）：気温 期間を選ぶ：2019/1/1～2019/12/6 データの項目は「日時」「気温」「品質情報」「均質番号」の4種類。品質情報、均質番号は、観測値が正常かどうかに関する情報です。各項目の詳細については、同サイトの「ダウンロードファイル(CSVファイル)の形式」ページを参照してください。 ファイルの先頭5行には、次の画像のような項目が入っています。このまま使うとやや面倒なので、あらかじめ先頭5行分は削除し、全てデータ行のみのCSVファイルに加工しておきます。 CSVファイルの仕様にはバリエーションがあり、その全てに対応するとコードが複雑になりますので、今回は気象庁のCSVデータに基づき、次の仕様を前提とします。 文字種は、ANK（1バイト文字）
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単
プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD
情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。
ID生成大全 - Qiita
セッションIDやアクセストークン、はたまた業務上で使う一意の識別子など、いろんなところで一意のIDを生成しなきゃいけないケースが存在します。 そこで世間で使われているIDの生成方法について調べてみました。 選択基準 ID生成における要求として、以下の観点が上げられるかと思います。 生成の速度 大量にデータを短期間で処理し、それらにIDを付与する場合、ID生成そのものがボトルネックとなることがあります。 推測困難性 IDを機密情報と結びつける場合、IDを改ざんされても、機密データが見れないようにできている必要があります。 順序性 採番した順にデータをソートする必要がある場合は、IDがソートキーとして使えないといけません。 それぞれについて各生成手段を評価します。 ID生成の手段 データベースの採番テーブル 採番用のテーブルを作り、そこで番号をUPDATEしながら取得していくやりかたです。古い
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
食べログ、裁判でアルゴリズム「異例」の開示 評価透明化なるか | 毎日新聞
Shota Imai@えるエル on Twitter: "コンピュータサイエンスで有名なアルゴリズムのPython実装を大量に公開しているリポジトリ https://t.co/379T4izBle 教養レベルのデータ構造やアルゴリズムから機械学習やブロックチェーン,Web関連などの応用ま… https://t.co/vSmYZW5SHw"
