Q&A
「考えている」「最適かどうか」「聞いた」といったぼんやりしたものでは無く、実際のデータが手元にお有りであれば、想定されるコード（を極力「最適化」したもの）を書いて実行・計測し、そのコードや結果/目標をご提示の上で、そこからさらに「こうしたいがどう出来るか/出来ないか」という形でご質問されたほうが、回答側も考えたものを試して比較したりと判断し易いように思いますが、如何でしょうか。
Javaで15万行ほどのIPアドレスと国の対応が書いたCSVを読み込んでおき、
アクセス元のIPとその読み込んだリストを照らし合わせて処理をしたいと考えています。
その場合、データ構造としてはハッシュマップを使うのが最適なのでしょうか？
また、そのときはサイズを指定した方が速いと聞いたのですが、
例えば20万とかの多めを指定すればよいのでしょうか？それとも少ないくらいの方が良いのでしょうか？
よろしくおねがいします。
どれくらいのターンアラウンドタイムを期待しているかによるんじゃ?
シビアじゃないならアクセスはデータベースに丸投げしてもいいし、そうじゃなかったら自前でなんとかするしかないってことで、そのへんのコストバランスは(背景を知らない)他人じゃ分からんスよ。
> そのときはサイズを指定した方が速いと聞いたのですが、例えば20万とかの多めを指定すればよいのでしょうか？
？ これはどのような状況での速い・遅いの話でしょう。ハッシュマップを生成するときに最終的な要素数より小さいサイズで用意しておくと、拡げる処理に時間がかかる（かもしれない）話、でしょうかね。いずれにせよCSVをもとにIPアドレスをキー、国の対応を値とするだけなら簡単そうなものなのですから、まずご自身でコードを書いて、ご自身の環境で試してみるのが先決です。
あと、こんだけ回答にするのもあれなので…
もし懸念事項がデータ増加時の再割り当てのことだったら今回は関係なさそうスね。
最適かどうかは私には分かりませんが(分からないので回答はできません)、経験的にはHashMapが普通だと思います。
速さという点では、初期サイズを指定した方が速いはずですが、そこが支配的になるかどうかは不明なので何とも言えませんし、最近のJVMなどは繰り返すほど速くなるので、正確な計測は出来ません。
HashMapを使用する場合は、初期サイズをデフォルトの係数0.75で割った数に1足すくらいにしておくことで、テーブルの拡張を抑えることができ、メモリ効率はいいでしょう。
上記を踏まえ、サンプルコードを用意しました。
import java.util.*;
import java.util.stream.Stream;
import java.util.stream.Collector;
import java.util.stream.Collectors;
import java.util.function.Supplier;
public class Main {
private static Random rand = new Random();
private static String getRandomIPv4String() {
return Stream.generate(()->String.valueOf(rand.nextInt(256)))
.limit(4)
.collect(Collectors.joining("."));
}
public static double measure(String[] array, Supplier<Map<String,String>> mapSupplier) {
final int N = array.length;
long nano = System.nanoTime();
Collector<String, ?, Map<String,String>> colloector = mapSupplier != null
? Collectors.toMap(
e -> e, // key
e -> e, // value
(e1, e2) -> e1, // 先優先
mapSupplier // 使用するマップ生成
)
: Collectors.toMap(
e -> e, // key
e -> e, // value
(e1, e2) -> e1 // 先優先
);
Map map = Arrays.stream(array).collect(colloector);
nano = System.nanoTime() - nano;
double sec = (double)nano / 1000000000L;
//System.out.println(map);
//System.out.println(map.size());
//System.out.println(map.getClass().getName());
System.out.println(sec);
return sec;
}
public static void main(String[] args) throws Exception {
//final int N = 15;
final int N = 150000;
String[] array = Stream.generate(()->getRandomIPv4String()).limit(N).toArray(String[]::new);
final int TEST_COUNT = 5;
System.out.println(Stream.generate(()->measure(array, () -> new HashMap<String,String>((int)((float)N/0.75+1)))).limit(TEST_COUNT).mapToDouble(e->e).average());
System.out.println(Stream.generate(()->measure(array, null)).limit(TEST_COUNT).mapToDouble(e->e).average());
}
}
paiza.ioで実行した結果は以下のとおりです。
0.044941748
0.039713869
0.044337646
0.017000638
0.030105166
OptionalDouble[0.0352198134]
0.045640248
0.015848375
0.040869445
0.02239253
0.008865428
OptionalDouble[0.0267232052]
ご参考までに。
＞dameoさん
>最適かどうかは私には分かりませんが(分からないので回答はできません)、経験的にはHashMapが普通だと思います。
あまり経験がないのでトンチンカンな方向に行ってないか確認したかったため、HashMapで問題なさそうで良かったです。
>初期サイズをデフォルトの係数0.75で割った数に1足すくらいにしておくことで、テーブルの拡張を抑えることができ、
テーブルの拡張で多少時間がかかるので初期サイズ指定した方が良いという記事は見たのですが、
あまり詳しく書いてなかったので、一般的な値助かります。
サンプルコードもありがとうございます。
paizaで何度か実行してみたら上記ほどの差にはならず、多少ブレがあるみたいですね
コードを見ると上が初期サイズ指定した方だと思ったのですが、
これは逆に遅くなっているということでしょうか？
> テーブルの拡張で多少時間がかかるので初期サイズ指定した方が良いという記事は見たのですが、
> あまり詳しく書いてなかったので、一般的な値助かります。
0.75は別に一般的な値というわけではなく、HashMapのデフォルト値です。
https://docs.oracle.com/javase/jp/8/docs/api/java/util/HashMap.html
> コードを見ると上が初期サイズ指定した方だと思ったのですが、
> これは逆に遅くなっているということでしょうか？
数字だけ見るとそのとおりです。元は順番逆にしていたのですが、上に書いた方が数字的に不利なのでこうしています。
この実験においては有為な差がないというか、誤差の方が大きいと個人的には見ています。定性的にはループで試行回数(TEST_COUNT)を増やすとどちらも時間が減っていき差も詰まるようでした。
あなたの回答
tips
プレビュー
