Git keeps asking me for my ssh key passphrase

stackoverflow.com

Do either:

  1. To add your private key to it:

ssh-add

This will ask you your passphrase just once, and then you should be allowed to push, provided that you uploaded the public key to Github.

  1. To add and save your key permanently on macOS:

ssh-add -K

This will persist it after you close and re-open it by storing it in user's keychain.

  1. To add and save your key permanently on Ubuntu (or equivalent):

ssh-add ~/.ssh/id_rsa

再帰関数とメモ化と分割統治法

  • 再帰関数
    • GCD(m, n) - 2つの整数から最大公約数を求める
      • ベースケース
      • 可視化
  • 再帰関数とメモ化

  • 部分和問題(最適な部分集合を見つける) with 分割統治法

    • 再帰関数を使うことで問題を少問題に分割できる

再帰関数

  • ベースケース
  • 振る舞いの可視化

ユークリッドの互除法

2つの整数m, n(m ≧ n)において、以下の手順を繰り返すことで最大公約数を求めることができる。

  1. 入力を m, n (m ≧ n) とする。
  2. n = 0 なら、 mを出力してアルゴリズムを終了する。
  3. mをnで割った余りを新たに nとし更に 元のnを新たにm とし 2. に戻る。
fn gcd(m: u32, n: u32) -> u32 {
    return if n == 0 {
        m
    } else {
        gcd(n, m % n)
    }
}

ベースケースと処理の可視化

無限ループしないように、ベースケースを定め、returnする。

f:id:yossan2:20211205183926p:plain

再帰関数とメモ化

フィボナッチ数列

f:id:yossan2:20211205183909p:plain

部分和問題 with 分割統治法

f:id:yossan2:20211205183849p:plain

参考書籍

https://www.amazon.co.jp/問題解決力を鍛える!アルゴリズムとデータ構造-KS情報科学専門書-大槻兼資-ebook/dp/B08PV83L3N

全探索 with 線形探索法

全探索 with 線形探索法

以下の3つの全探索問題を線形探索法を用いて解く方法を見ていく

  1. 1つの配列から1つの要素を見つける O(N)
  2. 2つの配列から各々1つの要素を取り出し、最適な組み合わせを見つける O(N2)
  3. ある集合から最適な部分集合を見つける O(2N)

線形探索法とは (About Linear Search Method)

一つ一つの要素を順に調べていく

問題例

1. 1つの配列から1つの要素を見つける




2. 2つの配列から各々1つの要素を取り出し、最適な組み合わせを見つける O(N2)




3. ある集合から最適な部分集合を見つける O(2N)




部分集合を2進数を使って表す方法

例: {a,b,c}の部分集合

添字 部分集合 2進数
0 {} 0b000
1 {c} 0b001
2 {b} 0b010
3 {b,c} 0b011
4 {a} 0b100
5 {a,c} 0b101
6 {a,b} 0b110
7 {a,b,c} 0b111

まとめ

全探索においては、「どうすればすべての場合を考慮し尽くせるか」ということが重要となる。

参考書籍

https://www.amazon.co.jp/問題解決力を鍛える!アルゴリズムとデータ構造-KS情報科学専門書-大槻兼資-ebook/dp/B08PV83L3N

SQL構文

SQL構文

書き順 評価順序 備考
1 7 SELECT (DISTINCT) 列の指定 DISTINCTを指定すると列の値が重複する場合、排除してくれる
2 2 FROM テーブル WHERE句で内部結合する際は、結合するテーブルをすべて列挙する
3 3 INNR(LEFT/RIGHT OUTER) JOIN 結合テーブル ON 結合条件 抽出条件より先に評価される
4 4 WHERE 抽出(選択)条件 集約より先に評価される
4 5 GROUP BY 集約キー SELECTで指定できるカラムは集約キーか集約関数に限定される
5 6 HAVING 集約条件 集約キーの値から集約対象にするのかどうか
6 - ORDER BY ソートキー
- 1 (サブクエリ) 別名「副問合せ」。なので句だけでなく関数の引数にも指定することができ、結果が()内に展開される

検索

列の選択

SELECT (DISTINCT) 列の選択
FROM 検索テーブル
  • SELECT DISTINCT 列1, ... 指定した列の値が重複する場合は、1つにまとめられる
    • NULLも一つの値として評価される

行の選択

SELECT (DISTINCT) 列の選択
FROM 検索テーブル
WHERE 抽出条件

抽出条件

述語(trueもしくはfalseを返す式)を指定することができる。 述語には、比較演算子、論理演算子やLIKE演算子などの特殊演算子が使用できる。

比較演算子

演算子 意味
= 等価
<> 等価でない
>= ~以上
> より大きい
<= ~以下
< より小さい

文字列'Hello'に一致する行を選択する

SELECT * FROM テーブル WHERE 列 = 'Hello'

特殊演算子

演算子 意味
LIKE 文字列検索
ANY 複数の値を実現し、どれか一致すればtrueを返す
ALL 複数の値を実現し、全てに一致すればtrueを返す
BETWEEN 範囲検索。両端を含む
IS (NOT) NULL =ではNULLかどうかの判定は不可
(NOT) IN 含まれるかどうか
EXISTS 他のテーブルにレコードが存在する場合、trueを返す

文字列に一致する行を選択する

SELECT * FROM テーブル WHERE 列 LIKE '完全一致検索'
SELECT * FROM テーブル WHERE 列 LIKE '%後方一致検索'
SELECT * FROM テーブル WHERE 列 LIKE '前方一致検索%'
SELECT * FROM テーブル WHERE 列 LIKE '_部分一致検索_'
  • % 0文字以上の任意の文字
  • _ 任意の一文字

ANYによる複数の値を実現

SELECT * FROM テーブル 列 = ANY(値1, 値2, 値3)
  • 列 比較演算子 ANY(...) という形を取る
  • ANY(値1, 値2, 値3) 値1,値2,値3のどれともなる
  • ANY(サブクエリ) サブクエリで出力される値となる

2021年8月1日から2021年8月31日の間の行を選択する

SELECT * FROM テーブル WHERE date BETWEEN '2021/08/01' AND '2021/08/31'

NULLでない行を選択する

SELECT * FROM テーブル WHERE 列 IS NOT NULL

任意の値に該当する行のみ選択する

SELECT * FROM テーブル WHERE 列 IN(値1, 値2, 値3)

Bテーブルにレコードが存在する行のみ選択する

SELECT * FROM Aテーブル WHERE EXISTS(SELECT * FROM Bテーブル WHERE B.列 = A.列)
  • サブクエリ側のSELECT句に指定する値は定数でもよい
  • サブクエリの結果、レコードが存在する場合は、trueを返す

テーブルの結合

SELECT -
FROM -
INNER(OUTER) JOIN 結合テーブルを指定
ON 結合条件
WHERE 行の選択

先に結合条件が実行され、次に抽出条件が実行される

3つのテーブルを結合する

SELECT A.列, B.列, C.列 FROM A 
    INNER JOIN B ON A.列 = B.列
    INNER JOIN C ON A.列 = C.列
    WHERE A.列 > 200
  • テーブルA,B,Cが結合条件に従って内部結合されてからWHEREによる抽出条件で行が選択される
  • 結合条件は過不足なくテーブルの列同士を'='で結びつける必要がある

NOTE

サブクエリの使用はNG

NG 1

SELECT A.列, B.列 FROM A 
    INNER JOIN B ON A.列 = (サブクエリ)

NG 2

SELECT A.列, B.列 FROM A 
    INNER JOIN B ON A.列 IN(サブクエリ)

WHERE句を使った結合

内部結合となる。 抽出条件と混ざるため、近年は、INNER JOINを使うのが一般的。

テーブルA,B,Cを内部結合する

SELECT * FROM A, B, C WHERE A.列 = B.列 AND B.列 = C.列 AND 抽出条件
  • FROM句に結合するすべてのテーブルを列挙する
  • WHERE句に結合条件を指定する
  • 抽出条件はANDで結ぶ

集約

行を1つもしくはグループごとにまとめる。

集約関数

集約関数を使うことで行を1つにまとめることができる。

集約関数 意味
SUM() 列の値を合計値
AVG() 列の値を平均値
MIN() 列の値の最小値
MAX() 列の値の最大値
COUNT(*もしくは) 引数に*を指定した場合、NULLを含める。DISITINCTキーワードが使用可能

列の値が重複しない行数を出力する

SELECT COUNT(DISTINCT 列) FROM テーブル

NOTE

入れ子にできない。

# NG
SELECT 集約関数(集約関数(列)) FROM テーブル

集約関数とGROUP BY句

テーブル全体で一行にまとめるのではなく、グループごとに集約する。

NOTE

SELECTに指定できるのは、集約キーもしくは、集約関数のみに制限される。

参考文献

  • SQL 第2版ゼロからはじめるデータベース操作
  • SQL 苦手を克服する本
    • 評価順序について
  • 出るとこだけ!基本情報技術者 午後
    • 標準SQL NG集
  • よく分かるSQL 高橋麻奈
  • 理論から学ぶデータベース実践入門
    • データベース実装について

Deref型

Deref型

代表的なDeref型

  • 参照型 &T
  • スマートポインタ String, Box<T>, ...

3つのDeref型強制

参照(More on Deref coersion)

If T implements Deref<Target = U>, and x is a value of type T, then:

  1. In immutable contexts, *x (where T is neither a reference nor a raw pointer) is equivalent to *Deref::deref(&x).
  2. Values of type &T are coerced to values of type &U
  3. T implicitly implements all the (immutable) methods of the type U.

1. Dereference(*)演算子によるDeref型強制

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Foo(i32);
let foo1 = Foo(1);
let foo2 = &Foo(2);

// *演算子でFoo型に戻すことができる
if foo1 > *foo2 {}

2. 型宣言とBorrow(&)演算子によるDeref型強制

型宣言 することで、参照型(&U)として取り出すことができる。 一種のキャスト?にあたるかも。

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Foo(i32);

struct FooBox(Foo);
impl Deref for FooBox {
    type Target = Foo;
    fn deref(&self) -> &Self::Target {
        &self.data
    }
}
let foo = Foo(5);
let foo_box = FooBox(foo);
let foo2: &Foo = &foo_box; // &演算子によるDeref型強制

3. ドット(.)演算子によるDeref型強制

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Foo(i32);
impl Foo {
    fn say_hello(&self) {
        println!("Hello Everyone")
    }
}

struct FooBox(Foo);
impl Deref for FooBox {
    type Target = Foo;
    fn deref(&self) -> &Self::Target {
        &self.data
    }
}
let foo = Foo(5);
let foo_box = FooBox {data: foo};
foo_box.say_hello(); // 自動参照外しによるDeref型強制

関連

自動参照外し (Auto-dereferencing) - あるマのメモ書き

*演算子(Dereference)とスマートポインター

*演算子(Dereference演算子)は

  • 参照型につかうと、参照外しされる。
  • スマートポインター(Deref実装型)に使うと、Deref型強制される。

メモ

pub trait Dref {
    type Target: ?Sized;
    fn deref(&self) -> &Self::Target;
}

不可変参照外し演算子(*v)によって使用される。

*演算子による明示的な参照外し演算子だけでなく、コンパイラによって暗黙的に使用される。 このメカニズムは、Deref型強制と呼ばれる。

Derefは、スマートポインターにのみ実装される。

Deref型強制

型Tが、Deref<Target = U> を実装し、xがTの値とした時、

  1. *x*Deref::deref(&x)と同一 - derefメソッドが呼ばれ、参照が外される
  2. &Tは、&U型に強制される
  3. Tは暗黙的に型Uのメソッドを実装する

例1. Box<T>型 (Deref)