public

Wiki » History » Revision 2

Revision 1 (hori, 11/06/2022 05:01 PM) → Revision 2/6 (hori, 11/06/2022 05:05 PM)

# 公開の記録 

 {{toc}} 

 ## AtCoder ABC 276 E について <2022-11-06 Sun 00:07> 

 https://atcoder.jp/contests/abc276/editorial/5162 
 公式解法のとおり、BFS や DSU を用いたにも関わらず TLE を解決できなかったので振り返る。 
 アルゴリズムの問題ではなく、Ruby の基本的なデータ構造の問題で遅くなっていた。 

 グリッド問題の入力は以下のような文字列で与えられるが、これをどういうデータ構造に落とすのがよいかという問題。 

 ``` 
 5 7 
 .#...#. 
 ..#.#.. 
 ...S... 
 ..#.#.. 
 .#...#. 
 ``` 

 安直なものでは以下のような格納方式が考えられる。 

 1. 1 つの文字列として格納する方式 
    ``` 
    ".#...#...#.#.....S.....#.#...#...#." 
    ``` 

 2. 1 次元の文字の配列として格納する方式 
    ``` 
    [".", "#", ".", ".", ".", "#", ".", ".", ".", ...] 
    ``` 

 3. 各行ごとの文字列の配列として格納する方式 
    ``` 
    [".#...#.", 
     "..#.#..", 
     "...S...", 
     "..#.#..", 
     ".#...#."] 
    ``` 

 4. 文字の 2 次元配列として格納する方式 
    ``` 
    [[".", "#", ".", ".", ".", "#", "."], 
     [".", ".", "#", ".", "#", ".", "."], 
     [".", ".", ".", "S", ".", ".", "."], 
     ...] 
    ``` 

 私はこれまで割と雰囲気で 1. や 2. を選んでしまっていた。 
 また、過去に別問題を変に学習してしまったようで 2D 配列は 1D 配列にした方が速い (添字を毎回変換していた) と思い込んでいたのもある。 

 一回自前で計測しておくと安心ということで測ってみた。 
 1000x1000 の適当なグリッドを作って各セルを走る処理を 5 回実行した時間を比較する (単位は秒)。 

 |     |                      | データロード | 全処理時間 | 
 |---|--------------------|--------------|------------| 
 | 1 | 文字列               | 0.22           | 4.35         | 
 | 2 | 一次元文字配列       | 4.96           | 6.49         | 
 | 3 | 行ごとの文字列配列 | 0.006          | 5.12         | 
 | 4 | 二次元文字配列       | 0.21           | 2.84         | 

 データロードにおいて一次元文字配列が遅いのは `array1 + array2` のような連結処理をしているからで、これは以前遅いことを学習済み。 
 文字列の添字でのアクセスよりも `string.chars` で文字れ配列に分割した方が、データロードには多少時間がかかるが、アクセスは高速になるようだ。 

 ということで、今後はグリッド問題が出た時は二次元文字配列で処理するようにしてみる。