全探索と計算量の見積もり

競技プログラミング AtCoder 勉強 C++

この記事の内容

可能性をすべて試すプログラム（全探索）と計算量の見積もりについて書きます。

目次

問題の大きさの把握

数値の表現

通常C++では、整数はint型の変数で表現します。int型では、231 ~ 2*109 くらいまでの数を表現できるので、それより大きな数を扱うときは、long long 型を使用します。（210 = 1024 ~ 103を覚えておくとよいでしょう。）

符号付き整数の表現
type bits 下限 上限 備考
int 32 -231 231 - 1 約20億
long 32/64 非推奨
long long 64 -263 263 -1 C++から標準形
_int128_t 128 gcc拡張

各型で表現可能な範囲は環境によって異なりうります。

時間と空間の制約

競技プログラミングで出題される各問題には、実行時間と利用可能メモリについての制約も付加されています。
プログラムの実行時間やメモリの使用量は、(1)実行環境、(2)問題の大きさ、(3)アルゴリズムによって大きく変わりうります。

(1)の実行環境については、通常競技プログラミング側の実行環境は、十分高速なので、手元で効率的に動くことが確認できたら大丈夫です。また(2)の問題の大きさについても、問題になることはほとんどないです。競技プログラミングにおいては（あるいは普通のプログラミングにおいても）、(3)のアルゴリズムについてがどのような役割を果たすかが、最も重要な話題です。

組み合わせを試す

コンピュータが得意な解法はすべての組み合わせを力づくで試すことです。実際多くの問題はそれで解くことができます。全ての可能性を試すためには、for文を用いたり、再帰を用いたりします。

計算量の簡単な検討

for文が最大何回回るかを考えることで、計算量を見積もることができます。C++で大体1秒間のどれくらいの計算ができるかは、下の表の通りなので、問題を解くときの目安にしてください。

演算回数 コメント
1 000 000 余裕をもって実行可能
10 000 000 多分可能
100 000 000 とてもシンプルな演算なら可能

この表の数値は実行環境によって変わりますが、最近の多くのコンピュータのCPUは、1GHz(109)程度で動作しているので、CPUが100サイクル以内にできる演算なら、1秒間に107回程度まではおそらく実行可能と期待できます。
演算によってサイクル数は異なり、たとえば、メモリ参照やnew/deleteは、単純な算術演算よりそれぞれ10倍,100倍程度遅いです。

試行回数の見積もりと計算の手順の改良

下の例題を参考にして、計算方法の微調整により、計算量が異なることを見ていきます。


例題：Space Coconut Crab
宇宙ヤシガニの出現場所を探す．エネルギー E が観測されたとして，出現場所の候補は，x + y2 + z3 = E を満たす整数座標 (x, y, z) で，さらに x + y + z の値が最小の場所に限られるという．x + y + z の最小値を求めよ．(x, y, z は非負の整数，E は正の整数で 1, 000, 000 以下，宇 宙ヤシガニは，宇宙最大とされる甲殻類であり，成長後の体長は 400 メートル以上，足を広げれば 1, 000 メートル以上 ← 同じ数値でも重要な制約と余計な情報の区別に注意)
（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2012 より）


まず次のような方針を考える。

  • 方針１：変数x,y,zのすべてのパターンを調べ、それが条件を満たすかどうかを調べる。
    この場合どれくらいの計算量が必要かを見積もってみましょう。x,y,zの動く範囲は、それぞれ、x:[0,E],y:[0,E^{1/2}],z:[0,E^{1/3}]です。Eの最大値が106 より、最大で10 ^ 6 * 10 ^ 3 * 10 ^ 2 = 10 ^ {11}の計算量が必要です。これは、制限時間の8秒以内には終わりそうにありません。

したがって別の方針を考える必要があります。

  • 方針２：xとyのみを考え、E - x - y ^ 2 = z ^ 3 からzを決定する。 この場合は、(x, y)の組のみを考えれば良いので、計算量のオーダーは、10 ^ 6 * 10 ^ 3 = 10 ^ 9で済みます。

  • 方針３：上の方針２で動かす変数をx,zにする。 この場合は、計算量のオーダーは、10 ^ 6 * 10 ^ 2 = 10 ^ 8となり、方針2よりも計算量を減らせています。

  • 方針４：方針２で動かす変数をy,zにする。 この場合は、計算量のオーダーは、10 ^ 3 * 10 ^ 2 = 10 ^ 5となり、方針3よりもさらに計算量を減らせています。


このようにどのような方針で問題にアプローチするか（アルゴリズムの選択）によって大幅に必要な計算量は変わるので、計算手順の改良は問題を解くうえで非常に重要です。

整列と貪欲法

競技プログラミング AtCoder C++ 勉強

この記事の内容

C++における整列の使い方と整列を利用したアルゴリズムである貪欲法について説明します。

目次

整列

数値と文字列の整列

C++では、標準関数（STLの関数）として、sortが用意されています。整列に要する計算量は、列の長さをNとしてO(NlogN)です。

#include <algorithm>
#include <iostream>
using namespace std;
int A[5] = {3,5,1,2,4};
int main() {
sort(A,A+5); // 半開区間 [l,r) で指定する．sort(&A[0], &A[5]) と同じ意味
cout << A << endl;
}

配列を整列させる範囲を指定するには、&A[0]のように配列の要素を指すポインタを用います。一次元配列の場合には、単に Aと書くだけで、先頭要素を表すポインタに自動的に変換されます。つまり、sort(A,A+5)はsort(&A[0],&A[5])と同じ意味で、A[0]からA[4]まで（端点含む）が整列されます。

文字列の整列

標準ライブラリのsort関数は、数値だけではなく文字列stringの整列を行うこともできます。（一般に、比較演算子>が定義されている要素の配列が可能です。）
注意点としては、辞書式順序は、大文字小文字が混ざる場合は、C++のstd::stringの比較演算子の比較順序とは異なります。

ペアと整列

二つの要素が組みになっているようなデータ構造をペアといいます。整数のペアは以下のような構造体を用いて表現できます。

structure pair {
    int first;
    int second;
};

また、これと同様の使い勝手のいい、標準関数としてpairが用意されています。例えば、整数intのpairは、pair<int, int>で表現され、intをほかの型に置きかえれば、他のペアも利用可能です。通常はこちらの利用が推奨されます。また、ペアの二つの要素を同時に初期化する方法として、make-pairが用意されています。

pairのsort

ペアの配列も整列することができます。標準では、第一要素が異なるときは第一要素で順序が決まり、第一要素が同じときは第二要素で順序が比較されます。

#include <utility> // pair のため
#include <algorithm> // sort のため
#include <iostream>
using namespace std;
int main() {
pair<int,int> a[3]; // 整数のペア
a[0] = make_pair(170,60);
a[1] = make_pair(180,90);
a[2] = make_pair(170,65);

for (int i=0; i<3; ++i) // a[0] から a[2] まで表示
cout << a[i].first << ’ ’ << a[i].second << endl;
// 170 60
// 180 90
// 170 65 と表示されるはず

sort(a, a+3); // a[0] から a[2] まで整列

for (int i=0; i<3; ++i) // a[0] から a[2] まで表示
cout << a[i].first << ’ ’ << a[i].second << endl;
// 170 60
// 170 65
// 180 90 と表示されるはず
}

貪欲法

整列の重要な応用例として、貪欲法があります。 貪欲法とは、組み合わせを考えることなく、単独の値を順にひとつずつみて、閾値を超えるまで、節約するすることを貪欲に決める方法です。

問題例

  • 問題
護衛を上手に雇って，道中に襲われる人数の期待値を最小化する．護衛は 1 単位距離あたり 1
の金額で，予算がある限り，自由に雇える．
入力は，区間の数 N, 予算 M に続いて，距離と 1 単位距離あたりの襲撃回数の期待値のペア
⟨D,P⟩ が N 個.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2019
  • 解答の方針（貪欲法）
    せっかく護衛を雇うなら，もっとも危険な区間を守ってもらうのが良いです。なので、一番危険な道を選び，予算がある限りそこに護衛を雇います。予算の残額で道の区間全てをカバーできない場合は、安全になる区間と、危険なままの区間が生じます。 予算が残っている限り，2 番目に危険な道，3 番目に危険な道の順に同様に護衛を配置していきます。 残った危険な区間についての襲撃回数の期待値の和が答えとなります。 この計算課程では，⟨ 危険度, 長さ ⟩ のペアで道を表現し，危険な順に整列しておくと便利です。 (ここで危険度は，距離 1 移動する間に襲われる回数の期待値 を表します。)

区間スケジューリング

貪欲法の応用で、区間スケジューリングというアルゴリズムを紹介します。

問題設定

一つの共有資源（例えば体育館など）と、多数の利用申請（開始時刻と終了時刻もペア）があったとします。このとき、利用時間が重ならないという条件の下で最大いくつの申請を受けられるでしょうか。

問題の単純化

体育館や時刻といった具体的なものをとると、これは、多数の線分の集合から重なりが空集合であるという条件の下で、最大の部分集合をとるという問題になります。

アルゴリズム

この問題は、以下の手順によって解くことができます。
1. 右端が一番左にある線分（＝早く終わる申請）を選び、重なる部分とともに取り除きます。（線分の対称性から、左端が一番右にある線分から消していく方法でも大丈夫です。）
2. 未選択の線分があれば、1.を繰り返します。

機械学習tips（更新中）

機械学習 特徴量 python3 勉強

はじめに

機械学習の分野で、一つの記事にするほどではないけど、役にたつことをつらつらと書いていきます。

目次

permutation importance

permutation importance とは？

特徴量の重要度を評価する方法です。

計算方法

Permutation Importanceの使い方

具体的なPermutation Importanceの計算は以下の手順で行われます。
学習済みモデルをf, 特徴量行列をX, ターゲットベクトルをy, 損失関数（例えばMSE）をL(y,f)としたとき

  1. 本体のモデルを用いて、誤差eo = L(y, f(X))を計算する
  2. 全ての特徴量j = 1,...,Jに対して、 jをpermutationすることで特徴量行列Xpjを計算する
  3. 上記を用いて、permutation後の誤差ep = L(y,f(Xpj))を計算する
  4. Permutation Importance PIj = ep/eoを計算する
    上記の手順で計算したPermutation Importanceが大きければ大きいほど、特徴量jがモデルにとって重要であることがわかります。

注意すること

  • 相関係数の高い特徴量がある場合、片方を消してももう片方が精度を出してくれるので、重要度が高くないと判定されてしまうことがある。

正規化と標準化

正規化と標準化の使い分け

  • 正規化

    • 画像処理におけるRGBの強さ
    • sigmoid, tanhなどの活性化関数を用いる、NNのいくつかのモデル

  • 標準化

    • ロジスティック回帰、SVM、NNなど勾配法を用いたモデル
    • kNN, k-meansなどの距離を用いるモデル
    • PCA, LDA(潜在的ディリクレ配分法), kernel PCA などのfeature extractionの手法

  • 使わない

    • 決定木、ランダムフォレスト

ライブラリのインポート

# 正規化
from sklearn.preprocessing import MinMaxScaler
mmsc = MinMaxScaler()

# 標準化
from sklearn.preprocessing import StandardScaler
stdsc = StandardScaler()

特徴量エンジニアリング

intraction

特徴量同士に演算を作用させて、新たな特徴量を作り出す方法。

  • 四則演算、特に特徴量同士の差や比率が精度向上につながるケースがある。
  • 網羅的にやっても良いが、ビジネス的に意味のある量を作ることで精度を上げていることが多い。
  • もともとある特徴量同士だけではなく、もとの量と集約値といったパターンも多い。

どんなときに有効か

物理量や意味が明確な数値列が多数ある場合（差や割り算が聞くのは、同一単位系の両同士のことが多い。）

注意点

相関係数が大きくなってしまうので、注意

# 標準化
from sklearn.preprocessing import StandardScaler

def std(X):    
    stdsc = StandardScaler()
    ans = stdsc.fit_transform(X.reshape(100,1))
    return ans.reshape(100)

X = np.random.rand(100)
Y = np.random.rand(100)
print("そのまま")
print(np.corrcoef(X,Y))
print("+")
print(np.corrcoef(X,std(X+Y)))
print("-")
print(np.corrcoef(X,std(X-Y)))
print("*")
print(np.corrcoef(X,std(X*Y)))
print("/")
print(np.corrcoef(X,std(X/Y)))

出力そのまま [[1. 0.01216205] [0.01216205 1. ]] + [[1. 0.71464402]

[0.71464402 1. ]]

[[1. 0.70616477] [0.70616477 1. ]] * [[1. 0.70383358] [0.70383358 1. ]] / [[1. 0.10135746] [0.10135746 1. ]]




    
    
  



    
  

  




      
      
    
  
    
      
        

  

    

  
    

    
      
    
      

  

  C++ 速習チートシート（第一章　基本文法編）



  
  

  

    
    C++
    
    勉強
    
  



  

  




    


    

  
    
初めに



この記事の内容は、AtCoder Programming Guide for beginners（APG4b） の第一章の内容を素早く参照するためにまとめたものです。APG4bはAtCoderのアカウントを作れば無料で利用することができます。良くまとまっていてわかりやすいので、初めて勉強する方に大変おすすめです！（媚びを売っていくスタイル）



atcoder.jp



実行環境



実行環境はGCC/C++14です。



目次





おまじない



とりあえず何も考えないで、最初はこれをコピペしましょう。
int main(){}
の{}の中に実行したいコードを書きます。



#include <bits/stdc++.h>
using namespace std;

int main() {
}





細かい話



#include <bits/stdc++.h>



#include <bits/stdc++.h>はc++の機能をすべて読み込むという意味です。それぞれの機能を個別に読み込むことも可能で、例えば、coutやendlという命令は、#include <iostream>というところに入っています。最初のうちは、ややこしいので、#include <bit/stdc++.h>ですべて読み込んでしまいましょう。



using namespace std;



using namespace std;はプログラムを短く書くための命令です。#includeで読み込んだcoutやendlを使うためには、通常std::coutやstd::endlと書かなければなりませんが、using namespace std;を使うことでこのstd::の部分を省略できます。



コメントアウト



//または/* */でコメントアウトします。



//同じ行の以降の分がコメントアウトされます。

/*
挟まれている部分がすべてコメントアウトされます。
複数の行にまたがっていても大丈夫です。
*/





出力



c++で出力するにはcoutを使います。下の例では、coutに<<で"Hello, world!"という文字列を入れ、その後改行を意味するendlという命令を送っています。文の終わりには;が必要になるので注意してください。(c++では、ほとんどの構文は文末に;を要求します。)



#include <bits/stdc++.h>
using namespace std;

int main() {
  cout << "Hello, world!" << endl;
}





出力



Hello, world!




複数の出力



下のように複数の文字列や数字を出力することもできます。



#include <bits/stdc++.h>
using namespace std;

int main() {
  cout << "a:";
  cout << 23 << endl;
  cout << "b:" << 32 << endl;
}





出力



a:23
b:32




四則演算



#include <bits/stdc++.h>
using namespace std;

int main() {
  cout << 1 + 1 << endl; // 2
  cout << 3 - 4 << endl; // -1
  cout << 2 * 3 << endl; // 6
  cout << 7 / 3 << endl; // 2
  cout << 7.0/3.0 << endl; // 2.333...

//剰余演算子（あまりを計算）
  cout << 7%3 << endl; // 1

}






変数の宣言







 型 
 書き込むデータの種類 






 int 
 整数 




 double 
 小数 




 string 
 文字列 








#include <bits/stdc++.h>
using namespace std;

int main() {
  int i = 10;
  double d = 0.5;
  string s = "Hello";

  cout << i << endl;
  cout << d << endl;
  cout << s << endl;
}





実行結果



10
0.5
Hello




注意点



異なる方同士の演算



    

  • int と double の演算はdoubleになります。
    • 

  • intやdouble と string の演算は型が合わないためコンパイルエラーになります。
    • 





異なる型同士の代入



    

  • 計算と同様に、変換できる型同士の場合は変換されて代入されます。(double→intの場合は小数点以下切り捨て。)
    • 

  • 変換できない型の場合は、コンパイルエラーになります。（stringとint等）
    • 





入力



入力を受け取るためには、cinと>>を使います。



#include <bits/stdc++.h>
using namespace std;

int main() {
  int a;

  // 変数aで入力を受け取る
  cin >> a;

  cout << a * 10 << endl;
}





入力



5




出力



50




　



つなげて入力



入力が複数ある場合、>>をつなげて入力を受け取ることができます。
入力がスペースか改行で区切られている場合、分割して受けとってくれます。



#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << a * b * c << endl;
}





入力



2 3
4




a=2,b=3,c=4と代入されます。
出力



24




比較演算子







 演算子 
 意味 






 x == y 
 xとyが等しい 




 x!= y 
 xとyが等しくない 




 x > y 
 xがyより大きい 




 x < y 
 xがyより小さい 




 x >= y 
 xがy以上 




 x <= y 
 xがy以下 








論理演算子







 演算子 
 意味 






 !(条件式) 
 条件式の否定 




 条件式1 && 条件式2 
 条件式1が真かつ条件式2が真 




 条件式1 || 条件式2 
 条件式1が真または条件式2が真 








if文



if文は、



if(条件式){
処理
}





の形で書きます。



#include <bits/stdc++.h>
using namespace std;

int main() {
  int x;
  cin >> x;

  if (x < 10) {
    cout << "xは10より小さい" << endl;
  }

  cout << "終了" << endl;
}





入力



5




出力



xは10より小さい
終了




前の条件が真でないとき



else文やelse if文を使います。

else文は前のif文の処理が偽のときに実行されます。



if (条件式1) {
  処理1
}
else {
  処理2
}





else if文は前のif文の条件式が偽かつelse if文の条件式が真の場合に実行されます。



if (条件式1) {
  処理1
}
else if (条件式2) {
  処理2
}





変数のスコープ



main関数やif文で出てくる{}で囲われたところをブロックといいます。

あるブロックで宣言された変数はそのブロックとそれより内側のブロックでしか使えないというルールがあります。この変数が使用できるの範囲のことをスコープといいます。   　　
異なるスコープでは、同じ名前の変数を宣言することができます。



スコープが重なっている場合



あるブロックで宣言した変数



#include <bits/stdc++.h>
using namespace std;

int main() {
  int x = 5;
  cout << x << endl; // 5

  if (x == 5) {
    cout << x << endl; // 5

    string x = "hello"; // int x = 5;のスコープと重なっている
    cout << x << endl; // hello
  }

  cout << x << endl; // 5
}





出力



5
5
hello
5




この挙動はしばしばバグの原因となるため気を付けてください。



for文とwhile文



for文とwhile文はどちらも繰り返し処理を書きたいときに使います。



while文



#include <bits/stdc++.h>
using namespace std;

int main() {

  // iを0からはじめる
  int i = 0;

  // iが5未満の間ループ
  while (i < 5) {
    cout << "Hello" << endl; //繰り返したい処理
    i++;
  }

}





for文



for文は以下のように書き、条件式が真である限り処理を繰り返します。



for (初期化; 条件式; 更新) {
  処理
}





continueとbreak



    

  • continue;はfor文の残りの処理をスキップして、次のループに入るという命令です。
    • 

  • break;は今いるfor文から抜け出すという命令です。
    • 





for文の()の省略



for文の(初期化;条件式;更新)の部分は省略することが可能です。



初期化の省略



あらかじめ存在する変数をカウンタ変数に使用したい場合は、初期化が不要です。その場合例えば次のように書きます。



int i = 0;//カウンタ変数として使用
for (; i < n;) { //初期化を省略
  i++;
}





条件式の省略



条件式を省略した場合、条件式は常にtrueとして扱われます。たとえば、次のプログラムは無限ループとなります。



for (int i = 0; ; i++) {
  cout << i << endl;
}





for文とwhile文の違い



for文とwhile文では主に二つの点で異なります。



    

  • カウンタ変数のスコープの違い
whille文では、while文の前にカウンタ変数を宣言する必要があるため、カウンタ変数のスコープははその宣言がなされてから、while文の書かれているブロックが終わるまでとなります。一方for文では、カウンタ変数のスコープはfor文の中だけです。
    • 

  • continue;の動作への注意
while文では、インクリメントの前にcontinue;を入れてしまうと、カウンタ変数が更新されず、無限ループになってしまいます。
    • 





文字列



文字列を扱うには、string型の変数を使います。



文字列の長さの取得



文字列の長さは、文字列変数.size()で取得できます。これはメンバ関数というクラスを利用しています。



i番目の文字



i番目の文字の取得は、文字列変数.at(i)でできます。iは0から始まることに注意してください。



文字(char型)



文字列の型として、string型がありますが、文字の型というものも存在していて、charという型を使います。string型と違って、char型は一文字分のデータしか保持することができません。

string型を表すのに""で囲ったように、char型を表すのには、''（シングルクォート）で囲みます。



#include <bits/stdc++.h>
using namespace std;

int main() {
  char c = 'a';
  cout << c << endl; // a
}





文字列変数.at(i)の型



文字列変数.at(i)の型はchar型です。



文字列の書き換え



文字列の一部を書き換えるときは、char型を使う必要があります。



#include <bits/stdc++.h>
using namespace std;

int main() {
  string str = "Hello";

  str.at(0) = 'M'; // char型の'M'

  cout << str << endl; // Mello
}





出力



Mello




注意点



全角文字の取り扱い



c++では、string型やchar型では、全角文字は文字化けしてしまい、うまく扱うことができません。全角文字を扱うには、string型ではない別の型を使う必要があります。(u32string等)



文字列のメンバ関数や演算子を利用するとき



"文字列".size()や後述する==演算子を利用するとき、一度変数に格納するか、"文字列".ssize()のように一度sを付ける必要があります。そうしないとコンパイルエラーになります。



#include <bits/stdc++.h>
using namespace std;

int main() {
  string str = "Hello";
  cout << str.size() << endl; // 5
  cout << "Hello"s.size() << endl; // 5（sを末尾につける）
  cout << "Hello".size() << endl; // できない
}





文字列の比較



string型にも数値型のような比較演算子が定義されています。







 演算子 
 意味 






 == 
 二つの文字列が完全に一致 




 != 
 二つの文字列に違いがある 




 <, <=, >, >= 
 辞書順による比較 








辞書順というのは、文字通り辞書に載っている順番のことです。

c++の順序では'0'～'9'→'A'～'Z'→'a'～'z'の順になっています。

例えば、"012"s < "ABC"s == trueであり"ABC"s < "xyz"s == trueです。



文字列の連結



+演算子を使うと文字列を連結することができます。ただし、数値型のように-,*,/は定義されていないので注意しましょう。



#include <bits/stdc++.h>
using namespace std;

int main() {
  string hello = "Hello";

  // +演算子による連結
  cout << hello + ", world!" << endl; // Hello, world!

  // +=演算子による連結
  hello += ", Lime!";
  cout << hello << endl; // Hello, Lime!
}





出力



hello, world!
Hello, Lime!




string型とchar型



    

  • string型とchar型の比較はできません。
    • 

  • string型とchar型を+演算子で連結することはできます。
    • 





char型の変数への入力



cinでchar型の変数に入力を格納すると、１文字ずつ値を入れることができます。



#include <bits/stdc++.h>
using namespace std;

int main() {
  char a, b;
  cin >> a >> b;

  cout << a << endl;
  cout << b << endl;
}





入力



OK




出力



O
K




エスケープシーケンス



改行などの特殊な文字を利用する場合、エスケープシーケンスを利用します。
エスケープシーケンスとして例えば以下のようなものがあります。







 エスケープシーケンス 
 意味 






 \n 
 改行 




 \" 
 ダブルクォート 




 \' 
 シングルクォート 




 \ 
 バックスラッシュ() 




 \t 
 タブ 




 \r 
 復帰 








#include <bits/stdc++.h>
using namespace std;

int main() {
  cout << "こんにちは\nLime";
}






出力



こんにちは
Lime




行単位での入力



cinを使うとスペースを区切りにして、簡単に入力を受け取ることができますが、場合によっては、行単位で入力を受け取りたいときもあります。その場合はgetlineを使います。



#include <bits/stdc++.h>
using namespace std;

int main() {
  string s, t;
  getline(cin, s); // 変数sで入力を一行受け取る
  getline(cin, t); // 変数tで入力を一行受け取る

  cout << "一行目 " << s << endl;
  cout << "二行目 " << t << endl;
}





入力



I have a pen.
I have an apple.




出力



一行目 I have a pen.
二行目 I have an apple.




配列



文字列を格納するための変数として、string型がありましたが、これはchar型をリストにしたものとみなすこともできます。これと同じように考えて、ある変数の型のリストとして、配列というものを考えることができます。
配列の宣言は次のようにして行います。



vector<型> 配列変数名;





また配列に値を代入する方法はいくつかありますが、その一つとして下のような方法があります。



配列変数 = { 要素1, 要素2, ... };




例



#include <bits/stdc++.h>
using namespace std;

int main() {

  // 文字列
  string str; // 文字列変数を宣言

  str = "abcd"; // 'a', 'b', 'c', 'd' という文字(char)の列を代入

  cout << str.at(0) << endl; // 1つ目である'a'を出力

  cout << str.size() << endl; // 文字列の長さである4を出力


  // 配列
  vector<int> vec; // int型の配列変数vecを宣言

  vec = { 25, 100, 64 }; // 25, 100, 64 という整数(int)の列を代入

  cout << vec.at(0) << endl; // 1つめである25を出力

  cout << vec.size() << endl; // 配列の長さである3を出力
}





配列が持つ一つ一つのデータのことを要素といいます。

また、文字列と同様に、.size()を使うことで配列の長さが取得でき、.at(i)を使うことでi番目の要素にアクセスすることができます。



配列の初期化



次のように書くと、指定したサイズで配列が初期化されます。どんな値で初期化するかは、要素の型によって変わります。



vector<型> 配列名(要素数);




初期値の指定



次のように書くと配列の初期値を指定できます。



vector<型> 配列名(要素数, 初期値);




例えば、vector vec(3,5);と指定した場合、長さ3の初期値が{5,5,5}の配列が生成されます。



配列変数への入力



配列変数で入力を受け取るには、十分大きな変数で配列を初期化した後、.at(i)で一つずつ入力していく必要があります。



// 3個の入力を受け取れるように 3要素の配列 {0, 0, 0} で初期化
vector<int> vec(3);

// atを使って1つずつ入力
cin >> vec.at(0) >> vec.at(1) >> vec.at(2);





要素の追加



配列は文字列のときのように+=を使って要素を追加することができません。しかし、その代わりに、"配列変数".push_back()を使って、配列の末尾に要素を追加することができます。



#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> vec = { 1, 2, 3 };

  vec.push_back(10); // 末尾に10を追加

  // vecの全要素を出力
  for (int i = 0; i < vec.size(); i++) {
    cout << vec.at(i) << endl;
  }
}





出力



1
2
3
10




また、要素の削除は"配列変数名".pop_back()をつかうことでできます。



配列同士の比較



文字列と同様に配列の比較も==を使って、行うことができます。

==では左辺と右辺の全要素が一致しているときのみtrueになり、それ以外はfalseとなります。

また、配列変数同士の比較のみ可能で、例えば{1, 2, 3}という記法はコンパイルエラーになります。



#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> vec1 = { 1, 2, 3 };
  vector<int> vec2 = { 1, 2, 3 };

  if (vec1 == vec2) {
    cout << "OK" << endl;
  }

  /*
  ↓これはコンパイルエラーになる
  if (vec1 == { 1, 2, 3 }) {
    cout << "NG" << endl;
  }
  */
}





STLの関数



 ## STLの関数とは何か？
C++にデフォルトで用意されている関数。以下のようにして呼び出せる。



関数名(引数1, 引数2, ...)





STLの関数の例



・min(a,b)
aとbのうち大きくないほうを返す。
・max(a,b)
aとｂのうち小さくないほうを返す。
・swap(a,b)
aとbの値を入れ替える。



配列を引数にする関数



reverse関数



reverse関数を使うと配列の要素の並びを逆にできます。

reverse関数には返り値がないことに注意してください。



#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> vec = {1, 5, 3};
    reverse(vec.begin(), vec.end()); // {3, 5, 1}

    for (int i = 0; i < vec.size(); i++) {
        cout << vec.at(i) << endl;
    }
}





sort関数



sort関数は配列の要素を小さい順に並び替えます。

sort関数にも返り値はありません。



#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> vec = {2, 5, 2, 1};
    sort(vec.begin(), vec.end()); // {1, 2, 2, 5}

    for (int i = 0; i < vec.size(); i++) {
        cout << vec.at(i) << endl;
    }
}





配列を渡す形式



STLの関数に配列を渡すときは、次の形式で渡すことが多いです。



関数名(配列変数.begin(), 配列変数.end())





細かい話



引数の実行順序



引数の実行順序は環境によって異なります。例えば、GCC,C++14では次のように後ろの引数から処理が行われます。



min(1 + 1, 2 + 2)
↓
min(2, 2 + 2)
↓
min(2, 4)
↓
2





関数



関数は自分で作ることもできます。関数を作成することを関数を定義するといいます。

次の例では、STLの関数のminと同じ動きをする、関数my_minを定義しています。



#include <bits/stdc++.h>
using namespace std;

// 関数定義
int my_min(int x, int y) {

  if (x < y) {
    return x;
  }
  else {
    return y;
  }

}

int main() {
  int answer = my_min(10, 5);
  cout << answer << endl; // 5
}





関数の定義



関数の定義はmain関数より前で行います。

関数の記法は以下の通りです。



返り値の型 関数名(引数1の型 引数1の名前, 引数2の型 引数2の名前, ...) {
  処理
}





返り値は次のようにreturn文で指定します。



return 返り値;





返り値がない関数



関数の返り値がない場合の存在します。

その場合は、返り値の型にvoidを指定します。返り値の型がvoidである関数のreturn文は次のように書きます。



return;





引数がない関数



関数の引数が不要な場合は、定義と呼び出しでは、()とだけ書きます。



#include <bits/stdc++.h>
using namespace std;

// 整数の入力を受け取って返す関数
// 引数なし
int input() {
  int x;
  cin >> x;
  return x;
}

int main() {
  int num = input(); // 引数なし
  cout << num + 5 << endl;
}





関数を自分で定義する理由



主に次のような3つの理由があります。



    

  • プログラムの重複が避けられる。
    • 

  • 処理の塊に名前を付けられる。
    • 

  • 再帰関数が書ける。
    • 





注意点



rturn文の動作



処理がreturn文の行に到達した時点関数の処理は終了してしまいます。



返り値の指定忘れ



返り値がある関数で返り値を指定し忘れると、どんな値が返ってくるかわかりません。エラーにならないので注意しましょう。　



引数はコピーされる



他の変数に値を渡した時と同様に、基本的に引数に渡した値はコピーされます。



#include <bits/stdc++.h>
using namespace std;

// 引数の値に5を足して出力する関数
void add5(int x) {
  x += 5;
  cout << x << endl;
  return;
}

int main() {
  int num = 10;
  add5(num); // numの値は引数xにコピーされる

  cout << num << endl; // numは10のまま
}





出力



15
10




関数が呼び出せる範囲



関数は宣言した後でしか呼び出せません。宣言するより前に関数を呼び出すとコンパイルエラーになります。



細かい話



プロトタイプ宣言



プロトタイプ宣言をすれば関数を定義する前に呼び出すことができます。プロトタイプ宣言とは、関数の名前と引数と返り値の型だけを先に宣言することです。



#include <bits/stdc++.h>
using namespace std;

// プロトタイプ宣言
void hello();

int main() {
  // プロトタイプ宣言をしたので呼び出せる
  hello();
}

void hello() {
  cout << "hello!" << endl;
  return;
}





引数名の省略



引数の名前は省略することができます。例えば、my_minのプロトタイプ宣言は次のように書くこともできます。



int my_min(int, int);





returnの省略



返り値がない場合、関数の末尾では、returnを省略できます。



main関数



初めのプログラムから出ていたmain関数も関数の一つです。

ただし、main関数は特別扱いされていて、returnを省略した場合は必ず0が返るようになっています。


    
    
  



    
  

  




      
      
    
  
    
      
        

  

    

  
    

    
      
    
      

  

  Zero-crossing rate（ZCR）の説明と実装(Python3)



  
  

  

    
    音声処理
    
    python3
    
  



  

  




    


    

  
    
概要



zero crossing rate(以下ZCR)とは、信号の中で正の値と負の値がどれくらい切り替わっているかを示す指標です。
英語版のwikipediaには、パーカッシブな音声を分類するのにつかわれると書いてあります。

また、ノイズがどれくらい入ってるかの指標として使われることもあるらしいのですが、体感的にはあまりわからないですね。



定義



数式的には例えば次のようにして、定義できます。（本当は指示関数で表したかったですが、はてなブログで書くのがめんどくさいので断念しました。）




\displaystyle{
zcr = \frac{1}{T-1}\sum_{t=1}^{T-1} (s_{t-1}s_t-1)*(-0.5)
}




ただし、Tは信号の長さ,s_iはi番目の信号の正負を表します。（正なら+1、負なら-1）。



実装



# python 3.6
#zcr 
def zcr(data):
    count = 0
    for i in range(len(data)-1):
        if data[i]*data[i+1] < 0:
            count += 1
    zcr = count/(len(data))
    return zcr







#show zcr graph
def show_zcr(data,sr,window_sec=1):
    split =int(len(data) / sr / window_sec)
    zcr_list = []
    for i in range(split):
        s = int(sr * window_sec * i)
        e = int(s + sr * window_sec)
        split_data = data[s:e]
        zcr_list.append(zcr(split_data))
        
    plt.plot(np.arange(0,(split*window_sec),window_sec),zcr_list)





参考



en.wikipedia.org


    
    
  



    
  

  




      
      
    
  
    
      
        

  

    

  
    

    
      
    
      

  

  コンピュータアーキテクチャの概要



  
  

  

    
    コンピュータアーキテクチャ
    
    コンピュータ科学
    
    勉強
    
  



  

  




    


    

  
    
この記事の内容



コンピュータアーキテクチャの概要について簡単に説明します。

それぞれの詳細については、また別の記事を書く予定です。



コンピュータアーキテクチャとは何か？



コンピュータアーキテクチャとはコンピュータの仕組みや構造のことをさします。



コンピュータの簡単な仕組み



コンピュータは一番下の階層にハードウェアがあり、その上にシステムソフトウェア、そのさらに上に、アプリケーションソフトウェア、そしてそのまたさらに上にユーザーがいるというように階層化されたシステムとして理解することができます。



重要な概念










コンピュータは非常に複雑な仕組みをしていて、すべての仕組みを理解することは容易ではありません。そこで、非専門家の人でも扱えるように、レイヤーという概念を利用して、コンピュータを利用しています。

レイヤーとは、ブラックボックス（入力とそれに対する出力だけ分かっているシステム、内部構造はわからない。）やモジュール、コンポーネント（ブラックボックスの集めて作ったさらに大きなブラックボックス。）によるシステムの階層化のことで、ブラックボックスの中の詳細の仕組みを知らずとも利用できるというある種の人類の工学的な知恵です。ブラックボックスにより階層化されているおかげで、われわれは、内部の詳細な動作を知らずともコンピュータを使いこなすことができるのです。



ハードウェアの構造



コンピュータは様々なハードウェアから構成されています。



    

  • CPU（Central Processor Unitの略で、コンピュータの計算のコアとなる部分。）
    • 

  • マウスやキーボードなどの入力機器
    • 

  • ディスプレイなどの出力機器
    • 

  • ディスク（データを記録し貯蔵しておく場所）
    • 

  • メモリ（実際にデータを動かしているところ）
    • 





メモリ階層



メモリ(memory)とは計算機を扱うときに、プログラムやデータを保存しておく装置のことです。

現在のコンピュータでは、このメモリは階層的に配置されています。

下に階層の例を挙げます。上に行くほど、高速に読み書きができますが、その分値段が高くなってしまいます。



    

  • レジスター
プロセッサの中にごく少数ある、もっとも高速に読み書きができるメモリ、非常に高速だが、その分値段も高い
    • 

  • キャッシュメモリ
レジスターよりは遅いが、そこそこ高速なプロセッサーの中にあるメモリ
    • 

  • メインメモリ（主記憶）　
プロセッサの外にあるメモリ、現在のコンピュータだと4~8GBくらいが標準
    • 

  • （磁気）ディスク
大きなデータを保存しておく場所
    • 





なぜ階層化されているのか



全てのメモリデータは常に参照されるわけではないため、”今”使用したいデータを上の階層（キャッシュやレジスタ）にもってきて、しばらく使わないデータは下の階層（ディスク）に保存しておいても、全部高速なメモリで実現した場合と比べて対して性能が変わらないためです。これにより、コンピュータのコストパフォーマンスは大幅によくなっています。



プログラミング言語






マルチプロセッサー（プロセッサーの並列化、分散化）



なぜ並列化、分散化する必要があるのか。



単体のプロセッサーの性能向上に陰りが見えてきたためです。（例えば、クロック周波数の上昇は近年、頭打ちとなってきています。）ムーアの法則は年々遅くなっています。



ワンチップマルチコア



一個のメモリーに複数のCPUをつなげる技術のことです。



分散処理



ワンチップマルチコアにCPUを載せられる量にも空間的な限界があるので、たくさんのコンピュータをネットワークでつないで、並列計算させる処理をします。この処理のことを分散処理といいます。


    
    
  



    
  

  




      
      
    
  
    
      
        

  

    

  
    

    
      
    
      

  

  情報理論を簡単に説明する。（第二章　情報理論の問題）



  
  

  

    
    勉強
    
    情報理論
    
  



  

  




    


    

  
    
この記事は、「今井秀樹(1984) 『情報理論』昭晃堂」の第二章を勉強した内容を記録した自分用のノートです。詳しい内容が気になる方は、元の教科書を買ってみてください！



第一章はこちら↓



slimelimestech.hatenablog.com



2.1 問題の提起



ここでは、2元通信路という通信路を使って説明します。2元通信路とは、0か1かという情報のみを伝達する通信路です。
さて、情報として{A,B,C,D}の4文字を伝える場合を考えます。この{A,B,C,D}のような情報源から発生する記号を情報源記号といいます。2元通信路では、時々0と1が誤って伝達されてしまうことがあります。今回はこの誤り率を10-4とします。そして、それぞれの情報源記号の発生確率が下の表のとおりであったとします。このとき次の二つの要請を満たす符号化の方法を考えてみたいと思います。







 情報源記号 
 発生確率 






 A 
 0.6 




 B 
 0.25 




 C 
 0.1 




 D 
 0.05 










(1)  2元通信路で送った文字数に応じて使用料金がかかるので、送る文字数をできるだけ小さくしたい。

(2)  送られた情報{A,B,C,D}が誤って送られる確率をできるだけ小さくしてほしい。（今回は少なくとも10-6以下にするとする。）





はじめに、次のような符号化C1を考える。

C1:{A,B,C,D}={00,01,10,11}

これは、A,B,C,Dに同じ長さの系列を割り当てる方法です。一般に、情報源符号(今回は、{A,B,C,D})に割り当てられた系列（今回は01,10など）を符号語といい、符号語全体の集合を符号と言います。また、符号語に用いられる記号の集合を符号アルファベットといいます。符号アルファベットの元の数がq個のとき、q元符号と呼びます。（今回は、符号アルファベットは{0,1}で２つ元からなるので、2元符号です。）



しかし、今回の場合{A,B,C,D}の発生確率には大きな差があります。そこで、これらの発生確率に応じて、次のような符号化C2を考えます。

C2: {A,B,C,D}={0,10,110,1110}

この符号化では、系列の長さは異なりますが、全ての系列は必ず末尾に0が来るため、連続して送っても区切れ目がわからなくなる心配はありません。

1情報源記号を送るのに、必要な0,1記号の平均値をLとすると、C1では、L = 2に対して、C2では、

L = 1×0.6 + 2×0.25 + 3×0.1 + 4×0.05 = 1.6

となり、C2の方がより少ない使用料金で送ることができます。



次に(2)の問題を考えます。C1 またはC2の方法でそのまま送っても(2)の条件を満たさないので、なんらかの符号化を行う必要があります。ここでは、同じ数字を3回ずつ送るという方法をとります。すると3つの記号うち1つまでは、誤りが許容されることとなり、（例えば、101は1とみなします。）１つの記号あたりで復号を誤る確率は、（復号誤り率という）は、例えばC1で送る場合は、  

3C 2×(10-4)2(1-10 -4) + 3C 3×(10-4)3=2.9998 × 10-8

となり、各符号語には、2つ記号があることから、複合誤り率は、5.9996×10 )-8となり、条件を満たします。また、C2で送る場合も、途中計算は冗長になるため省略しますが、およそ10 -7程度となり、条件を満たします。

ここで問題となるのは、これより効率の良い符号化はないのか？この符号化は、どの程度良い符号化なのか？といったことです。情報理論では、これらを主な問題として扱います。



2.2 問題の設定



今後特に断りがない限り情報源、通信路はデジタルであるとします。



2.2.1 問題の整理
前節で具体例を用いて説明したように、情報理論の中心課題は、(1)通信路使用の効率の向上、(2)信頼性の向上、の二つです。一般に効率と信頼性はトレードオフの関係になっています。そこで、符号化をする際は、(1)と(2)を同時に検討することが望ましいですが、これは普通非常に難しいタスクです。それゆえ、(1)と(2)の要請に対する符号化を、それぞれ、情報源符号化、通信路符号化として分けて考えてきました。まず、情報源符号化を行い、続いて通信路符号化を行うのです。（誤りが生じるのは通信路であるため、逆の順序ではうまくいきません。）このように問題を分割して、独立に考えることで、見通しがよくなります。



2.2.2 情報源符号化の問題
まず前提条件として、情報源符号化を行う際には、通信路で誤りが起きる確率は、十分小さいと仮定します。
情報源符号化とは、情報源から発生する情報源記号の系列（情報源系列といいます。）を通信路の効率化のための別の系列（符号系列といいます。）に変換する操作のことをいいます。

情報源符号化の第一の問題は、


【問題Ⅰ】できるだけよい情報源符号化法および復号法を見つけ出すこと


です。

ここで、よいというのは、1情報源当たりの符号系列の長さの平均値（    1情報源記号当たりの平均符号調）ができるだけ小さいものという意味です。これが、情報源符号化の最も基本的な評価基準です。

また、他の評価基準としては、実際の装置化の簡単さ、符号化、復号にかかる時間の長さなどが挙げられます。

ここでは、情報源符号化として可逆なもの（可逆符号化あるいは情報無損失符号化といいます。）ばかりを考えてきましたが、場合によっては、復号結果が元の通報と多少違っていても許される場合があります。（非可逆符号化あるいは情報損失符号化といいます。）この場合は、1情報当たりの平均符号長をさらに短くできる可能性があります。非可逆符号化における、元の通報と復号の違いのことをひずみといいます。非可逆符号化の場合には、ひずみが許容範囲内に収まり、1情報源記号
当たりの平均符号長が小さく、しかも装置化が簡単な符号法がよい符号化ということになります。    

さて、ある情報源符号化を考えたとそれがどの程度よいものなのかを知ることは重要です。そこで、情報源符号化の第二の問題として、


【問題Ⅱ】情報源符号の限界を知ること


があります。

これは、ある情報源と通信路が与えられたときに、1情報源記号当たりの平均符号長をどこまで小さくできるかという問題です。この問題についても歪みが許される場合とそうでない場合、すなわち、可逆符号化の場合と非可逆符号化の場合に分けられます。



2.2.3 通信路符号化の問題



通信路符号化の問題を考える際には、情報源と情報源符号化をまとめて新たな情報源として考え、情報源復号とあて先をまとめて新たな後先として考えます。

さて、符号系列（通信路符号化された通報）が通信路を経て相手側に届く際、通信路においては誤りが生じうるため、通信路の出力系列は入力系列と必ずしも一致しません。そこで、この出力系列のことを受信系列といいます。そして通信路復号とは、この受信系列から元の情報源系列を推定することをいいます。



【問題Ⅲ】 できるだけよい通信路符号化および復号法を見つけ出すこと



ここでも"よい"という言葉の意味を明確にする必要があります。誤りに対処するためには、余分な符号、すなわち、冗長性を付ける必要があります。逆に言えば、冗長性を付けることによって初めて、信頼性の向上が可能になるのです。しかし、符号化法によっては、付加した冗長性が、信頼性向上にはあまり有効には働かず、無駄に費やされてしまう場合もあります。したがって、よい符号化の最も重要な条件として、付加した冗長性が信頼性の向上にできるだけ有効に用いられることがあげられます。　　
またこのほかにも、装置化や符号化、復号に対する遅延時間の問題も極めて重要です。通信路符号化の場合は、一般に、符号化よりも復号の方が、複雑となるので、特に、復号の装置化の簡単さは符号化法の重要な評価基準となります。





【問題Ⅳ】  通信路符号化の限界を知ること



これは例えば、復号して得られた情報源記号が誤っている確率（復号後の記号誤り率といいます）を、ある値以下に抑えた時に、付加すべき冗長度をどこまで短くすることができるかという問題です。



2.3 問題の発展



これまで、情報源符号化と通信路符号化は分けて考えてきました。その方が問題を簡単に考えられるためです。しかし、本来両者は深くかかわっており、両者を統合して考えることにより、よりよい符号化方式が得られる可能性があります。

情報源符号化においても通信路符号化においても歪みを許容することによって、効率を上昇させることができます。そこで、全体としての効率を最大にするためには、全体として許されるひずみをそれぞれの符号化にどのように割り振るかという問題を考える必要があります。従来、デジタル通報に対しては、情報源符号化のひずみを０として、通信路符号化の部分だけひずみの発生を認めることが多いです。多く場合この割り振りで最適となることが知られていますが、情報源符号化にある程度歪みを割り振った方が効果的な場合もあります。
もう一つ、情報源符号化と通信路符号化の関わりにおける問題として、情報源符号化はそれが有効なものであればあるほど、誤りに足して弱くなるという問題点です。
これらのような問題を扱うには、情報源符号化と通信路符号化を統合する必要がありますが、その研究はあまり進んでいないというのが現状です。