アマゾンをふらついていて、見つけてしまった本です。
☆の評価が4.7点/5点中という人気の本なんですが
昭和２９年６月２５日に発行となったこの本がいまだ
人気を誇っているというのもそそられる要因だったりしたのです 笑
いかにして問題をとくか…
本書は、数学を通し未知の問題に出会った場合どのように考えたらよいかを示した本で
日常の仕事においては、未知なる問題のオンパレードです。
そういったことを踏まえても本書は、魅力的な１冊に見えてくるわけです。
今度暇があった読もう。
2008年7月2日水曜日
2008年7月1日火曜日
れっつ、そーと。
「Effective Perl」面白いですねっ！
「Perlクックブック」だと分厚すぎて、時間のある時に
読もうと思い持ち運びなんて使いしづらいですもんね。
その点、Effective Perlなら手ごろな厚さで内容
も濃厚で読んでいて楽しいことこの上なしです！
で、今日は14項の「数限りなきソート術を学ぼう」を読んだのですが…
変なのキター！
というわけで、これですこれkr。
@filesに格納されているファイル名をファイル変更日付でソートかけてるわけです。
これだけだと何のことだかわけわかめなんで、順を追ってメモメモ。
まずは、sort関数と言うと…下記の通りですよね。
ソートされた関数 ＝ sort (ソート順の定義)? ソート対象のリスト;
じゃ、数字をsortしようとすると…
もし、ASCII順に並べ替えたいのならばこれでよいですが
たいていの場合この結果を期待する人は少ないはずですよね 汗
そうなると次に登場するのがソートの定義です。
さきほどの、数字の並び替えを期待したとおりに行うには下記のように
スペースシップ演算子を使って数値的にソートを行う必要がありますね。
今度は、期待した通りになりましたね！
では、最初のファイルを更新日順にソートする話に戻ります。
簡単に書くのであれば
一般的に、比較をベースとするソートアルゴリズムは、
１回のソートでn log n回(nはソートする要素数)と言われているそうです。
つまり、単純な数値比較だとn log n回の数値比較を行うのに対し
ファイルの更新日順に並べるソートの場合、n log n回分の
ファイル更新時間の取得とその比較を行っている為無駄の
多いソートになっているわけです。
例えば、初めて比較する時だけファイル更新時間の取得を行い
それをキャッシュしておき、2回目以降の比較の際はキャッシュを
参照した方が高速になります。
要は、n log n回分の比較と n回分のファイル更新時間の取得で済むので。
それをあらわしたコードが下記のようになります。
ちなみに、 $m{$a} ||= -M $a は、
$a = $a + 10; の省略形が $a += 10; となるのと同様に
$m{$a} = $m{$a} || -M $a; が $m{$a} ||= -M $a;
と、なっているだけです。
で、上の内容をPerlハカーな方々は、シュウォーツ変換を
活用して書くそうでそれが、一番最初に出てきたコードだったわけです。
本によると、シュウォーツ変換とは、mapで囲まれたsortである（？）となってます。
キューピー３分●ッキング♪
本日の●ッキングは、３つのファイルを更新順にソート致します。
まずは、材料を用意します。
今回は、my @names = qw(file1.txt file2.txt file3.txt);を使います。
まずは、ソートの条件を確認します。
比較対象→ファイル更新日
アウトプット→ファイル名
と、言うことでまずは、下準備から。
では、mapで名無しリストを作成します。
@names_and_ages = map { [$_, -M] } @names;
この時、@names_and_agesの各要素には、[$_, -M]という
ファイル名と更新日時の無名リストのリファレンスが格納されます。
@names_and_ages = [["file1.txt", file1.txtの更新日],
["file2.txt", file2.txtの更新日],
["file3.txt", file3.txtの更新日]
];
こんな感じですね。
次が、この○ッキングのメインのソートです。
@sorted_names_and_ages = sort {
$a->[1] <=> $b->[1]
} @names_and_ages;
$a <=> $bだと、リファレンスの比較になっちゃいますね 汗
比較したのは、更新日なので、リファレンスの第２要素を指定する為
$a->[1] <=> $b->[1]となってます。
調理が完成したら、@sorted_namesという皿に盛り付けるだけです！
@sorted_names = map { $_->[0] } @sorted_names_and_ages;
@sorted_names_and_agesには、更新日を元にリファレンスが並び替えられてます。
最終的に欲しいデータは、ファイル名なので…
ファイル名は、リファレンスの第１要素に格納されているので
mapで$_->[0]を抜き出してリストを作って完成っと。
同じ変数を代入していくと…
完成です＼(^o^)／
とっても、おいしい料理ができあがりましたね！！
では、もう一度本日のおさらいです。
１．並び変えるデータと並び変え判定に使うデータのリファレンスを作成。(map)
２．並び変え判定に使うデータで並び替え。（sort）
３．並び変えるデータと並び替え判定に使うデータから並び替えるデータを取り出す。（map）
以上！
で、sort関係に関連してネットをさまよっていたら楽しい
ページをいくつか見つけたのでメモ書きしておきますね。
あなたが一番好きなアルゴリズムを教えてください。
また、その理由やどんな点が好きなのかも教えてください。
はてなの質問です。
個人的にはエラトステネスの篩が好きです 笑
プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
弾さんの記事です。
こういう記事を見ない限りなかなかアルゴリズムの知識も
増えないので非常に為になりました。。
最後は、
いろいろなソートアルゴリズム
バブルソート/バケットソート/基数ソート/ヒープソート/マージソート/クイックソート
をJavaアプレットを駆使してわかりやすく解説してあります。
昔、おもれーって思って何度も眺めていた記憶が 笑
「Perlクックブック」だと分厚すぎて、時間のある時に
読もうと思い持ち運びなんて使いしづらいですもんね。
その点、Effective Perlなら手ごろな厚さで内容
も濃厚で読んでいて楽しいことこの上なしです！
で、今日は14項の「数限りなきソート術を学ぼう」を読んだのですが…
変なのキター！
というわけで、これですこれkr。
@sorted_names =
map { $_ -> [0] }
sort { $a -> [1] <=> $b -> [1] }
map { [$_, -M] } @files;
@filesに格納されているファイル名をファイル変更日付でソートかけてるわけです。
これだけだと何のことだかわけわかめなんで、順を追ってメモメモ。
まずは、sort関数と言うと…下記の通りですよね。
ソートされた関数 ＝ sort (ソート順の定義)? ソート対象のリスト;
use strict;
use warnings;
my @before = qw(e c a d b);
my @after = sort @before;
print "@after\n"; #a b c d eじゃ、数字をsortしようとすると…
use strict;
use warnings;
my @before = 1..10;
my @after = sort @before;
print "@after\n"; #1 10 2 3 4 5 6 7 8 9もし、ASCII順に並べ替えたいのならばこれでよいですが
たいていの場合この結果を期待する人は少ないはずですよね 汗
そうなると次に登場するのがソートの定義です。
さきほどの、数字の並び替えを期待したとおりに行うには下記のように
スペースシップ演算子を使って数値的にソートを行う必要がありますね。
use strict;
use warnings;
my @before = 1..10;
my @after = sort { $a <=> $b } @before;
print "@after\n"; #1 2 3 4 5 6 7 8 9 10今度は、期待した通りになりましたね！
では、最初のファイルを更新日順にソートする話に戻ります。
簡単に書くのであれば
use strict;
use warnings;
my @files = qw(file1.txt file2.txt file3.txt);
my @sorted = sort { -M $a <=> -M $b } @files;
print "@sorted\n";一般的に、比較をベースとするソートアルゴリズムは、
１回のソートでn log n回(nはソートする要素数)と言われているそうです。
つまり、単純な数値比較だとn log n回の数値比較を行うのに対し
ファイルの更新日順に並べるソートの場合、n log n回分の
ファイル更新時間の取得とその比較を行っている為無駄の
多いソートになっているわけです。
例えば、初めて比較する時だけファイル更新時間の取得を行い
それをキャッシュしておき、2回目以降の比較の際はキャッシュを
参照した方が高速になります。
要は、n log n回分の比較と n回分のファイル更新時間の取得で済むので。
それをあらわしたコードが下記のようになります。
use strict;
use warnings;
my @files = qw(file1.txt file2.txt file3.txt);
my %m;
my @sorted = sort {
($m{$a} ||= -M $a) <=>
($m{$b} ||= -M $b)
} @files;
print "@sorted\n";ちなみに、 $m{$a} ||= -M $a は、
$a = $a + 10; の省略形が $a += 10; となるのと同様に
$m{$a} = $m{$a} || -M $a; が $m{$a} ||= -M $a;
と、なっているだけです。
で、上の内容をPerlハカーな方々は、シュウォーツ変換を
活用して書くそうでそれが、一番最初に出てきたコードだったわけです。
本によると、シュウォーツ変換とは、mapで囲まれたsortである（？）となってます。
キューピー３分●ッキング♪
本日の●ッキングは、３つのファイルを更新順にソート致します。
まずは、材料を用意します。
今回は、my @names = qw(file1.txt file2.txt file3.txt);を使います。
まずは、ソートの条件を確認します。
比較対象→ファイル更新日
アウトプット→ファイル名
と、言うことでまずは、下準備から。
では、mapで名無しリストを作成します。
@names_and_ages = map { [$_, -M] } @names;
この時、@names_and_agesの各要素には、[$_, -M]という
ファイル名と更新日時の無名リストのリファレンスが格納されます。
@names_and_ages = [["file1.txt", file1.txtの更新日],
["file2.txt", file2.txtの更新日],
["file3.txt", file3.txtの更新日]
];
こんな感じですね。
次が、この○ッキングのメインのソートです。
@sorted_names_and_ages = sort {
$a->[1] <=> $b->[1]
} @names_and_ages;
$a <=> $bだと、リファレンスの比較になっちゃいますね 汗
比較したのは、更新日なので、リファレンスの第２要素を指定する為
$a->[1] <=> $b->[1]となってます。
調理が完成したら、@sorted_namesという皿に盛り付けるだけです！
@sorted_names = map { $_->[0] } @sorted_names_and_ages;
@sorted_names_and_agesには、更新日を元にリファレンスが並び替えられてます。
最終的に欲しいデータは、ファイル名なので…
ファイル名は、リファレンスの第１要素に格納されているので
mapで$_->[0]を抜き出してリストを作って完成っと。
同じ変数を代入していくと…
use strict;
use warnings;
my @files = qw(file1.txt file2.txt file3.txt);
my @sorted_names =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [$_, -M] }
@files;
print "@sorted_names\n";完成です＼(^o^)／
とっても、おいしい料理ができあがりましたね！！
では、もう一度本日のおさらいです。
１．並び変えるデータと並び変え判定に使うデータのリファレンスを作成。(map)
２．並び変え判定に使うデータで並び替え。（sort）
３．並び変えるデータと並び替え判定に使うデータから並び替えるデータを取り出す。（map）
以上！
で、sort関係に関連してネットをさまよっていたら楽しい
ページをいくつか見つけたのでメモ書きしておきますね。
あなたが一番好きなアルゴリズムを教えてください。
また、その理由やどんな点が好きなのかも教えてください。
はてなの質問です。
個人的にはエラトステネスの篩が好きです 笑
プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
弾さんの記事です。
こういう記事を見ない限りなかなかアルゴリズムの知識も
増えないので非常に為になりました。。
最後は、
いろいろなソートアルゴリズム
バブルソート/バケットソート/基数ソート/ヒープソート/マージソート/クイックソート
をJavaアプレットを駆使してわかりやすく解説してあります。
昔、おもれーって思って何度も眺めていた記憶が 笑
Project Euler.net
で、前フリを済ませたとこで…
さすがに、ランキング形式になている以上
解答のコードをのっけるわけにはいかないので
参考までに、
マシーンスペックと解答にかかった時間でものっけときますね。
(無駄の多いコード書くと途方に暮れてしまう場合がありますしねぇ 笑)
※測定に使っているノートPC。
OS:Microsoft Windows XP Professional Version2002 SP2
CPU:Intel® Core™2 Duo 2GHz
ﾒﾓﾘ:1GB RAM
Perl 5.8.8
(※1 スペックが高いマシーンだと差が出ないのでノートでチェックしてます)
(※2 Time::HiResモジュール使用)
Problem 1 0.001秒
Problem 2 0.000秒
Problem 3 0.003秒
Problem 4 0.042秒
Problem 5 0.057秒
Problem 6 0.001秒
Problem 7 16.516秒
Problem 8 0.004秒
Problem 9 9.391秒
Ploblem (7|9)は、もう少しコードの見直しをする余地がありそうですねぇ...
Ploblem 3の600851475143の素因数のうち最大の値は？
って問題は、純粋にエラトステネスの篩を使ってみたところ
3時間2分44秒もかかってしまいましたからねぇ 笑
いかに無駄を無く書くかってのが大事かってのが身にしみました…
現在215番目/310人中
さすがに、ランキング形式になている以上
解答のコードをのっけるわけにはいかないので
参考までに、
マシーンスペックと解答にかかった時間でものっけときますね。
(無駄の多いコード書くと途方に暮れてしまう場合がありますしねぇ 笑)
※測定に使っているノートPC。
OS:Microsoft Windows XP Professional Version2002 SP2
CPU:Intel® Core™2 Duo 2GHz
ﾒﾓﾘ:1GB RAM
Perl 5.8.8
(※1 スペックが高いマシーンだと差が出ないのでノートでチェックしてます)
(※2 Time::HiResモジュール使用)
Problem 1 0.001秒
Problem 2 0.000秒
Problem 3 0.003秒
Problem 4 0.042秒
Problem 5 0.057秒
Problem 6 0.001秒
Problem 7 16.516秒
Problem 8 0.004秒
Problem 9 9.391秒
Ploblem (7|9)は、もう少しコードの見直しをする余地がありそうですねぇ...
Ploblem 3の600851475143の素因数のうち最大の値は？
って問題は、純粋にエラトステネスの篩を使ってみたところ
3時間2分44秒もかかってしまいましたからねぇ 笑
いかに無駄を無く書くかってのが大事かってのが身にしみました…
現在215番目/310人中
Project Euler.net
最初の投稿だけながながと。
Project Eulerとは…
以下サイトより拝借(別名引用)[引用先：http://projecteuler.net/]
----------------------------------------------------------------------
What is Project Euler?
Project Euler is a series of challenging mathematical/computer
programming problems that will require more than just mathematical
insights to solve. Although mathematics will help you arrive at
elegant and efficient methods, the use of a computer and programming
skills will be required to solve most problems.
----------------------------------------------------------------------
個人的主観を交えた意訳をするとProject Eulerってサイトは、
コンピュータを必要とするような大きな桁の数学の問題を
みんなで解いてランキングしようぜ！ってお話。(ﾏﾃ
→http://projecteuler.net/
で、好きな言語で問題を解いて各問題のページには
回答用のフォームが用意してあるので回答を入力して
送信することで正誤のチェックをしてもらえます。
その正誤を元にランキングが作られているってわけ。
ランキングは、Top1000 Scorers、国別のランキング、言語別のランキングがあります。
回答だけ書けばよいので、その気になれば手計算でもよいし！
BFだろうがWhitespaceだろうがちょっと草植えときますね型言語
であろうが何でもOKですね！
問題に正解すると、正解者だけが見ることのできる
フォーラムへ移動することが可能になります。
フォーラムには、コードをのっけている人もいれば
コメントだけの人もいます。
今日現在(2008/07/01)。
お題は、２００問に到達。少しずつ増えてます！
興味ある人は、登録してめきめき解いてみたらいかがでしょうか？
問題文の日本語訳は、こちらにまとまってます。→こちら
Project Eulerとは…
以下サイトより拝借(別名引用)[引用先：http://projecteuler.net/]
----------------------------------------------------------------------
What is Project Euler?
Project Euler is a series of challenging mathematical/computer
programming problems that will require more than just mathematical
insights to solve. Although mathematics will help you arrive at
elegant and efficient methods, the use of a computer and programming
skills will be required to solve most problems.
----------------------------------------------------------------------
個人的主観を交えた意訳をするとProject Eulerってサイトは、
コンピュータを必要とするような大きな桁の数学の問題を
みんなで解いてランキングしようぜ！ってお話。(ﾏﾃ
→http://projecteuler.net/
で、好きな言語で問題を解いて各問題のページには
回答用のフォームが用意してあるので回答を入力して
送信することで正誤のチェックをしてもらえます。
その正誤を元にランキングが作られているってわけ。
ランキングは、Top1000 Scorers、国別のランキング、言語別のランキングがあります。
回答だけ書けばよいので、その気になれば手計算でもよいし！
BFだろうがWhitespaceだろうがちょっと草植えときますね型言語
であろうが何でもOKですね！
問題に正解すると、正解者だけが見ることのできる
フォーラムへ移動することが可能になります。
フォーラムには、コードをのっけている人もいれば
コメントだけの人もいます。
今日現在(2008/07/01)。
お題は、２００問に到達。少しずつ増えてます！
興味ある人は、登録してめきめき解いてみたらいかがでしょうか？
問題文の日本語訳は、こちらにまとまってます。→こちら
登録:
コメント (Atom)