[B! algorithm][performance] lepton9のブックマーク

lepton9 id:lepton9

algorithmとperformanceに関するlepton9のブックマーク (13)

データベースでユニークキーにUUIDを使うメリットは何ですか？連番やタイムスタンプまたは複合などではいけないのでしょうか？どうも視認性が悪く使いにくく感じますし連番でも衝突しない気もします。
回答 (7件中の1件目) まずはUUID及びその対案として用いられる連番(自動採番)のメリット・デメリットを整理します。 (タイムスタンプキーや複合キーなどもその効率性から設計上有用なシーンはありますが、比較から除外します。) * UUIDを使うことのメリット * * データベースにSQLを送信する前からアプリケーションレイヤーでIDを生成できる。 * * トランザクション処理を実装しやすい場合がある。 * IDを推測しにくい。リソースが列挙可能ではない。 * UUIDを使うことのデメリット * * レコード・インデックスサイズが増加する。 * * ...
lepton9 2024/05/16
db

performance

algorithm
リンク
MySQLでプライマリキーをUUIDにする前に知っておいて欲しいこと | Raccoon Tech Blog [株式会社ラクーンホールディングス技術戦略部ブログ]
株式会社ラクーンホールディングスのエンジニア/デザイナーから技術情報をはじめ、世の中のためになることや社内のことなどを発信してます。 bashパフォーマンスMySQLInnoDB DB設計インデックスこんにちは、羽山です。今回は MySQL のプライマリキーに UUID を採用する場合に起きるパフォーマンスの問題を仕組みから解説します。 MySQL(InnoDB) & UUID のパフォーマンスについては各所でさんざん議論・検証されていますが、論理的に解説した記事が少なかったり一部には誤解を招くようなものもあるため、しっかりと理由から理解するための情報として役立つことができればと思っています。 UUID と比較される古き良き昇順/降順のプライマリキーはというと、 MySQL の InnoDB において良いパフォーマンスを出すために縁の下の力持ちのような働きをしてくれているケースが実は少な
lepton9 2021/08/31
performance

algorithm

db
リンク
CPUとGPUのマルチスレッディングの違いについて - arutema47's blog
"Locality is efficiency, Efficiency is power, Power is performance, Performance is King", Bill Dally マルチスレッディングとは？ CPUとGPUのマルチスレッディングの違いをブログにまとめていたけど例によって誰も興味なさそう— arutema47 (@arutema47) 2021年8月16日つぶやいたら読みたい方が多そうだったので完成させました。マルチスレッディングとはメモリ遅延を隠蔽しスループットを上げるハードウェアのテクニックです。ただCPUとGPUで使われ方がかなり異なるため、その違いについて考えてみる記事です。（SIMDについて並列プログラミングの観点から触れるべきでしたが、時間無いマルチスレッディングに注目するため初版では省きました。）本記事について本記事はCPUとG
lepton9 2021/08/28
performance

algorithm

hardware

gpu
リンク
シンプルかつ高速な文字列照合アルゴリズムを紹介します - エムスリーテックブログ
こんにちは！エンジニアリンググループマルチデバイスチーム新卒1年目の小林です。エムスリーでは、2週間に1度、Tech Talkという社内LT会（現在はリモートで）が開催されています。これは、とある回の発表テーマリストです。 Tech Talkのとある回の発表テーマリストこのように、最近エムスリーでは文字列が流行っている（？）ようなので、その勢いに乗って私も文字列照合アルゴリズムについて書きたいと思います！（業務とは全然関係ない話です） Knuth-Morris-PrattやBoyer-Mooreアルゴリズムは解説記事がたくさん出ていると思うので、この記事ではシンプルかつ高速なQuick-SearchとQuite-Naiveアルゴリズムについて説明し、速度比較を行った結果についてご紹介します。文字列照合アルゴリズムとはテキストとパターンという文字列が与えられたときに、中に出現す
lepton9 2020/09/28
algorithm

search

performance

programming
リンク
様々なrate limitアルゴリズム - Carpe Diem
概要インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入悪意ある人物からの攻撃クライアントのバグに依る大量リクエストなど、本来想定していた以上のトラフィックが来ることはよくあります。単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。 Leaky bucket Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。 ref: What is the difference between token
lepton9 2019/11/11
algorithm

performance

development
リンク
軽い気持ちでLinkedListを使ったら休出する羽目になった話 - Qiita
ざっくり言うとリスト構造のデータに対してランダムアクセスはしちゃだめだぞ。お兄さんとの約束だ！発端数年前に他部署の支援で作ったJavaのシステムに、ちょっとデカめのデータを突っ込んだらありえないほど遅いので助けてくれ、と連絡が入った。まぁクエリとかインデックスをちょっと見れば直るっしょ・・・と鼻をほじりながら支援に向かった。処理内容遅い部分の処理は以下のようなものであった。処理対象のデータをListで受け取る。それをforループで1件ずつ前処理する。処理結果をオブジェクトに格納し、ORマッパーでDBにINSERTする。これだけ？そう、これだけだ。並列処理なんて高級なことはもちろんやってない。インフラ調査処理中のサーバのようすを調査する。今回のインフラは典型的な3層3サーバ構成。 WEBサーバはなにもかもが余裕。 APサーバではCPUを1つ使い切っている。 14コア
lepton9 2018/02/19
programming

performance

java

algorithm
リンク
ID生成大全 - Qiita
セッションIDやアクセストークン、はたまた業務上で使う一意の識別子など、いろんなところで一意のIDを生成しなきゃいけないケースが存在します。そこで世間で使われているIDの生成方法について調べてみました。選択基準 ID生成における要求として、以下の観点が上げられるかと思います。生成の速度大量にデータを短期間で処理し、それらにIDを付与する場合、ID生成そのものがボトルネックとなることがあります。推測困難性 IDを機密情報と結びつける場合、IDを改ざんされても、機密データが見れないようにできている必要があります。順序性採番した順にデータをソートする必要がある場合は、IDがソートキーとして使えないといけません。それぞれについて各生成手段を評価します。 ID生成の手段データベースの採番テーブル採番用のテーブルを作り、そこで番号をUPDATEしながら取得していくやりかたです。古い
lepton9 2017/12/01
performance

algorithm

db
リンク
mixi Engineers’ Blog » スマートな分散で快適キャッシュライフ
今日は以前のエントリーで書くと述べたConsistent Hashingに関して語らせて頂こうかと思います。ただしConsistent Hashingはセミナーやカンファレンスなどでかなり語られていると思いますので、コンセプトに関しては深入りせず、実用性に着目したいと思います。問題定義分散されたキャッシュ環境において、典型的なレコードを適切なノードに格納するソリューションはkeyのハッシュ値に対しmodulo演算を行い、その結果を基にノードを選出する事です。ただし、このソリューションはいうまでもなく、ノード数が変わるとキャッシュミスの嵐が生じます。つまり実世界のソリューションとしては力不足です。ウェブサイトのキャッシュシステムの基本はキャッシュがヒットしなかったらデータベースにリクエストを発行し、レコードが存在したらキャッシュしてクライエントに返すという流れです。ここで問題なのが一瞬
lepton9 2017/06/28
performance

algorithm
リンク
計算量と僕とWeb開発 / computational complexity and I and Web
Beyond Prompts: Building Intelligent Applications with Genkit and the Model Context Protocol
lepton9 2016/07/10
performance

algorithm

db
リンク
Golangの新しいGCアルゴリズム Transaction Oriented Collector（TOC）
http://golang.org/s/gctoc Goの新しいGCのProposalが出た．まだProposal段階であり具体的な実装はないが簡単にどのようなものであるかをまとめておく． GoのGCはGo1.5において単純なStop The World（STW）からConcurrent Mark & Sweepへと変更され大きな改善があった（詳しくは“GolangのGCを追う”に書いた）．先の記事に書いたようにGo1.5におけるGCの改善は主にレイテンシ（最大停止時間）に重きが置かれいた．数値目標として10msが掲げられGo1.6においては大きなヒープサイズ（500GB）においてそれを達成していた． GCの評価項目はレイテンシのみではない．スループットやヒープの使用効率（断片化の対処）なども重要である．Go1.6までのGCではそれらについて大きく言及されていなかった（と思う）．例えばスル
lepton9 2016/06/30
golang

algorithm

performance
リンク
前置インクリメント vs 後置インクリメント | 闇夜のC++
後置インクリメントにはひと目で遅くなりそうな処理が見て取れますね。前置インクリメントがインクリメント処理後、単純に自身の参照を返すのに対し、後置インクリメントではインクリメント前に一時オブジェクトの生成、そしてインクリメント後にはその前に生成した一時オブジェクトを値で返しています。前置と後置では、単純にオブジェクトをコピーして返す分、普通に考えたら後置の方が遅いよね。というのが従来の認識でした。「C++ Coding Standards -101のルール、ガイドライン、ベストプラクティス」の中でも、特に後置インクリメントの必然性が無い時は迷わず前置インクリメントを使うことが推奨されてきました。元の値を必要としないときは前置形式の演算子を使おう＿＿C++ Coding Standards (p50) 新たな主張「ゲームエンジン・アーキテクチャ第二版」の中の一節を紹介します。しか
lepton9 2015/04/17
c++

programming

performance

algorithm
リンク
pixivでBloomFilterを使うためにやったこと - pixiv inside [archive]
こんにちは。最近はAndroidアプリ開発に入門しました、@edvakfです。 pixivではキャッシュ兼汎用KVSとしてKyotoTycoon (KT)を使用しており、頻繁にアクセスされるキーはアプリケーションサーバー内のAPC（PHPのshared memory cacheです）にもキャッシュすることで多段化しています。このような構成の弱点として、「ほとんどの場合は値が無いけど毎回存在確認が必要なキー」の場合に前段にキャッシュが無くて毎回後段にまで問い合わせなければいけないという問題があります。ネガティブキャッシュ（値がないことをキャッシュする）を使うという手もありますが、問い合わせるキーの数が膨大になってくると現実的ではありません。 pixivでは、作品に付いている最大10個のタグについて、ピクシブ百科事典に記事があるかどうかを判定する必要がありました。これに加え、最近ではBOOT
lepton9 2014/07/23
algorithm

performance

development
リンク
pt&Goroutines
pt(the_platinum_searcher) を高速化するために Goroutines まわりで試したことを発表しました。 http://connpass.com/event/6370/
lepton9 2014/06/01
golang

search

performance

algorithm
リンク
1