軽い気持ちで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, Dec 2022, Feb 2023, Oct 2024, Mar 2025 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, st
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まとめ
スマホ回線で上位レイヤに対する不可逆圧縮が行われてしまう「通信の最適化」問題 カドカワドワンゴ川上氏を擁護するUEI清水氏の意見と、その誤りについて指摘するプログラマ吉良氏とのやりとり 圧縮アルゴリズムの特性から、通信の最適化の問題点が分かりやすいのでまとめました。 続きを読む
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
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Heuristic" computer science – news · newspapers · books · scholar · JSTOR (November 2025) (Learn how and when to remove this message) In mathematical optimization and computer science, heuristic (from Gr
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,347 tasks, 401 draft tasks, and is aware of 989 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 approximate size of a function on a domain. Big O is a member of a family of notations invented by German mathematicians Paul Bachmann[1] and Edmund Landau[2] and expanded by others, collectively called Bachmann–Landau notation. The letter O was chosen by Bachmann to stand for Ordnung, meaning the order of approximation. In computer scie
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 Ethik Gremium Gleichstellungsbeauftragte Mitgliedschaften Formulare Aktuelles Aktuelles Stellenangebote Sitzungen
文字列検索アルゴリズムの覚え書き - 我らねぶた馬鹿
マイコミジャーナルの連載記事で、「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://peds.oxfordjournals.org/content/15/10/779.long
Donutsプロコンチャレンジ 2015 解説
