タグ

algorithmに関するshimookaのブックマーク (62)

  • The Algorithms

    You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert

    The Algorithms
  • 様々なrate limitアルゴリズム - Carpe Diem

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

    様々なrate limitアルゴリズム - Carpe Diem
  • 【Unity】ソートアルゴリズム12種を可視化してみた - Qiita

    はじめに ソートアルゴリズムの学習として、12種のソートアルゴリズムを実装して可視化してみました。 Unityにはあまり関係がなさそうな話題ですが、Unity上で作ったのでUnityタグをつけます。 バブルソート バブルソートのアルゴリズムは以下のような感じです。 配列の要素を最初から最後まで見ていき、順序が逆の要素があれば入れ替える 全ての要素の順序が正しくなるまで 1.を繰り返す. void BubbleSort(int[] a) { bool isEnd = false; int finAdjust = 1; // 最終添え字の調整値 while (!isEnd) { bool loopSwap = false; for (int i = 0; i < a.Length - finAdjust; i++) { if (a[i] < a[i + 1]) { Swap(ref a[i],

    【Unity】ソートアルゴリズム12種を可視化してみた - Qiita
  • 軽い気持ちでLinkedListを使ったら休出する羽目になった話 - Qiita

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

    軽い気持ちでLinkedListを使ったら休出する羽目になった話 - Qiita
  • GitHub - kjdev/php-ext-zstd: Zstd Extension for PHP

    shimooka
    shimooka 2017/04/25
    ZstandardのPHP拡張モジュール
  • Zstandard - Real-time data compression algorithm

    Zstandard is a fast compression algorithm, providing high compression ratios. It also offers a special mode for small data, called dictionary compression. The reference library offers a very wide range of speed / compression trade-off, and is backed by an extremely fast decoder (see benchmarks below). Zstandard library is provided as open source software using a BSD license. Its format is stable a

    shimooka
    shimooka 2017/04/25
    『Zstandard is a real-time compression algorithm, providing high compression ratios.』
  • [テスト] 畳み込みニューラルネットワークを用いたモノクロ動画の自動彩色 | BLOG | Nao Tokui / 徳井直生

    遅ればせながら… 2016年もよろしくお願いします. 今年のお正月、元旦から体調を崩してしまったために期せずして寝正月となってしまいました。その間、ベッドに横になりながら、なんとなくNHK BSを見ていたのですが、「映像の世紀」のデジタルリマスター版の再放送に釘付けになってしまいました。気づいたら元旦はほとんどぶっ通しで見ていたように思います。 その中で感じたのは、ぼやけた白黒映像からクリアなカラー映像になるだけで、歴史映像の視聴体験が体感として大きく異なるということです。山に囲まれた別荘で愛犬と戯れるヒトラー。映画プラトーンさながらにベトナムの村を焼き払うアメリカ兵。鮮明なカラー映像として目の当たりにすることで、歴史が「遠い昔のこと」ではなく、いまにつながる自分ごととして感じられる、そんな風に思いました。昨今憲法改正などをめぐっての議論がきなくさくなりつつある昨今ですが、もし仮に太平洋戦

    [テスト] 畳み込みニューラルネットワークを用いたモノクロ動画の自動彩色 | BLOG | Nao Tokui / 徳井直生
  • リバーシの作りかた – 2dgames.jp

    1.はじめに 今回はリバーシの作り方を解説します。 リバーシは、プログラム初心者でも簡単に作れるわりに、盤面の扱い・CPUの思考ルーチンなどにこだわれば、凝ったプログラムができる、なかなか面白い題材です。 2.盤面の設計 まず、リバーシの盤面の設計をします。クラス図としてはこんな感じです。 石であるStoneクラスを見てみます。属性としては、とりあえず「色」の属性があれば充分です。(サンプルのように、ひっくり返した場合に飛び跳ねるような処理を行いたい場合には、座標の情報などが必要になります) 他に、スタティックな属性として、 BLACK NONE WHITE WALL というものを持っています。 ポイントは、BLACKが「-1」でWHITE「1」となっているところです。これは、reverseメソッドなどで石を反転させる場合、-1をかけるだけでよいため、このようにしています。 もう一つのポイ

    リバーシの作りかた – 2dgames.jp
  • 華麗なる因数分解:FREAK攻撃の仕組み - ぼちぼち日記

    1. はじめに ちょうど今朝 OpenSSLをはじめとした様々なTLS実装の脆弱性の詳細が公表されました。 この InriaとMSRのグループは以前からTLSのセキュリティに関して非常にアクティブに調査・検証をしているグループで、今回も驚きの内容でした。 このグループは、TLSのハンドシェイク時の状態遷移を厳密にチェックするツールを開発し、様々なTLS実装の脆弱性を発見・報告を行っていたようです。 特にFREAKと呼ばれるOpenSSLの脆弱性(CVE-2015-0204)に関しては、ちょうど修正直後の1月初めに Only allow ephemeral RSA keys in export ciphersuites で見ていましたが、具体的にどのように攻撃するのかさっぱりイメージできず、あのグループだからまた超絶変態な手法だろうが、まぁそれほど深刻じゃないだろうと見込んでいました。 今回

    華麗なる因数分解:FREAK攻撃の仕組み - ぼちぼち日記
  • いまさらgrepが10倍高速化したのはなぜか – はむかず!

    最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事:grepコマンド最新版、”-i”で10倍の高速化 家のリリースノート:grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション(–ignore-case、つまり大文字小文字を区別しないオプション)をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか?逆を言えば今までなぜそんなに遅かったのか? そもそも、多くの日人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく

    shimooka
    shimooka 2014/02/25
    『マルチバイトロケールによっては、「大文字→小文字」または「小文字→大文字」の変換をすると文字のバイト数が変わってしまうことがある』な、なんだってー!
  • Deflate (gzip) のアルゴリズムを視覚化してみた

    のような感じにエンコードされることが分かります。 自分の好きなデータで試すことができて便利!という話でした。 PS. 以下は実行結果です。 % make % gzip < alice.txt > alice.txt.gz % ./puff -10 alice.txt.gz puff() succeeded uncompressing 1328 bytes 8 compressed bytes unused inpos=406,inbits=224,outpos=0,outbytes=45 41 6c 69 63 65 20 77 61 73 20 62 65 67 69 6e 6e 69 6e 67 20 74 6f 20 67 65 74 20 76 65 72 79 20 74 69 72 65 64 20 6f 66 20 73 69 74 74 A l i c e w a s b

  • ユーザーのパスワードを安全に保管する方法について - 11月 - 2013 - ソフォス プレス リリース、セキュリティニュース、ソフォスに関するニュース記事 - Sophos Press Office | Sophos News and Press Releases

    ※この記事は社サイト 「Naked Security」掲載の記事を翻訳したものです※ by Paul Ducklin on November 20, 2013 この記事に関する最新の更新情報は Naked Security 掲載記事をご確認ください。 読者の方は、Adobe 社で 2013 年 10 月に発生したデータ侵害のインシデントについてはご存じでしょう。 これは、1 億 5 千万件のレコードが漏えいした史上最大級のユーザー情報データベースに関するインシデントであるだけではありません。今回のインシデントから別の問題も見えてきました。 漏えいしたデータから、Adobe 社がユーザーのパスワードを不適切な方法で保管していたことが明らかになりました。同社の利用した方法よりも格段に安全でパスワードを保管する方法はあります。またそれが、決して難しくないことを考えると、セキュリティの観点からす

  • PageRankアルゴリズムを使った人事評価実験 | 株式会社サイバーエージェント

    2-2-1.一般的な360度評価による評価方法 問題点 一般的に評価プロセスが公開されていないため、最終評価までのプロセスが不透明である 全員が全員を評価するのは多数の社員がいる場合は不可能である ランダム抽出によるお互いの評価を行うと、まったく違う専門分野を評価したり、まったく関わりあいのない人を評価することになり精度が下がる 2-2-2.専門分野での評価者による評価方法 問題点 *評価者になる人材の不足 高い専門スキル、会社とのビジョンマッチ、メンバーからのその専門分野での高い信頼の全てを備えている人材が専門分野毎に必要。 さらに、評価の納得性を保つためにはメンバーからの信頼がある人材ではないと評価できない。 *評価者によって評価ポイントの違いがある 同じ分野の技術者でも、スキルの価値をどこに置いているかというスタンスの違いから評価ポイントにゆらぎが発生する。 さらに評価者自体

  • レインボーテーブル – パスワード流出への対策を根本から理解する。 | DevelopersIO

    はじめに 先日、Yahooに不正アクセスがあり、ユーザ名とパスワードを抽出しようとするプログラムが見つかったそうです。 そんな事もありまして、今回は少し趣を変えて、レインボーテーブルのお話をしたいと思います。 今まで概念は知っていても使う事がなかった技術ですが、この機会に詳しく知っておくのも良いかと思います。 レインボーテーブルは、ハッシュから平文を得るためのアルゴリズムの一つですが、実際にそのアルゴリズムで使用されるテーブルの事をいうこともあります。 今回はレインボーテーブルというアルゴリズムについて掘り下げて行きたいと思います。 ハッシュと平文のセットのテーブル レインボーテーブルの基的な考え方は、非常にシンプルで、このハッシュだったら平文はこれですよというのを事前に用意しておきましょうという事です。 例えば人気パスワードランキング2012より、上位5件のパスワードに付いてもしこのハ

  • すらるど 「これはグーグルが欲しがるな」東工大の開発したネットから情報を取得して学習するアルゴリズムに海外も騒然

    スライス・オブ・ワールド、略してすらるど。旧タイトル『海外の反応とか』。海外の反応をヘッポコな翻訳力で紹介しています。 東京工業大学 長谷川修准教授のグループの開発した機械学習アルゴリズム「SOINN」は画像に対してキーワードを与えてやるとネットでそのキーワードを検索して特徴を学習し、似た画像でも以前見せた画像と同じものだと認識するようになります。 この技術を使えば画像だけでなく音や動画からも特徴を拾って学習することが可能になるとのこと。 この動画を見た海外の反応です。 参考リンク:diginfo.tv 人工脳「SOINN」を用いて、ネット上の画像から高速機械学習 #DigInfo SOINN artificial brain can now use the internet to learn new things #DigInfo ↓この動画につけられたコメント ●オーストラリア 機械が

    shimooka
    shimooka 2013/05/08
    外人ホントにスカイネット好きだな
  • TechCrunch | Startup and Technology News

    Autonomous trucking company TuSimple last week successfully completed a fully autonomous semi-truck run on public roads in China without a human present in the vehicle and without human intervention. Shoppable Business wants to make it easier for businesses in the Philippines to source and procure branded products and other inventory, with an emphasis on making sure products are authentic. The B2B

    TechCrunch | Startup and Technology News
    shimooka
    shimooka 2013/03/01
    『この徹底的で容赦のない圧縮アルゴリズムは、エントロピーモデルの反復と最短経路アルゴリズムを駆使し、可能なすべてのデフレート表現のグラフ中にビットコストの低い経路を見つける』なるほどわからん
  • diffの動作原理を知る~どのようにして差分を導き出すのか | gihyo.jp

    UNIXの基的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS(Longest Common Subsequence) 2つの要素列の最長共通部分列 SES(Shortest Edit Script) ある要素列を別の要

    diffの動作原理を知る~どのようにして差分を導き出すのか | gihyo.jp
  • MD5やSHAの代替として利用可能な新たなハッシュ化技術「BLAKE2」登場 | OSDN Magazine

    12月21日、ハッシュアルゴリズム「BLAKE2」とそのCおよびC#実装が公開された。BLAKE2はMD5やSHAといったハッシュアルゴリズムの代替として利用できるもので、セキュリティに優れ高速に動作するのが特徴という。 BLAKE2は、与えられた入力に対し指定されたビット長のハッシュ値を生成するためのアルゴリズム。既存のハッシュアルゴリズムであるMD5よりもセキュリティに優れ、かつSHAよりも高速に処理を実行できるのが特徴という。 同様のハッシュアルゴリズムとしてSHA-2やその後継となるSHA-3(Keccak)などがあるが、BLAKE2はSHA-3アルゴリズムの候補の1つであったBLAKEを改良したものとなっている。BLAKE2はSHA-3やBLAKEと同等のセキュリティを備えつつ、64ビット環境においてMD5と同等の速度で動作し、SHA-2やSHA-3と比べて33%少ないメモリで動

    MD5やSHAの代替として利用可能な新たなハッシュ化技術「BLAKE2」登場 | OSDN Magazine
  • なぜBTreeがIndexに使われているのか - maru source

    この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。 RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル 1 2 3 4 5 CREATE TABLE user ( id INT UNSIGNED NOT NULL AUTO_INCREMENT, name VARCHAR(255) NOT NULL, PRIMARY KEY (id) )ENGINE=InnoDB; idカラムにIndex(PRIMARY KEY)を張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます(特にレコードが多くなった時) ではなぜIndexを貼ると検索が早くなるんでしょう?? Indexとはその名の通り索引を意味します。特定のカラム

  • クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた

    集合知プログラミング を読んでいたら、K-means 法(K平均法)の説明が出てきました。 K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。 クリックすると1ステップずつ動かすことができます。クラスタの数や点の数を変更して、Restart を押すと好きなパラメータで試すことができます。 こうやって1ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。 (追記) HTML5 版の K-means 法を D3.js でビジュアライズしてみた も作成しました。Flash を表示できない環境ではそちらをご覧ください。 K-means 法とは K平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージに

    クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた