WildTree Wiki

ユーザ用ツール

サイト用ツール

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

差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン		前のリビジョン
いろんな言語でハノイの塔 [2021/04/23 06:34] – [性能] arakiいろんな言語でハノイの塔 [2025/06/03 05:51] (現在) – [Batch (Cmd.exe)] araki
行 31: 行 31:
 ^bash |4.3.42 |Celeron N3150 (1.60GHz) |Vine Linux 6.5 |122 | ^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 | ^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|4 |+^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 ====
行 48: 行 49:
 ((管理者権限でPowerShellを起動して''PS C:\Windows\System32> Set-ExectionPolicy RemoteSigned''とする。)) ((管理者権限でPowerShellを起動して''PS C:\Windows\System32> Set-ExectionPolicy RemoteSigned''とする。))
 管理者権限を使ってシステム全体のポリシーを変更するのがコワイ場合は、 管理者権限を使ってシステム全体のポリシーを変更するのがコワイ場合は、
-<code>+<code powershell>
 PS C:\Users\araki> Set-ExecutionPolicy RemoteSignedd -Scope Process PS C:\Users\araki> Set-ExecutionPolicy RemoteSignedd -Scope Process
 </code> </code>
行 64: 行 65:
 ''Param()''の前にコードがあると、''Param()''がエラーとなる。 ''Param()''の前にコードがあると、''Param()''がエラーとなる。
 分かりにくいので、気づきにくいミス。 分かりにくいので、気づきにくいミス。
-<code>+<code powershell>
 Param([Int]$n = 3) Param([Int]$n = 3)
  
行 91: 行 92:
 === 実行結果 === === 実行結果 ===
 第2世代Core i7のVAIO Z2(VPCZ2)上のWindows 10/PowerShell 5.1.17763.592で実行した。 第2世代Core i7のVAIO Z2(VPCZ2)上のWindows 10/PowerShell 5.1.17763.592で実行した。
-<code>+<code powershell>
 PS C:\Users\araki> .\Documents\Hanoi.ps1 -n 4 PS C:\Users\araki> .\Documents\Hanoi.ps1 -n 4
 Disc 1 moved from 1 to 3. Disc 1 moved from 1 to 3.
行 130: 行 131:
 これを回避するために'':NORMALIZE''という関数を用意して、文字列''08''および''09''は、数値に置きかえるように処理している。 これを回避するために'':NORMALIZE''という関数を用意して、文字列''08''および''09''は、数値に置きかえるように処理している。
  
-<code>+<code dos>
 @echo off @echo off
  
行 205: 行 206:
 === 実行結果 === === 実行結果 ===
 PowerShell版と同じ環境で実行したが、恐ろしく遅い。 PowerShell版と同じ環境で実行したが、恐ろしく遅い。
-<code>+<code dos>
 C:\Users\araki\Documents>Hanoi -n 4 C:\Users\araki\Documents>Hanoi -n 4
 Disc 1 moved from 1 to 3 Disc 1 moved from 1 to 3
行 240: 行 241:
 ''getopt()''を使ったはずだけれど、違ったかも知れない。 ''getopt()''を使ったはずだけれど、違ったかも知れない。
 本体は''Hanoi()''関数であり、それ以外の部分は全て冗長である。 本体は''Hanoi()''関数であり、それ以外の部分は全て冗長である。
-<code>+<code c>
 #include <stdio.h> #include <stdio.h>
 #include <stdlib.h> #include <stdlib.h>
行 301: 行 302:
 速すぎて計測に意味がない。 速すぎて計測に意味がない。
 多分、''-n 20''くらいでやった方がいいんだろうと今更思う。 多分、''-n 20''くらいでやった方がいいんだろうと今更思う。
-<code>+<code bash>
 araki@chive[117]% time ./hanoic -n 4 araki@chive[117]% time ./hanoic -n 4
 Disc 1 moved from 1 to 3. Disc 1 moved from 1 to 3.
行 330: 行 331:
 Boostを使っているのは、コマンドライン引数の処理をしてくれる手頃なライブラリだからというだけで、別にGNU のparseoptなんかを使っても良かったのだが、まあ、そんな感じで、多分このせいでCに比べてやや遅くなっている。 Boostを使っているのは、コマンドライン引数の処理をしてくれる手頃なライブラリだからというだけで、別にGNU のparseoptなんかを使っても良かったのだが、まあ、そんな感じで、多分このせいでCに比べてやや遅くなっている。
 === コード === === コード ===
-<code>+<code cpp>
 #include <iostream> #include <iostream>
 #include <string> #include <string>
行 380: 行 381:
 === 実行結果 === === 実行結果 ===
  
-<code>+<code bash>
 araki@chive[131]% time ./hanoicc -n 4 araki@chive[131]% time ./hanoicc -n 4
 Disc 1 moved from 1 to 3 Disc 1 moved from 1 to 3
行 411: 行 412:
 でも、なんというか、C言語との食い合わせがいまいちなスタイルで、これが好きになれなかったんですよね。 でも、なんというか、C言語との食い合わせがいまいちなスタイルで、これが好きになれなかったんですよね。
  
-<code>+<code objc>
 #import <stdio.h> #import <stdio.h>
 #import <unistd.h> #import <unistd.h>
行 486: 行 487:
 そもそも、こういう題材に向いている言語ではないんだよね。 そもそも、こういう題材に向いている言語ではないんだよね。
 Quick Sortとか書くと Lispっぽくていいんだけれどね。 Quick Sortとか書くと Lispっぽくていいんだけれどね。
-<code>+<code lisp>
 ; ;
 (defun hanoi (n a b c) (defun hanoi (n a b c)
行 519: 行 520:
 </code> </code>
 === 実行結果 === === 実行結果 ===
-<code>+<code bash>
 araki@chive[171]% time clisp hanoi.cl -n 4 araki@chive[171]% time clisp hanoi.cl -n 4
  
行 556: 行 557:
 GNU Prologの場合ブートストラップコードをCで書くことが出来るので、コマンドライン引数の処理なんかはそっちでやっているから、本体だけしかないのでこのようになっている。 GNU Prologの場合ブートストラップコードをCで書くことが出来るので、コマンドライン引数の処理なんかはそっちでやっているから、本体だけしかないのでこのようになっている。
 参考までにブートストラップのコードも載せておく。 参考までにブートストラップのコードも載せておく。
-<code>+<code prolog>
  
 hanoi(0,A,B,C) . hanoi(0,A,B,C) .
行 562: 行 563:
 </code> </code>
  
-<code>+<code c>
 /* /*
  * Prolog Wrapper  * Prolog Wrapper
行 623: 行 624:
 === 実行結果 === === 実行結果 ===
  
-<code>+<code bash>
 araki@chive[177]% time ./hanoipro -n 4 araki@chive[177]% time ./hanoipro -n 4
 Disc 1 moved from 1 to 3 Disc 1 moved from 1 to 3
行 650: 行 651:
 コードにはコメントをつけてあります。 コードにはコメントをつけてあります。
 引数はなんとなくそんな感じになるように処理していますが、適当なので、あまり追求しないでください。 引数はなんとなくそんな感じになるように処理していますが、適当なので、あまり追求しないでください。
-<code>+<code rtl>
 #!/usr/bin/env rvtlw #!/usr/bin/env rvtlw
 1000 !=^GETARG       : Set Number of Discs 1000 !=^GETARG       : Set Number of Discs
行 704: 行 705:
 === 実行結果 === === 実行結果 ===
 処理系が優秀だからか、あるいは、そもそも、関数呼び出しなどの処理が軽いからなのか、かなり高速だと思います。 処理系が優秀だからか、あるいは、そもそも、関数呼び出しなどの処理が軽いからなのか、かなり高速だと思います。
-<code>+<code bash>
 araki@chive[109]% time ./hanoi.vtl -n 4 araki@chive[109]% time ./hanoi.vtl -n 4
 Disc 1 moved from 1 to 3. Disc 1 moved from 1 to 3.
行 740: 行 741:
 ''Hanoi''のインスタンスを作る際に円盤の枚数を宣言します。 ''Hanoi''のインスタンスを作る際に円盤の枚数を宣言します。
 あとは、''$hanoi->do;''とするだけで、処理を行います。 あとは、''$hanoi->do;''とするだけで、処理を行います。
-<code>+<code perl>
 #!/usr/bin/perl -w #!/usr/bin/perl -w
  
行 799: 行 800:
 </code> </code>
 === 実行結果 === === 実行結果 ===
-<code>+<code bash>
 araki@chive[125]% time ./hanoi.pl -n 4 araki@chive[125]% time ./hanoi.pl -n 4
 Disc 1 moved from 1 to 3 Disc 1 moved from 1 to 3
行 833: 行 834:
 特にひねりもなく、普通に実装してあります。 特にひねりもなく、普通に実装してあります。
 特筆するべきこともないかと思います。 特筆するべきこともないかと思います。
-<code>+<code ruby>
 #!/usr/bin/env ruby #!/usr/bin/env ruby
 # -*- coding: utf-8 -*- # -*- coding: utf-8 -*-
行 868: 行 869:
 </code> </code>
 === 実行結果 === === 実行結果 ===
-<code>+<code bash>
 araki@chive[131]% time ./hanoi.rb -n 4 araki@chive[131]% time ./hanoi.rb -n 4
 Disc 1 moved from 1 to 3 Disc 1 moved from 1 to 3
行 904: 行 905:
 ''if __name__ == '__main__':''で、''hanoi.py''をスクリプトとして起動した場合にのみ有効となるコードが記述されています。 ''if __name__ == '__main__':''で、''hanoi.py''をスクリプトとして起動した場合にのみ有効となるコードが記述されています。
 つまり、クラスライブラリとそれに付随するサンプル、あるいはテストコードをひとまとめにしておくことも出来るのはなかなかに便利だと思います。 つまり、クラスライブラリとそれに付随するサンプル、あるいはテストコードをひとまとめにしておくことも出来るのはなかなかに便利だと思います。
-<code>+<code python>
 #!/usr/bin/env python #!/usr/bin/env python
  
行 938: 行 939:
 </code> </code>
 === 実行結果 === === 実行結果 ===
-<code>+<code bash>
 araki@chive[146]% time ./hanoi.py -n 4 araki@chive[146]% time ./hanoi.py -n 4
 Disc 1 moved from 1 to 3 Disc 1 moved from 1 to 3
行 972: 行 973:
 このため再帰呼び出しの際に ''n = discs - 1''のようにして、減算を1回にしている他の言語と違って、呼び出しの度に''`expr ${1} - 1`''して、ローカル変数を避けています。 このため再帰呼び出しの際に ''n = discs - 1''のようにして、減算を1回にしている他の言語と違って、呼び出しの度に''`expr ${1} - 1`''して、ローカル変数を避けています。
  
-<code>+<code bash>
 #!/usr/bin/env bash #!/usr/bin/env bash
  
行 1003: 行 1004:
 </code> </code>
 === 実行結果 === === 実行結果 ===
-<code>+<code bash>
 araki@chive[152]% time ./hanoi.bash -n 4 araki@chive[152]% time ./hanoi.bash -n 4
 Disc 1 moved from 1 to 3 Disc 1 moved from 1 to 3
行 1027: 行 1028:
 awkは、AT&Tのベル研で、エイホ、ワインバーガ、カーニハンの三人により開発された、CSV形式のデータなどの処理に特化したスクリプト言語である。 awkは、AT&Tのベル研で、エイホ、ワインバーガ、カーニハンの三人により開発された、CSV形式のデータなどの処理に特化したスクリプト言語である。
 一行野郎などと言われるように、本来は、単機能を実装したコマンドを、パイプでつないで、複雑な処理を実現するのが主な使い方であり、コードそのものをコマンドラインにタイプしてしまい、わざわざスクリプトファイルにしたりしないことも多い。 一行野郎などと言われるように、本来は、単機能を実装したコマンドを、パイプでつないで、複雑な処理を実現するのが主な使い方であり、コードそのものをコマンドラインにタイプしてしまい、わざわざスクリプトファイルにしたりしないことも多い。
-<code>+<code bash>
 $ cat resul.txt | awk '{print $2;}' | sed -e "s/^(.*)$/'\1'/" $ cat resul.txt | awk '{print $2;}' | sed -e "s/^(.*)$/'\1'/"
 </code> </code>
行 1037: 行 1038:
 === コード === === コード ===
 普通の関数型言語の側面もあるので、そのまま、ストレートに実装してある。 普通の関数型言語の側面もあるので、そのまま、ストレートに実装してある。
-<code>+<code awk>
 #!/usr/bin/awk -f #!/usr/bin/awk -f
 function hanoi(n, a, b, c) function hanoi(n, a, b, c)
行 1066: 行 1067:
 </code> </code>
 === 実行結果 === === 実行結果 ===
-<code>+<code bash>
 araki@chive[157]% time ./hanoi.awk -n 4 araki@chive[157]% time ./hanoi.awk -n 4
 Disc 1 moved from 1 to 3 Disc 1 moved from 1 to 3
行 1085: 行 1086:
 0.003u 0.005s 0:00.00 0.0%      0+0k 0+0io 0pf+0w 0.003u 0.005s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
 araki@chive[158]%  araki@chive[158]% 
 +</code>
 +==== Go ====
 +=== 能書き ===
 +Goは比較的新しいコンパイラ言語である。
 +静的型付けを基本とする言語であるが、メモリ管理は言語側が行い、ガベージコレクションなどの機能も内包している。
 +
 +関数型言語であり、構造体を使った、オブジェクト指向っぽい記述もできる。
 +
 +=== コード ===
 +
 +コマンドラインの引数をとるために flagを、表示の加工用に fmtモジュールを利用している以外は、コード内で完結している。
 +
 +<code go>
 +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 bash>
 +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 rust>
 +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 bash>
 +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> </code>
  
いろんな言語でハノイの塔.1619159663.txt.gz · 最終更新: by araki