HsbtDiary

■ [logic][algorithm][programming]アレなロジック

昨日見かけたロジックなんだけど、要素数も内容も不定な1万件近いArrayList2つ(仮にA,Bとする)のdiffを作るのに

foreach(foo a in A)
{
  foreach(foo b in B)
  {
    if(a.equals(b))
      barDiff();
      break;
  }
}

みたいな処理をしてたんですよ。これって計算量が最悪O(n^2)になるわけで、こういうのを見かけるたびにぶち切れというか謎苦笑。いくら富豪的プログラミングでいいんじゃねとか思っていても、一致していた部分については、せめてBから抜きなさいよ。

なんつーかさあ、たまに「学校の勉強なんて関係ない。経験が重要。」とか言って、大学とか大学院とかに行った人をDISる人がいるけど、こういう計算量に関する概念とかロジックの話って基本的には学校で勉強する普遍的知識なんじゃないかと思うんだよなあ(別に経験上学んでもいいんだけど)。それらの普遍的な知識を元に経験とか学問を上乗せして、知恵として昇華させるわけでして。どちらも重要じゃないの? と問いただしたい(けど、立場上黙ってる)。

結局、この件については直したくてうずうずしたけど、いかんともしがたい大人の事情で見なかった事にした。

■ [ruby][CSharp]ちなみに

上の例を書くときに

foreach a in A
   …
end

とか無意識のうちにRubyとごちゃごちゃになって書いていたのは内緒だ。つーか、Arrayのイテレータにいちいち型宣言しないとダメとかダルすぎなんだよ!

あと上の話は全部フィクションなので真に受けないでください。今時、O(n^2)のアルゴリズムが許されるのは小学生までに決まっているよねー。