JavaScript の Array.prototype.concat で大きな配列を扱ったときの処理時間を確認した。

(a) => a.reduce((acc, i) => acc.concat([i]), []);
a が 10^5 個のとき手元で 28000ms かかった。
(a) => {
const l = a.length;
const b = new Array(l);
for (let i = 0; i < l; i++) {
b[i] = a[i];
}
return b;
}
これなら 2ms 。

— bouzuya (@bouzuya) 2019年3月27日

AtCoder の 2s 制限において Array.prototype.concat では要素数 10^5 の配列を前からひとつずつ順に構築はできない。 20s 以上もかかってしまうからだ。なので例えば↓のようなものを書いてはいけない。 a <> [i] の (<>) は Array.prototype.concat を使うので要素数が多いときに破綻する。

f :: Int -> Array Int
f n = MonadRec.tailRec go { a: [], i: 0 }
  where
    go { a, i }
      | i == n = MonadRec.Done a
      | otherwise = MonadRec.Loop { a: a <> [i], i: i + 1 }

Functor Array の map は JavaScript では new Array(n); で事前に確保して a[i] = f(v); していく形で速い。この形がおそらく最速。 [] に push していくのは次点。 a.concat([i]) を繰り返すのは桁違いに遅い。必要なら PureScript でも STArray などで mutable な Array を使っていく必要がありそう。

細かい気づき。 Array.intercalate "\n" a よりも String.joinWith "\n" a のほうが Array.prototype.join を使うことになるので良さそう。前者のほうが汎用的ではある。

https://pursuit.purescript.org/packages/purescript-arrays/5.2.0/docs/Data.Array#v:intercalate https://pursuit.purescript.org/packages/purescript-strings/4.0.1/docs/Data.String.Common#v:joinWith

ABC122 D 問題はすこし考えて厳しそうだったので今日は ABC120 A 問題に逃げた。簡単でも毎日 1 問は。

水曜日は魚の日。魚を食べた。

子どもの通院。当たり前だけど子ども向けの病院にはいつも子どもが居るなあ。