徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
Elixir のコレクション型のまとめ - Qiita
概要 他の言語でいう配列、リスト、マップ、ディクショナリーのようなコレクション型についてまとめました。 環境 Elixir 1.1.1 Erlang/OTP 18 [erts-7.1] tuple データやサイズの取得が早いリスト。更新は linked list より遅い。
初心者メモ：PythonのList/Tuple/Set/Dictのチートシート - Qiita
はじめに こんにちわ！Python入門中の石田です。あれこれ本を読んで勉強しているのですが、List->Tuple->Set->Dict ...と進んでいくうちに「あれ、この機能はListだと何だっけ?」とか「Listの追加はappend()だけどSetの追加はadd()かよ！」とか、元々物覚えの悪い頭が更に混乱してきました。ので４つの代表的なデータ構造を自分なりにExcelにチートシートの形でまとめてみたのですが、qiitaにも置いておこうと思ったので公開させて頂きます。基本、自分用のメモのつもりですが、タイポや誤り指摘・アドバイスなどいただけたら有難く。 環境:Python 3.6.4 初回執筆時点:2018/2/11 (随時更新) 2018/2/12 shiracamusさんの補足・アドバイスを反映 2020/12/10 @tomoykさんのアドバイスを反映
What's the difference between lists and tuples?
What's the difference between tuples/lists and what are their advantages/disadvantages?
5. Data Structures
5. Data Structures¶ This chapter describes some things you’ve learned about already in more detail, and adds some new things as well. 5.1. More on Lists¶ The list data type has some more methods. Here are all of the methods of list objects: list.append(x) Add an item to the end of the list. Equivalent to a[len(a):] = [x]. list.extend(iterable) Extend the list by appending all the items from the it
Erlang's Internal Data Representation - Detail oriented
Erlang's Internal Data Representation Jun 28 th , 2016 5:12 pm I find it interesting how the Erlang BEAM engine represents data in memory. Quick look: An Erlang list This is the in-memory layout of the Erlang list "phi" . [112, 104, 105] As a reminder, Erlang treats a string as a list of small integers; 'p' , for instance, is 112 . Don’t worry too much about the bitwise details of the diagram - we
Object composition - Wikipedia
This article may contain excessive or irrelevant examples. Please help improve the article by adding descriptive text and removing less pertinent examples. (August 2010) In computer science, object composition and object aggregation are closely related ways to combine objects or data types into more complex ones. In conversation the distinction between composition and aggregation is often ignored.
「それNArrayでできるよ」をもっと便利にした - 札幌市中央区Ruby会議01 - ぼくたち宇宙人
もう先週の話になってしまいましたが、Tricknotesさん主催の札幌市中央区Ruby会議01に参加してきました。 コンパクトな規模ながらも「非常に良いRubyistの活動が観測」（byしまださん）された、有意義かつ楽しい会議でした。 どの発表も聴き応えのあるすばらしいものでしたが、中でもtmaedaさんの「それNArrayでできるよ」は数値計算ライブラリのNArrayをbetter Excelとして使ってしまうコペルニクス的発想で衝撃的でした。 この発表のなかで、NArrayの軸をHuman-Readableな形式で扱えるラッパークラスを作ると便利だよ、というお話がありましたが、 これをもっと便利にするNArrayCubeクラスを試験的に実装してみたので紹介します。 使い方 # 店、世代、性別の3軸からなる売上表を作成 cube = NArrayCube.new(:int, { titl
連結リスト - Wikipedia
連結リスト（れんけつリスト、（英語: Linked list）は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。 一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる（場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する）。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。 連結リストは多く
スキップリスト - Wikipedia
スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した[1][2][3][4]。 スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。 スキップリストの例。1〜10を追加し、ソートされた状態で保持されている。 スキップリストはリストの階層になっている。最下層は通常の
リングバッファ - Wikipedia
リングバッファの概念図 実際のリングバッファ リングバッファ (英: ring buffer)、サーキュラーバッファ (英: circular buffer)、または環状バッファ（かんじょうバッファ）とは、リング状に配置されたバッファである（図を参照）。一時的にデータを貯めておくバッファ領域のうち、終端と先端が論理的に連結され、循環的に利用されるようになっている。最も古い内容を最新の内容で上書きし、常に一定の数の過去までのデータを蓄えるような用途に用いられる[1]。 バッファは一般的にメモリ空間効率の高い配列を使って実装されるが、配列を物理的にリング状に配置することはできないので、インデックス（添え字、添え数）をバッファサイズで割って剰余を取る正規化をし、一定の範囲に限定することで、直線状のバッファの両端を論理的に繋げる。正規化により、インデックスがバッファの最後を超えると最初に戻り、また
スタック - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "スタック" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2015年10月） push（プッシュ） およびpop（ポップ） のスタックの単純な表現 スタックの単純な表現 スタック（英: stack）は、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。 特にその具象としては、割込みやサブルーチンを支援するために極めて有用で
)
キュー (コンピュータ) - Wikipedia
キューの単純な表現 キュー（英: queue）あるいは待ち行列は、コンピュータにおける基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー[2]、取り出すことをデキュー[3]という。 プリンターへの出力処理や、ウィンドウシステムにおけるイベントあるいはメッセージのハンドリング、プロセスの管理など、データを入力された順番通りに処理する必要があるケースに用いられる。また、個々のタスクの実行時間が予測できない、あるいは実行に時間がかかってしまい、即座に（同期的に）実行することができない場合、キューを使っていったんタスクを溜め込んでおき、後からタスクを取り出して非同期で実行する、というような目的で使用できる。 キューの変形として、先頭と末尾の両端から
優先度付きキュー - Wikipedia
優先度付きキュー（ゆうせんどつきキュー、英: priority queue）は、以下の4つの操作をサポートする抽象データ型である。 キューに対して要素を優先度付きで追加する。 最も高い優先度を持つ要素をキューから取り除き、それを返す。 (オプション) 最も高い優先度を持つ要素を取り除くことなく参照する。 (オプション) 指定した要素を取り除くことなく優先度を変更する 実装[編集] 優先度付きキューを実装する最も簡単な方法は、連想配列を用いて、それぞれの優先度に要素のリストを繋げることである。連想リストやハッシュテーブルを連想配列の実装に用いた場合は、要素の追加はO(1)であるが、要素の削除や先頭の参照にはすべてのキーを探索しなければならないのでO(n)かかる。もし、平衡2分探索木を使用した場合は、上記の3つの操作をO(log n)で行うことができる。平衡木は用意されているが、それ以上のもの
)
リスト (抽象データ型) - Wikipedia
リストの例 - 3つの整数値からなる線形リスト 抽象データ型としてのリスト (英: list) は、順序つきのデータコンテナとして定義される。 リストはたいてい配列や連結リストを使って実装される。これは配列や連結リストと似た特性を持っているからである。また連結リストのことを単にリストと呼ぶこともある。順序を持つ点を強調してシーケンス (列; 英: sequence) と呼び、連結リストと区別することもある。 操作[編集] 型のないミュータブルなリストはコンストラクタと4つの操作によって特徴付けられる: 空のリストを作るコンストラクタ リストが空かどうかを確かめる操作 リストの先頭に要素を追加する操作（Lispのcons） リストの先頭要素 ("head") を求める操作（Lispのcar） リストの先頭を除く部分リスト ("tail") を求める操作（Lispのcdr） 特性[編集] リス
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Tuple vs List
Understanding the Structure of Lists — Otto Ops LLC
Comparing complex terms in Elixir
GitHub - masa16/narray: This repository contains OLD version of NArray. Please visit NEW version =>
Ruby科学データ処理ツールの開発 NArrayとPwrake
