軽い気持ちでLinkedListを使ったら休出する羽目になった話 - Qiita
ざっくり言うと リスト構造のデータに対してランダムアクセスはしちゃだめだぞ。お兄さんとの約束だ！ 発端 数年前に他部署の支援で作ったJavaのシステムに、ちょっとデカめのデータを突っ込んだらありえないほど遅いので助けてくれ、と連絡が入った。 まぁクエリとかインデックスをちょっと見れば直るっしょ・・・と鼻をほじりながら支援に向かった。 処理内容 遅い部分の処理は以下のようなものであった。 処理対象のデータをListで受け取る。 それをforループで1件ずつ前処理する。 処理結果をオブジェクトに格納し、ORマッパーでDBにINSERTする。 これだけ？ そう、これだけだ。並列処理なんて高級なことはもちろんやってない。 インフラ調査 処理中のサーバのようすを調査する。今回のインフラは典型的な3層3サーバ構成。 WEBサーバはなにもかもが余裕。 APサーバではCPUを1つ使い切っている。 14コア
Exponential Backoff And Jitter | Amazon Web Services
AWS Architecture Blog Exponential Backoff And Jitter Update (May 2023): After 8 years, this solution continues to serve as a pillar for how Amazon builds remote client libraries for resilient systems. Most AWS SDKs now support exponential backoff and jitter as part of their retry behavior when using standard or adaptive modes. Consequently, this pattern can be leveraged without having to incorpora
Red Blob Games: Hexagonal Grids
Mar 2013, updated in Mar 2015, Apr 2018, Feb 2019, May 2020, Oct 2021 This guide will cover various ways to make hexagonal grids, the relationships between different approaches, and common formulas and algorithms. I've been collecting hex grid resources[1] for over 25 years. I wrote this guide to the most elegant approaches that lead to the simplest code, starting from the guides by Charles Fu[2]
TCP Performance problems caused by interaction between Nagle’s Algorithm and Delayed ACK
TCP Performance problems caused by interaction between Nagle’s Algorithm and Delayed ACK Stuart Cheshire 20th May 2005 This page describes a TCP performance problem resulting from a little-known interaction between Nagle’s Algorithm and Delayed ACK. At least, I believe it’s not well known: I haven’t seen it documented elsewhere, yet in the course of my career at Apple I have run into the performan
Lamport timestamp - Wikipedia
The Lamport timestamp algorithm is a simple logical clock algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and conceptually provide a starting point for the more advanced vector clock method. The algorit
巡回冗長検査 - Wikipedia
巡回冗長検査（じゅんかいじょうちょうけんさ、英: Cyclic Redundancy Check, CRC）は、誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われている。送信側は定められた生成多項式で除算した余りを検査データとして付加して送信し、受信側で同じ生成多項式を使用してデータを除算し、その余りを比較照合することによって受信データの誤り・破損を検出する。 デジタル回路で簡単に実装でき、数学的にも分析が容易であり、また、ビットのランダム誤りやバースト誤りを検出できるので、HDLC手順やCSMA/CD方式などにおいて誤りチェック・伝送路ノイズチェックによく使われている。パリティや単純な加算によるチェックサムに比べ検出精度が高く、その点では高級なチェックサムと言える。単純なチェックサムと同じく、データの改竄に対する耐性はない。 W・ウェスレイ・ピーターソンが発明し
Promise Pipelining
In a conventional RPC system, each of the three calls on the left requires its own separate round trip. Typically these would be chained, causing the sequence as a whole to require three sequential round trips. Even when making maximal use of available parallelism, the "c(...)" message could not be sent until both "a()" and "b()" had returned, resulting in a minimum delay of two sequential round t
shi3zさんの通信上の圧縮アルゴリズム利用の認識と、big_brosさんによる指摘及び圧縮アルゴリズムの解説 - Togetterまとめ
吉良理人@ねもい @big_bros ゲーム畑出身のフリーランスSE/プログラマ、VOCALOIDで遊ぶDTMerのにわかギター弾き。秋葉原酔狂楽団(仮)楽長。日本飯盒協会員。投稿動画bit.ly/ePqOuE ピアプロpiapro.jp/bigbros まとめ kadongo38氏「日本の通信事業者よりAppleやFacebook, Google の方が問題」 「通信の最適化」でモバイル通信事業者が音声や画像をトランスコード（再圧縮）などする件が話題となっています。 これついて、kawango38氏による高木浩光氏への批判と、同調する意見への批判、及び、それへの反応。 主に、通信の秘密への侵害を問題視する意見への反論。 有益な情報や喧嘩腰な発言など雑多に集めたものです。 kadongo38氏によるshi3z氏のフォローと、それに続くtakagiichiroとの会話 http://toge
Caffeによる特徴抽出+AROWによる分類を試した - kivantium活動日記
Deep Learningのすごいところとしてよく挙げられるのは「画像から自動で特徴抽出をしてくれる」ことです。従来の手法であればタスクに合わせた画像の特徴をうまく抜き出すような特徴量を作る必要がありましたが、Deep Learningではネットワークが勝手に「特徴」を抽出してくれます。ネットワークが抽出した特徴量を使って別の分類器を学習させて分類することもできます。Deep Learningが自動で作った特徴量を使うことで人間が作ったSIFTなどの特徴量よりも高い精度で分類が可能になることもあるようです。 そこで今回はDeep LearningライブラリのCaffeを使って特徴抽出を行った後、AROWというアルゴリズムを使って分類を行ってみたいと思います。 Caffeによる特徴抽出 Caffe | Feature extraction with Caffe C++ code.とCaffe
計算量のはなし - 赤い黒歴史を蓄積する
どうも華麗なるキャッツパーです。キャットアッパーです。 この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。 私は過去に、暇に任せてこのようなスライドを作ってしまいました。 有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。 本記事では「計算量ってどうやって計算するの？」みたいな話を競プロの観点からします。 計算量とはなんぞやということについては上のスライドを読んでください。 計算量の種類 競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。 最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから
)
Heuristic (computer science) - Wikipedia
In mathematical optimization and computer science, heuristic (from Greek εὑρίσκω "I find, discover") is a technique designed for problem solving more quickly when classic methods are too slow for finding an exact or approximate solution, or when classic methods fail to find any exact solution in a search space. This is achieved by trading optimality, completeness, accuracy, or precision for speed.
Rosetta Code
Rosetta Code is a programming chrestomathy site. The idea is to present solutions to the same task in as many different languages as possible, to demonstrate how languages are similar and different, and to aid a person with a grounding in one approach to a problem in learning another. Rosetta Code currently has 1,265 tasks, 405 draft tasks, and is aware of 933 languages, though we do not (and cann
Knuth-Morris-Pratt algorithm
Idea After a shift of the pattern, the naive algorithm has forgotten all information about previously matched symbols. So it is possible that it re-compares a text symbol with different pattern symbols again and again. This leads to its worst case complexity of Θ(nm) (n: length of the text, m: length of the pattern). The algorithm of Knuth, Morris and Pratt [KMP 77] makes use of the information ga
Big O notation - Wikipedia
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by German mathematicians Paul Bachmann,[1] Edmund Landau,[2] and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for
Informatik - Universität Ulm
Fakultät Fakultät Fakultät Fakultät - Organisation Fakultät - Organisation Fakultätsrat Prüfungsausschüsse Prüfungsausschüsse PA Informatik EB CogSys Prüfungsausschuss ING Prüfungsausschuss Psychologie Studienkommissionen Promotionsausschüsse Habilitationsausschuss Zulassungsausschüsse Gleichstellungsbeauftragte Mitgliedschaften Formulare Aktuelles Aktuelles Stellenangebote Sitzungen und Termine W
文字列検索アルゴリズムの覚え書き - 我らねぶた馬鹿
マイコミジャーナルの連載記事で、「StringSearch」という文字列検索のためのJavaライブラリを紹介しました。 攻略! ツール・ド・プログラミング (44) 高速な文字列検索を実現するJavaライブラリ「StringSearch」 | マイナビニュース その補足も兼ねて、記事中に出てくる文字列検索アルゴリズムについて少しまとめてみました。細部を省略した大雑把な説明なので厳密な解説ではありませんが、参考までに。 naiveアルゴリズム 対象の文字列とパターン文字列を先頭から順番に比べていき、マッチしなかったら1文字進めてまた最初から比べるという手法です。 java.lang.StringのindexOf()メソッドなどはこの実装だそうです。 Knuth Morris Pattアルゴリズム（KMPアルゴリズム） マッチに失敗した場合に、比較するスタート位置を1文字ずつ進めるではなく、何
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The power of two random choices - Marc's Blog
【またかよ】「Haskellでクイックソート」問題【何度目だ】
https://academic.oup.com/peds/article-abstract/15/10/779/1521759
Donutsプロコンチャレンジ 2015 解説
