地形プロシージャル生成 - パーリンノイズアルゴリズム - QiitaDeleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?
ハッシュ値の使い方について - クックパッド開発者ブログ
モバイル基盤グループのヴァンサン(@vincentisambart)です。 先日以下のツイートを拝見しました。 Swift's stdlib moves to randomly seeded hashing: https://t.co/2T5oRYtD8B— ericasadun (@ericasadun) 2018年3月10日 この変更はSwift 4.1にはまだ入りませんが、4.2か5.0に入るはずです。コードレビューでこの変更が問題を起こそうなコードを指摘したことあるので、ハッシュ値のおさらいをする良いタイミングではないでしょうか。 Swiftのことを考えて書いていますが、多くのプログラミング言語にも当てはまります。ハッシュ値はSwiftではhashValueというプロパティが返しますが、多くの言語では単にhashというメソッド・関数が返します。 ハッシュマップ ハッシュ値はハッシュ
Maglev Hashing with Python - yunazuno.log
今更ながら，GoogleのMaglev論文で提案されているMaglev Hashingを手元で実装してみた． Maglev: A Fast and Reliable Software Network Load Balancer Maglev Hashingとは 所謂Consitent Hashの一種．Maglevロードバランサにおけるリアルサーバ選択に使用されている． 上記論文のSection 3.4で詳細が説明されている．NSDI'16での発表スライドも併せて眺めると分かりやすい． Maglev: A Fast and Reliable Software Network Load Balancer | USENIX Slide: https://www.usenix.org/sites/default/files/conference/protected-files/nsdi16_sli
私が書いた最速のハッシュテーブル – PART 3 | POSTD
テーブルを、異なるmax_load_factor()と比較する 先に示した最後のグラフは、私のテーブルとgoogle::dense_hash_mapがmax_load_factorに0.5を使う一方で、std::unordered_mapとboost::multi_indexが1.0を使って動作検証を行っていました。もしかすると他のテーブルも、低いmax_load_factorの値を使えば、より速くなるのではないでしょうか？ それを確かめるため、最初のグラフ（成功したルックアップ）に使ったのと同じベンチマークを実行しました。ただし、どのテーブルもmax_load_factorは0.5に設定しました。そして、テーブルの再割り当ての直前に測定を行いました。もう少し詳しく説明しますが、まずは次のグラフをご覧ください。 注釈： 成功したルックアップの占有率（load factor） 0.5 （縦軸
私が書いた最速のハッシュテーブル – PART 2 | POSTD
素数か2のべき乗か ハッシュテーブルのアイテムをルックアップする際に高負荷なステップが3つあります。 キーをハッシングする キーをスロットにマッピングする 該当スロットのメモリをフェッチする ステップ1は、キーが整数であれば、低負荷になります。単にintをsize_tにキャストするだけです。しかし、文字列のようなタイプのキーの場合は高負荷となります。 ステップ2はよくある整数モジュロ演算です。 ステップ3はポインタの間接参照です。std::unordered_mapの場合は複数のポインタ間接参照となります。 処理の遅いハッシュ関数でなければ、直観的にステップ3が最も高負荷になると考えると思います。しかし、全てのルックアップでキャッシュミスが生じなければ、整数モジュロが最も高負荷な処理となります。現代のハードウェアにおいても整数モジュロは非常に遅いのです。 Intelマニュアル では、整数モ
私が書いた最速のハッシュテーブル – PART 1 | POSTD
結局、やり出したら止まりません。私は以前、” I Wrote a Fast Hashtable（私が書いた高速なハッシュテーブル） “という記事と、それに次いで” I Wrote a Faster Hashtable（私が書いたより高速なハッシュテーブル） “という記事をブログにアップしましたが、今回ついに、最速のハッシュテーブルを書き上げました。これが意味するところは、ルックアップがどのハッシュテーブルよりも速いということです。それに加えて、挿入や削除も（最速とまではいかないまでも）非常に速く行えます。 秘訣は、探索回数の上限を設定したロビンフッドハッシュ法を使用することです。ある要素が、その理想的な位置からX数以上、離れた位置にある場合、テーブルを拡張することで、全ての要素が、その大きなテーブル内において、理想的な位置に近づくようにします。結果的に、このやり方は非常にうまくいきました。
Import APIとFuzzy Hashingでマルウエアを分類する ～impfuzzy～(2016-05-09) - JPCERT/CC Eyes
Top > “マルウェア”の一覧 > Import APIとFuzzy Hashingでマルウエアを分類する ～impfuzzy～(2016-05-09) 一般に、マルウエア検体の調査は、既知のマルウエアかどうかを判別することから始めます。データベース化された多数の既知のマルウエアと調査検体との比較を高速に実行するために、ハッシュ関数をマルウエア検体に施して得られたハッシュ値が利用されます。 ハッシュ関数の中でも、MD5やSHA1などの伝統的なハッシュ関数の場合には、入力データが1ビットでも異なれば、まったく異なるハッシュ値になりますので、完全に同じではないが類似した既知の検体があれば、既知のマルウエアと判定したい場合には役に立ちません。 現在では、カスタマイズされた上で攻撃に使われるマルウエアがほとんどであるため、カスタマイズされた検体を類似していると判断できるようなハッシュ関数が望まれ
#JJUG - Java で最速のハッシュアルゴリズムを求めて
【東京】【聴講者募集】JJUG ナイト・セミナー 「ビール片手にLT&納涼会」の発表資料です。 https://jjug.doorkeeper.jp/events/28182
A Fast, Minimal Memory, Consistent Hash Algorithm ご紹介(システム系論文紹介 Advent Calendar 2014）. - Qiita
(本稿は, システム系論文紹介 Advent Calendar 2014, 12/20 です http://www.adventar.org/calendars/440) 論文は arXiv から取得できます. http://arxiv.org/abs/1406.2294 Jump Consitent Hash と呼ばれる, 分散ストレージ系で有益なハッシュ関数を求めるアルゴリズムです. 現在史上最強のハッシュアルゴリズムのひとつと言えるでしょう. 無性に分散ストレージライブラリを作りたくなってきますね! 共著者の Eric Veach にも注目です. Google を救ったと言われている distinguished engineer です. (G 社のひとは彼の名前を社員名簿データベース? から探してみましょう! 社員番号 20 くらいにあるらしいですよ!) そんな彼がなんと 10 年以
Java8 で java.lang.Object#hashCode() の生成アルゴリズムが変更されていました。 - 地平線に行く
java.lang.Object#hashCode()の性質という記事で書いたのですが、Java の Object#hashCode() の値はただの乱数となっています。 この乱数のアルゴリズムが、Java SE 8 で「線形合同法」から「XORシフト方式」に変更になっていました。 といっても、変更されたのはたった1文字。 VMオプションのデフォルト設定が -XX:hashCode=0 から -XX:hashCode=5 に変わっただけでした。 hotspot-rt Udiff hotspot/src/share/vm/runtime/globals.hpp どういうこと？ もともと、Java の以前の実装*1 *2から、Object#hashCode() のアルゴリズムはVMオプション -XX:hashCode=? で選べるようになっていました。 ですが、デフォルトは長いこと 0(=線形
Locality Sensitive Hashによる類似ベクトル検索を試す - Negative/Positive Thinking
はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関数のこと 高次元データの次元圧縮を行える (P1,P2,r,cr)-sensitiveなHash族とは、 2つの特徴ベクトルp,qについて(P1>P2) ||p-q||P1 ||p-q||>crならPr[h(p)=h(q)] を満たすハッシュ関数h:R^d->U コサイン類似度に対するLSH 2つのk次元ベクトルu,vについて コサイン類似度: u*v / sqrt(|u|*|v|) d個のk次元のランダムベクトルr_iを考え、ハッシュ関数h_i(u)を h_i(u) = 1 (r*u >=0) h_i(u)
Pluto Scarab — Hash Functions
A hash function maps a bit vector onto another, usually shorter, bit vector. The result is uniformly distributed, which means that for an input vector chosen at random, each out bit is equally likely to be 0 or 1 and is not correlated with the other bits (unless the size of the range is not a power of 2 in which case the high bits will show correlations). Typically, m > n and this is why hash func
東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く - imHo
ダイクストラ法が小さなサンプルデータで動いたら、実際のデータを使ってみたくなるのが人情。東京を走る地下鉄のデータでやってみたいと思った。 JavaScriptとPrototype.jsとGoogleMapsAPIとすったもんだしたあげく、なんとか動くものができた。 502 Bad Gateway テストアプリはこちら JavaScriptのソースはここのhtmlに 駅や路線のデータは駅データ．ｊｐのものを使わせてもらいました。 使ったのは東京メトロ＋都営＋山手線 駅（ノード）の数は、同じ駅でも路線ごとで別にカウントして 322 駅同士をつなぐ線路（エッジ）の数は、徒歩や乗換えを含め 912 体感もっさり感じるけど、経路の検索以外のところがかなりかかってる Tips Prototype.js Array.without は超重い、使うな！ Hash.keys で返ってくるキーはすべて文字列に
バグから学ぶ計算機科学 Scalaのハッシュテーブルにおいて並列コレクションのためのコード変更が大量の衝突を引き起こした事例
バグから学ぶ計算機科学 Scalaのハッシュテーブルにおいて並列コレクションのためのコード変更が大量の衝突を引き起こした事例 書いた人: ると 書いた日: 2012年1月21日 はじめに Twitterで「有名なオープンソースソフトで今まであったおもしろいバグを解説した本とかないだろうか」とツイートしたらそれなりに需要があるようでした。そこで先ず隗より始めよという故事にのっとり、死馬の骨としてバグ解説記事を書いてみます。 今回のバグはScala 2.9の標準ライブラリに含まれるmutable.HashSet(ハッシュテーブルを使った重複無しコレクション)のコピーがJavaの標準ライブラリに含まれるHashSetの100倍遅いというバグです。並列コレクションのためにぱっと見問題の無い変更を加えたら思わぬところで影響が出たというものです。 なお、今回はScalaに関するバグですが、Scalaに
ssdeep - Fuzzy hashing program
Introduction ssdeep is a program for computing context triggered piecewise hashes (CTPH). Also called fuzzy hashes, CTPH can match inputs that have homologies. Such inputs have sequences of identical bytes in the same order, although bytes in between these sequences may be different in both content and length. A complete explanation of CTPH can be found in Identifying almost identical files using
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - skarupke/flat_hash_map: A very fast hashtable
Jean-Philippe Aumasson