Zenn
👏

Paizaで試行錯誤：文字と整数の組のソート2

2022/02/27に公開
Java
paiza
tech

文字と整数の組のソート2

Paizaにある、練習問題に関する個人的な記録です。
今回の問題で勉強になったのは、以下です。

  • sort全般
  • ArrayList、HashMapやMap.Entryについての知識

問題文

1行目に行数を表す整数 n、続く n 行の各行で「文字」と「整数」の組が空白区切りで入力されます。
n 個の組について、「文字」の値が同じ組同士の数値を足しあわせてまとめ、まとめた数値の降順で、文字とまとめた数値の組を出力してください。
この際、まとめた数値は重複しません。
詳細はこちら

Answer

My Answer


public static void myans() {
	// Read the test case
	Scanner sc = new Scanner(System.in); // on Paiza

	int len = sc.nextInt();
	sc.nextLine();
	HashMap<String, Integer> map = new HashMap<>();

	// Create HashMap
	// {key, value}  = letter (String), the result of addition (int)}
	for (int i = 0; i < len; i++){
		String[] temp = sc.nextLine().split(" ");
		String key = temp[0];
		int num = Integer.parseInt(temp[1]);
		if(map.get(key) == null){
			map.put(key, num);

		} else {
			int prevVal = map.get(key);
			map.put(key, num + prevVal);
		}
	}

	// Sort the list, based on the value in the ascending order
	List<Map.Entry<String, Integer>> entryList =
			new ArrayList<>(map.entrySet());
	entryList.sort(Map.Entry.comparingByValue());

	for(int j = entryList.size()-1; j >=0; j--){
		String item = entryList.get(j).getKey();
		Integer num = entryList.get(j).getValue();
		System.out.println(item + " " + num);
	}

}

Example


public static void example() {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	Map<Character, Integer> map = new HashMap<>();
	
	for (int i=0; i<n; i++) {
	  char c = sc.next().charAt(0);
	  int v = sc.nextInt();
	  if (map.containsKey(c))
		map.put(c, map.get(c) + v);
	  else
		map.put(c, v);
	}
	
	List<Integer> ll = new ArrayList<>(map.values());
	Collections.sort(ll);
	Collections.reverse(ll);
	
	for (int v : ll)
	  for (Character c : map.keySet())
		if (map.get(c) == v)
		  System.out.println(c + " " + v);
}

解答分析

以下、ローカル環境で実施したところ、タイムがまた、ぜんぜん違う。約4倍。

++++++++++myans()++++++++++ 
A -3
W -5
E -20
it took 122.396237 in microseconds
++++++++++example()++++++++++
A -3
W -5
E -20
it took 32.662398 in microseconds

基本的な流れは両者同じ。

  1. 連想配列(HashMap)を作る（key=文字、value=整数）
    1. keyが既に登録済みのものだった場合、既存のvalueに、新しい整数を足して、代入
    2. keyが新しいものだった場合、新しい整数をvalueとして代入
  2. 連想配列をValueで降順に並び替え、順に出力

HashMap作成部分

まずは前半のHashMapの作成のところから。私のコードでは、なぜかtempという配列を介してmapにkeyとvalueを入れている。ここは無駄！（新しい配列を作って、そこに新しい要素を入れて、取り出して、という処理のが余計に発生するため）普通にtempKeyとtempValueという新しい変数に代入すれば良い。特にint numはわざわざInteger.parseInt()で型の変換(String -> Integer)をしているけど、これも入力値から直接intとして持ってくればよい。
あとは、keyの型も、StringでなくCharacterでOK。

HashMap<String, Integer> map = new HashMap<>();
	// HashMap<Character, Integer> map = new HashMap<>();

//...

for (int i = 0; i < len; i++){
	String[] temp = sc.nextLine().split(" "); // delete
	String indexNum = temp[0];                // char c = sc.next().charAt(0);
	int num = Integer.parseInt(temp[1]);      // int num = sc.nextInt();
	if(map.get(key) == null){
		map.put(key, num);

	} else {
		int prevVal = map.get(key);
		map.put(key, num + prevVal);
	}
}

上記の部分と、関連する型の定義をStringからCharacterにして、myans2()というメソッドで実行した結果が以下。

++++++++++myans()++++++++++ 
A -3
W -5
E -20
it took 115.131262 in microseconds
++++++++++myans2()++++++++++ 
A -3
W -5
E -20
it took 8.245651 in microseconds
++++++++++example()++++++++++
A -3
W -5
E -20
it took 25.339607 in microseconds

但し、これも気休めなのだと思います。なぜなら、次にあるように、同じクラス内で実行する順番を変えるだけで、処理の時間が変わってしまうことが分かったので。

今の私のコードだと、処理時間はコードの効率の良さを示さないようだ...

但し、実行する順番を変えると...

++++++++++example()++++++++++
A -3
W -5
E -20
it took 155.430837 in microseconds
++++++++++myans()++++++++++ 
A -3
W -5
E -20
it took 46.96158 in microseconds
++++++++++myans2()++++++++++ 
A -3
W -5
E -20
it took 7.536397 in microseconds

あれ、Exampleが遅い...。
もっと言うと、

++++++++++example()++++++++++
A -3
W -5
E -20
it took 124.876295 in microseconds
++++++++++myans2()++++++++++ 
A -3
W -5
E -20
it took 41.23124 in microseconds
++++++++++myans()++++++++++ 
A -3
W -5
E -20
it took 4.845359 in microseconds

myans() -> myans2()の順番で実行するだけで、あんなに遅いと思われていた私の解答も爆速になる。
実際のコード、最初にやったテンプレートをベースにmain()で、以下のように各メソッドを呼び出している。

public static void main(String[] args) {  
  
	System.out.println("++++++++++example()++++++++++");  
	example();  
	System.out.println("++++++++++myans2()++++++++++ ");  
	myans2();  
	System.out.println("++++++++++myans()++++++++++ ");  
	myans();  
  
}

理由は今すぐ分からないが、おそらく各メソッドでの共通した名前の処理やvariable等が再利用されているとかなのだろうか。ともかく、私の実行速度表記入りのコードは、あくまでも参考程度ということで考えたほうが良さそうだと思いました。

並び替え

私のコードでは、Map.Entryを使いentryList という名のタプルを作成。そのソートのメソッドを使った処理。でも結局、entryList昇順で並び替えられているので、出力時に後ろから出力することで、なんとか欲しい結果にたどり着いている。

// Sort the list, based on the value in the ascending order
List<Map.Entry<String, Integer>> entryList =
		new ArrayList<>(map.entrySet());
entryList.sort(Map.Entry.comparingByValue());

for(int j = entryList.size()-1; j >=0; j--){
	String item = entryList.get(j).getKey();
	Integer num = entryList.get(j).getValue();
	System.out.println(item + " " + num);
}

一方Exampleの方では、シンプルな処理。まずはvalueの値だけを入れたListである llを作成し、Collectionのsort()とreverse()を使ってソート。この時点でllは既に降順に並び替えられており、あとは出力のみ。

List<Integer> ll = new ArrayList<>(map.values());
	Collections.sort(ll);
	Collections.reverse(ll);
	
	for (int v : ll)
	  for (Character c : map.keySet())
		if (map.get(c) == v)
		  System.out.println(c + " " + v);

個人的には（頭がこんがらがるからというしょうもない理由もあって）for文を複数で回すのは控えてしまっていたのだけれども、二重ループくらいならば特に問題もなさそうだ。

ぼやき

他の言語での例も見られたりするので、phpでの例ものぞいてみたが、Javaは実にverboseで記述が長くなってしまう言語だなとひしひしと感じている。

$n = trim(fgets(STDIN));
$array = [];

for ($i = 0; $i < $n; $i++) {
    [$s, $d] = explode(' ', trim(fgets(STDIN)));
    if (isset($array[$s])) {
        $array[$s] += $d;
    } else {
        $array[$s] = $d;
    }
}

arsort($array);

foreach ($array as $k => $v) {
    echo $k . ' ' . $v . "\n";
}

Javaは好きだけど、きっと競技プログラミング向きではない言語だと改めて思った。

Discussion