- - PR -
Vector/ArrayList と Hashtable/HashMap の使い分け
| 投稿者 | 投稿内容 | ||||
|---|---|---|---|---|---|
|
投稿日時: 2002-09-21 09:38
まとまった内容になりそうなんでたててみました。
ぱらぱらと調べた感じ、思ったより情報は少ないですね。 元スレは http://www.atmarkit.co.jp/bbs/phpBB/viewtopic.php?topic=2162&forum=12 「Vector、Hashtable は絶対に使うべきではない」と言われましたが、パフォーマンスの面で絶対に使うべきではないというのはどうなのかなと思いましたので、ちょいちょい調べてみました。現実問題として、それほど変わった記憶がないもので。 Vector/ArrayList でベンチしてみた感じ、シングルスレッドでの単純挿入、読み出し(index/Iterator)、削除は、なぜか Vector のほうが若干早いです:-)； with Sun 1.4.1rc on Linux。なにが効いてるのかな…。 同様の結果が http://java-house.jp/ml/archive/j-h-b/033343.html にもあります； with Sun 1.2.2 on Win。 まぁ、パフォーマンス自体は実装にもよるでしょうから、「不必要な sync はオーバーヘッドの*はず*である」という一般論からいえばどうとも言えないでしょうが。 http://www.javaworld.com/javaworld/javaqa/2001-06/03-qa-0622-vector.html では、「使い分けるべきで、場合によってはどちらも使うべきではない、となっています。 http://www.asahi-net.or.jp/~dp8t-asm/java/articles/notes/04/article.html に、配列、LinkedList、ArrayList の使い分けについての調査がされています。Vector は古いから却下？ 私の感じでは、ArrayList を使う *べき* かもしれない理由は、API や sync の存在意義のほうが大きいのかなと感じました。前スレでも書いてありましたが、マルチスレッドで Vector を使う場合は、sync が必要そうな場面なら結局はそれより大きな範囲で sync しちゃうので、Vector が内部的に sync しててもあまり意味があるとは思えないので、ArrayList を使っててもいっしょかなぁと。 使うべきではないというより、使っても意味はない(オーバーヘッドがある(?)だけ)であると。 パフォーマンス以外の面で使うと危険である理由は私には未だピンときません。 # まぁ、本当にスピード命だったら、配列ベースでやっちゃうべきなのでしょうね。 # そもそもの構造からして sync しなくてもいいようにするとか。 [ メッセージ編集済み 編集者: しょむ 編集日時 2002-09-21 10:43 ] | ||||
|
投稿日時: 2002-09-21 10:23
前スレより引用：
>>同時利用者数によって、リニア(それ以上の場合も？)にレスポンスタイムが >>悪化するというお話でしょうか。確かにそれだとぞっとしない状況ではあります。 > >最悪ではデッドロックを起こします． 「Vector が」デッドロックを起こす場合というのは、具体的にはどういう状況でしょうか。 幸いな(?)ことに、私はそういう状況に当たったことも聞いたこともないものですから。 >デッドロックを起こさない場合でも，「それ以上」になりえます． >スケジューリングやコンテキストスイッチばかりで，スレッドが >ほとんど全く走らない時などにこうなります． 非常に多数のスレッドに共有されているインスタンスがあり、書き換えと読み込みが同時に起こることはない（もしくは起こっても支障がない)とわかっている場合に限れば、読み込み時の sync が必要なくなりますね。これはある程度効くと思います。 逆に、読み込みと書き換えが同時に起こりうるならば、sync は避けられない気がします。書き換え中フラグでも作って wait かませばいいのかな…。 [ メッセージ編集済み 編集者: しょむ 編集日時 2002-09-21 10:44 ] | ||||
|
投稿日時: 2002-09-21 15:01
元スレッドにも書きましたが、VectorとArrayListでは、容量の増え方が違います（SUNの実装の場合。1.3も1.4もそうです）。 Vectorは２倍ずつ容量を確保しますが、ArrayListは1.5倍ずつに拡大していくので、何度も容量を増やす場合、ArrayListの方が無駄が出る可能性が高いわけです。 （ここでいう拡大は、もとのObject配列を捨てて、新たに２倍または1.5倍のサイズの配列を生成しているということです） また、Java2以降のCollectionライブラリの実装は基本的にそれ以前の物より複雑だと考えても良いでしょう。それが原因であるかもしれません。 実際に使用する場合、原則としてはArrayListの使用をお勧めしますが、Vectorの方が適している場合もありえます。 こういう場合には実行環境と同レベルでの計測が必要でしょう。 それが出来ない場合はArrayListの使用をお勧めします。 | ||||
|
投稿日時: 2002-09-21 16:16
> 元スレッドにも書きましたが、VectorとArrayListでは、容量の増え方が違います
>（SUNの実装の場合。1.3も1.4もそうです）。 上記のベンチでは、純粋に「意味のない同期によるオーバーヘッド」なるものを調べたかったので、初期サイズを明示的に与えてあります。まぁ、実際のアプリでそれをやるのはなかなか難しいでしょうから、どれだけ意味があるかはわかりませんが。 > また、Java2以降のCollectionライブラリの実装は基本的にそれ以前の物より > 複雑だと考えても良いでしょう。それが原因であるかもしれません。 ソースを見ればわかりそうではありますね。見てみるかな… まぁ、単純に Vector = 同期 ArrayList だというわけではない、つことで。 > 実際に使用する場合、原則としてはArrayListの使用をお勧めしますが、 > Vectorの方が適している場合もありえます。 ここなんですよね、具体的に知りたいのは。 * どちらがどういう場合に勧められるの? * Vector でなければならない場合というのはあるの? 理由は? * Vector であってはならない場合はどういう場合? 理由は? なんらかの危険要因があるのであれば、Vector は排除されそうな気がするのですが。 単純に 1.4.1 の src/java を grep した行数では、Vector が 618 行、ArrayList が 148 行でした。 Vector と ArrayList の機能的な差が「意味のない同期」にだけあるのならば、機械的に置換してもよさそうなものではないかと。 以下、よくある「パフォーマンスが云々」の理由の検証です。 えらい人のお話を鵜呑みにするのもなんですから。 - 無駄な同期処理によるパフォーマンスの問題 これは少なくともシングルスレッドではあながち ArrayList のほうが優れてるとは いえなさそう。実装依存なのでなんとも…。 ただし、積極的に Vector を勧めるほどの差でもないようです。 実はマルチ CPU のときにすんごい手間がかかることがあるとか？ - DataGrowth の差 拡大の仕方の違いによるパフォーマンスの違い。 これは全体の大きさがどれくらいかによりそう。 ただ、パフォーマンスに影響が出るほどの頻度で拡大が起こるんでしょうか？ また、「1.5 倍のメモリ確保およびコピー時間 * 拡大頻度」と 「2倍のメモリ確保およびコピー * 拡大頻度」ではトータルとしては それほど優位な差が出るような気もしません。 複数スレッドで共有するならこの処理はどちらにせよ sync すべきでしょうし。 # 仮に優位な差が出るほどのものがあったとしても、 # そんなでかい Vector/ArrayList をごりごり拡大縮小するような設計って… - マルチスレッド時の同期問題 少なくとも読み込みが多数の場合に非常にパフォーマンスが違う。 ただし、ArrayList を使っても、 読み込みと書き換えは排他処理を行わなければならない（ですよね）。 # ＝書き換え多数の場合のパフォーマンスに差はなさそう。 もちろん Vector ほど効率が悪くはならないようには作れそう。 その他の理由は… * マルチスレッドでは MT-safe なクラスは意味がない 一般的にはそうでなのかも。ただ、MT-safe でないといけない場面もあるのでは？ まったくもってないのでしょうか？ Vector の sync なんてのは単なるおまじないな気はしてきましたが。 * マルチスレッドではデッドロックが起こる可能性があり、危険 Vector は危険? * Vector を使うことによる具体的にうれしいことはなにもない そんな気はしてきました。 # が、絶対使っちゃダメ、なの？ * とにかく Sun が勧めてるんだから新しいのにしとけや # はぁそうですか。 # だったらさっさと下位互換性目的以外の Vector を追い出せばいいのに… # java.util.Date だって Calendar 使えや状態だし。 --- あえて積極的に Vecotor を使った方がいいと言っているわけではありません。 「原則として ArrayList が勧められる/Vecotor は使うべきではない」理由が知りたいのです。何か具体的な理由があるのか、それとも「マルチスレッドのおやくそく/Java のおやくそく/JVM のおやくそく/Sun のおやくそく」なのか。 [ メッセージ編集済み 編集者: しょむ 編集日時 2002-09-21 16:41 ] | ||||
|
投稿日時: 2002-09-21 17:30
ArrayListかVectorかは結構色々なところで話題になっているみたいです。私もしょむさんと同じ考えで、いまいちピンとこないのですが・・・。
JDCのフォーラムやJGuruのフォーラムでは １．ArrayListはSyncのオーバヘッドが無いからVectorよりも早い。 ２．ArrayListやVectorのどちらかを使うかで悩むのであればListを使うべき。 ３．ArrayListのほうが新しいから、ArrayListを使うべき。 ４．よって、Vectorじゃないといけない(Syncされてないといけない)場合でなければArrayListを使うべき とのことです。でも、やっぱりVectorじゃないといけない場合の例というのはないですねぇ。 パフォーマンスについてですが、 「Thinking in Java, 2nd edition, Revision 12」 ?2000 by Bruce Eckel （ http://www.mindview.net/Books/TIJ/ でダウンロードできます） というオンラインブックの実験結果では、ArrayListのほうが若干早かったそうです。 あとデッドロックについてですが、デッドロックが発生するのはVectorのせいではなくその使い方が間違っているからでしょう。Vectorを使用しなくても、Syncを使えばデッドロックの可能性はあるわけですしVectorがいけないというわけではないかなと思います。 [ メッセージ編集済み 編集者: H2 編集日時 2002-09-21 17:37 ] | ||||
|
投稿日時: 2002-09-21 18:31
ぬぉ〜、Readers/Writer Locker で ArrayList を wrap してみようとしてたらわかってきた感じ。
"array" 的なものの構造に手をつけようとする場合(たとえば remove(index))、必ずその構造を解析しなければならない(たとえば lastIndexOf() で remove 対象を探す)ため、「構造解析および変更」をまとめて sync しなきゃいけなくなるので、おのおのの method の内部で sync しても単に無駄が増えるだけですね…。 つまり、array や hashtable のような、それに対する一連の構造変更操作が sync atomic (なんてのは私の適当な造語) でないものは、結局は外部同期しなきゃいけないので、その操作自体を sync にしてもぜ〜んぜん意味がない、というのを実感。 外部同期のし忘れぐらいは防げる? 怪しいな…。 そんなの Vector でやったからってうまく動く気はしない:-b ラッシュテストで発見される確率が減ってしまうぐらい？(デメリットだ…) Vector の sync に期待するのは意味がない、までは理解。 Vector を使うと危険、はまだわからないです(read 競合以外で)。 [ メッセージ編集済み 編集者: しょむ 編集日時 2002-09-21 20:19 ] | ||||
|
投稿日時: 2002-09-24 10:49
＃Vectorでデッドロックの危険性ってのは，多分私の勘違いです．
＃ただし，マルチスレッドではデッドロックのことを理解して同期を ＃設計しないと極めて危険なのは事実です． ># まぁ、本当にスピード命だったら、配列ベースでやっちゃうべきなのでしょうね。 これは微妙かと．かなりのチューニングをされたライブラリと， お手製のライブラリとでは，どっちが早いかは条件にもよります． ># そもそもの構造からして sync しなくてもいいようにするとか。 マルチスレッドプログラミング(というより並列プログラミングかな？)では， まず第一にアルゴリズムのレベルからマルチスレッド向けに作り直すのが 基本でしょう．その中心となるのが，同期を最小限にすること． 書き込みだから同期が必要だとか，読み出しだから不要だとかは 一概には言えず，問題の性質に依存します． そのためにはVectorやHashtableは邪魔だだけなんです． そこまで考えずにプログラムを組んでいる人の場合は，Vectorを使っても それほどパフォーマンスの差は出ないかもしれません．でも，それは マルチスレッド上での性能を引き出せていないだけなんですよね． もちろん，そこまでのチューニングが必要ない場合もあります． ユーザー数が少なく，実質逐次で動いている場合などがそう．ただし， そういったプログラムが，後でユーザー数が増えた場合などには， なかなか原因のわからないパフォーマンスバグが発生し，最悪では プログラムをアルゴリズムレベルから書き直す必要に迫られる恐れが あります． | ||||
|
投稿日時: 2002-09-24 11:23
永井です。
ふと思い付きました。データの破壊やデッドロックとは全く違う危険性ですが。 仮に「MT上でのデータ保護が完全だが、ちょっと動作が重いクラス(データ構造)」 が存在したとします。 「MT上でのデータ保護が完全」という特性から、色々な場面でばんばん採用します。 (特にMTプログラミング初心者な)プログラマは深く考えずにどんどん使います。 ある操作のときにどのオブジェクトをロックしなければならないか等の 設計レビューが適当なまま組まれます。本当ならオブジェクトを切り分けて ロックを回避出来るようなケースでも共有オブジェクトを(暗黙のうちに)ロック したりします。 実際にサーバーで稼動させたら、サーバーが実質的な停止状態に陥ってしまいました。 このままジョブを追加せずにしばらく放置しておけば、いずれは正常なデータを 生成するのでしょうが。 ……というような感じで、プログラマの意識の方に危険が存在する気がします。 「どのオブジェクトをどのくらいロックしているか」をプログラマ(設計者)が 自覚していることが必要なのではないでしょうか。 ロックを意識するのは手間ですが、それをあえて強いることによって 構造的に「変、無駄」なプログラムをレビュー段階で排除(/修正)出来るという利点が あるかと思います。 逆に、「MT上でもデータ保護が完全なクラス」は 使い捨てのフィルタプログラムの作成ですとか、ユーザーに対して動作(要求)仕様の 確認を取るためだけのプロトタイプの作成ですとかには非常に便利な気がします。 | ||||
スキルアップ／キャリアアップ（JOB@IT）
Copyright © ITmedia, Inc. All Rights Reserved.
著作権はアイティメディア株式会社またはその記事の筆者に属します。
当サイトに掲載されている記事や画像などの無断転載を禁止します。
著作権はアイティメディア株式会社またはその記事の筆者に属します。
当サイトに掲載されている記事や画像などの無断転載を禁止します。