論文｜MESH: Compacting Memory Management for C/C++ Applications (PLDI 2019)
「MESH: Compacting Memory Management for C/C++ Applications」という論文を読んだのでその紹介です。arXiv.org で公開されています。PLDI 2019 で採択されている論文のドラフトだそうです。私は v2 を読みました。ソースコードが GitHub (plasma-umass/Mesh) で公開されています。 免責 読み間違えている可能性があります。正確な情報が欲しい方は必ず論文を読んでください。誤りの指摘や補足、議論などは GitHub Issue や Twitter へお願いします。 読んだ動機 C/C++ でリロケーションせずにコンパクションを行う手法に興味があった。 Speedmetor 2.0 benchmark を走らせた Firefox でメモリ消費量が減ったと報告されており、ブラウザ開発者として気になった。 Ch
javascript-algorithms/README.ja-JP.md at master · trekhleb/javascript-algorithms
数学 B ビット操作 - set/get/update/clear bits, 2つの乗算/除算, 否定的にする. 等 B 因果関係 B フィボナッチ数 - クラシックとクローズドフォームのバージョン B 素数性テスト (trial division 方法) B ユークリッドアルゴリズム - 最大公約数を計算する (GCD) B 最小公倍数 (LCM) B エラトステネスのふるい - 与えられた限度まですべての素数を見つける B Is Power of Two - 数値が2の累乗であるかどうかを調べる（単純なアルゴリズムとビットごとのアルゴリズム） B パスカルの三角形 B 複素数 - 複素数とその基本演算 B ラジアン＆度 - 度数と逆方向の変換に対するラジアン B 高速電力供給 A 整数パーティション A Liu Hui π アルゴリズム - N-gonsに基づく近似π計算 A 離散フ
プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD
情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。
MurmurHash - Wikipedia
MurmurHash is a non-cryptographic hash function suitable for general hash-based lookup.[1][2][3] It was created by Austin Appleby in 2008[4] and, as of 8 January 2016,[5] is hosted on GitHub along with its test suite named SMHasher. It also exists in a number of variants,[6] all of which have been released into the public domain. The name comes from two basic operations, multiply (MU) and rotate (
約3年かけてプログラマ向けニュース推薦アプリを作り直した話 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 概要 『もっとより良いニュースアプリはできないだろうか』 そう考えてMenthasというニュースアプリを開発し、プログラマ向けニュースキュレーションサービスを作ってみた話 という記事をQiitaに書き、自分の予想を超えた反響を受けてから約3年になります。 しばらく開発の更新は留まってしまいましたが、ニュース推薦に関しての探求が終わったわけではなく、むしろ見えてきた課題のために数多くの論文を読んだりプロトタイピングを繰り返していました。 そしてつい先日、これまで解けなかった問題に対してようやく答えを自分なりに導き出すことができたため、骨格
Statechart - 増井俊之
表を使って状態遷移を表現することもできる。transition[][]のような遷移表を作っておき、state = transition[state][input]のように現在の状態と入力から次の状態を計算するようにしておけばプログラムは簡単になる。 正確な遷移表を作ることだけ注意すれば良い。
Scalable memory allocation using jemallocの備忘録的和訳 - はてなかよっ！
Scalable memory allocation using jemalloc jemallocは今使ったりしてるし，今後ソース読む可能性もあるので，適当に(精度とかは期待しないように！)．気になる人は元記事を読みましょう． Scalable memory allocation using jemalloc Facebookは，8コア+CPUと8GiB RAMな専用マシンの上で走っている，様々な種類のサーバアプリケーションの集合で構成されています．これらのアプリケーションは，CPUとRAMと最大限使う事によって最高のスループットを目標に，並行処理のため大体POSIXスレッドを使っています．この環境は，メモリアロケーションのための重大なチャレンジをもたらします．具体的に言えば， 確保と解放は速くなければいけません．理想的に，メモリアロケーションはアプリケーションの定常状態においてはほとん
画像のノイズを落としたり容量を小さくしたりするにはどのようなコードを書く必要があるのか？
手書きのメモをスキャンししたときにどうしても発生してしまうノイズを取り除くとともに、ファイルサイズも減らす方法を、スワースモア大学准教授のMatt Zuckerさんが具体的に公開しています。 Compressing and enhancing hand-written notes https://mzucker.github.io/2016/09/20/noteshrink.html Zuckerさんが持つクラスの中には教科書を使用せずに行うものもあり、そうした場合Zuckerさんは「学生書記官」を任命してノートを取ってもらい、スキャンしてアップロードするそうです。 例えば、以下の画像のようなページをスキャンする場合を考えてみます。この画像は300DPIでスキャンされており、約7.2MBのPNG形式で保存されています。それを画質85でJPGに変換すると約790KBになりますが、1ページで7
写真の特徴を別の写真に移し替える軽量なアルゴリズム「FastPhotoStyle」をNVIDIAが開発
GPU最大手のNVIDIAが、画像イメージが持つ特徴的な「スタイル」をまったく別の写真に「移植」する「FastPhotoStyle」というアルゴリズムを開発しました。FastPhotoStyleはすでにGitHubで無料で公開されています。 [1802.06474] A Closed-form Solution to Photorealistic Image Stylization https://arxiv.org/abs/1802.06474 写真の見た目の特徴を別の写真に移し替える技術は、ディープラーニングを用いたものがすでにいくつか開発されていました。 ディープラーニングを用いて「写真の見た目の特徴」を別の写真に転送してしまう「Deep Photo Style Transfer」 - GIGAZINE NVIDIAによると、従来型の技術では加工に高い演算能力が必要とされVGA(64
The Z Garbage Collector - An Introduction
Copyright © 2018, Oracle and/or its affiliates. All rights reserved. | The Z Garbage Collector An Introduction Per Lidén & Stefan Karlsson HotSpot Garbage Collection Team FOSDEM 2018 Copyright © 2018, Oracle and/or its affiliates. All rights reserved. | Safe Harbor Statement The following is intended to outline our general product direction. It is intended for information purposes only, and may no
エレベータに見るアルゴリズムの性能と公平性のバランス｜Rui Ueyama
現実世界でもコンピュータの中でも、何らかの性能指標だけを追求すると参加者にとって極端に不公平になってしまうことがある。例えばエレベータとHDDは共通点がありそうに思えないが、この2つは性能特性的にとてもよく似ていて、リーズナブルな性能と公平性を両立させるために同じ制御方法が使われている。これについてちょっと説明してみよう。 1基しかない場合のエレベータの動き方は単純だ。一度上に動き出すと、上で待ってる人や降りる人がいる限り上昇し続ける。同じように、一度下に動き出すと、下で待っている人や降りる人がいる限り下降し続ける。これ以外の動き方をするエレベータはまず存在しないので、これが唯一の制御方法のように思えるけど、別にこうしなければいけないというルールはない。 エレベータの平均待ち時間を最適化することを考えてみよう。そうすると、一方向に動き続ける代わりに、エレベータが現在存在する階に一番近い人の
SQLトランザクション分離 実践ガイド | POSTD
(注：2017/10/16、いただいたフィードバックを元に翻訳を修正いたしました。) (注：2017/10/11、いただいたフィードバックを元に翻訳を修正いたしました。) データベースのドキュメントで分離レベルを目にして、軽く不安を感じつつ、あまり考えないようにしたことはないでしょうか。トランザクションの日常の使用例できちんと分離について言及しているものはほとんどありません。多くはデータベースの初期設定の分離レベルを利用しており、後は運頼みです。しかし、本来、理解しておくべき基本的なトピックであり、いくらか時間を投入してこのガイドの内容を学習すれば、もっと快適に作業できるようになるでしょう。 私はこの記事の情報を学術論文、PostgreSQLドキュメンテーションから集めました。分離レベルの 何たる かだけでなく、適用の正確さを保持しつつ最大速度で使うにはいつ使うべきか、という疑問に答えるべ
差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
SymSpell対BK木：100倍速い文字列のあいまい検索とスペルチェック | POSTD
注釈：500,000単語収録の辞書内における1,000単語の検索時間 X:最大編集距離 Y:検索時間/ms 従来、スペル修正や文字列のあいまい検索には、 BK木 が適していると言われてきました。しかし、これは本当でしょうか。 また、 スペル修正に関する私のブログ に寄せられたコメントには、BK木が、あいまい検索のためのデータ構造として優れていると言及されていました。 そのような経緯から、今回、BK木と他の選択肢のベンチマークを取って比較してみようと思い立ったわけです。 近似文字列検索アルゴリズム 近似文字列検索では、文字列リスト内の文字列を検索し、特定の 文字列メトリック に従って、それに近い文字列を返します。 文字列メトリックは多数あり、例えば レーベンシュタイン距離 、 Damerau-Levenshtein距離 、 ハミング距離 、 ジャロ・ウィンクラー距離 、 Strike a m
Google、TCPのスループットとレイテンシを改善する輻輳制御アルゴリズム「TCP BBR」をGoogle Cloudで利用開始
Google、TCPのスループットとレイテンシを改善する輻輳制御アルゴリズム「TCP BBR」をGoogle Cloudで利用開始 Googleは、同社が開発したTCPの輻輳制御アルゴリズム「TCP BBR」をGoogle Cloud Platformで利用可能にしたと発表しました。 インターネットにおける通信にはTCPを用いる場合とUDPを用いる場合に分かれますが、BBRはTCPにおける輻輳制御アルゴリズムを改善したもの。すでにGoogleはTCP BBRをYouTubeのネットワークで利用しており、従来のパケットロスをベースにした輻輳制御アルゴリズムであるCUBICを用いた場合と比較して、スループットが平均で4％、最大で14％以上改善したことを明らかにしています。 TCP BBRは現在の高速なネットワークに適した輻輳制御アルゴリズム TCP BBRのBBRは「Bottleneck Ba
私が書いた最速のハッシュテーブル – PART 4 | POSTD
要素の削除についても測定してみましょう。ここでも、キーを整数にして3つのテストを、キーを文字列にして3つのテストを行いました。使ったのは4バイト値、32バイト値、1024バイト値です。4バイト値の図は前掲のとおりです。32バイト値の図はほとんど同じなので省略します。1024バイト値の図は以下のようになります。 注釈： 削除 整数キー、1024バイト構造体値 （縦軸）ナノ秒/要素 （横軸）要素の数 大きく違う点は、dense_hash_mapがかなり遅くなったことです。これは、大きな値タイプでテストした他の図の時と同じ問題です。他のテーブルは、単純に要素が削除されたと見なし、デストラクタ（私の構造体ではno-op）を呼び出します。一方、dense_hash_mapは”空の”キーと値のペアでその値を上書きしますが、1024バイトのデータを持っている場合にはそれが大きな操作となるのです。 他に上
「クイックソート」「バブルソート」などのソート・アルゴリズムをフォークダンスで説明する恐るべきムービー集「AlgoRythmics」
たくさんのデータを大小関係に従って、小さい順(昇順)や大きい順(降順)に並び替える作業はソート(整列)と呼ばれ、ソフトウェア・プログラムではよく使われています。このようなソート作業を行うために並び替えの方法を手順化したのが「ソート・アルゴリズム」で、アイデアを理解すると「ほほー、なるほど」と思えるのですが、複雑すぎて理解しづらいものもあります。そんなソート・アルゴリズムの中でも有名で、仕組みを理解しておきたいものばかりを題材に、なんとフォークダンスに合わせてアルゴリズムを表現するムービー集「AlgoRythmics」が公開されており、学習効果があるかどうかは脇に置いて、思わず見入ってしまう魅惑のムービーとなっています。 最も有名なソート・アルゴリズムの一つである「バブルソート」をハンガリーのフォークダンスにのせて表現するのが「Bubble-sort with Hungarian ("Csá
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
xxHash - Extremely fast non-cryptographic hash algorithm
A Scalable Concurrent malloc(3) Implementation for FreeBSD
Amazon.co.jp: アルゴリズム図鑑: 絵で見てわかる26のアルゴリズム: 石田保輝, 宮崎修一: 本
