質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

2回答

3455閲覧

高速な要素検索をしたいです

RinT_hinabita39

総合スコア28

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

1グッド

0クリップ

投稿2017/04/27 05:35

###前提・実現したいこと
このページの問題を解きたいです。
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2949

概要は整数群AとBがあり、AとBに共通して含まれる整数の個数を出力させるというものですが、
UVaの内部でインプットされる整数の数がどうやら膨大らしいので、普通に実装するだけでは時間がかかってしまいます。

そこでHashSetを使えばいいという話を聞いたので、それを使ってやってみたのですが、それでも時間切れになってしまいます。(UVaのサイトの問題は3秒以内で実行できるプログラムでないと跳ねられてしまいます)

入力例は以下の通りです

3 3 //1つ目が整数群Aの要素数、2つ目が整数群Bの要素数 1 //ここから3行分が整数群Aに含まれる要素 2 3 1 //ここから3行分が整数群Bに含まれる要素 2 4 0 0 //0 0が入力されると終了させる ここで別の整数組を入れると、別の要素で続けて実験を行う

以下のソースコードで、まだどこかに無駄をカットできる箇所はありますか?
ちなみにコンパイルはちゃんと通り、出力も正しいものがプリントされています。

###該当のソースコード

java

1import java.util.Set; 2import java.util.HashSet; 3import java.util.Scanner; 4import java.util.InputMismatchException; 5 6class CD { 7 public static void main (String[] args) { 8 Scanner scan = new Scanner(System.in); 9 int output = 0; 10 11 while(scan.hasNext()) { 12 try { 13 int M = scan.nextInt(); 14 int N = scan.nextInt(); 15 if(M==0 && N==0) System.exit(0); 16 17 Set<Integer> cdnum = new HashSet<Integer>(); 18 19 for(int i=0; i<M; i++) 20 cdnum.add(scan.nextInt()); 21 22 for(int i=0; i<N; i++) { 23 if(cdnum.contains(scan.nextInt())) 24 output++; 25 } 26 27 System.out.println(output); 28 output = 0; 29 cdnum.clear(); 30 31 } catch(InputMismatchException e) { 32 System.out.println("Input must be type int."); 33 System.exit(1); 34 } 35 } 36 } 37} 38
KiyoshiMotoki👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

英語力低いので合っているかわかりませんが、問題文を読んだところ、以下の場所がポイントかと思います。

  • 同一のコピーは持っていない(つまり各々で重複したものは持っていない)
  • それぞれの番号は昇順で並んでいる

まずA郡を読み終わったあと、B郡に入るわけですが、上記ルールにより、一度重複を確認した値は検索対象から除外可能ですし、B郡に出てきた数字より下のA郡の要素は必要なくなります。HashSetを使ってB郡の数値を読み込むたびに最大100万件存在するA郡の中から探すより、どんどんA郡の数を削って候補を減らすほうが早くなるでしょう。

コードは自分で考えてください。

投稿2017/04/27 05:49

編集2017/04/27 05:50
masaya_ohashi

総合スコア9206

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

RinT_hinabita39

2017/04/27 06:29

昇順という条件がそういう風に活きてくるわけですね… ありがとうございます!
guest

0

考えられる可能性としては…
0. HashSet(の中身のHashMap)の容量拡張の回数が多く、時間がかかる
HashMapには容量があり、一定割合使用されると自動で容量が拡張される。これに時間がかかっているというケース
0. 探索の効率を考えると、Setより昇順に並べたListを使って二分探索で探した方が速いかもしれない。
0. BitSetという手段

投稿2017/04/27 05:56

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

RinT_hinabita39

2017/05/11 15:55

下で解答してくださった方の方針でやってもTime Limit Exceededになってしまい、BitSetは調べてもよくわからなかったのと、二分探索は過去にめっちゃ苦労した記憶があり、すぐ(ここでのすぐは1時間くらい)に書けそうになかったので、先生に聞いたところ、javaのScannerはクッソ遅いのでBufferedReaderを使ってね!とのことでした。それで直してみた結果、HashSetでも無事制限時間を切ることができたので、報告しておきます。ありがとうございました!
swordone

2017/05/11 17:11

二分探索はJavaのライブラリに、配列ならArrays.binarySearch、ListならCollections.binarySearchがありますよ。
RinT_hinabita39

2017/05/11 17:16

え!そうなんですか!?超便利ですね… 前に授業で二分探索を取り扱った時は、その定義に従って自力でやらされて、確かに仕組みの理解には役立ったのですが、なかなかできなくて苦しい思いをしたことがありまして…
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問