様々なrate limitアルゴリズム - Carpe Diem
概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。 ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。 Leaky bucket Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。 下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。 ref: What is the difference between token
HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ - エンジニアHub｜若手Webエンジニアのキャリアを考える！
HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ 過去、HashDosの影響を受けたRuby。言語開発者はいかにしてこうした問題に対応してきたのでしょうか。コミッターである卜部氏の貴重な記録を公開します。 2011年の末頃、HashDoSという脆弱性が公表され、Rubyもこの影響を受けた。本稿の筆者である卜部昌平（うらべ・しょうへい／@shyouhei／以下、卜部）は、報告当初からRuby側のチームメンバーとしてプログラム本体の修正を担当した。以下はその記録である。言語開発者たちが普段どのようなことを考え、どういった技術を用いて開発やバグフィックスを行っているのか。その概要を知ってもらえれば幸いだ。 オブジェクト指向スクリプト言語 Ruby HashDoSの概要 なぜ約6年後の今、修正内容を公開するに至ったか？ 前史：すでに内包されていたリスク
エレベータに見るアルゴリズムの性能と公平性のバランス｜Rui Ueyama
現実世界でもコンピュータの中でも、何らかの性能指標だけを追求すると参加者にとって極端に不公平になってしまうことがある。例えばエレベータとHDDは共通点がありそうに思えないが、この2つは性能特性的にとてもよく似ていて、リーズナブルな性能と公平性を両立させるために同じ制御方法が使われている。これについてちょっと説明してみよう。 1基しかない場合のエレベータの動き方は単純だ。一度上に動き出すと、上で待ってる人や降りる人がいる限り上昇し続ける。同じように、一度下に動き出すと、下で待っている人や降りる人がいる限り下降し続ける。これ以外の動き方をするエレベータはまず存在しないので、これが唯一の制御方法のように思えるけど、別にこうしなければいけないというルールはない。 エレベータの平均待ち時間を最適化することを考えてみよう。そうすると、一方向に動き続ける代わりに、エレベータが現在存在する階に一番近い人の
Quine Tweet: 自分自身へのリンクを持つ再帰的ツイート - まめめも
This tweet is recursive. https://t.co/bZISaPd3Ts— Quine Tweet (@quine_tweet) 2016年9月19日 「このツイートはありません」となっていますが、URL をクリックすれば自分自身に飛べます。 以下、このツイートが生まれるまでの経緯を長々と書きます。 問題設定 そのツイート自身の URL を埋め込んだツイートを作ります。ツイートの URL はツイートをした後でないと決まらないし、ツイート文面を後から更新する手段はない（と思う）ので、単純ですが意外に難しい問題です。 調査 ご存知のように、現在のツイートの URL は次のような形式です。 https://twitter.com/<username>/status/<id>username はそのままなので、id を事前に予測できれば解決です。*1 調べてみるとこの id
Chainerで顔イラストの自動生成 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? PFNのmattyaです。chainerを使ったイラスト自動生成をやってみました(上の画像もその一例です)。 20日目の@rezoolabさんの記事(Chainerを使ってコンピュータにイラストを描かせる)とネタが被っちゃったので、本記事ではさらに発展的なところを書いていきたいと思います。一緒に読んでいただくとよいかと。 概要 Chainerで画像を生成するニューラルネットであるDCGANを実装した→github safebooruから顔イラストを集めてきて学習させた 学習済みモデルをconvnetjsで読み込ませて、ブラウザ上で動くデ
ハッシュは頻繁に参照する値を最後に入れると高速 - まめめも
明日から RubyKaigi なので、ちょっとした小ネタを一つ。 例えば、0 から 9999 までをハッシュに順に入れます。 h = {} 10000.times do |n| h[n] = true end このとき、h[9998] や h[9999] は、h[0] や h[1] より高速です。 どのくらい高速かというと、 1_000_000_000.times { h } # 40.8 sec (ループ自体の速度) 1_000_000_000.times { h[9999] } # 57.2 sec 1_000_000_000.times { h[0] } # 89.1 sech[0] は 89.1 - 40.8 = 48.3 nsec 、h[9999] は 57.2 - 40.8 = 16.4 nsec ということになります。なんと 3 倍も速い。*1 なぜこんなことが起きるのか ハ
クーポンコードの打ち間違えを防ぐために工夫した話 - クックパッド開発者ブログ
こんにちは。会員事業部ビジネス開発グループの高田です。 クックパッドは今年、株主優待制度として、プレミアムサービス一年間無料クーポンを贈呈しました。本エントリではクーポンコードを打ち間違えて、意図せず他の人のクーポンコードを使用するのを防ぐために工夫した話をご紹介します。 はじめに クーポンコードは入力のしやすさを優先して数字だけの文字列にしました。はじめは rand 関数を使って生成しようとしていたのですが、数字の打ち間違えや順序間違いで、意図せず誤使用してしまうのを防ぐためにチェックサムを加えるのがいい、と同僚から助言をもらいました。 いくつか調べて見たところ、Luhn アルゴリズムが上記を満たしていたので利用することにしました。 Luhn アルゴリズムの利用 Luhn アルゴリズムとは、誤り検出のためのチェックサム符号で、1 桁の間違いや隣接する数字の順序間違いを検出できるという特徴
Latent Dirichlet Allocation(LDA)を用いたニュース記事の分類 | SmartNews開発者ブログ
株式会社ゴクロの中路です。 以前のベイズ分類をベースにしたSmartNewsのチャンネル判定で触れたように、SmartNewsで配信する記事を「スポーツ」「エンタメ」「コラム」のようなチャンネルに分類しているのは、人ではなく機械です。そのアルゴリズムとして前回ご紹介したのは「ナイーブベイズ分類器」ですが、記事の分類を行う手法は、他にも様々なものがあります。その中で今回はLatent Dirichlet Allocation(以下LDA)について、先日東京大学の博士課程の皆さんと、社内で合同勉強会を行った際に作成した資料をベースにご紹介します。 LDAでできることの例 前回ご紹介したナイーブベイズ分類器を構築する際には、すでにトピックのラベルが付けられた文章を、学習データとして用意する必要がありました。 一方、LDAの場合は、 東京でサッカー大会が開催された。xx選手のゴールが圧巻であった。
PageRankアルゴリズムを使った人事評価実験 | 株式会社サイバーエージェント
2-2-1.一般的な360度評価による評価方法 問題点 一般的に評価プロセスが公開されていないため、最終評価までのプロセスが不透明である 全員が全員を評価するのは多数の社員がいる場合は不可能である ランダム抽出によるお互いの評価を行うと、まったく違う専門分野を評価したり、まったく関わりあいのない人を評価することになり精度が下がる 2-2-2.専門分野での評価者による評価方法 問題点 *評価者になる人材の不足 高い専門スキル、会社とのビジョンマッチ、メンバーからのその専門分野での高い信頼の全てを備えている人材が専門分野毎に必要。 さらに、評価の納得性を保つためにはメンバーからの信頼がある人材ではないと評価できない。 *評価者によって評価ポイントの違いがある 同じ分野の技術者でも、スキルの価値をどこに置いているかというスタンスの違いから評価ポイントにゆらぎが発生する。 さらに評価者自体
ソーシャルゲームにレコメンドエンジンを導入した話
CEDEC2013にて発表させていただいた内容の一般公開用スライドです。 ネットサービスの基本中の基本とされるKPI 「DAU（Daily Active Users）」。売上の分解にも使いやすく、複数のサービスを比較するときには必須の指標です。しかし、運営の現場では「ノイズが多くて使いにくい」「経営者（えらい人）にサービスの状況の誤解を与える」という扱いを受けがちな指標でもあります。 セッションの内容 : 本セッションでは、ソーシャルゲームのDAUを題材に、測り方にほんの少し工夫（工夫の方法は汎用的なものです）を加えることで、DAUを現場の肌感覚にもあう指標に変身させる方法、特に、運営期間が長くなったサービスにおける課題抽出に活用する方法をご紹介します。 発表日時 : 2013年8月23日(金) 16:30～17:30 詳細URL : http://cedec.cesa.or.jp/201
ランダムソート(笑)とは - 西尾泰和のはてなダイアリー
誰が「ソートするときに比較関数に『ランダムに1か-1を返す関数』を与えたらシャッフルできる」って言い出したのかしらないけど、真に受ける方も真に受ける方だと思う。 たとえばソート関数が下のような「リストの先頭の値をピボットにしてそれより大きいものと小さいものに振り分けるクイックソート」だったとする。比較関数の所はランダムにしてある。 >>> def quicksort(xs): from random import random if len(xs) < 2: return xs pivot = xs[0] left = [] right = [] for x in xs[1:]: if random() < 0.5: left.append(x) else: right.append(x) return quicksort(left) + [pivot] + quicksort(right
イロレーティング - Wikipedia
イロレーティング (Elo rating) とは、対戦型の競技（2人のプレイヤーまたは2つのチームが対戦して勝敗を決めるタイプの競技）において、相対評価で実力を表すために使われる指標の一つ。数学的裏付けのある最も著名なレーティングシステムである。 イロレーティングは、もともとチェスの実力を表すために考案されたものだが、様々な競技に応用されている。具体的には 国際チェス連盟の公式記録 日本アマチュア将棋連盟の公式記録 将棋や囲碁などのオンライン対局場 サッカーのFIFAランキング ラグビーなどの一部の競技団体のランキング 対戦型オンラインゲームのランキングやマッチング などでイロレーティング、あるいはイロレーティングを改変したレーティングシステムが採用されている。一部の競技では単にレーティングと呼ぶこともある。 なお、「イロ」とは、考案者であるアルパド・イロ（ハンガリー生まれのアメリカ人物理
hirax.net::「童貞喪失機会問題」と「ページランク (PageRank) 」
最新記事(inside out)へ | 年と月を指定して記事を読む（クリック!） / 2001/ 2002/ 2003/ 2004/ 2005/ 2006/ 2007/ 2008/ 2009/ 2010/ 2011/ 2012/ 2013/ 2014/ 2015/ 2016/ 2017/ 2018/ 2019/ 2020/ 2011年4月 を読む << 2011年5月 を読む >> 2011年6月 を読む 「異性間（時には同性間の）評価」ということを主題にした「恋と童貞 ２号」の「童貞喪失機会問題に関する試論」を読みながら感じたのは、「結局、これはページランク (PageRank) が対象とする問題とよく似ている」ということでした。 女性の評価対象は、大きく分けて二つある。当該男性からの情報発信と当該男性の評判である。…当該男性の評判は、個々人の当該男性に対する評価の集合であると感柄れる
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
A Tour through the Visualization Zoo - ACM Queue
May 13, 2010 Volume 8, issue 5 PDF A Tour through the Visualization Zoo A survey of powerful visualization techniques, from the obvious to the obscure Jeffrey Heer, Michael Bostock, and Vadim Ogievetsky, Stanford University Thanks to advances in sensing, networking, and data management, our society is producing digital information at an astonishing rate. According to one estimate, in 2010 alone we
[O] 神嶌敏弘「推薦システムのアルゴリズム」
« 脳年齢テスト 整数の瞬間記憶 | トップページ 神嶌敏弘「推薦システムのアルゴリズム」 [日記] 神嶌敏弘さんの「推薦システムのアルゴリズム」を、人工知能学会誌を借りて通読しはじめたところです。 - 人工知能学会誌：目次 -- http://www.ai-gakkai.or.jp/jsai/journal/contents/ - Ｖｏｌ．２２ Ｎｏ．１（２００７年１月） - Ｖｏｌ．２３ Ｎｏ．１（２００８年１月） - Ｖｏｌ．２３ Ｎｏ．２（２００８年３月） に掲載されており、全部で40ページ以上。 なんで急に読み始めたのかというと、ある疑問が湧いたからです。 以下のようなコンテストが開催され、人工知能学会も協賛してるみたいなので、楽しいかもなと興味をもったのです。 - リコメンデーションコンテスト -- http://kgmod.jp/contest/ # 参
Ywcafe.net
Ywcafe.net This Page Is Under Construction - Coming Soon! Why am I seeing this 'Under Construction' page? Related Searches: fashion trends All Inclusive Vacation Packages Best Mortgage Rates find a tutor Credit Card Application Trademark Free Notice Review our Privacy Policy Service Agreement Legal Notice Privacy Policy|Do Not Sell or Share My Personal Information
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Maze Algorithms
IBM Developer
http://atnd.org/events/1840
