徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
データサイエンティストが知っておくべき5つのグラフアルゴリズム - Qiita
こちらの記事は、2019年 8月に公開された『 Data Scientists, The 5 Graph Algorithms that you should know』の和訳になります。 本投稿は転載であり、本記事はこちらになります。 はじめに 私たちデータサイエンティストは、Pandas、SQL、他のどんなリレーショナルデータベースに対しても、かなり満足しています。 私たちは、ユーザーの属性を列で表現し、ユーザを行として並べることに見慣れています。 しかし、現実の世界は本当にそのようになっているでしょうか？ コネクテッドワールドでは、ユーザーを独立したエンティティと見なすことはできません。 ユーザーはお互いが一定の繋がりをもっているため、機械学習モデルを構築するときに、関係性を含めたい場合があります。 リレーショナルデータベースでは、異なる行（ユーザー）の間でこのような関係性を使用する
Algorithms by Jeff Erickson
🔥1st edition, June 2019 🔥 (Amazon links: US, UK, DE, ES, FR, IT, JP) This web page contains a free electronic version of my self-published textbook Algorithms, along with other lecture notes I have written for various theoretical computer science classes at the University of Illinois, Urbana-Champaign since 1998. More information Get the book More algorithms lecture notes Models of computation n
Open Data Structures
Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs. Data structures presented in the book include stacks, queues, deques, and lists implemented as arrays and linked-lists; space-efficient implementations of lists; skip lists; hash tables and hash codes; binary search
みんなのデータ構造（電子書籍のみ）
PDFのみの提供です 無償で入手できるバージョンはこちらから 紙書籍も必要な場合は、こちらからお得なセットをお求めください 紙書籍のみを差額等でお求め頂くことはできません 配列、リスト、木、グラフ、それぞれの理論的な特性を知り、実装まで理解するためのガイドブック Pat Morin 著、堀江 慧・陣内 佑・田中 康隆 共訳 288ページ A5判 電子書籍の形式：PDF ISBN：978-4-908686-06-1 2018年7月20日 第1版第1刷 発行 正誤情報 データの格納方法を工夫するだけで、魔法みたいにアルゴリズムが導出できる。うまくデータを整頓するだけで、画期的に計算が速くなる。仕事で直面している問題がなかなか解決しないのは、問題に対する適切なデータ構造を知らないから、というだけかもしれません。 計算機科学の授業で当たり前のように学ぶさまざまなデータ構造。学部生向けの教科書として
ハミング符号 : データの誤り検知/訂正をインタラクティブに学ぶ | POSTD
今週お話しするのは、誤りの検知についてと、さらに誤りの訂正についてです。 我々が住んでいる世界は完璧ではなく、デジタルの信号(on/off)を扱う時でさえ誤りが生じます。電力の異常によりビットが反転することがあるのです。ハードウェアも失敗を起こすことがあり、信号が歪められることもあります。 デジタル信号に生じた誤りを検知する方法については既に過去に書いたことがあります。もっとも一般的なやり方は、ある種のパリティビット(ご存知なくともご心配なく。以下でパリティの意味を説明します)です。ある長さの単語に対し、シンプルなパリティビットをたった1つ加えることで、単語中のビットが1つ反転した場合にそれを検知することができます。「エラーが起こったことがわかる」ということは有益ですが、1個のパリティビットだけではその誤った信号を修復することができません。また、信号中に2個以上の誤りがあった場合、その誤り
A beginner's guide to Big O Notation - Rob Bell
Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm. Anyone who’s read Programming Pearls or any other Computer Science books and doesn’t have a grounding in Mathematics will hav
go言語によるhtmlcat実装 htmlcatgo の紹介 - はこべにっき ♨
go言語の勉強に、motemenさんが作ったhtmlcat(標準入力をブラウザで tail -f できる htmlcat というのを書いた - NaN days - subtech)をgoで実装してみました。この記事ではhtmlcatgoの紹介と実装の見どころについて解説します。 htmlcatgoの紹介 htmlcatgo は、標準入力をブラウザ上でtail -fできるソフトウェアです。元祖htmlcatの使い方とほぼ一緒です。 $ tail -f /var/log/messages | htmlcatgo のように実行すると、 2013/12/16 08:15:02 htmlcatgo: http://localhost:45273のようにURLが表示されます。これをブラウザで表示すると、画面にtail -fの結果がリアルタイムで流れてきます。元祖htmlcatにある --execオプ
Day 16: gzip + poetry = awesome
Gzip compresses by replacing text with pointers to earlier parts of the text. Here’s a visualization of what actually happens when you decompress “The Raven”. It highlights the bits of text that are copied from previously in the poem. I showed this as a Thursday talk at Hacker School today :) I really like how you can see the rhyming inside the poem like (rapping… tapping) come out in the compress
coursera Algorithms PartⅠを受講しました
アルゴリズムの知識を強化するために、coursera Algorithms PartⅠを受講しました Algorithms, Part I | coursera TopCoder対策の方法を探していたら、オンライン大学 courseraの存在を知り、アルゴリズムのコースを受講してみた。初の受講ということで、感想を書いてみようと思います。 ２つの壁# ２つの言語の壁があっだ。EnglishとJavaだ。 英語はできないので、そもそもLectureを聞き取れるのかという疑問はあったものの、意外に大丈夫だった。たぶん、Sedgewick先生の英語がゆっくりでわかりやすかったからだと思う。これはけっこう自信がついた。 どちらかというと、Javaのほうが初めはけっこうきつかった。コンパイルの方法がわからん。Assignmet以前に、開発環境をEclipseで整えるのにアタフタ。でも、慣れてくればC+
FluentdとRedisを使ったランキング機能の実装 | SmartNews開発者ブログ
ゴクロの大平です。ごくろうさまです。 Redisは高速で、かつデータの永続化や、複数のデータ型によるストア(list,set,sorted set等）も対応しており、機能的が豊富ということから愛用者の多いKVS実装の一つだと思います。 特に私のようなアプリケーションエンジニアの人間にとってはデータ型のバリエーションの豊富さが便利さを感じる部分で、たとえばlistを用いてタイムライン的な情報や履歴情報の管理、sorted setを用いてランキング情報の管理、などのようにアプリケーションの需要の多くにRedisが対応することができます。 これらの情報を登録する際のフローとしては自作のアプリケーションから直接、というケースが多いと思いますが、せっかくFluentdのような便利なlog collector実装があるので、FluentdとRedisを組み合わせる事でカジュアルに情報の蓄積を行いたい
algorithm - mapBetween - 配列の隣接する2項にそれぞれ演算を施した配列 : 404 Blog Not Found
2012年01月04日21:00 カテゴリLightweight Languages algorithm - mapBetween - 配列の隣接する2項にそれぞれ演算を施した配列 言語を増やしたかったのと、そういう関数に名前を付けたかったのとで1 entry割くことにしました。 等差数列 - タイトル 配列の隣接する2項にそれぞれ演算を施した配列を得たい。つまり、 f (+) [1,2,3,4,5] = [3,5,7,9] のような f が欲しい。 名前 もちろん等差数列を作るのにもこの関数は使えるのですが、この一般的に使える関数に使う名前としてはあまりに局所的。というわけで mapBetween としてみました。使いどころはかなり多そうです。各言語に標準装備されていないのがちょっと不思議なほど。 JavaScriptによる実装 Array.prototype.mapで滅多に使われない第
algorithm - 重みをつけて乱択する : 404 Blog Not Found
2011年12月27日17:15 カテゴリ algorithm - 重みをつけて乱択する 数学ガール/乱択アルゴリズム 結城浩 同意なのだけど… Perlで生でrand関数をごちゃごちゃ使うコードはもう嫌だ | hirobanex.net とにかく、プログラムッチクというとなにかとランダムという要件が多いし、こんなコードばかりグチャグチャ書くのはもういやですね。 これを一般化するという問題はアルゴリズムの実習にちょうど手頃なサイズなので。 JavaScriptによる実装 頻度を高い順に並べて、乱数＜合計頻度となったところでそれを選択します。O(n)ですが選択肢を頻度順に並べることでその分ループが回る確率を抑えています。 (function(global){ var make_random_picker = function(picks){ var choices = Array.proto
2つの期間が重なり合うかどうかを判定する。 - こせきの技術日記
2つの期間 A〜B と X〜Y が重なっているかどうかを判定したい場合。 のように4つのパターンがある。これを単純に、 A <= X && Y <= B || X <= A && Y <= B || A <= X && B <= Y || X <= A && B <= Yのように判定してはいけない。 Xは青い線の上を、Yは赤い線の上を動くとき、A〜B と X〜Y は重なり合う。この条件は、 X <= B && A <= Yこれで4つのパターンをカバーできる。ORは不要。始点と終点をわかりやすく書くと以下になる。 始点2 <= 終点1 && 始点1 <= 終点2アルゴリズムに名前がありそうな気がするけど、見つけられなかった。 (追記) 矩形の重なり判定の方が情報が見つかった。 * Life is beautiful: ビル・ゲイツの面接試験－私の場合 * 長方形の重なりを判定する問題 - ザ
第4回 memcachedの分散アルゴリズム | gihyo.jp
株式会社ミクシィの長野です。第2回、第3回と前坂がmemcachedの内部について紹介しました。今回は内部構造から離れて、memcachedの分散についての紹介をいたします。 memcachedの分散 連載の1回目に紹介しましたが、memcachedは「分散」キャッシュサーバと言われていますが、サーバ側には「分散」の機能は備わっていません。サーバ側には当連載の第2回、第3回で前坂が紹介したメモリストレージの機能のみが組み込まれており、非常にシンプルな実装となっています。では、memcachedの分散はどのように実現しているのかと言うと、すべてクライアントライブラリによって実現されます。この分散方法はmemcachedの大きな特徴です。 memcachedの分散とは ここまで数度「分散」という言葉を用いてきましたが、あまり詳しく触れてきませんでした。ここでは各クライアントの実装に共通する大ま
ファイルから複数の行を高速に取り出すプログラム(Pure Perl)
ファイルから複数の行を高速に取り出すプログラム(Pure Perl) 2010-08-13-2 [Programming][Algorithm] インデックスを使った指定行取り出しプログラム[2010-08-10-1] についての記事を先日公開した。 そのプログラムを作成した動機の一つが 「リードオンリーのテキストファイル（それもメモリに読み込むのがうんざりするくらいに巨大なやつ）からランダムに複数の行を取り出したい」 というもの。 この記事ではランダム複数行取り出しタスクについて、先日の記事[2010-08-10-1]に沿って先頭から走査する方法とインデックスを用いた方法を紹介する。 頭から操作する方法 ランダムに一行だけ取り出すには定番の方法がある。 詳しくは[2004-11-30-5]を参照のこと。 エッセンスだけ一行で書くとこんな感じ： rand($.) < 1 && ($line
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
How to analyze time complexity: Count your steps
Lecture Videos | Design and Analysis of Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare
Amazon.co.jp: プログラミングコンテストチャレンジブック: 秋葉拓哉, 岩田陽一, 北川宜稔: 本
