探索系アルゴリズム用のメモ

A* とかダイクストラ法とかが可視化されてるサイト。
こないだググったら案外うまくヒットしなかったので、メモ用に記録。

qiao.github.io

ロジック裏で把握するのも大事だけど、こんな風に可視化状態で見れるのもよいよね。

2021-01-08

やっぱすげぇ……

元ネタ
Linuxを生み出したリーナス・トーバルズが考える「優れたコード」とは何か？
gigazine.net

とりあえず、すげぇ雑にコード書いてみた。
gccでコンパイル可能( -std=c99 オプション、付けてちょ)。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//
typedef struct IntListItem {
  int value;
  struct IntListItem *next;
} IntListItem;
//
typedef struct {
    IntListItem *head;
} IntList;

void remove_01(IntList *l, IntListItem *target) {
  IntListItem *cur = l->head, *prev = NULL;
  while(cur != target) {
    prev = cur;
    cur = cur->next;
  }
  if(prev) {
    prev->next = cur->next;
  } else {
    l->head = cur->next;
  }
}
//
void remove_02(IntList *l, IntListItem *target) {
  IntListItem **p = &l->head;
  while( (*p) != target ) {
    p = &((*p)->next); // ちょっとだけ括弧を追記
  }
  *p = target->next;
}


int main() {
  //
  IntListItem *wk_before;
  IntListItem *wk_after;
  IntList l;
  l.head = NULL;

  // 作成
  for(int i = 0; i < 5; i++) {
    wk_after = (IntListItem *)malloc( sizeof(IntListItem) );
    wk_after->value = i + 1;
    wk_after->next = NULL;
    if (l.head == NULL) {
      l.head = wk_after;
    } else {
      wk_before->next = wk_after;
    }
    wk_before = wk_after;
  }


  // 表示
  IntListItem *wk;
  IntListItem *del;
  wk = l.head;
  while(wk != NULL) {
    printf("%d \n", wk->value);
    // 削除用のポインタを取得(後のテスト用)
    if (wk->value == 5) {
      del = wk;
    }
    wk = wk->next;
  }
  printf("\n\n");

  // 削除
  //remove_01(&l, del);
  remove_02(&l, del);
  // 表示
  wk = l.head;
  while(wk != NULL) {
    printf("%d \n", wk->value);
    wk = wk->next;
  }
  printf("\n\n");

  // 削除
  //remove_01(&l, l.head);
  remove_02(&l, l.head);
  // 表示
  wk = l.head;
  while(wk != NULL) {
    printf("%d \n", wk->value);
    wk = wk->next;
  }

  return 0;
}

「スタンフォード大学の計算機科学講義「Computer Science 101(CS101)」で紹介されていたコード」がremove_01、ライナスさんのコードがremove_02。

とりあえずどっちも動く事を確認。

大学のほうのロジックは普通に理解。

ライナスさんのほう……あぁなるほど「targetにきたら"その次"にすっとばしてtargetを実質的に骨抜きにする」んだ。
あと「先頭の削除」の時は、初っぱなの処理が「List->head へのポインタ」だから、「*p = target->next」でそのまま書き換わるんだ。

うん「言われて見て熟考したらわかる」んだけど、これを「思いつく」のって、すンごいなぁ………
面白くもあり、高みが遠くもあり。

2021-01-03

おいちゃんがプログラムで気にする所

親方

まぁつまり「気にしないところ」も少なからずあるのですが。
「規約がある所では、書いてある範囲で規約を重視しましょう / 書いてない規約は"既存のコード"に出来るだけあわせましょう」とかいう最低限のお話とか、さらにもっと最低限未満のお話として「syntax errorとか脆弱性あるコードとか書いてくんなボケ*1とかあるのですが。

その辺は押さえた上で、じゃぁおいちゃんが「何を気にしていて」「それはなんでなの？」ってのを、自分自身の内面の整理を兼ねて書いてみようかなぁ、と。

多分、おいちゃんが一番気にするのは

・YAGNI(You Aren't Going to Need it.)：それ、要らないよね？
・DRY(Don't Repeat Yourself.)：同じ知識を2箇所以上書くな

この2つ。
YAGNIのほうは割と簡単(な、はず)で、「まだ使わないけど使うかもと思ったので書いてみました」は大体ペケぽんの対象。
ただ、突き詰めていくと少しゴリゴリしてきて……その辺は

・KISS(Keep It Simple,Stupid)：シンプルにしておけ

とも関連するんだけど、「いらんループがある」とか「無駄な中間データを作ってる」とか、色々と出てくる。
昔、とある友人のエンジニアさんから「おいちゃんのコード、なんでそんなに短いの？」って聞かれた事があって、その言葉がずっと気になってたんだけど、多分、この辺を意識していたんだと思う。

少しかみ砕くと。
多分、何割かの人は「簡単"に"コードが書ける」のをよしとしているように思うんだけど。
おいちゃんは「簡単"な"コードが書ける」のをよしとしているんだろうなぁ、と思う。

「簡単なコードを書く」のは、試行錯誤もあるし書き直しもあるし考察もあるし色々あるんだけど、その辺の手間はあんまり惜しまないかなぁ、的な。
「アルルの女」あるいは職人の片思い( https://gallu.hatenadiary.jp/entry/2018/12/03/003823 )とか職人がかける手間暇( https://gallu.hatenadiary.jp/entry/20081118/p1 )とか参照していただければ幸い。
そういう手間をかけるのか、それとも「とりあえず書けたし動いてるしいいじゃん」で片付けるのか、の違いなのかもしれない。

なので、その辺まで考えると、YAGNIとかKISSとかって「結構深いお話」になるんだけど。
その辺の深さを「どれくらいまで追いかけていくか」ってのは、とても面白いんじゃないかなぁ？と思うんだけどどうなんだろ。

とりあえずお仕事でコードを見る時は
・「同じ配列をなんどもぶん回してる」コードとかは一端気にする(無理でなければ、1つにまとめてもらう)
・「今は不要なコード」は削除してもらう
ってあたりが気になる所かなぁ。

で、次にDRY。……こっちのほうがより気にするかもしれない。
「同じコードを二度かかない」って勘違いするケースがあって、そこを起点にしちゃうと色々と「スカポンタンな異論が出てくる」。
そうじゃなくて「Every piece of knowledge must have a single, unambiguous, authoritative representation within a system.(DeepL訳：すべての知識の断片は、システム内で単一の明確で権威のある表現を持たなければならない。)」なの。
この辺は DRYを勘違いしてたお orz( https://gallu.hatenadiary.jp/entry/20120410/p1 )を参照してくださいませ。

この話をすると

・PIE(Program Intently and Expressively)：意図を表現して！！
・SLAP(Single Level of Abstraction Principle)：抽象度は揃えろ！！

の話が絡んでくるんだけど。
「抽象度を揃えた状態で」「意図を表現して」「同じ意図の記述が二箇所以上あってコピペしている時」に、100tハンマーが飛び交います。

んで。この辺を前提にすると
・ここのコードもあっちのコードも「引数の10%の値を端数切り捨てでreturnしてる」から、1つにまとめよう
は、これがDRYにかなってるかは「わからない」んだよ。
だって「意図が見えない」んだから。

もしその処理が
・どっちも消費税計算
なんだとしたら、思考するまえに脊髄反射で共通化しつつ、コピペした人間を洗い出しましょう*2。

でも
・片方は消費税計算
・もう片方は手数料計算
だとしたら。すくなくとも「SLAPに従って"処理を書いてある"レイヤーの実装」は、それは「混ぜちゃ駄目」なんだよ。
だって「消費税計算」と「手数料計算」なんだもん。混ぜてどうすんのさ？

だから、まず「SLAPとPIE」なんだよ。
PIEとちょりとずれるかもしれないけど「意図をコメントで書いてよ」なんだよ。まぁこれくらいなら「コメントじゃなくて関数名でちゃんと」でもよし。
んで、その「意図」が「同じ(＝同じ知識の断片)」なのか「違う(＝異なる知識の断片)」なのか、を判断したいし、しなきゃいけないんだよ。

ちな、じゃぁ「違う意図だけど同じ実装を書いている場合の、実装レイヤーをどうする？」ってのは、まぁ議論としてはあって。
つまり「抽象度を揃えて"一番具象のレイヤー"の実装」の場合。
おいちゃんなら

public function 端数切り捨て計算(float|int $元値, float|int $百分率)

とかって具象関数切って、とりあえず処理はここに集約するかなぁ。入り口は別々にして。
例えばこれで「手数料だけ端数切り上げ」になったら、切り上げ用の関数(メソッド)切って、そっちに処理移せばよいし。

この辺までは「1つのメソッドだったり処理だったりの書き方」の部分で。
ここからもう少し広域なお話。

基本的には

・単一責任の原則：1つのプログラムには1つのことをうまくやらせる＠UNIXという考え方

を尊ぶので。
1つのクラスは「そのクラス(≒1インスタンスの意味)を20～30文字くらいで語れる」くらいの粒度で切るのが好きかなぁ。
なので「複数の役割(責任)が1つのクラスに渾然一体となっている」のは大変にお好まない感じ。
ただ「1つの責任の処理内容がそもそも割と膨大」な時は、程度問題でもあるんだろうけど「でっかくなっても、いいんじゃない？(とりあえず)」とは思う。
分解する必要性が見えてから分解すりゃいいんだし(ここもまた、レイヤーが違う YAGNI である。つまり「必要になってから分解する」)。

この辺が出来てくると、大分おちついてくるかなぁ。
後は、自分が書いたコードにしても人が書いたコードにしても、気になるところはあるか、と思うので。
コードリーダーとかにちゃんと相談してから、なんだけど

・ボーイスカウトの規則：来た時よりも美しく

ってのも大事だと思う。
っつか定期的なリファクタ、大切だよねぇ。明日になったら「明日」になるから、多分、綺麗にならない( https://gallu.hatenadiary.jp/entry/2019/04/17/220708 )辺りを参照していただければ幸い。

最後に。

・驚き最小の原則：自然な書き方にしようよ

ってのがあるんだけど、これ、割と難しいと思う。
おいちゃんは端的には「既存のコードを読んで出来るだけ"近い書き方"をする」ようにしてるかなぁ。
あと「同じ処理」の時は「同じ書き方」をするようにしてる。

ここから先「この言語だとこの書き方がよりよろし」とか色々あるんだけど、とりあえずざっくり、こんな事を考えながらコードをチェックしている気がする。
こーゆーのはまた色々、文章化してから後で読み返すと気づきがあったりもするので、一端まず、文面化してみませう。

突っ込み歓迎なので、なんかあったらコメントくださいませ。

*1:……どっちも実務上で実話 orz orz orz

*2:その後どうするかはしらにゃい

2021-01-01

0部まずは初めてみよう

親方 PHP PHP初心者本

0部まずは初めてみよう

本書では、最終的にはPHPを「概ねある程度のレベルまでを一通り」文法を中心に学習していけるように作成する予定です。
ここで諸々の蘊蓄をたれてもよいのですが、きっとこういったものを読むからにはなにがしか「プログラムを組む学習をしたい！！」というモチベーションがあるかと思うので。
その勢いを大切に、速やかにプログラムの学習に移っていきましょう。

2021-01-01

PHP初心者本、書いてみます！！

親方 PHP PHP初心者本

今年の目標「アウトプットを増やす」の一環として、PHP初心者本を書いていこうかなぁ、と思っています。

GItHubで
github.com
で書いていきますが、同時にここにも内容を記載していこうかなぁ、と……修正までは反映しないと思うので、修正版まで見たいようであればgithubをみていただくと確実かと思われます。

目次を
github.com
に書いていく予定なので、ここみておいてもらうと手っ取り早いのかもしれません。

……というわけで主に「自分を追い込むよう」に、ここに宣言をします(笑

2020-12-12

派遣と請負と準委任

親方

過去に書いた記事をざっくりとまとめてみようかなぁ、と。
……多分これくらいだと思うのですが、忘れてる記事とかあったらつっこんでくださいませノ

奴隷船の船員たち https://gallu.hatenadiary.jp/entry/20091128/p1
興味深いので：「完成」とは？「約束」とは？ https://gallu.hatenadiary.jp/entry/20131021/p1
で、本当のところは https://gallu.hatenadiary.jp/entry/20110127/p3
「偽装請負」を別の角度から https://gallu.hatenadiary.jp/entry/20140205/p1
おまけ：契約書上の注意 https://gallu.hatenadiary.jp/entry/20140205/p2
「炎上案件」を思い返しつつ分析してみる https://gallu.hatenadiary.jp/entry/20141106/p1
準委任の請け方 https://gallu.hatenadiary.jp/entry/2018/10/05/214857

と
身の処し方、守り方 http://gallu.hatenablog.com/entry/2014/11/02/171204

2020-11-27

2a問題が解決した！！！！

PHP

素晴らしき自動的な世界～或いは「型のない」世界～ https://gallu.hatenadiary.jp/entry/20061108/p1 で書いた、こんなお話、記憶にございますでしょうか？

PHP驚愕の事実
if ('2a' == 2) {
　ここ通る
}

ここから幾星霜、涙が大河となるくらいまであちこちで色々な問題を引き起こしてきました2a問題(大げさ)。
2a問題再びｗ https://gallu.hatenadiary.jp/entry/20070516/p1 でも書いた通り、switch でも遺憾なくその威力を発揮してまいりました。

が！！！
https://www.php.net/manual/ja/migration80.incompatible.php

下位互換性のない変更点
PHP コア
文字列と数値の比較
(厳密でないやり方で)数値と非数値文字列を比較する場合、数値を文字列にキャストし、文字列と比較するようになりました。

との事でさりげなく書いてあるこの内容が！全てを！改善しました！！！！

ってなわけで、まずソースコード。

<?php
declare(strict_types=1);

var_dump( PHP_VERSION );

var_dump( 2 == '2a' );

$i = '2a';
switch ($i){
    case 2:
        echo "2\n";
        break;
    case '2a':
        echo "2a\n";
        break;
}

環境その1

string(6) "7.4.11"
bool(true)
2

まぁ毎度お困りの状態*1。

環境その2

string(5) "8.0.0"
bool(false)
2a

ききました奥様？
falseですって！
2aですって！！

これですよコレ！！！

というわけで。
まぁもう少し色々と掘ってみないと、な所はありますが、とはいえ一端「2a問題が(多分大体)落ち着いてきた！！」ってことで、これは快挙なんじゃないかなぁ？と思うわけでございます。

ってなわけで記念Blog。

＆余談。
PHP8.0.0ですが、PHP7.4.xのconfigureオプションで(おいちゃんの場合)問題なくコンパイルできました。
インストール、とりあえずは楽なんじゃないですかしらん？？？

*1:なんでメンテナンスが11か、ってぇと、12と13が「This is a bug fix release.」だから、ちょいと止めてる状態

gallu’s blog

エンジニアでゲーマーで講師で占い師なおいちゃんのブログです。

探索系アルゴリズム用のメモ

やっぱすげぇ……

おいちゃんがプログラムで気にする所

0部まずは初めてみよう

0部まずは初めてみよう

PHP初心者本、書いてみます！！

派遣と請負と準委任

2a問題が解決した！！！！

0部 まずは初めてみよう

0部まずは初めてみよう