やかんです。
今日はややじめっとして暑めの1日だった気がします。
今日やったことについて
今日は、日中頑張って夕方走りに行って気分転換するというほぼ理想的な1日を送りました。
統計学（自学）
- やっぱり、連続型の確率変数について確率を求めるということに慣れてないな。
- 慣れるまでやるだけっすね。
- 連続型の確率分布についても期待とかはちゃんと定義されてる。いや、当然すぎてびびるけど。
- これ、Rをサラサラ使いこなせたら多分すごい便利だろうな。。検算とか。
- 正規分布は、期待値とか分散とかがちょうどいい値（整数とか）だったら標準正規分布に変換して扱えばいいんだ。
- 部分積分と置換積分は関数の積についての積分方法。
- これに慣れるの大事だよなあ。
アルゴリズムとデータ構造（自学）
- AVL木の実装むずいよー。
- 初期状態を考えて、そこからの変化を再帰的に表現したい。
- いや、シンプルかもしれない！←違いました。
- ツリーの下から考える。
- 子供が増えたら、親にtrue返す
- 親は、子供からtrue返ってきたら「子供増えたから左右でバランス取れてるかチェックして」ってことだから、同様の処理する。
- ということは、スタートは、追加された要素の親（要素が追加されたノード）が左右のバランスをチェックすることか？
- でもこれ、例えば何世代も連なっている親は、何世代も数えるということか？
- 100世代の親の場合、100数えるの？10^10とかきても同じなの？これどうなんだ？
- 平衡木って、バランスをとるための処理は計算量増やさないの？
- もう二分探索木のinsertは大丈夫だ。シンプルだし、実装方法も知ってしまえば簡単。
- これ、ツリーの実装は根から考えたほうがいいのかな？
- 根から考えると、必然的に要素数が少ない時から考え、徐々に要素数を増やしながら考えられる。これ結構有用なのでは？
- ぼてぼてだけど、とりあえずバランス処理の前までは実装できた。。肝要なのは、子供が成長していなかったら親も成長しなくていいってところだよな。
- 子供の高さが変わっていないなら、親の高さも変わっていないということ。
構造体の名前とかえぐ汚いけど、途中経過以下。これでようやく3割くらい？
#include <iostream>
#include <random>
using namespace std;
struct Node {
int data;
Node* right;
Node* left;
Node(int _data, Node* _right = nullptr, Node* _left = nullptr) : data(_data), right(_right), left(_left) {}
};
Node* root = new Node(1);
struct InsertReturnValue {
Node* node;
bool grow; // 木が成長したかどうか
};
// 子が付け加えられた親のnodeを返り値とする。
InsertReturnValue insert(Node* insertingNode, Node* node){
int insertingData = insertingNode -> data;
int data = node -> data;
if(insertingData < data){
// 左に行く。
if(node -> left == nullptr){
node -> left = insertingNode;
return {node, true};
} else {
InsertReturnValue val = insert(insertingNode, node -> left);
if(val.grow){} else {
return {node, false};
}
}
} else {
// 右に行く。
if(node -> right == nullptr){
node -> right = insertingNode;
return {node, true};
} else {
InsertReturnValue val = insert(insertingNode, node -> right);
if(val.grow){} else {
return {node, false};
}
}
}
}
Node* create_tree(){
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1,100);
for(int i = 0; i < 10; i++){
int data = dis(gen);
Node* node = new Node(data);
InsertReturnValue returnValue = insert(node, root);
Node* parent = returnValue.node;
}
}
int main(){
create_tree();
return 0;
}- 子供が成長したかどうかだけじゃダメなんだ。
- バランスについて-1, 0, 1を元に場合分けして親に伝える。
- 子供は親の状態を踏まえる必要がある？
ちょっと改善。まだ共通化とかはしない。今すると逆にごちゃりそう。いやでもこれ筋が悪いよなあ。
#include <iostream>
#include <random>
using namespace std;
struct Node {
int data;
int balance;
Node* right;
Node* left;
Node(int _data, int _balance = 0, Node* _right = nullptr, Node* _left = nullptr) : data(_data), balance(_balance), right(_right), left(_left) {}
};
Node* root = new Node(1);
struct InsertReturnValue {
Node* node;
int balance; // 木のバランス（-1, 0, 1）
};
// 子が付け加えられた親のnodeを返り値とする。
InsertReturnValue insert(Node* insertingNode, Node* node){
int insertingData = insertingNode -> data;
int data = node -> data;
if(insertingData < data){
// 左に行く。
if(node -> left == nullptr){
node -> left = insertingNode;
int balance = node -> right == nullptr ? 0 : 1;
node -> balance = balance;
return { node, balance };
} else {
InsertReturnValue val = insert(insertingNode, node -> left);
if(val.balance != 0){
// バランスを取るための処理。
} else {
return { node, 0 };
}
}
} else {
// 右に行く。
if(node -> right == nullptr){
node -> right = insertingNode;
int balance = node -> left == nullptr ? -1 : 0;
node -> balance = balance;
return { node, balance };
} else {
InsertReturnValue val = insert(insertingNode, node -> right);
if(val.balance != 0){
// バランスを取るための処理。
} else {
return { node, 0 };
}
}
}
}
Node* create_tree(){
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1,100);
for(int i = 0; i < 10; i++){
int data = dis(gen);
Node* node = new Node(data);
InsertReturnValue returnValue = insert(node, root);
Node* parent = returnValue.node;
}
}
int main(){
create_tree();
return 0;
}- これ、子ノードのバランスで条件分岐する前に、親ノードのバランスで分岐させるべきでは？
難しいので、再度挑戦します。今日はここまで。
アルゴリズムとデータ構造（授業）
今日オンラインだと思ってたら対面だった。。ハッシュ聞き逃したー、けどまあ自分で理解できないものでもなさそうだからよしとするか。。
集合群、ソートはちゃんと聞けたからよかった。
- ハッシュを使う場合は、データサイズを見積もって初期化する。
- ハッシュの再構成には時間がかかるから。
- つまり、データサイズの上限を見積もってそれより大きいサイズのハッシュを準備する。初期化。
- ハッシュの初期化をサボるとほぼバグのような状態になる。
- 集合IDによる表現は、mergeをO(logn)にすることができる。
- mergeの時に、必ず要素数の少ない方を書き換える。
- ハッシュは、言語ランタイムが提供してくれているのか？
- だとしたら、自分で実装する必要はないということか。
エンジニア業務
- 新しいPJになるから、まあまずはコードリードだよね。
- まあでもその前に使われているものを一通り手元で動かしてみるか。
- eslint
- prettier
- prettierについて、.prettierrcと.prettierrc.jsは機能同じだからどっちか一つ。
- clerkいじりたいな。
- firestore.indexes.jsonってなんだ？多分インデックス張るのと関係あるんだろうけど。
- インデックスは2-3木の応用。
- GPTとの問答。
オペレーティングシステム（自学）
- 今日は条件変数。今日もか。
- 条件変数の概念むずいな。
- 条件が満たされるまでは、スレッドを寝かす。実行可能じゃなく、中断中にする。
- わかりにくいから、条件変数を用いない場合と比較して理解してみる。
- pthread_cond_wait()は、スレッドのunlock、blockを行う。
- で、pthread_cond_broadcastとか実行されると、ここでブロックされたスレッドはrunnableな状態になる。
- 原則的に、pthread_cond_wait()でブロックされたスレッドはpthread_cond_broadcast()あるいはsignal()によってrunnableへと状態が変更される。
- pthread_cond_wait()は、ロックされたスレッドを引数にとる。つまり、条件変数を用いるときは、スレッドの排他制御が行われている必要がある。
- ロックされたスレッドを含むスレッド全体の効率を上げることが目的っぽい。
- で、pthread_cond_wait()はスレッドのunlockとblockが両方行われる。
- このunlockとblockは不可分に行われる必要があるということ。
- これはまあ、unlockとblockがnot不可分に行われた場合の不都合を考えればなんとなく直感的にわかる。
- 条件変数はとりあえずOKかな。
次、不可分更新命令等。
- CPUというかOSには不可分更新命令というものがある。不可分な処理をしてくれるapi。
- 休眠待機、ビジーウェイトってなんだっけか。
- 確かに、条件変数って必須じゃないよな。わざわざスレッドを寝かす必然性はないと言われればない。スレッドをブロックしなくても、解放してあげれば良いんだから。
- ↑演算結果は変わらない。つまり、演算自体は意図通りに済まされるが、CPUコアは、何もしないにもかかわらず割り当てられる場合がある。これが無駄だよね、という話だ。
- ビジーウェイトというのは、CPUのコアを使って、何度も条件をチェックするもの。だから、何回もif文に向き合う方法。確かに、if文がtrueになった瞬間にスレッドをスイッチできるから、そこだけ見れば速い。が、全体として見ればCPUの無駄遣いになってパフォーマンスが落ちると。
- ビジーウェイトによる排他制御はスピンロックと呼ばれる。
どうでもいいですが、今日やったことをGPTに与えてイラスト描いてもらったらこれ描いてくれました↓
ということで、今日の日記は終了。最後までお読みいただきありがとうございます。
