軽い気持ちでLinkedListを使ったら休出する羽目になった話 - Qiita

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

[su_zu_ki_1010]

若いころに何気ない気持ちで使った機能が原因で障害を出したことをない人だけが石を投げなさい案件ではないかと思う。僕はやらかしたことがあるので書いた人の気持ちがわかる。いい勉強したねと思えばいい。

[turanukimaru]

これ拡張for文が無かった時代でもiteratorで書くべきだった奴では。

[vanbraam]

拡張for文で正解だけど,それがなかった時代でも普通にrecord.next()する案件だと思う;"ランダムアクセスしちゃダメ"というより,sequencial accessでいいのに無意味にrandom accessしてる例では

[megumin1]

記事やコメントでの「ランダムアクセス」の言葉の使い方がみなさん根本的に間違っています。「リスト構造はランダムアクセスをサポートしていないので、インデックスによるアクセスはO(n)かかる」が正しい文。

[razokulover]

「何気ないLinkedListがパフォーマンスを傷つけた」案件だ

[ntstn]

昔やらかしたことあるなー。コメのマウンティングが香ばしい。アナタは大丈夫かもしれないが、これから通る人にとってはこういう失敗例はすごく有用。

[junjun777]

APがCPUを一つ使い切ってる時点で、SQLを疑うのはナンセンス。（DBがアホ設定にチューニングされているのは想定外でいい）。／添え字でアクセスしたくなるのは悪癖なので直した方が良い。悪いのはLinkedListでなく設計。

[NOV1975]

処理中でiを使いたいってあるあるなんだけど、それで拡張for文を止めるのはよろしくないんだよなー

[honeybe]

解ってみるとなんてことはないけど気付きにくい奴だ

[nishik-t]

Javaは使わないけど、そもそも連結リスト型にget(index)がある時点でおかしな実装だと思うなあ。挿入した場合ずれるけどどう処理するんだろ？頭からカウントするの？

[shun_libra]

これは気をつけたい知見。何に最適化されているかというのを見落としてはならない。

[mas-higa]

C言語じゃあるまいし今時 for (i = 0; i < n; ... とか書くやつなんなの

[AmaiSaeta]

怖い怖い怖い似たようなチョンボどっかで知らずにやってないか気になって怖い!

[yukkesan]

前職でクエリ結果をCSVに吐くだけで死ぬほど遅いjarがあったけど、こういう実装だったのかも。.netにもLinkedListがあることも知れて勉強になりました。

[nekoruri]

本当にランダムアクセスが必要な場合はどういうインターフェースにすれば良いのかな、と思ったらRandomAccessというマーカーインターフェースがあった。

[issyurn]

アルゴリズムとデータ構造の理解、APIドキュメントを読み込む能力って基本だけど大事だよなあと再認識。あと、実運用を見越した負荷テスト（そもそもこれやってなくね？っていうのはある）。解決策たくさんいいね。

[Hash]

あえての LinkedList... コメント欄含め勉強になる / こう表れるという実例 / プロファイラ使うと出力どんな感じだったか

[ka-ka_xyz]

気になったけど、拡張for文がIteratorのシンタックスシュガーなのって、javac仕様なのか実装依存なのか。-> https://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html#jls-14.14.2 仕様

[mohno]

これ「ほぼINSERTしかやってないような処理」になんで LinkedList を使ったの？という話じゃないのかな←コメントで指摘されてた^_^;/LinkedList にインデックスアクセスあるのか。というか.NETと違うんだ。（そりゃ違うか）

[mojimojikun]

タイトルでオチが見えてたんだけどこういうのを共有するのは正しい。 でもなんかこのくらいのやらかしを学習している段階だと自分でやらかさないと学習しない率が高いような気もしないでもない。

[da-yoshi]

JavaのListやStreamにzipWithIndex相当の機能が無いので、JDKが新しくてもindex目当てにgetを使いたくなることは多々ありそう

[tokoyax]

こういう失敗談をだしてくれるのはありがたい

[p_tan]

C++屋さんは嫌でもSTLで意識させられるデータ構造の話。計算量とインターフェースによる抽象化は相性悪い。

[FunnyBunnyDizzy]

こういう失敗公開するの良いね

[kmaebashi]

この話から導ける教訓はいくつかあると思うけど、最初からListじゃなくてLinkedListが見えてたらこんなアクセスしなかったかもしれないわけで、「下手に抽象クラスとかで実装を隠すな」と言えるかも。

[digo]

気づけてよかったね。。中途半端なデータだと「なんか遅いけど仕方ないのかなぁ」って使い続けられることになって皆不幸。

[gabari]

これ実装によってはsize()も時間かかるやつなのでは。流石に今日び無いかな。/コレクションの名前は変に抽象化しないで実装書いとけよと思う。c#のDictionaryとか。hashちゃうんかと/あえて言うとデータ構造は基礎

[lainof]

LinkedListだからインデックスによるアクセスが遅いだけで、ArrayListなら遅くないことを理解してないと思われるコメントが…

[lizy]

Listインタフェースにget(int)をつけてしまったのがそもそもの原因なのかな

[mandel59]

「ランダムアクセスって言うより、連結リストだから特定の位置にジャンプしてアクセスする際、常に最初から探していく必要があるから」それをランダムアクセスというのでは

[haneuma0628]

つらい

[slumbers99]

身近に頑なにLinkedListに詰め込んでる人いるんだよなぁ。わかってやってる感ないので恐ろしい。

[tsz]

ドライバでリスト管理に問題があり、ループ構造になってハングアップしたことはしょっちゅう。

[rin51]

何気ないforループがプログラマを傷つけた

[ma38su]

そもそもListのインターフェースが悪いと思うんだが。

[uva]

綺麗なグラフ

[okzk]

特別な理由がなくてLinkedList使ったんなら、リファクタすべきはまずArrayListに変更することじゃないかな？

[kabacsharp]

stlのアルゴリズムコンテナとイテレータの組み合わせも考え物だしなぁ。

[fukken]

あー、for文だと、1000件目を取るために先頭から順番にアクセス、1001件目を取るためにまた先頭から順番にアクセス、1002番目を取るためにまた先頭から…ってなるのか

[eichisanden]

休出はしてないけど、他人の書いたコードで同じ目にあったことがある。LinkedList使う理由がサッパリ分からない処理だった。