Apache Benchの使い方

はじめに

Apache BenchvはWebサーバをベンチマークするためのツールです。この記事では、Apache Benchの簡単な使い方についてまとめます。

基本

abで利用します。ab -hで使い方が確認できます。

1
Usage: ab [options] [http[s]://]hostname[:port]/path

具体的には以下のように使います。

1
ab https://localhost:8000/

負荷をかける

負荷をかけたい場合はオプションを利用します。nが総リクエスト数、cが同時接続数を表します。n>=cである必要があります。

1
2
-n requests     Number of requests to perform
-c concurrency Number of multiple requests to make at a time
1
ab -n 20 -c 4 https://localhost:8000/

フォームのPOST

以下のようなテキストファイルを用意します。(param.txt)

1
username=hoge&password=fuga
1
ab -p param.txt -T "application/x-www-form-urlencoded" https://localhost:8000/login

参考

http://lapis25.hatenablog.com/entry/20070208/1170929622
https://stackoverflow.com/questions/4007969/application-x-www-form-urlencoded-or-multipart-form-data

記事情報

  • 投稿日:2020年6月23日
  • 最終更新日:2020年6月23日

ABC171

はじめに

この記事では、AtCoder Beginer Contest 171のA~E問題を解説します。

A - alphabet

https://atcoder.jp/contests/abc171/tasks/abc171_a

大文字・小文字の判定にはisupper(), islower()を使うことができます。

1
2
3
4
5
s = input()
if s.isupper():
print('A')
else:
print('a')

B - Mix Juice

https://atcoder.jp/contests/abc171/tasks/abc171_b

ソートとスライスを組みあわせます。

1
2
3
4
N, K = map(int,input().split())
P = list(map(int,input().split()))
P.sort()
print (sum(P[:K]))

C - One Quadrillion and One Dalmatians

https://atcoder.jp/contests/abc171/tasks/abc171_c
ordはpythonの組み込み関数で、Unicodeコードポイントを表す整数を返します。chrはその逆で、整数を受け取り文字を返します。
参考:言語処理100本ノック2020 第1章 準備運動

1
2
3
4
5
6
7
N = int(input())
ans = ''
while(N):
N -= 1
ans+=chr(ord('a')+N % 26)
N //= 26
print (ans[::-1])

D - Replacing

https://atcoder.jp/contests/abc172/tasks/abc172_d

  • 置換のたびに和を計算し直すと間に合いません。そのため、和がどれだけ増えるかを求めます。
  • それぞれの数字がいくつ存在するかは辞書で保持します。
    • getを使うことで、keyが存在しない場合の処理を考えなくてよくなります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N = int(input())
A = list(map(int, input().split()))
d = dict()
for a in A:
v = d.get(a, 0)
d[a] = v+1
S = sum(A)
Q = int(input())
B = []
C = []
for q in range(Q):
b, c = map(int,input().split())
v = d.get(b, 0)
S += v*(c-b)
d[b] = 0
d[c] = d.get(c,0) + v
print (S)

E - Red Scarf

https://atcoder.jp/contests/abc172/tasks/abc172_e

配列の要素に対してxor処理を繰り返して一つの値にします。このような処理はreduceと呼ばれます。

1
2
3
4
5
6
from functools import reduce
N = input()
A = list(map(int,input().split()))
S = reduce(lambda x, y : x ^ y, A)
ans = [str(S^a) for a in A]
print (' '.join(ans))

関連記事

過去のABC解説記事です。

  • ABC170
    • A-D問題を解いています。
  • ABC169
    • A-F問題を解いています。
  • ABC168
    • A-E問題を解いています。
  • ABC167
    • A-E問題を解いています。
  • ABC166
    • A-F問題を解いています。
  • ABC165
    • A-F問題を解いています。
  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日:2020年6月22日
  • 最終更新日:2020年6月22日

JOI2015本選A 鉄道旅行

この記事で使うアルゴリズム

累積和

いもす法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_a

この問題では累積和を応用したいもす法というアルゴリズムで解くことができます。

方針

それぞれの鉄道について独立に、紙の切符とICカードのどちらを使った方が安いかを考えます。そのためにはA,B,Cの情報に加えて、その鉄道を何回利用するかが分かれば良いです。

これはいもす法を用いて高速に求めることが可能です。いもす法の詳細は以下のページに書いています。

ABC014C AtColor

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import itertools
N, M = map(int, input().split())
P = list(map(int, input().split()))
A = []
B = []
C = []
for n in range(N-1):
a,b,c = map(int, input().split())
A.append(a)
B.append(b)
C.append(c)
imos = [0] * N
for m in range(M-1):
if P[m] < P[m+1]:
imos[P[m]-1] += 1
imos[P[m+1]-1] -= 1
else:
imos[P[m]-1] -= 1
imos[P[m+1]-1] += 1
csum = list(itertools.accumulate(imos))
ans = 0
for n in range(N-1):
cnt = csum[n]
ans += min(A[n]*cnt, B[n]*cnt+C[n])
print (ans)umulate(imos))
print (max(csum))

記事情報

  • 投稿日:2020年6月21日
  • 最終更新日:2020年6月21日

JOI2011本戦A 惑星探索

この記事で使うアルゴリズム

幅優先探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2011ho/tasks/joi2011ho1
https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/2011-ho.pdf#page=2

この問題は累積和で解くことができます。

方針

二次元の累積和を求めます。

コード

想定解法で実装していますがPythonの場合TLEとなります。メモリ使用量が大きいため、PyPyではMLEとなります。PythonでのACがほぼ存在しないため、Pythonで取り組むのは難しい問題でした。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import itertools
def transpose(mat): # 二次元のリストを転置する関数
return list(zip(*mat))
M, N = map(int, input().split())
K = int(input())
A = []
for m in range(M):
a = input()
A.append(a)

J = [[0] * (N+1) for _ in range(M+1)]
O = [[0] * (N+1) for _ in range(M+1)]
I= [[0] * (N+1) for _ in range(M+1)]

for m in range(M):
for n in range(N):
if A[m][n]=='J':
J[m+1][n+1] = 1
elif A[m][n] == 'O':
O[m+1][n+1] = 1
else:
I[m+1][n+1] = 1


def calc_csum_mat(A):
B = []
for a in A:
csum = list(itertools.accumulate(a))
B.append(csum)
B = transpose(B)

csum_mat = []
for a in B:
csum = list(itertools.accumulate(a))
csum_mat.append(csum)
csum_mat = transpose(csum_mat)
return csum_mat

J = calc_csum_mat(J)
O = calc_csum_mat(O)
I = calc_csum_mat(I)
query = []
def calc_csum(mat,a,b,c,d):
a -= 1
b -= 1
return str(mat[c][d] - mat[c][b] - mat[a][d] + mat[a][b])
for k in range(K):
query.append(list(map(int,input().split())))
for q in query:
a,b,c,d = q
print (calc_csum(J,a,b,c,d) + ' ' + calc_csum(O,a,b,c,d) + ' ' + calc_csum(I,a,b,c,d))

記事情報

  • 投稿日:2020年6月20日
  • 最終更新日:2020年6月20日

ABC026D 高橋君ボール1号

この記事で使うアルゴリズム

二分探索

はじめに

カテゴリーAtCoder版蟻本中級編では、AtCoder 版!蟻本 (中級編)でまとめられている問題をPythonで解いています。

問題

https://atcoder.jp/contests/abc026/tasks/abc026_d

方針

二分探索を用いて解くことができます。関数は単調増加ではありませんが、解の一つを求めれば良いだけなので問題ありません。

またb * math.sin(c*t*math.pi)の最小値は-bであることと、a,bの制約から、解はt=200より大きくは成り得ないことがわかります。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
import math
a,b,c = map(int,input().split())
def func(t):
return a * t + b * math.sin(c*t*math.pi)
l = 0
r = 400
for i in range(100):
mid = (l + r) / 2
if func(mid)>100:
r = mid
else:
l = mid
print (mid,func(mid))

記事情報

  • 投稿日:2020年6月19日
  • 最終更新日:2020年6月19日

GCP $300分無料トライアル期限の確認方法

はじめに

GCP(Google Cloud Platform)には二つの無料枠があります。

  • 12か月間の無料トライアル
  • Always Free

前者は12か月間だけ、$300分のリソースを使うことができます。このトライアルに参加するためにはクレジットカードを登録する必要があるので、
「無料トライアルだけのつもりがうっかり期限を過ぎてしまい、料金が発生してしまった」というような展開は避けたいものです。

Google Cloud Consoleから残額を確認することができますが、最近GUIのデザインが少し変わり場所がわかりにくくなったので、メモを残しておきます。

  1. 左上の「ナビゲーションメニュー」から「お支払い」をクリック。
  1. 右下の「プロモーション クレジット」から「クレジットの詳細」をクリック。
  1. この画面の表ですが、右が見切れています。横スクロールバーで表の右を確認すると、「終了日」が記載されています。

記事情報

  • 投稿日:2020年6月18日
  • 最終更新日:2020年6月18日

AOJ1611 ダルマ落とし

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp

この問題は動的計画法を用いて解くことができます。

方針

i番目のブロックからj番目のブロックまでのうちで取り除くことができるブロック数の最大値をdp[i][j]として表します。

j-idとして、奇数の場合は計算が簡単で、計算量を削減できます。

  • dが偶数の場合
    • dp[i+1][j-1]==d-1の場合(間の区間が全て取り除ける場合)
      • 両端を取り除けるかを判定
    • dp[i+1][j-1]!=d-1の場合(間の区間に取り除けないブロックがある場合)
      • dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])kでループ
  • dが奇数の場合
    • 全ブロックを削除することはできないので、最善となる偶数の2パターンを考える
      • dp[i][j] = max(dp[i+1][j], dp[i][j-1])

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def solve():
ans = []
while(1):
N = int(input())
if N==0:
break
W = list(map(int,input().split()))
dp = [[0]*N for _ in range(N)]
for d in range(1,N):
for i in range(N-d):
j = i+d
if d%2==1:
if dp[i+1][j-1]==d-1:
if abs(W[i] - W[j])<=1:
dp[i][j] = d+1
else:
dp[i][j] = d-1
for k in range(i+1,j):
new = dp[i][k]+dp[k+1][j]
if new > dp[i][j]:
dp[i][j] = new
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
ans.append(dp[0][-1])
for a in ans:
print(a)
solve()

記事情報

  • 投稿日:2020年6月17日
  • 最終更新日:2020年6月17日

AOJ2199 Differential Pulse Code Modulation

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2199&lang=ja

この問題は動的計画法を用いて解くことができます。

方針

n番目までの二乗和について、yn=kとして二乗和の最小値をdp[n][k]に記録していきます。

コード

残念ながらPythonではこの問題は、本質的ではない定数倍の工夫をしないとTLEとなります。

こちらのコードを参考にさせていただきました。

以下の工夫は高速化に役立ちました。

  • 全体を関数化する
  • minを用いずに比較と代入で実装する
  • dp[n][k]でhなくdp[k]を二つ用意する
  • dpnk = dp1[k]のような事前のメモ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def solve():
ans = []
INF = 10**10
while(1):
N, M = map(int,input().split())
if N==0:
break
C = [int(input()) for _ in range(M)]
X = [int(input()) for _ in range(N)]
dp1 = [INF]*256
dp2 = [INF]*256
dp1[128] = 0
cost = []
decoder = tuple(tuple(255 if i + c > 255 else 0 if i + c < 0 else i + c for c in C) for i in range(256))
ls_square = tuple(tuple((x - t)**2 for x in range(256)) for t in range(256))
for n in range(N):
x = X[n]
square = ls_square[x]
for k in range(256):
dpnk = dp1[k]
for code in decoder[k]:
# #dp[n+1][d] = min(dp[n+1][d], dp[n][k] + (d-X[n])**2)
new = dpnk + square[code]
if new < dp2[code]:
dp2[code] = new
dp1 = dp2[:]
dp2 = [INF]*256
ans.append(min(dp1))
for a in ans:
print(a)
solve()

記事情報

  • 投稿日:2020年6月16日
  • 最終更新日:2020年6月16日

docker for beginners

はじめに

この記事では、docker for beginersを実行していきます。

必要な事前準備はDockerのインストールのみです!

入門

コンピュータのセットアップ

下記のコマンドを実行してDockerを正しくインストールできているか確認します。

1
docker run hello-world

以下のようなメッセージが表示されれば成功です。少し時間がかかる場合があります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Hello from Docker!
This message shows that your installation appears to be working correctly.

To generate this message, Docker took the following steps:
1. The Docker client contacted the Docker daemon.
2. The Docker daemon pulled the "hello-world" image from the Docker Hub.
(amd64)
3. The Docker daemon created a new container from that image which runs the
executable that produces the output you are currently reading.
4. The Docker daemon streamed that output to the Docker client, which sent it
to your terminal.

To try something more ambitious, you can run an Ubuntu container with:
$ docker run -it ubuntu bash

Share images, automate workflows, and more with a free Docker ID:
https://hub.docker.com/

For more examples and ideas, visit:
https://docs.docker.com/get-started/

イメージhello-worldをからコンテナを生成して起動しています。初回実行時は、イメージが存在しないためレジストリからイメージを自動でダウンロードしています。

Hello World

Busyboxで遊ぶ

イメージbusyboxをダウンロードします。

1
docker pull busybox

下記のコマンドでホスト上にあるイメージの一覧を確認できます。

1
docker images

Docker Run

イメージからコンテナを作成し、実行してみます。

1
docker run busybox

一見、何も起きなかったように見えますが、コンテナが起動し空のコマンドを実行してから終了しました。

次のようにすると、コンテナ上でコマンドを実行してから終了します。

1
docker run busybox echo "hello from busybox"

次のコマンドで起動中のコンテナを確認できます。

1
docker ps

先ほど実行したコンテナはすでに終了しているので、このコマンドでは確認できません。
終了したコンテナも含めて確認するには以下のコマンドを実行します。

1
docker ps -a

Dockerを利用したWebアプリケーション

静的サイト

デモ用に作成されたWebサイトを起動します。

1
docker run --rm prakhar1989/static-site

--rmオプションをつけることで、コンテナ終了時に自動でコンテナを削除することができます。

さて、実はこれではポートの割り当てをしていないためWebサイトにアクセスすることができません。
Ctrl+C等で、一旦終了して実行方法を変えてみましょう。

  • ターミナルが実行中のコンテナに接続されないようにする
  • コンテナに名前をつける
  • (ランダムに)ポートを割り当てる
1
docker run -d -P --name static-site prakhar1989/static-site

これでhttp://localhost[PORT]でアクセすることができます。

以下のようにポートを指定することも可能です。

1
docker run -p 8888:80 prakhar1989/static-site

以下のコマンドでコンテナを停止することができます。--rmオプションで起動していた場合は、同時に削除されます。

1
docker stop static-site

Docker Iamges

ローカルで使用可能なDockerのイメージ一覧を確認します。

1
docker images

docker pullする際に、タグ(バージョン)を指定することができます。

1
docker pull ubuntu:18.04

初めてのイメージ

次に自分でイメージを作成します。

1
2
git clone https://github.com/prakhar1989/docker-curriculum.git
cd docker-curriculum/flask-app

Dockerfile

Dockerfileを作成します。

1
vi Dockerfile
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FROM python:3

# set a directory for the app
WORKDIR /usr/src/app

# copy all the files to the container
COPY . .

# install dependencies
RUN pip install --no-cache-dir -r requirements.txt

# define the port number the container should expose
EXPOSE 5000

# run the command
CMD ["python", "./app.py"]
1
docker build -t yourusername/catnip .

記事情報

  • 投稿日:2020年6月15日
  • 最終更新日:2020年7月4日

ABC170

はじめに

この記事では、AtCoder Beginer Contest 170のA~D問題を解説します。

A - Five Variables

https://atcoder.jp/contests/abc170/tasks/abc170_a

1
2
3
4
A = list(map(int,input().split()))
for i in range(5):
if A[i] == 0:
print(i+1)

B - Crane and Turtle

https://atcoder.jp/contests/abc170/tasks/abc170_b

シミュレーションしても十分に間に合います。

1
2
3
4
5
6
7
x, y = map(int,input().split())
for a in range(x+1):
b = x-a
if 2*a+4*b==y:
print ('Yes')
exit()
print ('No')

C - Forbidden List

https://atcoder.jp/contests/abc170/tasks/abc170_c

解が0101になる可能性があります。

1
2
3
4
5
6
7
8
9
10
11
X, N = map(int,input().split())
P = list(map(int,input().split()))
P.sort()
diff = 10**10
for p in range(102):
if p in P:
continue
if abs(X-p) < diff:
diff = abs(X-p)
ans = p
print (ans)

D - Not Divisible

https://atcoder.jp/contests/abc170/tasks/abc170_d

ソートをして、小さい順にAの倍数を記録していきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
if P[a]==0:
for i in range(MX+1):
x = a*i
if x > MX:
break
P[x] = 1
if cnt[a]==1:
ans+=1
print (ans)

F - Pond Skater

https://atcoder.jp/contests/abc170/tasks/abc170_f

公式の解説にはダイクストラ法による解法がありますが、幅優先探索で解くこともできます

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利

H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
mp = [input() for _ in range(H)]
INF = 10**10
dist = [[INF]*W for _ in range(H)]
dist[x1-1][y1-1] = 0
q = deque()
q.append((x1-1,y1-1)) # スタート地点をenqueue
while(q):
x, y = q.popleft()
if x==x2-1 and y==y2-1:
print (dist[x2-1][y2-1])
exit()
else:
for dx, dy in dxdy:
for i in range(1,K+1):
nx = x + dx*i
ny = y + dy*i
if not (0<=nx<H and 0<=ny<W) or mp[nx][ny]=='@':
break
if dist[nx][ny] <= dist[x][y]:
break
if dist[nx][ny] == INF:
q.append((nx,ny))
dist[nx][ny] = dist[x][y] + 1
print(-1)

関連記事

過去のABC解説記事です。

  • ABC169
    • A-F問題を解いています。
  • ABC168
    • A-E問題を解いています。
  • ABC167
    • A-E問題を解いています。
  • ABC166
    • A-F問題を解いています。
  • ABC165
    • A-F問題を解いています。
  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日:2020年6月14日
  • 最終更新日:2020年6月15日