2020-10-10

アルゴリズムとデータ構造（けんちょん本）4.1,4.2

トリボナッチ数列を計算するプログラム

メモ化なし

import time

def tori(n):
  if n == 1:
    return 0
  if n == 2:
    return 0
  if n == 3:
    return 1

  return  tori(n-1) + tori(n-2) + tori(n-3)

k = int(input())
memo = [-1 for _ in range(k+1)]
start = time.time()
print(tori(k))
print(time.time() - start)

として、標準入力から第何項を求めるか入力させる形とした。 $k=50$ とすると手元の環境（Google colab）ではしばらく待っても終了しなかった。

メモ化あり

#import sys
#sys.setrecursionlimit(100000)

def tori(n):
  if n == 1:
    return 0
  if n == 2:
    return 0
  if n == 3:
    return 1

  if memo[n] == -1:
    memo[n] = tori(n-1) + tori(n-2) + tori(n-3)

  return memo[n]

k = int(input())
memo = [-1 for _ in range(k+1)]
start = time.time()
print(tori(k))
print(time.time() - start)

メモ化して実行すると $k=50$ としても0.00018秒程度で結果が返ってきた。メモ化すごい。

計算量

メモ化した場合の計算量は $O(N)$ と思われる。
メモ化しない場合の計算量はいくつだろう？（章末問題4.3をやります）

2020-10-09

アルゴリズムとデータ構造（けんちょん本）4.1,4.2

競技プログラミング python3

トリボナッチ数列を計算するプログラム

メモ化なし

import time

def tori(n):
  if n == 1:
    return 0
  if n == 2:
    return 0
  if n == 3:
    return 1

  return  tori(n-1) + tori(n-2) + tori(n-3)

k = int(input())
memo = [-1 for _ in range(k+1)]
start = time.time()
print(tori(k))
print(time.time() - start)

として、標準入力から第何項を求めるか入力させる形とした。[tex;k=50]とすると手元の環境（Google colab）ではしばらく待っても終了しなかった。

メモ化あり

#import sys
#sys.setrecursionlimit(100000)

def tori(n):
  if n == 1:
    return 0
  if n == 2:
    return 0
  if n == 3:
    return 1

  if memo[n] == -1:
    memo[n] = tori(n-1) + tori(n-2) + tori(n-3)

  return memo[n]

k = int(input())
memo = [-1 for _ in range(k+1)]
start = time.time()
print(tori(k))
print(time.time() - start)

メモ化して実行すると $k=50$ としても0.00018秒程度で結果が返ってきた。メモ化すごい。

計算量

メモ化した場合の計算量は $O(N)$ と思われる。
メモ化しない場合の計算量はいくつだろう？（章末問題4.3をやります）

2020-10-06

アルゴリズムとデータ構造（けんちょん本）3.4

競技プログラミング python3

アルゴリズムとデータ構造（けんちょん本）

この本の気になった章末問題等をPythonでやったりして更新してみることにする。いつまで続くかはわからない。おかしな点があれば教えてください。

章末問題3.4

#入力の受け取り
#入力でa_1, a_2, ,,,,a_Nを受け取る
A = list(map(int,input().split()))

#最大値，最小値はこの範囲内に収まっているとする
max = -10000000
min =  10000000

#Aは長さNなのでO(N)
for i in range(len(A)):
  if A[i] > max:
    max = A[i]
  if A[i] < min:
    min = A[i]
#差の最大値は最大値―最小値で得られる。
print(max-min)

これでええんか？

2020-10-06

アルゴリズムとデータ構造（けんちょん本）２．６

競技プログラミング高校数学

章末問題２．６

$y = \dfrac{1}{x}$ のグラフとその下側に作った長方形の面積を考える。
赤い長方形の面積は左から順に， $1, \dfrac{1}{2}, \dfrac{1}{3}, \cdots ,\dfrac{1}{10}$ となっている（縦横の比率がおかしいのは目をつぶる）。
$（赤い長方形の面積の和） \lt \int_1 ^N \dfrac{1}{x} dx + 1$ である。
ここで，
$\int _1 ^N \dfrac{1}{x} dx = \log N$ であるから，赤い長方形の面積の和< $\log N$ を得る。 f:id:masuTomo:20201006221522p:plain

以上のことから， $1+\dfrac{1}{2}+ \dfrac{1}{3} + \cdots + \dfrac{1}{N} = O(\log N)$ であることがわかった。

おまけ

上記の図では， $y = \dfrac{1}{x}$ の下側の長方形の面積の和（不足和，Lower Sum）と積分値を比較したが，逆にグラフの上側にはみでるように長方形を作って，その長方形の和（過剰和, Upper Sum）を考えることで，上から抑えることもできる。下からも上からも評価できるので，結果として $1+\dfrac{1}{2}+ \dfrac{1}{3} + \cdots + \dfrac{1}{N} = \Theta(\log N)$ がわかる。

2020-07-24

Paiza 「Python×AI・機械学習入門編1: 機械学習の概要を知ろう」無料分だけやってみた

paizaの有料講座の無料分だけやってみました

Python×AI・機械学習入門編1: 機械学習の概要を知ろうのチャプター一覧 | プログラミング学習サービス【paizaラーニング】

機械学習は少しだけ勉強したことがあったのですが、ここから先、どうやって勉強を進めていくか悩ましかったので、とりあえず無料分だけやってみました。

想定する受講者はPythonの基礎ができている人、とのこと。とりあえずやってみたが、無料分だけだと何ともいえない。チャプター1は機械学習のほんとに最初の部分について。具体的には

分類問題、回帰分析
教師あり、教師なし

あたりの説明

チャプター２は、paizaラーニングのこの講座で使う環境と少しだけライブラリ（matplotlib）の話

jupyternotebookが使えるので環境構築不要
matplotlibを使って簡単なグラフを描画

という感じでした。

有料部分の講座

こちらは受講していないので詳細は分かりませんが

問題と入出力データを考えよう
画像から特徴量を抽出しよう
scikit learnで学習と予測を行おう
特徴量に明度のヒストグラムを利用しよう

という内容でした。

お金を払ってやってみるべきかどうか

正直、この講座だけのためであれば無料のものを利用してこれ以上の内容が学習できると思います。例えば、大学生のためのデータサイエンス（Ⅱ） | gacco などのmoocといわれるサービス（？）を利用しても良いかもしれません。

ただ、Paizaは1講座いくら、という料金体系ではなく、月額制でPaizaが提供する講座のすべてを受講できる（たぶん）という仕組みのようです。
料金は * 1078円/月

4488円/半年 = 748円/月
7200円/年　= 600円/月となっています。この講座だけでなく、
C入門
linux入門
DB/SQL入門など幅広い講座があります。いちいち書籍等を購入することを考えると有料会員になっても良いような気もします。書籍を購入したら1冊3000円とかざらですからね。

また、自分のコードを採点してもらえるのも書籍等にはない強みだと思います。継続的に勉強できる人（月額料金を無駄にしない自信がある人）にはおすすめできるかもしれません。

最後に

この記事は、ステッカー等が欲しくて頑張って書きました。普段はPaizaのスキルチェックしかほぼ利用していませんが、スキルチェック問題の解説を公開するのは違反のようでしたので、無料講座を受講してその紹介記事を書きました。

思ったよりも月額料金が安かったので、やってみてもいいかなという気持ちになりました。

2020-07-24

Paiza 「Python×AI・機械学習入門編1: 機械学習の概要を知ろう」無料分だけやってみた

paizaの有料講座の無料分だけやってみました

Python×AI・機械学習入門編1: 機械学習の概要を知ろうのチャプター一覧 | プログラミング学習サービス【paizaラーニング】

分類問題、回帰分析
教師あり、教師なし

あたりの説明チャプター２は、paizaラーニングのこの講座で使う環境と少しだけライブラリ（matplotlib）の話

jupyternotebookが使えるので環境構築不要
matplotlibを使って簡単なグラフを描画

という感じでした。

有料部分の講座

こちらは受講していないので詳細は分かりませんが

問題と入出力データを考えよう

*画像から特徴量を抽出しよう

scikit learnで学習と予測を行おう
特徴量に明度のヒストグラムを利用しよう

という内容でした。

お金を払ってやってみるべきかどうか

ただ、Paizaは1講座いくら、という料金体系ではなく、月額制でPaizaが提供する講座のすべてを受講できる（たぶん）という仕組みのようです。
料金は * 1078円/月 * 4488円/半年 = 748円/月 * 7200円/年　= 600円/月となっています。この講座だけでなく、

C入門
linux入門
DB/SQL入門など幅広い講座があります。いちいち書籍等を購入することを考えると有料会員になっても良いような気もします。書籍を購入したら1冊3000円とかざらですからね。

また、自分のコードを採点してもらえるのも書籍等にはない強みだと思います。継続的に勉強できる人（月額料金を無駄にしない自身がある人）にはおすすめできるかもしれません。

最後に

思ったよりも月額料金が安かったので、やってみてもいいかなという気持ちになりました。

2020-06-21

Pythonでwebスクレイピング（ログインとデータ取得）

python3 webスクレイピング

動機

バイクの免許を取ろうと，自動車学校に通うことにした。講習はwebからの予約制であり，今は新型コロナウイルスで大学が休みだったりするらしく，例年より生徒が多いらしい。そこで，予約に空きがでたらすぐに確認・予約ができるようにpythonでwebスクレイピングしてみることにした。

条件

自動車学校のホームページの予約ページから，idとパスワードを入力してログインする
ログイン先の画面から予約可能枠を取得
予約可能枠を自分のラインに送信する
上記の操作を定期的に実行する

自動で予約するところまで作ろうかとも思ったが，変な予約してしまうことのリスクを避けるため，予約状況を送信するにとどめました（大変そうだったからというのもある）。

実装

やり方を調べる

とりあえず，「python　webスクレイピング　ログイン」などとしてググってみると，いろいろ記事がある。seleniumというのを利用すると簡単らしいということがわかったので，それを利用した。

shimi-dai.com

また，ブラウザ（Google Chrome）にアクセスするためにはchromedriverと呼ばれるものが必要らしく，それをダウンロードしてきて，適当な場所に格納する（そこにパスを通すのを忘れずに）

Downloads - ChromeDriver - WebDriver for Chrome

最新版でいいだろ，と思って適当にやったらエラーがでました。サポートしているchromeのバージョンを確認しておきましょう。（Chromeのヘルプでバージョンを確認したら83，最新です。となっていたのにchromedriverの最新版はchromeのver84をサポートしているようでした。どういうこと？）

ログインする

from selenium import webdriver
from selenium.webdriver.chrome.options import Options

url = "ログインしたいwebページのURL"

# ヘッドレスモードの設定。
# True => ブラウザを描写しない。
# False => ブラウザを描写する。
options = Options()
options.add_argument('--headless')

# Chromeを起動
driver = webdriver.Chrome(executable_path="chromedriverのexeのパスを指定", chrome_options=options)

# ログインページを開く
driver.get(url)

idとパスワードを入力する

まずは，idとパスワードの入力欄を取得してくる必要がある。chromeブラウザでログインページを開いてF12（その他のツールからデベロッパツール）を押すと，ページソースが見れる。 f:id:masuTomo:20200621111220p:plain さらにソースが見えているエリアの左上の矢印ボタンを押しておく。
その状態で，画面左側にマウスカーソルを持っていくと，画面上のアイテムに該当するソースがハイライトされる。 f:id:masuTomo:20200621111246p:plain この方法で入力欄のidなどを調べる。idを指定して，アイテムを取得し，そこに値を引き渡す。

from selenium.webdriver.common.keys import Keys

#入力欄にidを入力する処理
driver.find_element_by_id('idを入力するアイテムのid').send_keys('あなたのid')
driver.find_element_by_id('パスワードを入力するアイテムのid').send_keys('あなたのパスワード')
#ログインボタンをクリックする処理
driver.find_element_by_id('ログインボタンのid').send_keys(Keys.ENTER)

アイテムによってはidが指定されていなかったりという状況もあるので，取得したいアイテムに合わせるメソッドを利用する。classやname属性を指定することもできる。

qiita.com

これで，ログイン後の画面に遷移しているはずである。ただし，ページ読み込みなどに時間がかかる場合があるので念のためこんな感じの処理を入れておく。

from time import sleep
#ページ読み込み待機
sleep(5)

ログイン後画面から予約情報を読み取る

なんだかよくわからないがbeautifulsoupなるものを利用することが多いらしく，真似してみた。

from bs4 import BeautifulSoup

# # soupオブジェクトを作成（ここはよくわかっていないのでおまじないのつもり）
soup = BeautifulSoup(driver.page_source, "lxml")

で，このsoupオブジェクトからページ要素を取得する方法がわからなかったのだが，find，fild_allなどというメソッドが用意されているようで，それを利用すれば，ページ要素からタグを指定して値を取得することができるようだった。私が調べたいサイトは予約枠がテーブルで書かれており，idが割り振られていなかったため，tdタグとclassを指定して取得した。
ページソースを眺めていると，classがstatus1だと予約可能，status3は自分の予約，という風になっていたので，statsu1を指定して要素を取得することとした。当然，複数の予約可能枠があるので，それをリストに格納することにした。

#予約ページからstatus1（予約可能）の情報を取得
tmp_list = list(str(soup.find_all('td', class_ = 'status1')).split())

そこのタグ内に日付や時間情報も持っていたので，文字列操作でそこを取り出しておいた。

取得した予約可能枠をLINEに送信する

LINEのアクセストークンというものを発行しなければならないらしいが，とても簡単だった。

qiita.com

import requests

#line送信の準備    
lineurl = "https://notify-api.line.me/api/notify"
access_token = '自分のアクセストークン'
headers = {'Authorization': 'Bearer ' + access_token}

message = ’送信したい文字列’
payload = {'message': message}
r = requests.post(lineurl, headers=headers, params=payload,)

定期的に実行する

pythonプログラムを実行するbatファイルを作成して，それをタスクスケジューラから定期的に実行する形にした。
batファイルはこんな感じ

cd C:\Users\username\workspace\pythonファイルのパス
py 実行したいファイル.py

タスクスケジューラの場所は[スタートメニュー]→[Windows管理ツール]→[タスクスケジューラ]

masuTomo’s blog

競技プログラミングの勉強メモです．主にPythonを使用します．数学の記事も書くかもしれません．

アルゴリズムとデータ構造（けんちょん本）4.1,4.2

トリボナッチ数列を計算するプログラム

メモ化なし

メモ化あり

計算量

アルゴリズムとデータ構造（けんちょん本）4.1,4.2

トリボナッチ数列を計算するプログラム

メモ化なし

メモ化あり

計算量

アルゴリズムとデータ構造（けんちょん本）3.4

アルゴリズムとデータ構造（けんちょん本）

章末問題3.4

アルゴリズムとデータ構造（けんちょん本）２．６

章末問題２．６

おまけ

Paiza 「Python×AI・機械学習入門編1: 機械学習の概要を知ろう」無料分だけやってみた

paizaの有料講座の無料分だけやってみました

有料部分の講座

お金を払ってやってみるべきかどうか

最後に

Paiza 「Python×AI・機械学習入門編1: 機械学習の概要を知ろう」無料分だけやってみた

paizaの有料講座の無料分だけやってみました

有料部分の講座

お金を払ってやってみるべきかどうか

最後に

Pythonでwebスクレイピング（ログインとデータ取得）

動機

条件

実装

やり方を調べる

ログインする

idとパスワードを入力する

ログイン後画面から予約情報を読み取る

取得した予約可能枠をLINEに送信する

定期的に実行する