WildTree Wiki

ユーザ用ツール

サイト用ツール

トレース:
いろんな言語でハノイの塔

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン		前のリビジョン
いろんな言語でハノイの塔 [2019/06/27 22:40] – [性能] arakiいろんな言語でハノイの塔 [2021/04/30 12:38] (現在) – [Rust] araki
行 29: 行 29:
 ^Ruby |1.8.7 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |32 | ^Ruby |1.8.7 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |32 |
 ^Python |2.6.6 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |52 | ^Python |2.6.6 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |52 |
 +^bash |4.3.42 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |122 |
 +^awk (gawk) |3.1.8 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |8 |
 +^go|1.16.0|Core i3 5010U (2.1GHz) |Ubuntu 20.4 LTS|0.004 |
 +^Rust|1.47.0|Core i3 5010U (2.1GHz) |Ubuntu 20.4 LTS|0.004 |
 ===== プログラム ===== ===== プログラム =====
 ==== PowerShell ==== ==== PowerShell ====
行 44: 行 48:
 なお、デジタル署名するのが面倒くさかったので、実行にあたっては、実行ポリシーを''AllSigned''から''RemoteSigned''に変更した。 なお、デジタル署名するのが面倒くさかったので、実行にあたっては、実行ポリシーを''AllSigned''から''RemoteSigned''に変更した。
 ((管理者権限でPowerShellを起動して''PS C:\Windows\System32> Set-ExectionPolicy RemoteSigned''とする。)) ((管理者権限でPowerShellを起動して''PS C:\Windows\System32> Set-ExectionPolicy RemoteSigned''とする。))
 +管理者権限を使ってシステム全体のポリシーを変更するのがコワイ場合は、
 +<code>
 +PS C:\Users\araki> Set-ExecutionPolicy RemoteSignedd -Scope Process
 +</code>
 +のようにして、実行中のプロセス内でのみ許可することも出来る。
 +この方法には管理者権限は不要なので、気軽にスクリプトを試すことが出来る。
 +
 一般的な関数型言語が採用している、関数呼び出しと違い、引数を括弧でくくってカンマで区切ってはいけない。 一般的な関数型言語が採用している、関数呼び出しと違い、引数を括弧でくくってカンマで区切ってはいけない。
 括弧でくくってカンマで区切るとそれは配列として、関数の第一引数に全て渡されてしまう。 括弧でくくってカンマで区切るとそれは配列として、関数の第一引数に全て渡されてしまう。
行 879: 行 890:
 </code> </code>
  
 +==== Python ====
 +=== 能書き ===
 +Perl、Rubyと来たら、Pythonを出さないわけにはいかないでしょう。
 +今日では恐らくPythonが最も広く使われているのではないかと思います。
  
 +Pythonもオブジェクト指向言語であり、Perlよりずっとすっきりと記述できます。
  
 +ただ、個人的には、インデントでブロックを構成する仕様が好きになれなくて、PythonでもRubyでもいいならRubyを使いたい派です。
 +インデントによるブロックが嫌いなのは、エディタによっては、勝手にいくつかのスペースをタブに置きかえる場合があり、これが発動すると、見た目にはOKなブロックが実は破綻しているなど、コーディングに集中できないケースがあるからです。
  
 +こちらも、Perlに比べて、実行速度の面では劣る傾向があります。
 +=== コード ===
 +こちらも、特にひねりもない実装かと思います。
 +''if __name__ == '__main__':''で、''hanoi.py''をスクリプトとして起動した場合にのみ有効となるコードが記述されています。
 +つまり、クラスライブラリとそれに付随するサンプル、あるいはテストコードをひとまとめにしておくことも出来るのはなかなかに便利だと思います。
 +<code>
 +#!/usr/bin/env python
  
 +import optparse, sys
 +
 +class Hanoi:
 +    """ Hanoi's tower """
 +    def __init__(self, size = 3):
 +        self.size = size
 +
 +    def size(self):
 +        return self.size
 +
 +    def do(self, n = None, a = 1, b = 2, c = 3):
 +        if n is None:
 +            n = self.size
 +        if a == b or b == c or c == a:
 +            print "Same placement: ", a, ", ", b, ", and ", c
 +            raise
 +        if n == 0:
 +            return
 +        self.do(n - 1, a, c, b)
 +        print "Disc", n, "moved from", a, "to", b
 +        self.do(n - 1, c, b, a)
 +
 +if __name__ == '__main__':
 +    parser = optparse.OptionParser()
 +    parser.add_option('-n', '--size', help='Number of discs.', nargs=1, type='int', default=3, dest='size', action = 'store')
 +    args,r = parser.parse_args()
 +
 +    hanoi = Hanoi(args.size)
 +    hanoi.do()
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@chive[146]% time ./hanoi.py -n 4
 +Disc 1 moved from 1 to 3
 +Disc 2 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +Disc 3 moved from 1 to 3
 +Disc 1 moved from 2 to 1
 +Disc 2 moved from 2 to 3
 +Disc 1 moved from 1 to 3
 +Disc 4 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +Disc 2 moved from 3 to 1
 +Disc 1 moved from 2 to 1
 +Disc 3 moved from 3 to 2
 +Disc 1 moved from 1 to 3
 +Disc 2 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +0.043u 0.009s 0:00.06 66.6%     0+0k 112+0io 0pf+0w
 +araki@chive[147]% 
 +</code>
 +==== bash ====
 +=== 能書き ===
 +bashは、Bone Shell (sh)に変わって、現在のUNIX系システムの標準シェルの地位を確保しているシェルです。
 +シェルスクリプトはそれなりに強力であり、簡単な処理であれば、これだけでこなすことができます。
 +シェルがないUNIX環境は事実上ないので、どんな環境でも実行できるポータビリティは魅力です。
 +
 +もちろん、本格的なプログラム言語に比べて見劣りする部分も少なくないですが、DOSのバッチに比べればはるかに強力です。
 +PowerShellとであれば、いい勝負でしょうか。
 +PowerShellはパイプでオブジェクトも渡せるので、システムの機能をフルに引き出すという点ではbashに勝りますが、他は似たようなものでしょう。
 +=== コード ===
 +特に凝ったことはしていません。基本的には shでも動くんじゃないかと思います。
 +関数の引数は関数ローカルになっているので、ローカル変数を使わない限り普通に再帰もおこなえます。
 +このため再帰呼び出しの際に ''n = discs - 1''のようにして、減算を1回にしている他の言語と違って、呼び出しの度に''`expr ${1} - 1`''して、ローカル変数を避けています。
 +
 +<code>
 +#!/usr/bin/env bash
 +
 +function hanoi()
 +{
 +    if [ ${1} -gt 0 ]; then
 +        hanoi `expr ${1} - 1` ${2} ${4} ${3}
 +        echo "Disc ${1} moved from ${2} to ${3}"
 +        hanoi `expr ${1} - 1` ${4} ${3} ${2}
 +    fi
 +}
 +
 +size=3
 +while [ $# -gt 0 ]; do
 +    case $1 in
 +    "-h" | "--help")
 +        echo " -n <NUM>: Number of discs."
 +        echo " -h: show this message."
 +        exit 1
 +        ;;
 +    "-n" | "--size")
 +        size=$2
 +        shift; shift;
 +        ;;
 +    *)
 +        shift
 +    esac
 +done
 +hanoi ${size} 1 2 3
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@chive[152]% time ./hanoi.bash -n 4
 +Disc 1 moved from 1 to 3
 +Disc 2 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +Disc 3 moved from 1 to 3
 +Disc 1 moved from 2 to 1
 +Disc 2 moved from 2 to 3
 +Disc 1 moved from 1 to 3
 +Disc 4 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +Disc 2 moved from 3 to 1
 +Disc 1 moved from 2 to 1
 +Disc 3 moved from 3 to 2
 +Disc 1 moved from 1 to 3
 +Disc 2 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +0.051u 0.071s 0:00.13 92.3%     0+0k 0+0io 0pf+0w
 +araki@chive[153]%
 +</code>
 +==== awk ====
 +=== 能書き ===
 +awkは、AT&Tのベル研で、エイホ、ワインバーガ、カーニハンの三人により開発された、CSV形式のデータなどの処理に特化したスクリプト言語である。
 +一行野郎などと言われるように、本来は、単機能を実装したコマンドを、パイプでつないで、複雑な処理を実現するのが主な使い方であり、コードそのものをコマンドラインにタイプしてしまい、わざわざスクリプトファイルにしたりしないことも多い。
 +<code>
 +$ cat resul.txt | awk '{print $2;}' | sed -e "s/^(.*)$/'\1'/"
 +</code>
 +などのように、することで、ファイルの特定カラムの値を'でくくるなどの処理を簡単に行える。
 +
 +言語仕様が単純なこともあって、処理はそれなりに早い。
 +
 +また、パターンマッチングに正規表現が使えることも利点の一つである。
 +=== コード ===
 +普通の関数型言語の側面もあるので、そのまま、ストレートに実装してある。
 +<code>
 +#!/usr/bin/awk -f
 +function hanoi(n, a, b, c)
 +{
 +    if (n > 0) {
 +        hanoi(n-1, a, c, b);
 +        printf("Disc %d moved from %d to %d\n", n, a, b);
 +        hanoi(n-1, c, b, a);
 +    }
 +}
 +
 +BEGIN {
 +    size = 3;
 +    for (i = 0 ; i < ARGC ; i++)
 +    {
 +        if (ARGV[i] == "-h" || ARGV[i] == "--help")
 +        {
 +            printf(" -n <NUM>: Number of discs.\n -h: show this message.\n");
 +            exit(1);
 +        }
 +        if (ARGV[i] == "-n" || ARGV[i] == "--size")
 +        {
 +            size = ARGV[++i];
 +        }
 +    }
 +    hanoi(size, 1, 2, 3);
 +}
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@chive[157]% time ./hanoi.awk -n 4
 +Disc 1 moved from 1 to 3
 +Disc 2 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +Disc 3 moved from 1 to 3
 +Disc 1 moved from 2 to 1
 +Disc 2 moved from 2 to 3
 +Disc 1 moved from 1 to 3
 +Disc 4 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +Disc 2 moved from 3 to 1
 +Disc 1 moved from 2 to 1
 +Disc 3 moved from 3 to 2
 +Disc 1 moved from 1 to 3
 +Disc 2 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +0.003u 0.005s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
 +araki@chive[158]% 
 +</code>
 +==== Go ====
 +=== 能書き ===
 +Goは比較的新しいコンパイラ言語である。
 +静的型付けを基本とする言語であるが、メモリ管理は言語側が行い、ガベージコレクションなどの機能も内包している。
 +
 +関数型言語であり、構造体を使った、オブジェクト指向っぽい記述もできる。
 +
 +=== コード ===
 +
 +コマンドラインの引数をとるために flagを、表示の加工用に fmtモジュールを利用している以外は、コード内で完結している。
 +
 +<code>
 +package main
 +
 +import (
 +  "fmt"
 +  "flag"
 +)
 +
 +type Discs int
 +
 +type Hanoi struct {
 +    N Discs
 +    a int
 +    b int
 +    c int
 +}
 +
 +func NewTower(n int) *Hanoi {
 +    h := new(Hanoi)
 +    h.N = Discs(n)
 +    h.a = 1
 +    h.b = 2
 +    h.c = 3
 +    return h
 +}
 +
 +func (n Discs) doit(a int, b int, c int) {
 +    if n > 0 {
 +        (n - 1).doit(a, c, b)
 +        fmt.Printf("Disc %d moved from %d to %d.\n", n, a, b)
 +        (n - 1).doit(c, b, a)
 +    }
 +}
 +
 +func (h Hanoi) run() {
 +    h.N.doit(h.a, h.b, h.c)
 +}
 +
 +func main() {
 +    n := flag.Int("n", 3, "n <NUM>: Number of Discs.")
 +    flag.Parse()
 +    hanoi := NewTower(*n)
 +    hanoi.run()
 +}
 +</code>
 +=== 実行結果 ===
 +
 +<code>
 +araki@cherry:~/work/Hanoi$ time ./hanoigo -n 4
 +Disc 1 moved from 1 to 3.
 +Disc 2 moved from 1 to 2.
 +Disc 1 moved from 3 to 2.
 +Disc 3 moved from 1 to 3.
 +Disc 1 moved from 2 to 1.
 +Disc 2 moved from 2 to 3.
 +Disc 1 moved from 1 to 3.
 +Disc 4 moved from 1 to 2.
 +Disc 1 moved from 3 to 2.
 +Disc 2 moved from 3 to 1.
 +Disc 1 moved from 2 to 1.
 +Disc 3 moved from 3 to 2.
 +Disc 1 moved from 1 to 3.
 +Disc 2 moved from 1 to 2.
 +Disc 1 moved from 3 to 2.
 +
 +real    0m0.004s
 +user    0m0.005s
 +sys     0m0.001s
 +araki@cherry:~/work/Hanoi$
 +</code>
 +
 +==== Rust ====
 +=== 能書き ===
 +システム記述言語として注目を集めているRust。
 +メモリの管理が静的に行われており、予期せぬメモリリークなどによるセキュリティホールなどを言語レベルで防止できる。
 +
 +cargoを使用してひな型を作り、getoptsによるオプション処理を加えた。
 +ハノイの塔本体部分より、オプションの処理部分のほうが大きい。
 +なお、ハノイの塔部分に関しては特にオブジェクト指向的なつくりにはしていない。
 +=== コード ===
 +コードは、RubyやPythonなどのスクリプト型言語と似た感じになっているが、静的な片付けが行われているところが、これらの言語とは違っている。
 +また、ガベージコレクションによる動的なメモリ管理ではなく、静的な管理が中心となる。
 +
 +<code>
 +use getopts::Options;
 +use std::process;
 +use std::env;
 +
 +fn print_usage(prog_name: &str, opts: Options)
 +{
 +    let brief = format!("Usage: {} [Options]", prog_name);
 +    print!("{}", opts.usage(&brief));
 +    process::exit(1);
 +}
 +
 +fn hanoi(n: i32, a: i32, b: i32, c: i32)
 +{
 +    if n > 0
 +    {
 +        hanoi(n - 1, a, c, b);
 +        println!("Disc {} moved from {} to {}", n, a, b);
 +        hanoi(n - 1, c, b, a);
 +    }
 +}
 +
 +fn main()
 +{
 +    let args: Vec<String> = env::args().collect();
 +    let program = args[0].clone();
 +
 +    let mut opts = Options::new();
 +    opts.optopt("n","discs","Set number of discs.", "NUM");
 +    opts.optflag("h","help","show this message.");
 +    let matches = match opts.parse(&args[1..])
 +    {
 +        Ok(m) => { m }
 +        Err(f) => { panic!(f.to_string()) }
 +    };
 +    if matches.opt_present("h")
 +    {
 +        print_usage(&program, opts);
 +        return;
 +    }
 +    let n = match matches.opt_get_default::<i32>("n", 3)
 +    {
 +        Ok(t) => { t }
 +        Err(f) => { panic!(f.to_string()) }
 +    };
 +    hanoi(n, 1, 2, 3);
 +}
 +</code>
 +=== 実行結果 ===
 +<code>
 +araki@cherry:~/work/Hanoi/hanoi$ time target/debug/hanoi -n 4
 +Disc 1 moved from 1 to 3
 +Disc 2 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +Disc 3 moved from 1 to 3
 +Disc 1 moved from 2 to 1
 +Disc 2 moved from 2 to 3
 +Disc 1 moved from 1 to 3
 +Disc 4 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +Disc 2 moved from 3 to 1
 +Disc 1 moved from 2 to 1
 +Disc 3 moved from 3 to 2
 +Disc 1 moved from 1 to 3
 +Disc 2 moved from 1 to 2
 +Disc 1 moved from 3 to 2
 +
 +real    0m0.004s
 +user    0m0.003s
 +sys     0m0.001s
 +araki@cherry:~/work/Hanoi/hanoi$ 
 +</code>
  
  
  
  
いろんな言語でハノイの塔.1561675227.txt.gz · 最終更新: 2019/06/27 22:40 by araki