K.Maebashi's BBS

>もう一つ質問なのですが、36行目から始まる外側のforループの判定条件を >「i < score_count - 1」としなかったのは何か訳があってのことでしょうか？ >もし何か訳があれば補足をお願い致します。 特に理由があるわけではないですし、こっちがよいとか主張したいわけでもないですが。 ・sorted_countは「ソートされた要素の数」である。 ・すべての要素がソートされた要素になればよいのだから、sorted_countが 　score_countになるまで回せばよい。 ということで、直感的であるかとは思います。 　107ページの図(Fig.2-7)に、「ソートずみの範囲」と「未ソートの範囲」を色分けし、間に線を引いた図がありますが、ソートが進むにつれ、この境界線がだんだん右に移動し、ついに右端に至ったときがソートの終了と考えれば、「sorted_count < score_count」になるように思います。境界線の右から左に、ぽいぽい要素を放り込んでいくイメージです。 　単純選択ソートにおいて、未ソート範囲から最小値を選ぶとき、たまたま未ソート範囲内の左端が最小値であれば、事実上交換は発生しません(同じ変数同士の交換になる)。、「sorted_count < score_count」としたとき最後に起きる無駄な交換も、現象としてはこれと同じです。単純選択ソートであれば、確かに言われてみれば最後に残った要素は最大値に決まってますから「境界線の右から左に放り込む」必要はないわけなのですが、コメントでも書いておかないと、私の場合「あれっ」とか思ってしまいそうです。 　挿入ソート(List 4-6)でも、「境界線の右から左に、ぽいぽい要素を放り込んでいく」操作を行いますが、こちらでは、最後に残るのが最大値とは限りません。単純選択ソートにおいて最後に最大値が残るのは、あくまでこのソート方法の特性なので、そこを理解して効率のよいコードを書くのもよいですが、必ずしもそこまでやらなくてもバチはあたらないのではないでしょうか。 # とか言いつつ挿入ソートのサンプルソースでは、sorted_countを1から始めてるな…(^^;

> 36行目から始まる外側のforループの判定条件を > 「i < score_count - 1」としなかったのは何か訳があってのことでしょうか？ > もし何か訳があれば補足をお願い致します。 C言語のfor文の判定条件は毎回評価されるので、年寄りとしては ループ内で不変な値を条件式に書くのは躊躇しちゃいますね。 たいてい lim = score_count - 1; for (sorted_count = 0; sorted_count < lim; sorted_count++) { としちゃいます。 まあ score_count が auto 変数でかつアドレス参照されてなければ、 あるいはループ内に関数呼びだしがなければ、いまどきのコンパイラは 自動的に同等な機械語に変換してくれるんでしょうけど。

面白い話題ですね。 私だったら、実行時の無駄を承知の上で判定条件を sorted_count < score_count; /* (-1)は付けない */ とします。 最小値を表す記号を min{x, y, z, ...} と書いたとき、 min{5, 3, 8} = 3 min{2, 2} = 2 min{6} = 6 などとなりますが、このminを定義(あるいは実装)するときに、 ・要素数が2個以上のとき……最小の要素を選ぶ ・要素数が1個　　のとき……その要素そのもの と場合分けするのが良いと考える人は少ないと思います。 そんな話はこの判定条件の問題とは違うのかもしれませんが、 大局的には同じようなセンスの問題をはらんでいると私には感じられます。 経験上は(って、アマチュアですけど)、このようなスタンスで臨むほうが 仕様変更や拡張に強いコーディングになるような気がします。

>my_sort5.cは挿入ソートではなく、単純選択ソートですね。 間違えました。 >(1)条件は「<」なのですから、sorted_countのループ内での最大値は >　score_count-1です。よって、score[sorted_count]で参照する限り、 >　範囲外を参照することはありません。 >(2)38行目からのループは、 >　for (i = sorted_count + 1; i < score_count; i++) { >　で始まっています。iがsorted_count + 1から始まりますが、 >　sorted_countが最大のとき、このループは1回も回らないので、score[i]で >　範囲外が参照されることもありません。 こちらから指摘しておいてすいません。その通りのようです。私が勘違いしていました。 もう一つ質問なのですが、36行目から始まる外側のforループの判定条件を 「i < score_count - 1」としなかったのは何か訳があってのことでしょうか？もし何か訳があれば補足をお願い致します。

>p106のmy_sort5.cのソースコード36行目から始まる単純挿入ソートなのですが、 >誤：for(sorted_count = 0; sorted_count < score_count; sorted_count++) { >正：for(sorted_count = 0; sorted_count < score_count - 1; sorted_count++) { >ではないでしょうか（判定条件の-1が抜けてる）。 >誤りと思われるコードでは、配列の範囲外を（配列の要素数より1つ分多く） >参照してしまうと思います。 my_sort5.cは挿入ソートではなく、単純選択ソートですね。 ソースを確認しましたが、 (1)条件は「<」なのですから、sorted_countのループ内での最大値は 　score_count-1です。よって、score[sorted_count]で参照する限り、 　範囲外を参照することはありません。 (2)38行目からのループは、 　for (i = sorted_count + 1; i < score_count; i++) { 　で始まっています。iがsorted_count + 1から始まりますが、 　sorted_countが最大のとき、このループは1回も回らないので、score[i]で 　範囲外が参照されることもありません。 ただ、単純選択ソートの原理は「未ソート部分から最小値を探してきて左端に持ってくる」というものですから、最後にひとつ残された未ソートの要素は最大値に決まっているので、無駄といえば無駄ではあります。現状のソースだと43～45行目のスワップで、必ず同じ変数をひっくり返します。 これはバグとは思いませんが、補足かなにかで書いておいた方がよいかもしれませんね(今日は時間が時間なのでアレですが)。 ご意見ありがとうございました。

前橋さんの「C言語体当たり学習」の読者です。 正誤表に反映されてない誤りと思われる記述を見つけたので報告させていただきます。 p106のmy_sort5.cのソースコード36行目から始まる単純挿入ソートなのですが、 誤：for(sorted_count = 0; sorted_count < score_count; sorted_count++) { 正：for(sorted_count = 0; sorted_count < score_count - 1; sorted_count++) { ではないでしょうか（判定条件の-1が抜けてる）。 誤りと思われるコードでは、配列の範囲外を（配列の要素数より1つ分多く）参照してしまうと思います。

>僕も新しいプログラミング言語を開発しました。言語名はKIです。 … >ぜひ、試してみてください。できる限り、オープンな形で今後も >開発を進めたいと思っていますので。 　すみません、ページを拝見したのですが、どういうソフトでどういう言語なのか、よくわかりませんでした。 　SaLAというのがKI言語の実行系のようですが、SaLAはHTMLの代わりにKI言語を解釈するWebブラウザのいとこようなものなのでしょうか。そして、それを使うと「KSCS Labo」に接続できて、お絵かきコンテストに参加できる? 　それはそれで面白そうではありますが、失礼ながら私は「有限会社カテナス」という会社を存じ上げているわけではないですから、「出処不明のソフトウェア」をそうそう軽々しくインストールするわけにも行きませんし。

>オブジェクト指向初心者です。 こんにちは。 >最終行の"こちら"の部分がリンク切れのようですが、どこへのリンクでしょうか？ 　すみません、以前にも指摘があって、掲示板には書いたのですが、HTMLの方は直していませんでした。 　書いたのはずいぶん前なので記憶が曖昧なところはありますが、ここのリンク先は↓です。 　http://kmaebashi.com/programmer/object/shigoto.html 　strtok()のように同時に2箇所で使えない「関数」では再利用性が高いとはいえないが、StringTokenizerのようにオブジェクトにすることで、より広く、どこでも自由に使えるようになった、という意図で書いています。

オブジェクト指向初心者です。 「疑り深いあなたのためのオブジェクト指向再入門」を拝見しましたが、 一部リンク切れがあり、内容が非常に気になりますので教えていただければ幸いです。 2. なぜわからなくなってしまうのか? オブジェクト指向で再利用性は高まるか? ～この点についてはこちらで後述します。 最終行の"こちら"の部分がリンク切れのようですが、どこへのリンクでしょうか？

僕も新しいプログラミング言語を開発しました。言語名はKIです。 いわゆる手続き型のプログラミング言語ではありません。 HTMLにJavaSctiptとCSSを加えたようなものと言えばいいでしょうか。 僕は、レイアウト言語と呼んでいます。HTMLは、巻物のようなもの、 つまり、終わりのない文書を整形するための言語ですが、KI言語は ページ内に文字列や図をレイアウトするための言語になっています。 僕自身も、プログラミング言語に関しては、全くの素人ですが、 いつの間にか、結構、大規模なものになりました。 ぜひ、試してみてください。できる限り、オープンな形で今後も 開発を進めたいと思っていますので。 http://www.kathenas.com/

>…と思ったら、 >http://b.hatena.ne.jp/HiromitsuTakagi/ 　高木さんのブックマークに取り上げられたおかげか、はてなでずいぶんブックマークされているようです。 http://b.hatena.ne.jp/entry/http://kmaebashi.com/zakki/zakki0042.html 　「反論」というほどではないにせよ「異論」的なものはあるようですのでコメントしたいのですが、いまちょっと時間が…

>高木さんによるサニタイズに関する記事に対する解釈は、僕も全く同じです。 …と思ったら、 http://b.hatena.ne.jp/HiromitsuTakagi/ で、高木さんご本人からお墨つきがあったんですね。 まあ当然ですなあ。

お、mmasudaさんのリンクをたどると見なれたページが… :-) 高木さんによるサニタイズに関する記事に対する解釈は、僕も全く同じです。 普段読んでる日記だと、 http://www.coins.tsukuba.ac.jp/~hdk/diary/d200602b.html#10-4 でも、本質的には同じ解釈がされてたし(日記の著者は筑波の院生さん)、 そう解釈している人はたくさんいるのではないかと思います。 ただし、それが多数派かどうかは断言できないかもしれないところが、 ちょっと怖い…

>８行目の >>違いが分かるようになりました。 >という書き込みは、本を全て読んだのではなく、まだまだ読むところがあるので >>違いが分かるようになってきました。 >に訂正です。 >小さなことで悪いですが・・・気になって夜も眠れないので訂正させてもらいます。 　や、190ページとのことなので3章の終盤程度ですか。 　3章のラストが「頭に叩き込んでおくべきこと――配列とポインタは別物だ!」なので、配列とポインタの違いに関して言えば、そこでひとまず終了、のつもりです。もちろん4章以降も読んでいただきたいですけれど。

>[895]のComroさんの誤植指摘を見て、なんとなく該当ページを久々に覗いてみたら…… >なんかSPAMトラックバックがえらいことになっていますね。 　ご指摘ありがとうございます。 　実はトラックバックSPAMは定期的に消しています(消すためのページを作りました。1件ずつチェックボックスで選んで削除するUIにしてしまったので数が多いと大変です)。 　ここ数日、出張してたりとかいろいろあって溜め込んでしまいました。放っておくと1日数十とかのオーダーでSPAMが来ます。 　あんまりひどいので、トラックバックのリンク先URLをドメイン単位ではじく機能を追加し、削除する際そのテーブルにドメインを追加しているのですが、それでもこの有様です。 　ちなみに現在禁止ドメインは1315件あります。はじいたトラックバックについては現在特に記録を残していないのですが、そのうち修正して、どれくらいの比率でSPAMをはじいているのかを見てみようと思っています。 　それにしてもなんでまたこんなWebの片隅にある手作りトラックバックにまでSPAMがやってくるのやら… 　「Brainfuckのせいか?」と思ったこともあるのですが、SPAMが来るのはあそこばかりでもないですし。

>前橋さんの書いた本(C言語ポインタ完全制覇)を入門書の次の次に読み、 お読みいただきありがとうございます。 >僕はPerlしか知りませんが、Perlはelsifです。 こちらもご指摘ありがとうございます。 elseifがふたつありましたね… typoでした。

８行目の >違いが分かるようになりました。 という書き込みは、本を全て読んだのではなく、まだまだ読むところがあるので >違いが分かるようになってきました。 に訂正です。 小さなことで悪いですが・・・気になって夜も眠れないので訂正させてもらいます。

[895]のComroさんの誤植指摘を見て、なんとなく該当ページを久々に覗いてみたら…… なんかSPAMトラックバックがえらいことになっていますね。 雑記帳のインデックスのページでは一番下の過去記事リンクにたどり着くまで ぐぉぉぉーっとスクロールしなきゃいけなくなってます。 http://kmaebashi.com/zakki/index.html 余計なお世話かと思いましたが、もし前橋さんがご存知でなければと思い、 指摘させていただきました。 個人的には閲覧の妨げとして無視できない量になりつつあるので、 できれば削除して欲しいなぁ、と思います。

前橋さんの書いた本(C言語ポインタ完全制覇)を入門書の次の次に読み、 分かりやすいし、補足も面白くて、良い本だと思い、作者をＹＡＨＯＯで検索したら、このページに着きました。 ちなみに、入門書の次に読んだ本は、よく分からず途中で止めて、C言語ポインタ完全制覇を読みはじめました。 今までに僕の買ったＣ言語関係の本にはこんなこと書いてなく、 この本を読むまでいつも、配列とポインタの違いが分からず混乱していましたが、 違いが分かるようになりました。 まだ、１９０Ｐぐらいまでしか読んでいませんが、早くこの本を全部読んで、 途中で読むのを止めていた入門書の次の本を読破したいです。 この本と早めに出合えて本当に良かったです。 そして、訂正ですが、 「プログラミング言語を作る」の「見た目の問題(2005/6/25)」の Perl, Ruby, MODULA-2, Ada, Eiffel elseifについて、 僕はPerlしか知りませんが、Perlはelsifです。 それでは。

>うーん、私が想定していたのは、内部形式をふたつ作るのではなく、 >「読み込んで内部形式に変換するところ」でまとめて変換する、というものでした。 >内部形式をふたつ作ってもよいでしょうが、ストロークを少なくするという >code golfの趣旨に反するような気がします。 ここでおっしゃっている内部形式が私の考えているものとずれているかもしれないですが、例えば、入力(文字列)を内部形式(メモリ上の変数)、例えば、リストなどに変換するのは、Pythonでは、sが入力文字列だとすると、list(s)とするだけですし、forなどに文字列(シーケンス)を直接渡しても、1文字ずつ処理してくれるので文字列が内部形式としても良いですし、どのタイミングで変換するかは問題ではないように思えますがどうでしょう？ 文字列を1文字ずつ処理するのは、例えば、以下のような感じ。 >>> s = 'test' >>> for c in s: ... print c, ... t e s t >Perlはたまに使いますがたまにしか使わないので身に付かず、 >PHPはここの掲示板を作った程度、 >Rubyはちょこちょこ見ては試しにプログラムを動かしたりはしてますが、 >Rubyのソースを書くのに費やした時間よりRubyの実装のソースを読んだ時間の方が >長いくらい、 >PythonはRubyについてよりも浅学ですねえ。 なるほどです。しかし、crowbarみたいなスクリプト言語を作れるというのはすごいと思います。PythonがRubyよりも浅学というのはPythonファンの私としては残念です。 >「Rubyソースコード完全解説」をWebで読んじゃって本を購入しなかったので、 >罪滅ぼしに「ふつうのHaskellプログラミング」を読んでたり。 私も「ふつける」は購入しましたが、最近、MYCOMから出た「入門Common Lisp」という本も買ってしまいました。最近、(ぱ)さんが本を出さないのは残念です。何か書く予定があったら教えてください。

>>それをすべきタイミングは >>Brainfuckソースを読み込んで内部形式に変換するところでしょうから、 >>「文字列変換」ではないですよね。 > >リスト(内部形式)に変換してから別のリスト(内部形式)に変換しても >良いかもしれません。 うーん、私が想定していたのは、内部形式をふたつ作るのではなく、 「読み込んで内部形式に変換するところ」でまとめて変換する、というものでした。 内部形式をふたつ作ってもよいでしょうが、ストロークを少なくするという code golfの趣旨に反するような気がします。 >Perl、PHP、Ruby、Pythonなどを想定していました。 Perlはたまに使いますがたまにしか使わないので身に付かず、 PHPはここの掲示板を作った程度、 Rubyはちょこちょこ見ては試しにプログラムを動かしたりはしてますが、 Rubyのソースを書くのに費やした時間よりRubyの実装のソースを読んだ時間の方が 長いくらい、 PythonはRubyについてよりも浅学ですねえ。 「Rubyソースコード完全解説」をWebで読んじゃって本を購入しなかったので、 罪滅ぼしに「ふつうのHaskellプログラミング」を読んでたり。

すいません(汗)。先ほどの返信で、 >さすがに(ぱ)も手を出しているのかなと思いました。 「(ぱ)さんも」と書こうとして、「(ぱ)も」と書いてしまいました…。大変失礼致しました…<_O_>

ご回答ありがとうございます。 >Code Golf自体は以前「Matzにっき」からリンクを辿って、ページの構成が >わかりにくいのもあってちょっと眺めただけでしたが。 ルールがどこに明記されているのか分かりにくいのは私も感じました。 >ええと、Brainfuck問題というのは > > ... > >で、課題は、 >・マスタングさんがPythonで書いたBrainfuckの処理系に、 >・課題のページで与えられているBrainfuckのコードを食わせて、 >・正しい解答が、4秒以内に得られること > >ですよね? (「4秒以内」という制限がどこに書いてあるのか、見つけられていませんが) その通りです。４秒以内というのは問題によってたまに書いてるのですが、Code Golfでのルールみたいです。 >うちの処理系をベースにしたのであれば、実行部分は、アルゴリズム的に小手先で >最適化できる余地はあんまりないのではないでしょうか(Brainfuck処理系には、 >「]」が来たとき実行時に「[」を検索しているようなものもありますが、うちの >処理系はそのへんは読み込み時に済ませていますし)。 >Pythonの実装に依存するチューニングの余地はあるかもしれません。読み込んだ >Brainfuckプログラムをどのような内部形式で保持するか、とか。 Pythonの実装に依存するチューニングは確かにありそうですが、残念ながら思いつきません。内部形式もリストを使用しているのですが、dict(辞書)も値として式しか書けないので使えなさそうですし他には分かっていません。 >5秒を4秒にする程度のことであれば、「++++」を「+4」のようなひとつのコードに >するというアイディアで十分かとは思いますが、それをすべきタイミングは >Brainfuckソースを読み込んで内部形式に変換するところでしょうから、 >「文字列変換」ではないですよね。 6秒を4秒かもしれません。文字列変換というのは、例えば、'>+++++[<+++]<.'という入力(文字列)が与えられたときに、'>+5[<+3]<.'という文字列に変換してからリスト(内部形式)に変換することを想定していました。リスト(内部形式)に変換してから別のリスト(内部形式)に変換しても良いかもしれません。 文字列変換を考えていたのは、正規表現で簡単にできないかなと考えていました。 >(「スクリプト」が何なのかが不明ですが)いろいろな言語の本やら解説ページやら >読んではいますが、簡単なチュートリアルの例題とかではなく、実際に日頃から >自分の問題を解くために使っていないと、「身に付く」ことにはならないようですね。 スクリプトは、最近、LL言語と言われているもの、例えば、Perl、PHP、Ruby、Pythonなどを想定していました。普段使ってないと身に付くことにならないというのは同感です。私もC++やJavaは本読んでいただけなので全く身についていません。 Ruby、Pythonは世間で今流行っているというイメージがあったので、さすがに(ぱ)も手を出しているのかなと思いました。Haskellとか関数型言語などを勉強しているのかなとか。 悩んでいても進まないのでとりあえず、Brainfuck問題はPendingしておくことにしました。ありがとうございます。

Code Golf自体は以前「Matzにっき」からリンクを辿って、ページの構成が わかりにくいのもあってちょっと眺めただけでしたが。 >最近Pythonを覚えて、Code Golf(http://codegolf.com/) >というコンペにはまっているのですが、Brainfuck問題というのがあり、(ぱ)さんのソースを参考にさせて頂いたのですが、最後の問題が４秒以内という制限にTime outでパスしません。恐らくあと1秒くらい短縮しないとダメみたいです。 ええと、Brainfuck問題というのは http://codegolf.com/brainfuck ここのことで、「最後の問題」というのは、このページの一番下のところにある Rot-13の問題のことですか? WikipediaのRot-13のページ： http://ja.wikipedia.org/wiki/ROT13 で、課題は、 ・マスタングさんがPythonで書いたBrainfuckの処理系に、 ・課題のページで与えられているBrainfuckのコードを食わせて、 ・正しい解答が、4秒以内に得られること ですよね? (「4秒以内」という制限がどこに書いてあるのか、見つけられていませんが) >ネックは、入力の1文字1文字をループで回しているところだと思うのですが、3百万回のループが問題になっていそうです。スクリプトはループに弱いので。 うちの処理系をベースにしたのであれば、実行部分は、アルゴリズム的に小手先で 最適化できる余地はあんまりないのではないでしょうか(Brainfuck処理系には、 「]」が来たとき実行時に「[」を検索しているようなものもありますが、うちの 処理系はそのへんは読み込み時に済ませていますし)。 Pythonの実装に依存するチューニングの余地はあるかもしれません。読み込んだ Brainfuckプログラムをどのような内部形式で保持するか、とか。 >何か一般的に早くアウトプットを得る方法はあるのですか？とりあえず、'++++'などを'+4'のようにすればループ回数が劇的に減るかなと思っているのですが、まだ試していません。うまい文字列変換が思いつかないので。 5秒を4秒にする程度のことであれば、「++++」を「+4」のようなひとつのコードに するというアイディアで十分かとは思いますが、それをすべきタイミングは Brainfuckソースを読み込んで内部形式に変換するところでしょうから、 「文字列変換」ではないですよね。 >あと(ぱ)さんはスクリプトは勉強とかされていますか？ (「スクリプト」が何なのかが不明ですが)いろいろな言語の本やら解説ページやら 読んではいますが、簡単なチュートリアルの例題とかではなく、実際に日頃から 自分の問題を解くために使っていないと、「身に付く」ことにはならないようですね。

お久しぶりです、マスタングです。もし分かれば教えて欲しいです。 最近Pythonを覚えて、Code Golf(http://codegolf.com/) というコンペにはまっているのですが、Brainfuck問題というのがあり、(ぱ)さんのソースを参考にさせて頂いたのですが、最後の問題が４秒以内という制限にTime outでパスしません。恐らくあと1秒くらい短縮しないとダメみたいです。 ネックは、入力の1文字1文字をループで回しているところだと思うのですが、3百万回のループが問題になっていそうです。スクリプトはループに弱いので。 何か一般的に早くアウトプットを得る方法はあるのですか？とりあえず、'++++'などを'+4'のようにすればループ回数が劇的に減るかなと思っているのですが、まだ試していません。うまい文字列変換が思いつかないので。他に何かうまい方法ありますか？ あと(ぱ)さんはスクリプトは勉強とかされていますか？

>プログラミング（超）初心者です。 はじめまして。ほめていただきありがとうございます。 最近仕事に追われておりまして、Webページの更新もすっかり滞り、 この掲示板も放置状態でしたが、久々に投稿いただきその点でもありがとうございます。 >前橋先生の他の本を購入しようと思っています。 それはもう是非(商魂モード)

プログラミング（超）初心者です。 「C言語体当たり学習　徹底入門」を図書館で借りました。 あまりのわかりやすさに大感激です。　(^o^)/ 前橋先生の他の本を購入しようと思っています。

>そういえばLGPLはスタティックリンクはだめでしたっけ。すっかり忘れてました。 必ずしもスタティックリンクが駄目というわけじゃないですが、 スタティックリンクすると、 LGPL http://www.gnu.org/licenses/lgpl.html の第6項 a) みたいな制約を満たさないといけなくなります。 すなわち、LGPL なライブラリを再リンクできるようにするため、 アプリケーションの側のオブジェクトコードか、ソースコードを 提供する必要が生じます。 それよりはダイナミックリンクして、第6項 b) の適用を選んだ方が 楽なことが多いんじゃないかと思います。