2020-07-12 課題

メモ：先に進む前に録画してあるか確認しよう

自分用メモ

Matplotlib

\begin{align} \sigma(x) = \frac{1}{1 + e^{-x}}. \end{align}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(-10, 10, 501)
y = 1 / (1 + np.exp(-x))

plt.plot(x, y, label="sigmoid")

plt.grid()
plt.legend()
#plt.axes().set_aspect('equal', 'datalim') # アスペクト比を合わせる
plt.show()

TeX の記録

\begin{align} f(y) \geq f(x) + \langle \nabla f(x), \, y-x \rangle. \end{align}

競プロ、AtCoder

ABC087B - Coins

あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。 同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def solve(A, B, C, X):
    lst = []
    for a in range(A+1):
        for b in range(B+1):
            for c in range(C+1):
                lst.append(500*a+100*b+50*c == X)
    # 下のセルで補足
    return sum(lst) #len(list(filter(lambda x: x == True, lst)))

[A, B, C, X] = [2, 2, 2, 100]
print(solve(A, B, C, X)) # 2

[A, B, C, X] = [30, 40, 50, 6000]
print(solve(A, B, C, X)) # 213

1
2
2
213

注意

ブール値は True = 1、False = 0 として足せるらしい。

1
sum([True, False, True, False, False])

1
2

上のコードをリスト内包表記で簡潔に

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#A, B, C, X = [int(input()) for i in range(4)]
def solve(A, B, C, X):
    return sum(500*a+100*b+50*c == X
               for a in range(A+1)
               for b in range(B+1)
               for c in range(C+1))

[A, B, C, X] = [2, 2, 2, 100]
print(solve(A, B, C, X)) # 2

[A, B, C, X] = [30, 40, 50, 6000]
print(solve(A, B, C, X)) # 213

1
2
2
213

ABC083B

1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

サンプル

1
list(range(1, 20+1))

1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

1
2
a <= b && b <= c
a <= b <= c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def solve(N, A, B):
    lst = []
    for i in range(1, N+1):
        if A <= sum(map(int, str(i))) <= B:
            lst.append(i)
    return sum(lst)

N, A, B = [20, 2, 5]
print(solve(N, A, B)) # 84

N, A, B = [10, 1, 2]
print(solve(N, A, B)) # 13

N, A, B = [100, 4, 16]
print(solve(N, A, B)) # 4554

1
2
3
84
13
4554

わからなければ分解しよう

1
sum(map(int, str(i)))

1
2
3
4
5
6
7
i = 20
map(int, str(i))

lst = []
for a in str(i):
    lst.append(int(a))
print(lst)

1
[2, 0]

1
2
3
4
5
6
7
8
9
i = 20
print(list(str(i)))
print(list(map(int, str(i))))

i = 123
print(list(map(int, str(i))))

i = 3564565
print(list(map(int, str(i))))

1
2
3
4
['2', '0']
[2, 0]
[1, 2, 3]
[3, 5, 6, 4, 5, 6, 5]

1
2
3
4
i = 3564565
l = len(str(i))
int(i / (10**(l-1)))
i % 10**(l-1)

1
564565

リスト内包表記で簡潔に

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def solve(N, A, B):
    return sum(i for i in range(1, N+1) if A <= sum(map(int, str(i))) <= B)

N, A, B = [20, 2, 5]
print(solve(N, A, B)) # 84

N, A, B = [10, 1, 2]
print(solve(N, A, B)) # 13

N, A, B = [100, 4, 16]
print(solve(N, A, B)) # 4554

1
2
3
84
13
4554

IT 一般論

前回

そもそもなぜ IT 一般論の話をしだしたか

シンプルなシステムからの成長

大事で面倒な話：「サーバー」とは何か？

基本構成

一番単純

状況に応じていろいろ分かれる

他の状況

ハードウェア構成の基礎

コンピューター構成の5大要素

CPU からキャッシュ

補足コメント

複数のキャッシュレベル

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
Latency Comparison Numbers
--------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy            10,000   ns       10 us
Send 1 KB bytes over 1 Gbps network     10,000   ns       10 us
Read 4 KB randomly from SSD*           150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from 1 Gbps  10,000,000   ns   10,000 us   10 ms  40x memory, 10X SSD
Read 1 MB sequentially from disk    30,000,000   ns   30,000 us   30 ms 120x memory, 30X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms
追加説明

「それぞれのキャッシュには役割があるから」

「キャッシュは容量が大きいほどデータ転送速度が遅く、記憶密度が高く、省電力という性質を持つため、必要性に応じて異なる種類のキャッシュを使い分けるのが有利だから」

補足：いろいろなキャッシュ

補足その 2：「キャッシュ」があるとなぜ重くなる？

補足

データ構造とアルゴリズム

（連結）リストと配列

リストの特徴

配列の特徴

ベクター（参考）

シーケンシャルアクセス

参考：HDD でのシーケンシャルアクセス・断片化・ディスクデフラグ

デフラグとは、デフラグメンテーション（defragmentation）の略です。PCはハードディスクに読み書きを行っていますが、何度も繰り返すうちに連続した広い領域が確保できなくなり、狭い複数の領域に分散して書き込むようになります。データが分散している状態を「断片化」といい、断片化しているとファイルを読み込むのが遅くなり、PC速度が低下します。

断片化したデータを連続した状態に整理することをデフラグといいます。デフラグを定期的に行うことで、読み込み、書き込みが速くなるだけではなく、PC起動が早くなったり、ハードディスクの残り空き容量が増える、というメリットがあります。

なぜ遅くなるのか

補足：なぜ空き容量が増えるのか

HDDにデータを書き込む時、データはセクタという最小単位（主に512バイトまたは4,096バイト）に切り分けられ、プラッタの同心円状に作られているトラックと呼ばれる領域に保管されます。