List of data structures - Wikipedia
This is a list of well-known data structures. For a wider list of terms, see list of terms relating to algorithms and data structures. For a comparison of running times for a subset of this list see comparison of data structures. Boolean, true or false. Character Floating-point representation of a finite subset of the rationals. Including single-precision and double-precision IEEE 754 floats, amon
Content-aware image resizing in JavaScript | Trekhleb
More examples Here are some more examples of how the algorithm copes with more complex backgrounds. Mountains on the background are being shrunk smoothly without visible seams. The same goes for the ocean waves. The algorithm preserved the wave structure without distorting the surfers. We need to keep in mind that the Seam Carving algorithm is not a silver bullet, and it may fail to resize the ima
Idiomatic tree and graph like structures in Rust
If you want to create data structures which can be modified during runtime, a possible solution could lead into tree or graph like structures. Writing tree structures in Rust is no trivial problem. Nevertheless there are some common idiomatic ways how to handle lifetime and borrowing issues. In other languages like C/C++ we would simply use pointers to create graphs or trees. This is also possible
GitHub - Poojavpatel/dsa: Data structures and Algorithms implemented in JavaScript with explanations
FLoCとはなにか - ぼちぼち日記
1. はじめに Google がChrome/89よりトライアルを開始しているFLoC (Federated Learning of Cohorts)技術に対して、現在多くの批判が集まっています。 批判の内容は様々な観点からのものが多いですが、以前より Privacy Sandbox に対して否定的な見解を示してきたEFFの批判「Google Is Testing Its Controversial New Ad Targeting Tech in Millions of Browsers. Here’s What We Know.」が一番まとまっているものだと思います。 これまで Privacy Sandbox 技術に関わってきた身としては、各種提案の中でFLoCは特にユーザへの注意が最も必要なものだと思っていました。しかし、これまでのド直球なGoogleの進め方によって、FLoCのトラ
秘密計算技術の普及を目的とする「秘密計算研究会」 | スラド セキュリティ
NECなどの3社が2月18日「秘密計算研究会」を立ち上げたと発表した。この研究会はデータを暗号化したまま運用する「秘密計算」の普及を目的とした組織であるという。参加企業はNEC、デジタルガレージ、ソフトウェア開発企業のレピダム（秘密計算研究会、ITmedia、TECH+）。 公式サイトによれば、 秘密計算は、高度な暗号理論を用いて、データを暗号化した状態のままでデータベース処理、統計分析、AIによる分析などができる技術です。データ保護性が非常に高いクラウドサービスや、複数組織のデータを安全に共有・統合して1つのビッグデータとして利活用できるシステムを実現する技術として、期待されています。 とのこと。 秘密計算には「秘密分散」や「準同型暗号」を元に下した異なる方式が複数存在しているが、それぞれ独立して研究されてきたことから、安全性や性能などを一定のの基準で定量的に評価する方法が確立されていな
N番目の素数を求める - すぎゃーんメモ
SNSなどで話題になっていたので調べてみたら勉強になったのでメモ。 環境 Pythonでの実装例 例1 例2 例3 エラトステネスの篩 Rustでの実装例 試し割り法 エラトステネスの篩 アトキンの篩 おまけ: GMP Benchmark 高速化のテクニック 上限個数を見積もる Wheel factorization オチ Repository References 環境 手元のMacBook Pro 13-inchの開発機で実験した。 2.8 GHz Intel Core i7 16 GB 2133 MHz LPDDR3 Pythonでの実装例 例1 最も単純に「2以上p未満のすべての数で割ってみて余りが0にならなかったら素数」とする、brute force 的なアプローチ。 import cProfile import io import pstats import sys def m
QuickDrawはどのように素早く円を描いていたのか？ - ザリガニが見ていた...。
かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時（25年以上前）のCPUは、動作クロックが8MHzという性能だった。（現在は2GHz=2000MHzかつ、複数コアが当たり前） そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp： レボリューション・イン・ザ・バレー
メモリを節約しつつ動的計画法の経路を復元する - www.kotha.netの裏
背景 動的計画法を実行する際、計算した部分問題の解をテーブルに書き込んでいくわけだが、問題によっては、テーブルの全体を最後まで持っておく必要がないこともある。 例として、2つの文字列のレーベンシュタイン距離を求める問題を考える。二つの文字列の先頭それぞれi文字とj文字を取ったもののレーベンシュタイン距離をdp[i][j]とすると、dp[i][j]の計算にはdp[i-1][j]、dp[i-1][j-1]、dp[i][j-1]の値があれば十分なので、iが小さい方から計算していくなら、dp[i][j]を計算する時点でdp[i-2][*]やdp[i-3][*]などは忘れてしまっていても良い。コードは例えば以下のようになる。 use std::cmp; use std::iter::Iterator; use std::mem; // 二つの配列のレーベンシュタイン距離を求める fn levensh
西暦1年は閏年か？ - プログラマーの脳みそ
閏年（うるうどし）の話題。 Twitterで見かけた話題で「西暦1年は閏年かどうかぱっとわからん人おる？」という些か煽り気味のツイートを見かけたのだけども、反射的に「閏年じゃないに決まってるじゃん」とぱっと答えてしまわないだろうか。本当にそうだろうか？ そう単純な話なのだろうか？ プログラミングを学んでカレンダーを扱うことを学ぶ際に置閏法についても簡単に触れられることがある。置閏法というのは閏年や閏月（太陰暦では1年が13ヵ月になるケースがあり追加の月を閏月と呼ぶ）をどのようなルールで挿入するかという話で、まさにアルゴリズムであるからプログラミングの話題と相性がいい。 置閏法 現代の西暦の置閏法（ちじゅんほう）は 西暦を 400 で割り切れる年は閏年 上記以外で西暦を 100 で割り切れる年は平年 上記以外で西暦を 4 で割り切れる年は閏年 上記以外は平年 といった手続きで閏年（つまり2月
広島大学、ハフマン符号の処理を高速化するデータ構造「ギャップ配列」を考案 | スラド デベロッパー
広島大学の中野浩嗣教授らの研究チームは8月31日、GPUによる「ハフマン符号」の並列展開処理を高速化する新しいデータ構造「ギャップ配列」を考案したそうだ（広島大学リリース[PDF]、マイナビ）。 ハフマン符号はJPEGやZIPなど多くのデータ圧縮で使われている符号化方式。NVIDAのGPU「Tesla V100」を用いた実験では、10種類の様々な種類のファイルを用意し、既知の最速プログラムとギャップ配列用に構築したプログラムを用いて比較したという。その結果、従来の展開プログラムと比較した場合、圧縮処理で2.5～7.4倍、また展開処理については、2.5倍から最大1万1000倍もの高速化が達成できたとしている。 ちなみにこの論文は、8月に開催された第49回並列処理に関する国際会議（ICPP）で最優秀論文賞に選ばれたとのこと。
GitHub - scandum/quadsort: Quadsort is a branchless stable adaptive mergesort faster than quicksort.
Rate Limiting, Cells, and GCRA — brandur.org
Rate limiting is a mechanism that many developers (especially those running services) may find themselves looking into at some point in their careers. It’s useful for a variety of purposes, some of which might be: Sharing access to limited resources. e.g. Requests made to an API where the limited resources are your server capacity, database load, etc. Security. e.g. Limiting the number of second f
Generic cell rate algorithm - Wikipedia
The generic cell rate algorithm (GCRA) is a leaky bucket-type scheduling algorithm for the network scheduler that is used in Asynchronous Transfer Mode (ATM) networks.[1][2] It is used to measure the timing of cells on virtual channels (VCs) and or Virtual Paths (VPs) against bandwidth and jitter limits contained in a traffic contract for the VC or VP to which the cells belong. Cells that do not c
abseil / Swiss Tables and <code>absl::Hash</code>
By Sam Benzaquen, Alkis Evlogimenos, Matt Kulukundis, and Roman Perepelitsa We are extremely pleased to announce the availability of the new “Swiss Table” family of hashtables in Abseil and the absl::Hash hashing framework that allows easy extensibility for user defined types. Last year at CppCon, We presented a talk on a new hashtable that we were rolling out across Google’s codebase. When asked
第4回 BBRの出現 | gihyo.jp
バッファサイズ増加とバッファ遅延増大 近年、ルータやスイッチ等のネットワーク機器に搭載されるバッファメモリのサイズが増加してきました。この主な要因としては、メモリの低価格化が進んだことが挙げられます。またネットワーク機器に限らず、メモリサイズは大きい方が良い、という通念が主流となってきたことも大きく影響しているでしょう。ネットワーク機器のバッファサイズが大きくなることで、パケット廃棄が起こりにくくなるという利点があります（図1）。すなわち、ネットワーク機器に一度に大量のパケットが到着した場合にも、それらのパケットをメモリに蓄積しておき、順番に送出することができるようになります。 図1 バッファサイズとパケットロス しかしながら、バッファサイズが大きくなることによる弊害もあり、それがバッファ遅延の増大です。バッファ遅延の増大によって生じる遅延の増加現象はバッファブロート（Bufferbl
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - saschagrunert/indextree: Arena based tree 🌲 structure by using indices instead of reference counted pointers
GitHub - ka-weihe/fastest-levenshtein: The fastest implementation of Levenshtein distance in JS/TS.
GitHub - s-macke/VoxelSpace: Terrain rendering algorithm in less than 20 lines of code
KiloGram - マルウェア検出AIの新たなテクニック
