omas/advent.md

## advent.md

      
    Raw
  

              advent.md
            
          
    プログラム言語いまむかし

初めに

先週は，世界的なプログラミングWeekが開催されました。
それに因んでプログラミング言語の変遷と潮流を書きます。
プログラミング言語の歴史

プログラミングの始まり

世界初のコンピュータがどれかは諸説あるが，ノイマンによるハードウェアとソフトウェアの分離後，最初の高級プログラミング言語は1954年に誕生したFortranである。同時期にCOBOL,関数型言語のLISPが登場する。これらのプログラム言語は今もなお使われている。
プログラミング手法

1972年にCが考案されるとともに，「構造化プログラミング」が作法として定着することになる。しかし構造化プログラミングは，比較的低レベルの抽象化を扱うもので，もっと高レベルでの抽象化こそがソフトウェア危機への対応策だとして別のアプローチが考案され，SimulaからSmalltalk，C++，そしてJava，C# などにつらなる「オブジェクト指向」という現在のプログラミングの主流となる。
スクリプト言語

一方，1987年のPerlの登場から，スクリプト言語と呼ばれるプログラム言語が次々と誕生。当初のスクリプト言語は，機能の少ない簡易言語であったが，インターネットとの親和性からWebアプリケーションの言語として広まった。こうしたものの代表としてPHP，Python，Rubyなどがある。また今後出てくる言語もスクリプト型が多くなるであろう。
プログラミング言語のこれから

プログミング言語の違いはデータとデータの扱いをどのように表現するか，再利用の扱いをどうするかという違いにしか過ぎない。これからも新しい言語が誕生するが，プログラミング言語のアプローチ手法にも着目すると，どのようにプログラムを書くべきかの指針となる。今後注目すべき潮流は大量のデータのアプローチである。統計言語としてのRや高速化手法としての関数型，久しぶりの本格的言語Swiftなどに注目したい。
言語別アプローチをやってみた

ここで様々なプログラミング言語や解法へのアプローチを実際にコードで確認してみよう。題材はpaizaオンラインハッカソン7 恋愛SLG: プログラミングで彼女をつくるの眼帯を取り上げ，言語や手法によるアプローチの違いをみていこう。
課題

あなたは、巻数が全 N 巻の古い本を集めています。
古本屋に訪れたあなたは売られている各巻のうち買うべきなのは何巻かを知りたいです。
あなたの持っている巻のリストと、中古本屋で売られている巻のリストを入力として与えられたとき、あなたの買うべき巻のリストを出力してください。
入力される値

入力は標準入力にて以下のフォーマットで与えられます。
N
M1
x_1 x_2 ... x_M1
M2
y_1 y_2 ... y_M2

N は、ある本の出版されている巻の総数です。
出版されているのは、1 巻から始まり、N 巻までです。
M1 は、あなたの持っている巻の総数を表します。
次の行には、あなたの持っている巻のリストが与えられます。
M2 は、中古本屋で売られている巻のリストの総数を表します。
次の行には、中古本屋で売られている巻のリストが与えられます。
期待する出力

あなたの買うべき巻を小さい順に空白区切りで出力してください。
ただし、買うべき巻がない場合は None と出力してください。
入力例

入力
5
3
1 3 4
3
2 3 5

出力
2 5

解法

ダイクストラ的手法

1 − N巻までループしM1，M2それぞれをループさせながら比較して
M2にありかつM1にないリストを作成し，並び替えて出力。
JavaScriptで実装

(function(stdin) {
  var inputs = stdin.toString().trim().split('\n');
  var N = parseInt(inputs[0], 10);
  var M1 = makeBookList(inputs[2],inputs[1]);
  var M2 = makeBookList(inputs[4],inputs[3]);
  var buff = []; // 買う本のリスト
  var index = 0;

  for (var i = 1; i <= N; i++ ) {
    var matchM1 = 0;
    var matchM2 = 0;
    // M1にあるか
    for (var j = 0; j < M1.length; j++) {
      if (i === M1[j]) {
        matchM1 = 1;
        break;
      }
    }
    // M2にあるか
    for (var k = 0; k < M2.length; k++) {
      if (i === M1[k]) {
        matchM2 = 1;
        break;
      }
    }
    // M1になくかつM2にあれば
    if (matchM1 === 0 && matchM2 === 1) {
      buff[index] = i;
      index++;
    }
  }

  bsort(buff); // 並び替え

  if (buff.length === 0) {
    console.log('None');
  } else {
    console.log(listToStr(buff));
  }

  function listToStr(list) {
    var str = '';
    for (var i = 0; i < list.length; i++) {
      str = str + list[i] + ' ';
    }
    return str.trim();
  }

  function bsort(list) {
    for (var i = 0; i < list.length; i++) {
      for (var j = list.length - 1; j > i; j--) {
        if (list[j] < list[j - 1]) {
          var tmp = list[j];
          list[j] = list[j - 1];
          list[j - 1] = tmp;
        }
      }
    }
  }

  function makeBookList(data, limit) {
    var ret = [];
    var index = 0;
    for (var i = 0; i < limit; i++) {
      ret[index] = parseInt(data[i],10);
      index++;
    }
    return ret;
  }

})(require('fs').readFileSync('/dev/stdin', 'utf8'));

Perlでのダイクストラアプローチ

M2のリストをループさせ，さらにM1をループさせながら値を比較し，M1にないものをバッファして並び替え，最後に出力する。
use 5.010;
# 入力データ配列， 持っている本， 売っている本，差分を入れる配列
my (@lines, @M1, @M2, @result);
# 標準入力を入力データ配列に格納
while (<>) {
  chomp; # 改行の除去
  push(@lines, $_);
}
# スペース区切りのデータを分割し指定の個数を配列に格納
@M1 = split(/ /, $lines[2], $lines[1]);
@M2 = sort { $a <=> $b } split(/ /, $lines[4], $lines[3]);

for my $var (@M2) {
    # 売っている本($var)が持っている本のリスト(@M1)になければpush
    push(@result, $var) unless (grep {$_ == $var} @M1);
}
# リストが空ならNone そうでなければリストを空白区切りで出力
say @result == 0 ? "None" : "@result";

JavaScript 関数言語的アプローチ

M1のリストにマッチしないM2のリストを作り並べ替えて出力する。
function makeBookList(data, limit) {
  return data.split(' ', limit).map(Number);
}

(stdin => {
  let inputs = stdin.toString().trim().split('\n');
  let result = ((M1, M2) => 
    M2.filter(v => !M1.includes(v)) // マッチしないリストを作成
      .sort((a, b) => a - b)                     // 昇順に並び替え
      .join(' ')                                 // 空白を間に入れる

  )(makeBookList(inputs[2],inputs[1]), makeBookList(inputs[4],inputs[3]));

  // データが存在しなかったら ”None” を出力
  console.log(result.length === 0 ? 'None' : result);

  function makeBookList(data, limit) {
    return data.split(' ', limit).map(Number);
  }
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

Pythonによる関数 & オブジェクト指向アプローチ

セットオブジェクトを用いて，M2とM1の左差集合を作り並び替えて出力

set(M2).difference(M1) M2とM1のリストの差集合をつくる
sorted(iterable)       昇順に並び替え
map(str, list)         文字列に変更
" ".join(iterable)     空白をセパレータにして結合

# coding: utf-8
lines =  [input() for i in range(5)]
M1 = map(int,lines[2].split())
M2 = map(int,lines[4].split())

result = " ".join(
  map(str,list(sorted(set(M2).difference(M1)))))

print("None" if len(result) == 0 else result)

終わりに

関数型スタイルやオブジェクト指向のアプローチがより人間にとってのわかりやすさやシンプルさを目指していることがお分かりいただけただろうか。モダンなプログラミング言語は，両方の良い点が使えるようになっている。ぜひこういった手法を用いてのプログラムを組んでほしい
今回はマシン語やアセンブラには触れなかったが，プログラミング手法の潮流を理解し，さまざまなプログラミングスタイルを身につけ，状況によって使い分けられるようにしよう。