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

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

ただいまの
回答率

88.92%

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

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 1,978

前提・実現したいこと

このページの問題を解きたいです。
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が入力されると終了させる ここで別の整数組を入れると、別の要素で続けて実験を行う

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

該当のソースコード

import java.util.Set;
import java.util.HashSet;
import java.util.Scanner; 
import java.util.InputMismatchException;

class CD {
    public static void main (String[] args) {
        Scanner scan = new Scanner(System.in);
        int output = 0;

        while(scan.hasNext()) {
            try {
                int M = scan.nextInt();
                int N = scan.nextInt();
                if(M==0 && N==0) System.exit(0);

                Set<Integer> cdnum = new HashSet<Integer>();

                for(int i=0; i<M; i++)
                    cdnum.add(scan.nextInt());

                for(int i=0; i<N; i++) {
                    if(cdnum.contains(scan.nextInt()))
                        output++;
                }

                System.out.println(output);
                output = 0;
                cdnum.clear();

            } catch(InputMismatchException e) {
                System.out.println("Input must be type int.");
                System.exit(1);
            }
        }
    }
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+5

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

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/04/27 15:29

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

    キャンセル

+2

考えられる可能性としては…

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/12 00:55

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

    キャンセル

  • 2017/05/12 02:11

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

    キャンセル

  • 2017/05/12 02:16

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

    キャンセル

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

  • ただいまの回答率 88.92%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る