20200805のPythonに関する記事は30件です。

pythonの基礎: リスト

リスト型

1つの変数に複数のデータが入っている状態です。

リストの基本

文字列,数値混在でも可

a = 1
b = 'みかん'
c = 2

li = [a, b, c]

print(li)
# 出力 [1,みかん,2]

多重リスト

リストの中にリスト


a = "いち"
b = 2
c = "さん"
d = 4

li = [[a, b], [c, d]]


print(li)
# 出力: [["いち", 2], ["さん", 4]]

値取出

リストにはインデックス(番号)が割り振られています。
それを指定して取り出せます

①左端から0として始まり、数値を指定することで取り出せます
②1番最後を-1として
-2,-3と順番に取り出せることもできます。
List = [0, 1, 2, 3]
print(List [0]) 
# インデックスが0の「0」が出力される

List = [0, 1, 2, 3]
print(List [-3]) 
# 後ろから3番目の「1」が出力される

多重リストから範囲値取出。

①番号: で指定番号より取り出し
②:番号 で番号一つ手前まで取り出し(-の場合左から数えて手前)
al = ["0","1", "2", "3", "4", "5", "6", "7", "8", "9", "10"]
print(al[1:4]) 
# インデックス1~3: ["1", "2", "3"]

print(al[:4]) 
# インデックス0〜3: ["0", "1", "2", "3"]

print(al[7:]) 
# インデックス7〜終 ["7", "8", "9","10"]が出力される

print(al[0:100]) 
# 範囲を超えてるため全て出力

print(al[0:-5]) 
# インデックス0~後ろから6番目までの ["0","1", "2", "3", "4","5"]

リストの上書きと追加

追加方法として
① 番号指定
② appendで最後に(1つだけしかできない)
③ += で最後に  (複数できる)

al = ["0","1", "2", "3", "4"]
al[0] = "A" 
print(al) 
# 出力結果: ["A", "1", "2", "3", "4"]


al = ["0","1", "2", "3", "4"]
al[1:3] = ["B", "C"] 
print(al) 
# 出力結果: ["0", "B", "C", "3", "4"]

al = ["0","1", "2", "3", "4"]
al.append("f") 
print(al) 
# 出力結果: ["0","1", "2", "3", "4","f"]

al = ["0","1", "2", "3", "4"]
al += ["f","g"] 
print(al)
# 出力結果: ["0","1", "2", "3", "4","f","g"]

要素削除

del リスト[インデックス]
al = ["0","1", "2", "3", "4"]
del al[3:] 
print(al) 
# 出力結果: ["0", "1", "2"]


al = ["0","1", "2", "3", "4"]
del al[1:3] 
print(al) # ["0", "3", "4"]が出力される

コピー

リスト変数にリスト変数を代入するだけの時
代入先を変えた場合、代入元も変化する。
# リストの中身だけの時
list() # 左記を使用します。
# 変数そのまま
al = ['0', '1', '2']
al_copy = al 
al_copy[0] = 'A' 
print(al_copy)
print(al)

# 出力結果

['A', '1', '2']
['A', '1', '2']
# list()を使って中身だけ
al = ['0', '1', '2']
al_copy = list(al)
al_copy[0] = 'A'
print(al_copy) 
print(al) 

# 出力結果

['A', '1', '2']
['0', '1', '2']
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

APIで取得したJSONデータの日本語文字化けを解消する。

発生した問題

youtube Data APIでデータを取得する練習をしていたら、取得したデータを出力すると日本語が文字化けしてた。

search.py
if __name__ == "__main__":
    try:
        response = youtube_search(
            q='公式', part='snippet', type='video', max_count=1, order='date')

        CURRENT_DIR = os.getcwd()
        with codecs.open(CURRENT_DIR + '/' + 'data.json', 'w', encoding='utf-8') as f:
            f.write(json.dumps(response, indent=2))

        print(json.dumps(response, indent=2))

    except HttpError as e:
        print("An HTTP error %d occurred: \n%s" % (e.resp.status, e.content))
結果.
########################
## 関係ないところは省略
########################
        "title": "\u4eee\u9762\u30e9\u30a4\u30c0\u30fc\uff08\u65b0\uff09\uff08\u30b9\u30ab\u30a4\u30e9\u30a4\u30c0\u30fc\uff09\u3000\u7b2c14\u8a71[\u516c\u5f0f]",
        "description": "\u4eee\u9762\u30e9\u30a4\u30c0\u30fc\uff08\u65b0\uff09 \u7b2c14\u8a71\u300c\u30cf\u30a8\u30b8\u30b4\u30af\u30b8\u30f3 \u4eee\u9762\u30e9\u30a4\u30c0\u30fc\u5371\u6a5f\u4e00\u9aea\u300d \u6d0b\u306f\u5bcc\u58eb\u6025\u30cf\u30a4\u30e9\u30f3\u30c9\u3067\u3001\u5148\u8f29\u30fb\u8c37\u6e90\u6b21\u90ce\u3068\u518d\u4f1a\u3002\u3060\u304c\u3001\u3053\u306e\u5730\u4e0b\u306b\u306f\u3001\u30cd\u30aa\u30b7\u30e7\u30c3\u30ab\u30fc\u306e\u602a\u4eba\u30cf\u30a8\u30b8\u30b4\u30af ...",
        "thumbnails": {
          "default": {
            "url": "https://i.ytimg.com/vi/yTFJ-6NnUNY/default.jpg",
            "width": 120,
            "height": 90
          },
          "medium": {
            "url"

解消方法

json.dumps()のオプション「ensure_ascii」がデフォルトでTrue、つまりASCII文字を含む場合は自動的にエスケープする処理を実行する設定がデフォルトになっている。
これをFalseに設定してエスケープされないようにする。

search.py
if __name__ == "__main__":
    try:
        response = youtube_search(
            q='公式', part='snippet', type='video', max_count=1, order='date')

        CURRENT_DIR = os.getcwd()
        with codecs.open(CURRENT_DIR + '/' + 'data.json', 'w', encoding='utf-8') as f:
            f.write(json.dumps(response, indent=2, ensure_ascii=False))

        print(json.dumps(response, indent=2, ensure_ascii=False))

    except HttpError as e:
        print("An HTTP error %d occurred: \n%s" % (e.resp.status, e.content))
結果.
########################
## 関係ないところは省略
########################
        "title": "仮面ライダー(新)(スカイライダー) 第14話[公式]",
        "description": "仮面ライダー(新) 第14話「ハエジゴクジン 仮面ライダー危機一髪」 洋は富士急ハイランドで、先輩・谷源次郎と再会。だが、この地下には、ネオショッカーの怪人ハエジゴク ...",
        "thumbnails": {
          "default": {
            "url": "https://i.ytimg.com/vi/yTFJ-6NnUNY/default.jpg",
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

[備忘録]CADqueryサンプルコード

はじめに

本記事は、PythonモジュールであるCadQueryのサンプルコード集です。

導入方法は、CadQueryを使って、3Dプリンタデータ(STLファイル)を作成するを参照ください。

※適宜更新予定です。

[box]直方体をかく

  • x:2mm, y:2mm, z:0.5mmの直方体を作成
test.py
import cadquery as cq

result = cq.Workplane("front").box(2.0, 2.0, 0.5)
show_object(result)

image.png

[translate]直方体を座標指定で移動する

  • x:2mm, y:2mm, z:0.5mmの直方体を作成
  • 直方体の中心座標をx方向に2mm, y方向に3mm, z方向に1mm移動
test.py
import cadquery as cq

result = cq.Workplane("front").box(2.0, 2.0, 0.5)
result = result.translate((2, 3, 1))
show_object(result)

image.png

[hole]直方体に穴をあける

  • x:80mm, y:60mm, z:10mmの直方体を作成
  • 直径22mの穴を直方体にあける
test.py
import cadquery as cq

length = 80.0
height = 60.0
thickness = 10.0
center_hole_dia = 22.0

result = (cq.Workplane("XY").box(length, height, thickness)
    .faces(">Z").workplane().hole(center_hole_dia))

show_object(result)

image.png

[cboreHole]直方体にネジ穴をあける

  • x:80mm, y:60mm, z:10mmの直方体を作成
  • faces(">Z")
    • Z方向の一番大きい面を取得するため指定
  • rect(70.0, 50.0, forConstruction=True)
    • 70.0 x 50.0の大きさを指定
    • forConstruction=Trueは、ワイヤー参照
    • ※forConstruction=Falseは、パーツジオメトリ用
  • vertices()
    • 頂点を選択
  • cboreHole(3.0, 4.0, 2.0, depth=None)
    • 3.0mmのネジ穴
    • 4.0mmのネジ頭穴
    • 2.0mmは、ネジ頭の深さ
    • depthで、ネジ穴の深さ。None指定で貫通
test.py
import cadquery as cq

length = 80.0
height = 60.0
thickness = 10.0

result = (cq.Workplane(cq.Plane.XY()).box(length, height, thickness))
result = result.faces(">Z").workplane().rect(70.0, 50.0, forConstruction=True).vertices().cboreHole(3.0, 4.0, 2.0, depth=None)

show_object(result)

image.png

[union]直方体を融合する

  • x:2mm, y:2mm, z:0.5mmの2つの直方体(r1, r2)を作成
  • r1をx方向に1mm, y方向に1mm移動
  • r1とr2を融合
test.py
import cadquery as cq

r1 = cq.Workplane("front").box(2.0, 2.0, 0.5)
r1 = r1.translate((1, 1, 0))
r2 = cq.Workplane("front").box(2.0, 2.0, 0.5)
r2 = r2.translate((0, 0, 0))

r1 = r1.union(r2)

show_object(r1)

image.png

[circle]円柱をつくる

  • 直径2mm, 高さ:3mmの円柱を作成
test.py
import cadquery as cq

result = cq.Workplane("front").circle(2).extrude(3)
show_object(result)

image.png

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

Erosion Thickness on Medial Axes of 3D Shapesを実装してみた

この記事ではSIGGRAPH2016で発表されたErosion Thickness on Medial Axes of 3D Shapes1 を解説し、実際に実装しています。

はじめに

CGの世界には、Medial Axisというものがあります。Medial Axisは、とても大雑把に言うと「その図形の骨格」です(Topological Skeletonとも言われます)。

image.png2

2Dであれば、上図の赤い線がそれにあたります。青い円を見ると、鳥の首と右翼の付け根あたりで外周と接していることがわかります。このように外周と2点以上で接している円を「接触円」と呼び、Medial Axisはこの接触円の中心の軌跡になっています。

image.png 3

3Dでも同様に、物体の表面と2点以上で接している球の軌跡がMedial Axisになり、その形状は曲面になります。

Medial Axisはその形状の大体の「骨格」なので、画像や3次元形状を処理する時に形状を単純化したり、3次元モデルの変形に使ったり、といった時に役に立ちます。

このMedial Axisの普遍的な課題として「どの軸を『メインの軸』とすべきか」、つまり「重要な軸を決定する」タスクがあります。例えば上の鳥の例では、両翼を通る軸と、頭と尾を通る軸の二つが「メインの軸」になりそうです。

スクリーンショット 2020-07-27 17.38.35.png 1

2Dの図形のMedial Axis上のある点の重要度を決めるタスクは、Erosion Thickness(後述)という値を求めることが有効らしいということがわかっています。上の3つはそれぞれ「接触円の2接線の角度」「接触円の半径」「Erosion Thicknessの値」でそれぞれMedial Axis上の点を色付けしたもので、下の3つはある閾値以上の点のみを抽出したものです。角度の場合は(馬の毛のような)極端に鋭い表面部分に反応したり、軸が途中で途切れてしまっていたりします。また、半径の場合は馬の足のように細い部分になっているところが切れてしまっています。一方で、Medial Axisによる色付けはうまくいっています。

しかし、3Dの形状のMedial Axis上の点の重要度を求めるタスクは、長らく有効な手法が見つけられていませんでした。唯一有効っぽい手法 4は、多面体上の全ての2面のペアの距離を求めなければならず、計算量が $O(n^2)$ になっていました。

そこで、この論文ではErosion Thicknessを3DのMedial Axisに応用する手法を提案しています。これにより、3D形状のMedial Axisの内「重要な骨格」を抜き出すことに成功しています。また計算量も、3Dモデルの頂点の数を$A$、点の数を$N$とすると、 $O(|A|log|N|)$ に抑えることができています。

2DのErosion Thickness

スクリーンショット 2020-07-28 12.50.19.png1

まず、既存の2DのErosion Thicknessを用いる手法を概観します。上の図中の $S$ は曲線の外周で、 $M$はMedial Axisです。図中の $y$ はMedial Axisの端点で、 $R(y)$は$y$における接触円の半径です。ここで、$M$上の点 $x$を選び、$y$からの$M$上の距離を$d_M(x, y)$と表します。

この時、$x$におけるErosion Thickness $ET(x)$ は、上の図中の値を用いて

ET(x)=R(y)+d_M(x, y) - R(x)

と表されます。これを分岐のあるMedial Axisに対しても一般化するため、先行研究 5 では Burning Time というものを定義しています。まず、Medial Axisが全て可燃性の線香のような素材でできていると考えます。この時、Medial Axisの各終端点(上図でいう$y$)に$R(y)$秒後に点火します。点火した炎は1秒あたり1の距離で進むものとします。もしこの炎が分岐点に到達した場合、「分岐点の枝分かれが一つを除き全て燃え尽きるまで」その先に進むのを待ちます。もしこれが満たされたら、炎は残った一つの枝分かれの方に進んでいきます。

ここで、$M$上の各点に何秒後に炎が到達するか(Burning Time)を$BT(x)$と表せます。そして、この場合、$ET(x)$は

ET(x) = BT(x) - R(x)

で表されます。要するに、Medial Axisと各点における接触円の半径がわかれば、Burning Timeを求めるだけで(?)Erosion Thicknessを求めることができるのです!

3DのBurning Function

筆者は2DでのErosion Thicknessの理論を応用し、3DのMedial Axis上におけるErosion Thicknessも「Burning Timeと接触球の半径の差である」と定義しています。しかし、3DのMedial Axisは曲面になっていて、2Dのような曲線とは勝手が違いそうです。

3Dの曲面状のMedial Axisの場合、Medial Axisの端を $\partial D$ とおけば、 上の点 $y$ とその点における接触円 $R(y)$ は定義できそうです。また、Medial Axisが一枚のシート状であれば、その上の点 $x$ におけるBurning Timeの値 $BT(x)$は、$y$からの$M$上の距離を$d_M (x,y)$と表すと、

BT(x) = \min \{d_M(x,y) + R(y), y \in \partial D \}

と表せます。

分岐点

スクリーンショット 2020-08-05 18.21.26.png1

ここで問題になるのが分岐点の扱いです。2DのBurning Timeでは

もしこの炎が分岐点に到達した場合、「分岐点の枝分かれが一つを除き全て燃え尽きるまで」その先に進むのを待ちます。

と書いたように、炎が「止まる」動作が定義されています。

スクリーンショット 2020-08-05 18.11.45.png1

これを3Dで再現するために、論文ではSectorという概念を定義しています。Sectorは、点に隣接する面のトポロジーを表したものです。
もし点に隣接する面の集合が一枚の円盤の同じトポロジーとみなせる場合(上図右の $x_1$ と $x_2$)は、その点のSectorは1つです。一方で、その点で複数の面が交差しているような場合(上図右の $x_3$ 〜 $x_6$)には、各面同士の交線で全ての面を切断した結果得られるパーツがSectorになります。例えば、$x_3$の場合は中心点から上に伸びている面と中心点の周りを囲む面の交線で周囲の面を分割でき、それぞれがSectorを形成します。
先行研究により、(理想的な)Medial Axis上の点の周りの面のトポロジーは、上図右の6種類しか存在しないことが示されているので、点の周りでのSectorの数は1,2,3,6のいずれかの値をとるということになります(今回用いたテストデータではこれに当てはまらないトポロジーの点も存在しましたが…)。

このSectorを使えば、2Dの「分岐点の枝分かれが一つを除き全て燃え尽きるまでその先に進むのを待つ」操作を表現できます。
本研究では、炎がSectorが2つ以上の点に到達した場合、「一つを除いて全てのSector経由で炎が到達するまで」その先に進むのを待つようにしています。

ポリゴンメッシュモデルにおける実装

世の中に存在する3Dモデルのほとんどはポリゴンモデルで構成されています。3Dモデルを大きく拡大すると三角形の面が現れるのを見たことのある方も多いでしょう。

このポリゴンモデルで「炎を燃やす過程」を再現するため、本研究ではMedial Axis上の各点 $N$ と、ポリゴン上の辺 $A$ を用いてグラフ $G$を構成しています。

グラフは以下の疑似コードで表したような3種類の要素で形成されています。

// 点
interface Vertex {
  radius: number // その点における接触円の半径
  time: number // その点におけるburning timeの値。デフォルト値は無限
  burned: boolean // Burning Processの結果燃やされたかどうか
  sectors: Sector[] // その点におけるSector
  primeSector: Sector // その点におけるSectorのうち、経路として採用されたSector
}

// Sector
interface Sector {
  time: number // そのSectorのburning timeの値
  burned: boolean // そのSectorがBurning Functionの結果燃やされたかどうか
  arcs: Arc[] // Sectorに含まれる辺
  primeArc: Arc // Sectorに接続している辺のうち経路として採用された辺
}

// 辺
interface Arc {
  length: number // ノード間の距離
  vertices: [Vertex, Vertex] // 辺を共有している2点
}

このグラフに対し、Dijkstra-likeに各点のBurning Timeを決定します(詳しいアルゴリズムは論文をご覧ください…)。

実装

今回はこのBurning Processをpythonで実装しました。実装はこちら

下準備

まず、グラフ $G$ を以下のコマンドにより作成します。コマンドの第2引数がmedial axisのplyファイル、第3引数が元の3Dモデルのplyファイルです。

$ python main.py ./models/hand_ma.ply ./models/hand.ply

plyファイルは各点のxyz座標と全ての面の情報を保持しているので、それを元に各点のSectorを算出して、グラフを作成します。

graph.py
    vertices = pd.DataFrame(datadict['coords'])  # 1 DataFrameの作成
    vertices['index'] = vertices.index
    vertices['burned'] = False
    vertices['primeSector'] = None # 2 初期値をセット
    vertices.loc[:, 'faces'] = vertices.index.map(getFaces) # 3 各点に隣接する面をセット

    vertices.loc[:, 'sectors'] = vertices.apply(getSectors, axis=1) # 4 各点に隣接する面の情報から、Sectorを算出

    vertices.loc[:, 'time'] = vertices.apply(getTime, axis=1) # 5 接触円の半径を算出

    vertices.loc[:, 'sectorTime'] = vertices.sectors.map(getSectorTime)
    vertices.loc[:, 'sectorBurned'] = vertices.sectors.map(getBurned)
    vertices.loc[:, 'sectorPrimeArc'] = vertices.sectors.map(getPrimeArc) # 6 Sector関連の初期値をセット

    vertices.to_pickle('./tmp/complete-vertices.pickle') # 7 一時ファイルとして保存

接触円の半径は、「元の3Dモデル上の最近傍点」を求めることにより得ています。

Burning Function

次に、生成されたグラフに対してBurning Processを実行します。

$ python queue.py

Erosion Thickness

次に、$ET(x) = BT(x) - R(x)$ により各ノードにおけるErosion Thicknessの値を計算します。コマンドの第2引数は元の3Dモデルのplyファイルです。

$ python export_ply.py ./models/hand.ply

plyファイルの生成

最後に、plyファイルを生成します。このplyファイルは、各頂点のErosion Thicknessの値に応じて色の情報を持っています。

$ python export_ply.py

結果

著者が公開している手の3Dモデル を用いて実行しました。

生成されたplyファイルをblenderでレンダリングした結果、以下のようになりました。

result-1.png

Erosion Thicknessの値が大きい部分を赤で、小さい部分を青で表示しています。手のひらの真ん中あたりの骨格として適切そうな部分が赤くなっていて、概ね良さそうな感じがします。

比較のため、Radius Functionの値で色付けしたものと並べてみました。

result-4.png

Radius Functionは薬指の付け根あたりが中心でないと判定されてしまう一方で、Erosion Thicknessなら全体からみた「芯の位置」を検出できていることがわかります。

感想

点の周囲をSectorに分割するタスクが思いの外大変でした。

点の周辺の面のトポロジーは理想的なMedial Axisでは6種類となっていましたが、面が縮退しているようなものや、「やばい接続の仕方」をしている面を分割するのが大変でした。

あと、このアルゴリズムの実行には元の3DモデルとMedial Axisの3Dモデルの両方が必要なのですが、Medial Axisの生成に使用しようと思っていたライブラリ のコンパイルが通らなかったので、この手の3Dモデルでしか実行ができませんでした…?

この記事は東京大学の講義「映像メディア学」(https://www.hal.t.u-tokyo.ac.jp/~yamasaki/lecture/index.html )の最終レポートも兼ねています。


  1. Yajie Yan, Kyle Sykes Erin Chambers, David Letscher, Tao Ju. Erosion Thickness on Medial Axes of 3D Shapes. ACM Transactions on Graphics, SIGGRAPH 2016. DOI:https://doi.org/10.1145/2897824.2925938 

  2. http://pages.cs.wisc.edu/~csverma/CS558_11/MedialAxis.html 

  3. Tamal K. Dey, Hyuckje Woo, and Wulue Zhao. 2003. Approximate medial axis for CAD models. In Proceedings of the eighth ACM symposium on Solid modeling and applications (SM ’03). DOI:https://doi.org/10.1145/781606.781652 

  4. Tamal K. Dey and Jian Sun. 2006. Defining and computing curve-skeletons with medial geodesic function. In Proceedings of the fourth Eurographics symposium on Geometry processing (SGP ’06). 

  5. Lu Liu, Erinn W. Chambers, David Letscher, Tao Ju. 2011. Extended grassfire transform on medial axes of 2D shapes. Computer-Aided Design. DOI:https://doi.org/10.1016/j.cad.2011.09.002 

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

PythonとGDALを使ってウェッブマップを作ろう

オープンソースのPythonとGDALを使って無償でGISデータを処理する方法を紹介します。今回使用するデータは国土地理院が提供している基盤地図情報の数値標高モデル。

PythonとGDALの組み合わせで上記のウェッブマップが作成されます。

インストール

まずはMinicondaを使ってPythonと必要なライブラリをインストールしましょう。ダウンロードが完了したと後はMinicondaのコマンドラインを開きPythonの仮想環境を立ち上げます(デフォルトのPython3バージョンを使用):

conda create --name myenv
conda activate myenv

次にPythonのスクリプトに使用するライブラリをインストールします:

conda install -c conda-forge gdal numpy beautifulsoup4

最後にウェッブマップ作製に使用するPythonのスクリプトをダウンロードします:

git clone https://github.com/danielhoshizaki/hillshade

使い方

まずは./data/rawディレクトリに数値標高モデルファイルがあることを確認しましょう。他のファイルをダウンロードしている場合はこの段階で./data/rawの中に置きます。

Pythonスクリプトを回す前にコードの一部を変える必要があります。condaでインストールしたライブラリGDALのパスを指定する必要があります。GDALは協力なソフトですがインストールが非常に複雑である為今回は絶対パスを使いましょう。GDALのバイナリーを探すにはLinuxのfindを使うかWindosの検索ボックスを使います。上記で作成したmyenv仮想環境のディレクトリを探せばすぐに出てきます。探すのはgdaldem.exeとgdalbuildvrt.exeが入っているはディレクトリとgdal2tiles.pyが入っているディレクトリ。見つけたらPythonスクリプトのgdal_bin_pathとgdal_tiles_pathを設定します。

準備が整ったらスクリプトを起動してウェッブマップが出来るのを待ちます。

仕組み

Pythonスクリプトは大きく分けて二つの役割を果たしています。一つはconvertと言うファンクションを使って生の数値標高モデルファイル(ZIPされたXMLファイル)をGeoTiffに変換すること。二つめの役割はコマンドラインを通してGDALに直接データを処理してもらうこと。GDALに直接流すコマンドは三つあります以下のデータ処理が行われます:

  1. 各DEMのGeoTiffを陰影起伏GeoTiffに変換
  2. 全ての陰影起伏GeoTiffをバーチャルデータセットvrtにまとめる
  3. バーチャルデータセットをウェッブマップに変換

最後に回すgdal2tilesコマンドは新規に./data/WTMSディレクトリを作ります。ディレクトリの中にはLeaflet.htmlと言うファイルがあるのでダブルクリックをしましょう。独自のウェッブマップが完成です!ただしこのウェッブマップは自分のPCで見ることしかできません.. 他の人にも見てもらい場合はGithub PagesやAWS S3に乗せるかもうちょっと頑張ってウェッブサバーに乗せてみましょう!

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

競プロで使えそうな基礎的アルゴリズム

何の記事?

競プロで使えそうなアルゴリズムを羅列してみました。

※随時更新します

素数判定(エラトステネスのふるい)

https://atcoder.jp/contests/abc084/tasks/abc084_d

from itertools import accumulate
import math
m = 10**5

L = [x for x in range(2,m+1)]

#エラトステネスのふるいで素数を抽出
for y in range(2, int(math.sqrt(m)+1)):
    L = [z for z in L if(z == y or z % y != 0)]

#N+1/2も素数であるものを抽出
P = []
for w in L:
    if (w+1)/2 in L:
        P.append(w)

#累積和のために作成
G = [0] * (m+1)
for i in P:
    G[i+1] = 1

#累積和
Q = list(accumulate(G))



n = int(input())
for _ in range(n):
    s, t = map(int, input().split())
    print(Q[t+1]-Q[s])




'''
以下の素数判定は遅い。
上のようにエラトステネスの篩を使う

def isPrime(n):

    if n == 1:
        return False
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)+1), 2):
        if n % i == 0:
            return False
    return True

'''

Bit 動的計画法(巡回セールスマン問題)

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

v, e = map(int, input().split())

inf = 10**7
edges = [[inf]*v for _ in range(v)]

for i in range(e):
    s, t, d = map(int, input().split())
    edges[s][t] = d

#Dpは全体集合の部分集合Sについて最後がvであるという制約の下で順序を最適化したときのSの中での最小コスト
dp = [[inf]*v for _ in range(2**v)]
dp[0][0] = 0

#集合(訪れたか訪れていないかを表す二進数)
for x in range(2**v):
    #最後に訪れたノード
    for y in range(v):
        #最後に訪れた以外のノード
        for z in range(v):
            #1.すでに訪れたかどうか 2.最後に訪れたノードではないか 3. yとzはそもそもつながっているのか
            if ((x >> y) & 1) and y != z and edges[z][y] < 10**6:
                dp[x][y] = min(dp[x][y], dp[x^(1<<y)][z]+edges[z][y])

if dp[-1][0] > 10**6:
    print(-1)
else:
    print(dp[-1][0])
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

heroku(無料プラン)で独自ドメインサイトにする方法

herokuの無料プランは、無料でサイトを公開できる素晴らしいサービスです。
でも、[appname]herokuapp.comはダサいし、独自ドメインが欲しい。。

そんな人のために、今回僕が行った方法をメモ代わりに残しておきます。

開発環境

・MacbookAir
・python(3.6.5)
・wagtail(2.9.2)

今回お世話になったサービス

・heroku
・cloudflare
・Freenom

 前提条件

・herokuにサービスをアップしている。
・独自ドメインを所有している(今回はFreenomを使用しました)。

参考サイトとの相違点

車輪の再発明を避けるために参考文献と重複する場所が多々あるのでサラッと行きます。
まずは、参考文献と同様に、
1.cloudflareにアカウント登録し、独自ドメイン後のサイト名でFreeプランを選択。
2.初期に入っているものを全て削除し、以下のように設定する。(画像は以下の参考文献から拝借しました)
https___qiita-image-store.s3.ap-northeast-1.amazonaws.com_0_346533_85d72494-9277-5ff0-a782-8f69ee6a391c.png

3.今回は、Freenomなので、Freenom上でNameServer(Mydomain>Managing domain>ManagementTools)よりNameServerをcloudflareに記載されているものに変更
今回の相違点
4.herokuに変更を適用させる。参考文献では、「Personal>'appName'>Setting>Domains and cerfificates 」とありましたが、私の方ではDomains and cerfificatesは確認できず、別個でした。
そのため、Personal>'appName'>Setting>Domains」から独自ドメインを適用しました。

参考文献

【無料】Cloudflareを使ってHerokuで独自ドメインで運用する方法

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

PythonとSeleniumでDeepLに英文流して自動翻訳させる

やりたいこと

とりあえず、Science Directから書誌情報+アブストをゲットした。次は、これはDeepLに流し込んで翻訳させていく、っていう処理をしたい。有料プランに契約すれば、ファイルを一気に翻訳させることが可能になるけど、まあ、ものは試しということでselenimuとchromedriverでやってみようということでチャレンジ。

準備

とりあえずCSVファイルをpythonに読み込む。

import pandas as pd

df = pd.read_csv("DB.csv",header=None, delimiter=",", quoting=1)
print(df.at[0,1])  #   タイトル
print(df.at[0,9])  #   アブスト
print(df.at[0,10]) #  キーワード

for title in df[1]:
    print(title)

まあ、これはすんなり。

SeleniumとChromDriverでDeepLにアクセス

from selenium import webdriver  

load_url = "https://www.deepl.com/ja/translator"
driver = webdriver.Chrome(executable_path='c:/work/chromedriver.exe')  #  driver = webdriver.Chrome()
driver.get(load_url)

ここもまあすんなりいく。

英文をDeepLに送る

テキストを送り込んで、翻訳をゲットする、ということで、英文を入力するtextareaと翻訳を出力してくるtextareaのcss selectorをChromeのdevelopper画面から探し出す。
で、入力についてはすんなり、

#dl_translator > div.lmt__sides_container > div.lmt__side_container.lmt__side_container--source > div.lmt__textarea_container > div > textarea

だということがわかった。
ということで、

title = df.at[0,1]
input_selector = "#dl_translator > div.lmt__sides_container > div.lmt__side_container.lmt__side_container--source > div.lmt__textarea_container > div > textarea"
driver.find_element_by_css_selector(input_selector).send_keys(title)

すなおに、英語はDeepLに送りこめた。

日本語訳の取得 その1

一方で、出力のほうが嵌まった。
とりあえず、一回適当な英文で翻訳を作らせて出力させて、その出力テキストを使ってDevelopper画面で検索して探してみたら、なんとtextareaにそのまま入力されているのではなく、buttonタグが付けられて表示されている。
へー、と思いながら、じゃあ、ということでそのbutton要素を取得して、テキストを取ろうとしたのだが、なぜか取れない。
VSCodeのデバッガで変数の状態を見ても、要素がもつtextは空文字になっている。え?なんで??
Chrome上では見えてるのに、Developper画面ではちゃんとbuttonタグにはさまれて訳が表示されているのに、なんで空文字なん??

とりあえず、対処として、DeepLにはクリップボードに訳をコピーしてくれる便利なボタンがあるので、それをSeleniumでクリックしてクリップボードにコピーさせ、クリップボードから訳を取得することにする。
ってことで、クリップボードを扱うためのパッケージpyperclipをインストールして、クリップボードにコピーしてくれるボタンのCSS Selectorを見つけ出して、以下のようなスクリプトをかいて実行。

import pyperclip

title = df.at[0,1]
input_selector = "#dl_translator > div.lmt__sides_container > div.lmt__side_container.lmt__side_container--source > div.lmt__textarea_container > div > textarea"
driver.find_element_by_css_selector(input_selector).send_keys(title)

time.sleep(5)

OutputCopyBtn = "#dl_translator > div.lmt__sides_container > div.lmt__side_container.lmt__side_container--target > div.lmt__textarea_container > div.lmt__target_toolbar.lmt__target_toolbar--visible > div.lmt__target_toolbar__copy > button"
driver.find_element_by_css_selector(OutputCopyBtn).click()

print(pyperclip.paste())

ふむ、これで取るのは取れた。

日本語訳の取得 その2

なんか負けた感があるので、button要素から直接テキストを取れないかリトライ。
ググってると、行きついたのが@riikunn1004さんの記事
なるほど。.getAttribute("textContent")というのでとれるのか。
画面上でも見えてるし、Developper画面でも見えてるのに取れない理由はよくわからないけど、
ということで、これを参考に、以下のようなスクリプトにしてみた。

Output_selector = "#dl_translator > div.lmt__sides_container > div.lmt__side_container.lmt__side_container--target > div.lmt__textarea_container > div.lmt__translations_as_text > p > button.lmt__translations_as_text__text_btn"
Outputtext = driver.find_element_by_css_selector(Output_selector).get_attribute("textContent")
print(Outputtext)

これで取れることを確認。ふう。

おまけ

もうすこしDeepLのページの造りをしらべてみた。
入力のテキストエリアと同様に出力のテキストエリアも

#dl_translator > div.lmt__sides_container > div.lmt__side_container.lmt__side_container--target > div.lmt__textarea_container > div.lmt__inner_textarea_container > textarea

で指定されている。ただ、CSSみてみると:disabledにがついていて操作が無効化されている。
実際に、英文を入力するまえは出力エリアは選択できない。
で、英語を入力すると、ここのエリアのクラス名が変わり、disableが消える。(css selectorは変わらない。)

ただ、じゃあ、このエリアに訳が入っているのか?というと入っていない。
現時点では空のまま。

なのだが、このエリアをマウスでクリックして、テキストエリアにフォーカスをあてると、以下のような要素がポンっと表れて訳が表示される。(ちなみに英語としてtestを入力してる。なので訳はしけん)

<div class="lmt__textarea_base_style" 
  style="
    position: absolute; transform: translate(-500%, -500%); 
    padding: 16px 32px 80px 24px; margin: 0px; overflow: hidden; font-family: &quot;
    Open Sans&quot;, sans-serif; font-size: 24px; font-stretch: 100%; font-weight: 400;
    line-height: 36px; height: 468.5px; width: 448.5px;">
  <span style="outline: green solid 1px;">しけん</span>
  <span style="outline: red solid 1px; display: inline-block; position: relative; height: 1em;"></span>
  <span style="outline: blue solid 1px;"></span>
</div>

こいつのCSS Selectorは

#dl_translator > div.lmt__sides_container > div.lmt__side_container.lmt__side_container--target > div.lmt__textarea_container > div.lmt__inner_textarea_container > div

んー、何となくわかってきた。
つまり、DeepLさんのページは、英文が入力されると、画面上に訳は表示されるけど、テキストエリアに表示させているわけではない。

実は下の方に、こういう形で

<button class="lmt__translations_as_text__text_btn">しけん</button>

で隠し持っている。
で、画面上で出力の「テキストエリア」っぽく見えるところにカーソルを持ってきてクリックを押すと上のようなdiv要素が展開し、訳が表示される、というようになっている。この切り替えをするために、button要素にしてる、ということかな?

随分ややこしい造りにしてる。なんでこんな造りにしてるんやろ??
ただ、なるほど、こういう造りであれば、「テキストエリア」っぽく見えるところを一回クリックしない限り、テキストエリアの回りを探してみても訳にはたどり着けない。
また、buttonも基本的にはdisableかinvisibleかとにかく見えないようにしているんだろうから、.textでは取れない。
多分、一回テキストエリアにフォーカスをあてたら現れる要素のCSS Selectorを取得して、アクセスを試みても、一回テキストエリアにフォーカスをあてない限りは、「そんな要素はない」と弾かれる。逆に1回フォーカスをあててみたら、要素が見つかるので取れるんだろと思う。

ほんと、なんでこんなややこしいことしてるんだ??

最終的なソースコード

とりあえず、DeepLに流して英文を自動翻訳させる部分は以下のような形。
途中のwhile文は、要するに英文の翻訳に時間がかかるから、その待ち時間のため。
1秒おきに翻訳できたかどうかをチェックしに行き、翻訳が完成していたらブレークする。

import pandas as pd
import time
from selenium import webdriver  #  
import chromedriver_binary

df = pd.read_csv("Reliablity EngineeringDB.csv",header=None, delimiter=",", quoting=1)

df.columns=["Authors", "Title", "jTitle", "VolIssue","Year", "Pages", "ISSN","DOI","URL","Abst","Keywords"]
print(df)

Title.df.at[0,1]

load_url = "https://www.deepl.com/ja/translator"
driver = webdriver.Chrome()  #  driver = webdriver.Chrome("c:/work/chromedriver.exe")
driver.get(load_url)

input_selector = "#dl_translator > div.lmt__sides_container > div.lmt__side_container.lmt__side_container--source > div.lmt__textarea_container > div > textarea"
driver.find_element_by_css_selector(input_selector).send_keys(Title)
while 1:
    Output_selector = "#dl_translator > div.lmt__sides_container > div.lmt__side_container.lmt__side_container--target > div.lmt__textarea_container > div.lmt__translations_as_text > p > button.lmt__translations_as_text__text_btn"
    Outputtext = driver.find_element_by_css_selector(Output_selector).get_attribute("textContent")
    if Outputtext != "" :
        break
    time.sleep(1)
print(Outputtext)
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

【備忘録】shape[0], shape[1], shape[2]の中身

忘れやすいから注意!

a.shape[0]はaの行(row)の数、a.shape[1]は列(col)の数、a.shape[2]はチャンネル数

unnamed.png

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

GoogleColaboratoryでゼロから作るDeep Learningのサンプルコードを実行した際のメモ

はじめに

O'REILYから出版された「ゼロから作るDeep Learning -Pythonで学ぶディープラーニングの理論と実装」をGoogleColaboratory環境でサンプルコードを実行する際にメモした内容となります。

  • 書籍のサンプルデータをGitHubより入手
  • データのマウント方法について(マイドライブにデータをアップロードするだけでは、利用できないので接続方法の紹介)
  • 画像の表示について(サンプルコード記述してもGoogleColaboratoryでは画像が表示されなかった為、代替え方法の紹介)

第3章 ニューラルネットワーク

3.6.1 MNISTデータセット
3.7.1 ニューラルネットワークの推論処理

上記の内容を実行した際のメモとなります。
(P72〜P75)

データの取得

GitHubよりデータを取得します。(ダウンロード)
https://github.com/oreilly-japan/deep-learning-from-scratch
フォルダ名 = deep-learning-from-scratch-master

データのアップロードとマウントについて

  1. マイドライブGoogleドライブ内にフォルダをアップロードします。
  2. 新規でGoogle Colaboratoryを作成します。
  3. ドライブをマウントします。(ノートブックでデータを使用できる状態にする)
  • アイコンをクリックすることで処理が始まります。
    mount_1.png
  • Googleドライブに接続
    接続.png
  • driveが表示されたら接続完了
    mount_2.png

ディレクトリを移動する

最初のコードを入力する前に、カレントディレクトリを変更する必要があります。
cd.png

load_mnist 関数のインポート

load_minst関数インポート.png

mnist_show.pyを実行

  • 6行目までのコードを省略することも可能です。(load_mnistのインポートの際に実行済み)
  • 1枚目の訓練画像の数字 = 5
  • 1次元配列の個数 = 784,
  • 1次元配列より元の形状に再変形 = 28, 28
  • 本来、表示されるはずの訓練画像が表示されません。 = imgに格納はされているが表示されない。 mnist_show.png

画像の表示

  • 本当に 5 であるか確認する為、別の表示方法を試みました。
  • matplotlibをインポートし画像の表示を実行。
  • 1枚目の訓練画像を表示することに成功しました。
    5img.png

neuralnet_mnist.pyを実行

  • 正解した認識精度 = 0.9352(93.52%)で分類する。

最後に

ただサンプルコードをGoogleColaboratoryで実行するだけですが、結構な時間を費やしてしまいました。
同じような内容で悩んでいる方に、少しでも役立てていただけるよう初めて投稿しました。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

【備忘録】VSCode cv2インテリセンスエラー

治すには
File → Prefarence → Setting → 「Python.linting.pylintArgs」で検索 → 「AddItem」をクリック →
「--extension-pkg-whitelist=cv2」を追加

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

PythonのOpenCVにC++のcopyTo, Cloneはない

気をつけよう

copyToの代わり

copyTo.py
src1[ 0 : src2.shape[0], 0 : src2.shape[1]] = src2

Cloneの代わり

clone
src2 = src1.copy()
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

【備忘録】PythonのOpenCVにC++のcopyTo, Cloneはない

気をつけよう

copyToの代わり

copyTo.py
src1[ 0 : src2.shape[0], 0 : src2.shape[1]] = src2

Cloneの代わり

clone
src2 = src1.copy()
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

PythonにcopyTo, Cloneはない

気をつけよう

copyToの代わり

copyTo.py
src1[ 0 : src2.shape[0], 0 : src2.shape[1]] = src2

Cloneの代わり

clone
src2 = src1.copy()
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

Python + Seleniumで「Message: session not created」が発生した場合

PythonでSeleniumを動かしている時に「Message: session not created」が発生して、気づいたら数時間エラー解決に掛かっていました。
このエラーをググると大体「Chromeのバージョン」と「Chrome-driverのバージョン」違いで発生するという情報が出てきますが、今回自分が経験したパターンは異なっていたので、備忘録として残しておきたいと思います。

[root@v111-111-111-11 html]# python3 run.py
Traceback (most recent call last):
  File "/usr/local/lib/python3.7/site-packages/selenium/webdriver/chrome/webdriver.py", line 81, in __init__
    desired_capabilities=desired_capabilities)
  File "/usr/local/lib/python3.7/site-packages/selenium/webdriver/remote/webdriver.py", line 157, in __init__
    self.start_session(capabilities, browser_profile)
  File "/usr/local/lib/python3.7/site-packages/selenium/webdriver/remote/webdriver.py", line 252, in start_session
    response = self.execute(Command.NEW_SESSION, parameters)
  File "/usr/local/lib/python3.7/site-packages/selenium/webdriver/remote/webdriver.py", line 321, in execute
    self.error_handler.check_response(response)
  File "/usr/local/lib/python3.7/site-packages/selenium/webdriver/remote/errorhandler.py", line 242, in check_response
    raise exception_class(message, screen, stacktrace)
selenium.common.exceptions.SessionNotCreatedException: Message: session not created
from disconnected: Unable to receive message from renderer
  (Session info: headless chrome=80.0.3987.122)

エラー原因

バージョンも両方一致しているし、バージョン変更していないし、以前まで動いていたから、何かChromeのプロセスが大量に溜まってたりしないかなと思って、実行しているサーバ上でChromeのプロセスを確認しました。

[root@v111-111-111-11 html]# pgrep -l chrome
10436 chrome
10444 chrome
[以下略]

ずらっとChromeのプロセスが50個くらい大量に残っていました。恐らくwebdriverの処理が終了した後にChromeのプロセスを終了できておらず、溜まってしまったのかと思います。

解決方法

[root@v111-111-111-11 html]# pkill chrome

Chromeのプロセスを終了させ、再度スクリプトを実行したところ、問題なく動きました。
「Chromeのバージョン」と「Chrome-driverのバージョン」が一致しているにも関わらず、上記エラーが発生する場合は参考にしてみてください。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

tensorflow-gpuが動いたCUDA, cuDNNのバージョンのメモ

PyPIに置かれているtensorflow-gpuビルドが対応している
CUDA, cuDNNバージョンをメモするだけの記事です。

対応CUDA, cuDNN一覧

このページは個人が自分用メモとして作っていますので
tensorflow公式に記載がない場合のみ参考までにご覧ください。

tensorflow公式
https://www.tensorflow.org/install/source#tested_build_configurations

Windwows10

tensorflow CUDA cuDNN 備考
2.3.0 10.1 7.6 手元環境で動作を確認
2.2.0 10.1 7.6 手元環境で動作を確認
2.1.0 10.1 7.6 Release Noteに記載あり
2.0.0 10.0 7.4 公式サイトに記載あり

Ubuntu 18.04

tensorflow CUDA cuDNN 備考
2.3.0 10.1
2.2.0 10.1 7.6 手元環境で動作を確認
2.1.0 10.1 7.6 Release Noteに記載あり
2.0.0 10.0 7.4 公式サイトに記載あり

バージョンについて

pip installでインストールされるtensorflow-gpuビルドは特定のバージョンのCUDAを参照するようになっているので、バージョンが違うCUDAを入れると動きません。

どのバージョンのtensorflow-gpuがどのバージョンのCUDAを使うようにビルドされているかは古いバージョンについてはこちらに一覧されているので問題ないんですが、2020年8月現在tensorflow 2.3.0までリリースされているのに一覧表には2.1.0までしか載ってません。
https://www.tensorflow.org/install/source#tested_build_configurations

じゃあRelease Notesに載ってるかというとtensorflow 2.1.0には対応CUDAバージョンが書かれているのにtensorflow 2.2以降のRelease Notesには載ってません。
https://github.com/tensorflow/tensorflow/releases

これだと困るので新しいバージョンがちゃんと動いたらそのときのバージョンをメモしておこうというのがこの記事です。新しいバージョンについても新しい記事を書くんじゃなくてここに追記していきます。

自分で確認する方法

CUDAが入っていないかバージョンが適切でない場合、importした際に以下のようにエラーメッセージが出ます。その際に表示されるdllのファイル名でバージョンが分かります。以下ではcudart64_101.dllを読もうとしているのでおそらくCUDA10.1が必要なんだろうという感じです。

python
>>> import tensorflow as tf

2020-08-05 00:33:55.037723: W tensorflow/stream_executor/platform/default/dso_loader.cc:59] Could not load dynamic library 'cudart64_101.dll'; dlerror: cudart64_101.dll not found
2020-08-05 00:33:55.037919: I tensorflow/stream_executor/cuda/cudart_stub.cc:29] Ignore above cudart dlerror if you do not have a GPU set up on your machine.
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

PFRL(PyTorch+OpenAIGym)でrandomのseedを固定する方法

はじめに

All you need is 再現性
強化学習を試すにとても便利なライブラリPFRLが先日公開されましたが、公式のチュートリアルのseedが固定されていなかったためその方法を調べて記した備忘録です。

code

言うて大した話ではなく、

env = gym.make('CartPole-v0')

のすぐあと辺りにでも

numpy.random.seed(1234)
torch.manual_seed(1234)
env.seed(1234)
env.action_space.seed(1234)

と書き加えれば、無事seedが固定され結果が毎度同じになります。
env用に固定しなくてはいけないseedが二つある点に注意が必要ですね。



以上です。
ありがとうございました。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

Codeforces Round #660 (Div. 2) バチャ復習(8/4)

今回の成績

スクリーンショット 2020-08-05 12.11.34.png

今回の感想

今回は三問解けました。C問題は実装が重めでしたが方針を整理したことで正解することができました。

D問題についても実装を整理すれば解けていたところなので、引き続き意識していきたいです。

A問題

$x$を異なる四つの正の整数の和(そのうち少なくとも三つは$nearly \ primer$)で表現しますが、できるだけ多くの$x$を表現するために最小の$nearly \ primer$を探すことにしました。$nearly \ primer$は二つの素数の掛け算で表せる数であり、$6,10,14$が最も小さい三つの$nearly \ primer$になります。したがって、$x$が$30(=6+10+14)$以下の場合は題意の四つの整数を構成することができません。

また、$x >30$の時は$6,10,14$を選ぶとすると、もう一つ選ぶ数として$6,10,14$は選べず$x=36,40,44$の時はこの方法の場合は題意の四つの整数を構成できませんが、$14$の代わりに$15$を選ぶことで$x=36,40,44$の場合も題意の四つの整数を構成することができます。

A.py
for i in range(int(input())):
    n=int(input())
    if n<=30:
        print("NO")
    elif n==36:
        print("YES")
        print("6 10 15 5")
    elif n==40:
        print("YES")
        print("6 10 15 9")
    elif n==44:
        print("YES")
        print("6 10 15 13")
    else:
        print("YES")
        print("6 10 14"+f" {n-30}")

B問題

問題を要約すると、$n$が与えられている元で、$n$桁の10進数$x$のそれぞれの桁を2進数表現にして連結した2進数$k$を考え、$k$の下$n$桁を無視した数$r$を最大にする中で最小の$x$を構成するというものです。また、二進数表現にするときに0埋めはしません。

まず、$r$を最大にするには$x$を$99…99$にすれば良いのは自明です。しかし、この時$x$は最大になります。したがって、無視する$k$の下$n$桁をできるだけ小さくする必要があります。また、2進数表現した時に$9$は$4$桁になので、$r$が最大のまま$x$を小さくするには$9$を$8$に置き換えるしかありません。よって、無視する$k$の下$n$桁に相当する$x$の桁を$8$にすれば良く、幾つの桁を$8$に置き換えられるかを$n\%4$の値で場合分けして考えます。

IMG_E4AE8B90A96E-1.jpeg

上記より、$n\%4=0$の時は$x$の下$[\frac{n}{4}]$桁を$8$に、$n\%4 \neq 0$の時は$x$の下$[\frac{n}{4}]+1$桁を$8$にすることができ、コードは下記のようになります。

B.py
for _ in range(int(input())):
    n=int(input())
    l=n//4 if n%4==0 else n//4+1
    ans="9"*(n-l)+"8"*(l)
    print(ans)

C問題

まず、首都(頂点1)を根とする根付き木を考えます。この元で、任意の頂点で$h_i,p_i$が成り立つように気分の良い人と悪い人の人数を決めますが、闇雲に決めていくと難しいことがわかります。また、辺の途中で気分が変わる($h_i$への寄与が+1から-1になる)ことを扱うのも難しいです。したがって、このような場合は木を根の方向か葉の方向から辿っていきます。前者の場合はBFS、後者の場合はDFSを使うことが多いです。また、今回の問題では、葉において気分の良い人と悪い人の人数を一意に定められそうだったのでDFSを行うことにしました。

ここで、$i$番目の頂点が葉であると仮定し、その頂点を通る気分の良い人と悪い人の人数をそれぞれ$c,d$とすると、その頂点を通る人はその都市に住んでいる人だけなので、$c-d=h_i,c+d=p_i $が成り立ちます。これを式変形すると$c= \frac{p_i+h_i}{2},d=\frac{p_i-h_i}{2}$となり、$c,d$はいずれも0かつ整数であれば題意を満たします。

次に、$i$番目の頂点が葉でないと仮定するとDFSは葉に近い頂点から順に探索するので、その頂点を根とした部分木に含まれるそれぞれの頂点を通る気分の良い人と悪い人の人数はすでにわかっています。ここで、DFSの再帰関数でそれぞれの頂点を通る気分の良い人と悪い人の人数をペアにして返せば、$i$番目の頂点を通るが$i$番目の頂点には住んでいない良い人と悪い人の人数を先に求めることができ、それぞれ$x,y$とおきます。

この時、$i$番目の頂点を通る気分の良い人と悪い人の人数をそれぞれ$c,d$とすれば、$c-d=h_i,c+d=p_i +x+y$が成り立ちます。これを式変形すると、$c= \frac{p_i+x+y+h_i}{2},d=\frac{p_i+x+y-h_i}{2}$となります。また、$c,d$はいずれも0かつ整数であることに加え、気分が一回悪くなった人は気分が良くなることはないので、$c<x$となることもあり得ません。

葉と葉でない場合分けに注意してDFSを行って全ての頂点をチェックすレバ答えを求めることができます。また、成り立たない頂点がある場合は再帰関数で(-1,-1)のペアを返すようにしました。

今回重要な事項


・木を根の方向から辿りたい場合はBFS
→根からその頂点までの経路の情報を先に求めることができる
・木を葉の方向から辿りたい場合はDFS
→その頂点を根とする部分木に含まれる頂点の情報を求めることができる

C.cc
//デバッグ用オプション:-fsanitize=undefined,address

//コンパイラ最適化
#pragma GCC optimize("Ofast")

//インクルードなど
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
//FORAは範囲for文(使いにくかったら消す)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define CANT MP(ll(-1),ll(-1))

pair<ll,ll> dfs(vector<ll> &p,vector<ll> &h,vector<bool> &seen,vector<vector<ll>> &graph,ll v) {
    seen[v] = true;
    bool f=false;
    //良い悪いのペア
    pair<ll,ll> x(0,0);
    for (auto ne:graph[v]) { 
        if(seen[ne])continue;
        f=true;
        pair<ll,ll> y=dfs(p,h,seen,graph,ne);
        if(y==CANT)return CANT;
        x.F+=y.F;x.S+=y.S;
    }
    //cout<< x.F << " " << x.S << " " << v << endl;
    if(f){
        if(abs(p[v]+x.F+x.S)%2!=abs(h[v])%2){
            //cout<<-1<<endl;
            return CANT;
        }else{
            ll c=(p[v]+x.F+x.S+h[v])/2;ll d=(p[v]+x.F+x.S-h[v])/2;
            if(c<0 or d<0 or c<x.F){
                //cout<<-2<<endl;
                return CANT;
            }else{
                return MP(c,d);
            }
        }
    }else{
        if(abs(p[v]%2)!=abs(h[v]%2)){
            //cout<<-3<<endl;
            return CANT;
        }else{
            ll c=(p[v]+h[v])/2;ll d=(p[v]-h[v])/2;
            if(c<0 or d<0){
                //cout<<-4<<endl;
                return CANT;
            }else{
                return MP(c,d);
            }
        }
    }
}

signed main(){
    //入力の高速化用のコード
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    REP(_,t){
        ll n,m;cin>>n>>m;
        vector<bool> seen(n,false);
        vector<vector<ll>> graph(n);
        vector<ll> p(n);REP(i,n)cin>>p[i];
        vector<ll> h(n);REP(i,n)cin>>h[i];
        REP(i,n-1){
            ll x,y;cin>>x>>y;
            graph[x-1].PB(y-1);
            graph[y-1].PB(x-1);
        }
        pair<ll,ll> z=dfs(p,h,seen,graph,0);
        if(z==CANT){
            cout<<"NO"<<endl;
        }else{
            cout<<"YES"<<endl;
        }
    }
}

D問題

残り時間が少なかったこともあって焦って雑な方針になってしまいました。残り時間を気にしすぎないようにしたいです。

コンテスト中は貪欲に数の大きいものを選んでいくと思っていましたが、順番が関係する場合は有向グラフを考えることで見通しが良くなります。

この問題では、$i$を選んで操作を行う際、$a[i]$を$ans$だけでなく$a[b[i]]$へと加えますが、$a[i]$が負の場合は$i \rightarrow b[i]$よりも$b[i] \rightarrow i$の順で操作を行えば良いです。逆に$a[i]$が正の場合は$i \rightarrow b[i]$で操作を行えば良いです。

自分は適当に考えて貪欲に正の大きい数のものから選ぼうとしましたが、それぞれの$a[i]$は値が変わりうるので最適ではありません。しかし、逆に言えば値の変わらない$a[i]$は選ぶことができます。したがって、それぞれの数を重みのついた頂点として有向グラフを考えれば、他の頂点から入ってくる辺が0本の頂点(出次数が0の頂点,源点)では値は変わりません。

よって、入力で受け取った$b[i]$が辺の先を示すものとして有向グラフを考え、源点から次の判定を行います($\because$有向無閉路グラフなので必ず源点は存在します)。$a[i] \geqq 0$の時は、他の頂点の重みを増やすことができるので、a[i]をfに挿入し$i$番目の頂点と繋がる頂点の重みに$a[i]$を足します。$a[i] < 0$の時、他の頂点の重みを増やすことができないので、a[i]をsに挿入するのみです。また、判定を行った先の頂点の出次数は1つずつ減らし、出次数が0になったものを新たに考える頂点の候補とします。有向無閉路グラフなので、以上で任意の頂点のチェックを行うことができます。また、更新されたa[i]の値の総和が$ans$の最大値で、操作の順番はfに挿入された頂点は重みを増やすので昇順でsより先に行い、sに挿入された頂点は重みを減らすので逆順に行えば良いです。

D.py
from collections import deque
ans=0
n=int(input())
a=list(map(int,input().split()))
b=[i-1 if i!=-1 else -1 for i in list(map(int,input().split()))]
flow=[0]*n
graph=[[] for i in range(n)]
for i in range(n):
    if b[i]!=-1:
        flow[b[i]]+=1
        graph[i].append(b[i])
check=[a[i] for i in range(n)]
ver=deque()
lv=0
for i in range(n):
    if flow[i]==0:
        ver.append(i)
        lv+=1
f,s=[],[]
while lv:
    #print(ver)
    for i in range(lv):
        x=ver.popleft()
        lv-=1
        if check[x]>=0:
            f.append(x)
            for j in graph[x]:
                flow[j]-=1
                check[j]+=check[x]
                if flow[j]==0:
                    ver.append(j)
                    lv+=1
        else:
            s.append(x)
            for j in graph[x]:
                flow[j]-=1
                if flow[j]==0:
                    ver.append(j)
                    lv+=1
#print(check)
print(sum(check))
print(" ".join(map(lambda x:str(x+1),f+s[::-1])))

E問題以降

今回は飛ばします

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

【Python】ワンライナーFFT(高速フーリエ変換)などという狂気

使うNumpy関数+定数

from numpy import tile, interp, linspace, exp, r_, pi

DFT(遅い)

def dft(x):return exp(-2j * pi * r_[:len(x)] / len(x))**r_[[r_[:len(x)]]].T @ x

FFT(2の累乗要素限定)

def fft(x):return tile(fft(x[::2]), 2) + (r_[[[1],[-1]]] * (exp(-2j * pi * r_[:len(x) // 2] / len(x)) * fft(x[1::2]))).ravel() if len(x) > 1 else x

FFT(要素数制限なし、長い)

def fft(x):return interp(linspace(0, 1 << (len(f'{len(x) - 1:b}')), len(x)), r_[:1 << (len(f'{len(x) - 1:b}'))], fft(r_[x, [0] * ((1 << (len(f'{len(x) - 1:b}'))) - len(x))])) if ('1' in f'{len(x):b}' [1:]) else tile(fft(x[::2]), 2) + (r_[[[1], [-1]]] * (exp(-2j * pi * r_[:len(x) // 2] / len(x)) * fft(x[1::2]))).ravel() if len(x) > 1 else x

動作確認

from numpy import sin, fft, random
import matplotlib.pyplot as plt

変換する波形

周波数、振幅がランダムな5つの$sin$波の合成、$2048(=2^{11})$要素

n = 1 << 11
x = linspace(0, 2 * pi, n)
y = 0

for w in n / 2 * random.rand(5):
    y += random.rand() * sin(w * x)

plt.plot(x, y, lw = .3)

image.png

Numpy.fft.fft

%timeit fft.fft(y)
plt.plot(abs(fft.fft(y))**2)

9.01 µs ± 42.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
image.png

DFT

%timeit dft(y)
plt.plot(abs(dft(y))**2)

568 ms ± 899 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
image.png

FFT(2の累乗要素限定のほう)

%timeit fft(y)
plt.plot(abs(fft(y))**2)

51.2 ms ± 76.9 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
image.png

FFT(長いほう)

%timeit fft(y)
plt.plot(abs(fft(y))**2)

54.1 ms ± 159 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
image.png

まとめ

NumpyのFFT早すぎィ!
出力は一致してますが、FFTではただのDFTの約10倍高速化出来ていることが確認できます。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

for i in range(len(hoge)): って書かないで

初めてのfor文

多くのPython教材のfor文の章は、

n = 10
for i in range(n):
    print(i)

と書くと「0〜9が出力できる!」というところからはじまる。

次に、「"Hello, World!"を1文字ずつ出力するにはどうすればいいか?」という問題に直面すると、

hoge = "Hello, World!"
for i in range(len(hoge)):
    print(hoge[i])

と書く人が多い気がする。
もし以前に「文字列はhoge[i]と指定することでi番目を取り出せる」ことを知っていると、「0〜9が出力できる!」の2つの知識が合わさって上のコードが完成する。

しかし、私は

hoge = "Hello, World!"
for i in hoge:
    print(i)

の書き方を強く推したい!

なぜ?

正直、「見た目がすっきりするから」(逆にいうと、range(len(hoge))は見た目がごちゃごちゃするから)でしかない。しかし、感じ方は人それぞれなのでもう少し説得力のある理由を無理やりひねり出してみた。

  • 速い
  • 変数名に意味が生じる
  • 変数を分けられる
  • コードに一貫性が生じる

速い

hoge = "Hello, World!"としてjupyterで速度を測定すると、

# In[1]:
%%timeit
for i in range(len(hoge)):
    hoge[i]  # 出力はしない
# Out[1]:
# 976 ns ± 34.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

# In[2]:
%%timeit
for i in hoge:
    i
# Out[2]:
# 294 ns ± 3.83 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

となり、3倍ほど速い。しかし、単位がnsなので実感は特にない。

変数名に意味が生じる

for i in range(len(hoge)):の場合、ihogeがどんなものであろうとただのインデックスでしかない。しかし、for i in hoge:と書くと、ihogeの各要素が入ることになる。
例えば、hoge = schoolsという2次元配列があり、その要素を全て出力するコードを以下の2通りで書いてみる。

# サンプル1
for i in range(len(schools)):
    for j in range(len(schools[i])):
        print(schools[i][j])

# サンプル2
for students in schools:
    for student in students:
        print(student)

サンプル1では、schools[i][j]と言われても何が出てくるのか分からず、schoolsの定義までさかのぼらなければならない。サンプル2では、schoolsstudentsという生徒名簿が入っていて、各学校の生徒studentが1人ずつ出力されるということをなんとなく予測できる。

変数を分けられる

hoge = [("H", "h"), ("E", "e"), ("L", "l"), ("L", "l"), ("O", "o")]として、for文内で大文字と小文字を別々に使いたい場合、

for upper, lower in hoge:
    print(upper)
    print(lower)

のように、分けることができる。上の章と同じ理由で、hoge[i][0], hoge[i][1]とするよりも可読性が上がる。

コードに一貫性が生じる

hogeがもしイテレータだったとしたらTypeError: object of type 'generator' has no len()のようなエラーが生じるため、lenは使えない。よって、for i in hoge:と書かなければならない。ここで、イテレータではないlistやstrなどの場合もfor i in hoge:と書くとコードに一貫性が生じる。
そもそも、Pythonのfor文はイテレータであってもイテレータでなくても、内部的にはiter(hoge)でinの後ろに置いたイテラブルオブジェクトはイテレータ化され、next(hoge)を繰り返すという動作は全く同じである。そのため、listやstrなどの場合もあたかもイテレータであるかのように実装する方が自然に感じる。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

connextionとmarshmallow-sqlalchemyでDB定義上not nullかつdefaultありなフィールドで「Field may not be null.」が出るのを抑制した

とりあえず動いたからよし!したけどもっと筋の良い方法もありそう。

環境

requirement.txt
# 抜粋
connexion==2.7.0
marshmallow-sqlalchemy==0.23.1
marshmallow==3.7.1
sqlalchemy==1.3.18
flask-marshmallow==0.13.0
flask-migrate==2.5.3
flask-sqlalchemy==2.4.4
flask==1.1.2

問題のColumn

model.py
hoge_date = db.Column(db.Date(), nullable=False, default=date.fromisoformat('2099-12-31'))

エラー内容

console.log
marshmallow.exceptions.ValidationError: {'hoge_date': ['Field may not be null.']}

対処

schema.py
class HogeSchema(ma.SQLAlchemyAutoSchema):
    class Meta:
        model = Hoge

    # これを追加
    @pre_load
    def remove_has_defalt_key_if_none(self, in_data: dict, **kwargs):
        if in_data.get('hoge_date') is None:
            in_data.pop('hoge_date', None)
        return in_data
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

connexionとmarshmallow-sqlalchemyでDB定義上not nullかつdefaultありなフィールドで「Field may not be null.」が出るのを抑制した

とりあえず動いたからよし!したけどもっと筋の良い方法もありそう。

環境

requirement.txt
# 抜粋
connexion==2.7.0
marshmallow-sqlalchemy==0.23.1
marshmallow==3.7.1
sqlalchemy==1.3.18
flask-marshmallow==0.13.0
flask-migrate==2.5.3
flask-sqlalchemy==2.4.4
flask==1.1.2

問題のColumn

model.py
hoge_date = db.Column(db.Date(), nullable=False, default=date.fromisoformat('2099-12-31'))

エラー内容

console.log
marshmallow.exceptions.ValidationError: {'hoge_date': ['Field may not be null.']}

対処

schema.py
class HogeSchema(ma.SQLAlchemyAutoSchema):
    class Meta:
        model = Hoge

    # これを追加
    @pre_load
    def remove_has_defalt_key_if_none(self, in_data: dict, **kwargs):
        if in_data.get('hoge_date') is None:
            in_data.pop('hoge_date', None)
        return in_data
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

MacOS CatalinaにPythonとPython向けライブラリをインストールするまで

はじめに

Pythonを勉強するに当たって環境構築をしようとしたのだがこれが意外と難しかった。

MacにはデフォルトでPythonはインストールされているけれど、最新のversion3系統ではなく、古いversion2系統がインストールされているので、新しく開発するにはそのままできません。

しかもインストール方法もいくつもあって、どの方法でインストールすればいいのかPython初心者には分かりにくかったです。
さらに右も左もわからない状態だとPythonのインストール方法とライブラリのインストール方法と混同してしまって「あれ?今何やってたんだっけ?」となる場面が何回もありました。

Python勉強仲間に聞いても同じ悩みを抱えていたので、なら備忘録も兼ねて方法をまとめてみようと思って書いてみみました。

今回はMacOS CatalinaでHomebrewとpyenvを利用してPython3の最新版とゲームライブラリpygameをインストールしました。

実行環境

  • MacBookPro Mid 2014
  • macOS Catalina ver.10.15.16

使用するパッケージ

  • Homebrew

    • 言わずと知れたMacとLinux向けのパッケージ管理ツール。
  • pyenv

    • Pythonのバージョン管理ツール。 これを使わなくてもPythonのインストール自体はできるみたいですが、複数のバージョンをインストール&切り替えが容易なのでpyenvを利用してインストールする方が後々の使い勝手もよさそうなので今回はこれを使います。
  • pip

    • Python 用ライブラリの管理ツール。 各ライブラリのインストール作業はこれを使用します。Pythonをインストールすると一緒にインストールされるので特に導入作業は必要ありません。
  • pygame

    • Python向けのゲーム作成モジュール集。 これを利用するとPythonだけで割と簡単にゲームを作れます。実際Python初学者でも2日でゲームを作れました。Pythonを学習するに当たってこれを使ったゲームを作ったので、今回はこれを使ってライブラリをインストールする手順をまとめます。

※ 各パッケージの詳しい説明は各公式ドキュメントを参照して下さい。
※ 初めてのPython環境構築だと特にpyenvとpipを混同しやすいと思うので(実際私も散々苦労しました)、特にこの2つは意識的に区別しておくほうがいいと思います。

インストールの流れ

  1. Homebrewをインストール
  2. pyenvをインストール
  3. pyenvでPythonをインストール
  4. pipでライブラリをインストール

1.Homebrewをインストール

公式ドキュメントに従ってターミナルで以下のコマンドを実行します。もちろんインストール済みなら飛ばしても問題ありません。

$ /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install.sh)"

インストールが成功していればbrew -vでHomebrewのバージョンが確認できます。

$ brew -v
Homebrew 2.4.9
Homebrew/homebrew-core (git revision 3b87b; last commit 2020-08-04)
Homebrew/homebrew-cask (git revision 2ee9f; last commit 2020-08-04)

2.pyenvをインストール

brew updateでHomebrewを最新の状態にアップデートして、brew installでpyenvをインストールします。

$ brew update
$ brew install pyenv

pyenv -vでpyenvのバージョンが確認できればOKです。

$ pyenv -v
pyenv 1.2.20

pyenv自体はこれで動作しますが、ターミナルにpyenvの設定を追加しないとpyenv経由でインストールしたPythonが認識されないので、下記のコマンドでターミナルに設定を追加、追加した設定をターミナルに認識させます。

$ echo -e 'if command -v pyenv 1>/dev/null 2>&1; then\n  eval "$(pyenv init -)"\nfi' >> ~/.zshrc
$ source .zshrc

ターミナルがbashの場合は以下のコマンドで。

$ echo -e 'if command -v pyenv 1>/dev/null 2>&1; then\n  eval "$(pyenv init -)"\nfi' >> ~/.bash_profile
$ source .bash_profile

もちろんvimで直接プロファイル等に書き込んでも問題ありません。

if command -v pyenv 1>/dev/null 2>&1; then
  eval "$(pyenv init -)"
fi

3.pyenvでPythonをインストール

pyenv install -lコマンドで、pyenvでインストール可能なPythonのバージョンが確認できます。

$ pyenv install -l
Available versions:
  2.1.3
  2.2.3
  2.3.7
  2.4.0
  2.4.1
  2.4.2
  ...
  3.8.4
  3.8.5
  3.9.0b5
  3.9-dev
  3.10-dev
  ...

特に理由がない限り最新安定版(数字の後ろに'dev'とついていないもの)をインストールしておくほうがいいでしょう。
ちなみにanaconda等のプラットフォームもpyenvでインストールできます。
今回は3.8.5をpyenv installコマンドでインストールします。

$ pyenv install 3.8.5

この段階ではインストールが完了しただけで、使用するPythonのバージョンはまだ切り替わっていません。
python -Vコマンドでバージョンを確認しても、Macにデフォルトでインストールされているversion2系統が認識されます。

$ python -V
Python 2.7.16

pyenv globalコマンドでインストールしたPythonがデフォルトで動くように切り替えます。

$ pyenv global 3.8.5

python -Vでバージョンが切り替わったのが確認できればインストール成功です。
上手く認識しないときは$ source .zshrcでpyenvの設定をターミナルに再読み込みさせてみて下さい。
(※bashの場合は$ source .bash_profileで。)

$ python -V
Python 3.8.5

ちなみにpyenv versionsでインストールされているPythonのバージョンを一覧で確認できます。
先頭に*がついたものがデフォルトのバージョンとして動作します。

$ pyenv versions
  system
* 3.8.5 (set by /Users/linus/.pyenv/version)

4.pipでライブラリをインストール

pip installコマンドでライブラリをインストールします。今回はpygameをインストールします。

$ pip install pygame

今回は最新安定版ではなく開発中の最新版が必要なので、バージョンを指定してインストールします。
ライブラリ名の後ろにバージョンを付け加えるとバージョン指定でインストールできます。

$ pip install pygame==2.0.0.dev10

pip listコマンドでpipを使用してインストールしたライブラリを一覧で確認できます。

$ pip list
Package    Version
---------- -----------
pip        20.1.1
pygame     2.0.0.dev10
setuptools 47.1.0

指定したバージョンでインストールできてますね。
Djangoなどの他のライブラリも同じ方法でインストールできます。

おまけ

今回インストールしたパッケージ等をアンインストールときは以下のコマンドで実行できます。
アンインストールするときはインストールしたときとは逆順で削除しないとファイルが残ることがあるので注意して下さい。。

$ pip uninstall pygame
$ pyenv uninstall 3.8.5
$ brew uninstall pyenv

あとがき

初めて環境構築に取り組んでいたときも散々苦労しましたが、改めてまとめ直してみても結構大変でした。
Pythonはプログラミング初心者にもとっつきやすい言語だとよく聞きますが、環境構築はどうも初心者向けとは言い難いところがありますね。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

PythonでWEBスクレイピング(個人メモ用)

Pythonを独学し始めて2日目の私が簡単なWEBスクレイピングに挑戦しました。
いくつかのサイトを参考にして作成しました。
個人的なメモ用として投稿します。
今回は
・title
・h2
2つの要素を抽出します。

準備

・requestsモジュールをインストール

コマンド
pip install requests

・Beautiful Soupモジュールをインストール

コマンド
pip install beautifulsoup4

プログラム

コード
import requests
from bs4 import BeautifulSoup

# 取得したいURL
url = "*********"

# urlを引数に指定して、HTTPリクエストを送信してHTMLを取得
response = requests.get(url)

# 文字コードを自動でエンコーディング
response.encoding = response.apparent_encoding

# HTML解析
bs = BeautifulSoup(response.text, 'html.parser')
# titleを抽出
title_tag = bs.find('title')
print(title_tag.text)
# h2要素を抽出
h2_tags = bs.select('h2')
for h2_tag in h2_tags:
    print(h2_tag.text)

参考サイト

いつも隣にITのお仕事

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

GPUを3枚積んだマシンを自作していろんな計算(GPGPU)してるんですが、なんかマシンの性能がいまいちな気がしてて、「やっぱGPUの冷却が悪いせいで性能が出てないんじゃないのか?」と、わかったところで色々めんどくさいから普段は考えないようにしていたことについて、ある日勇気を出して調べてみたら案の定その通りで、「これじゃあ高いグラボ買った意味ないよなぁ」との結論を得てしまったので、重い腰をあげて思い切って水冷化してみたら爆速PCが爆誕したので、今回の過程を一応記録しておきます。

とりあえず最初に自作したGPUマシンがこちら(以下、"空冷マシン")。
_MG_0180.JPG
ASUS STRIX-GTX1080-A8G-GAMING(コアクロック: Base 1,670MHz /Boost 1,809MHz)を3枚積んで、無駄にでかいCPUクーラーまで積んでます。この時点で、外排気のGPUにしろよと言われそうですが、そんなことは買ったときは知らなかったのです。内排気のGPUを3枚も隙間なく重ねたことによって今回の熱問題が発生してしまっていることは否めないでしょう。ってことでGPUを複数枚ケース内に収めようと思っている人は、少なくとも外排気のGPUを購入したほうがよいでしょう。

GPUの温度測定

https://proc-cpuinfo.fixstars.com/2017/10/gpu-temperature/
を参考に、温度計測を行いました。
cuBLASのSGEMMをひたすら回して(main.cu)、その時の温度をpython(watchGPU.py)で出力していきます。

watchGPU.py
# -*- coding: utf-8 -*-
import sys
import time
from datetime import datetime
from py3nvml.py3nvml import *

class Device:

    def __init__(self, device_id):
        self.__device = nvmlDeviceGetHandleByIndex(device_id)

    def temperature(self):
        return nvmlDeviceGetTemperature(self.__device, NVML_TEMPERATURE_GPU)

    def graphics_clock(self):
        return nvmlDeviceGetClockInfo(self.__device, NVML_CLOCK_GRAPHICS)

    def sm_clock(self):
        return nvmlDeviceGetClockInfo(self.__device, NVML_CLOCK_SM)

    def memory_clock(self):
        return nvmlDeviceGetClockInfo(self.__device, NVML_CLOCK_MEM)

    def fan_speed(self):
        return nvmlDeviceGetFanSpeed(self.__device)

    def power_usage(self):
        return nvmlDeviceGetPowerUsage(self.__device) * 1e-3


def main():
    nvmlInit()
    device0 = Device(0)
    device1 = Device(1)
    device2 = Device(2)
    while True:
        print('{:.0f} : {}C, {}MHz, {}MHz, {}%, {:.0f}W : {}C, {}MHz, {}MHz, {}%, {:.0f}W : {}C, {}MHz, {}MHz, {}%, {:.0f}W'.format(
            datetime.now().timestamp(),
            device0.temperature(),
            device0.sm_clock(),
            device0.memory_clock(),
            device0.fan_speed(),
            device0.power_usage(),
            device1.temperature(),
            device1.sm_clock(),
            device1.memory_clock(),
            device1.fan_speed(),
            device1.power_usage(),
            device2.temperature(),
            device2.sm_clock(),
            device2.memory_clock(),
            device2.fan_speed(),
            device2.power_usage()))
        time.sleep(1.0)
    nvmlShutdown()

if __name__ == '__main__':
    main()
sgemm.cu
#include <cstdio>
#include <chrono>
#include <time.h>
#include <cublas_v2.h>
#include <thrust/device_vector.h>

inline double get_current_epoch(){
    timespec tp;
    clock_gettime(CLOCK_REALTIME, &tp);
    return tp.tv_sec + tp.tv_nsec * 1e-9;
}

int main(int argc, char *argv[]){
    namespace chrono = std::chrono;
    using duration_type = chrono::duration<double>;
    const int n = 8192;

    if(argc < 2){
        printf("Usage: %s device-id\n", argv[0]);
        return 0;
    }
    cudaSetDevice(atoi(argv[1]));

    cublasHandle_t handle;
    cublasCreate(&handle);

    const float alpha = 1.0f, beta = 0.0f;
    thrust::device_vector<float> A(n * n), B(n * n), C(n * n);
    while(true){
        const auto start = chrono::steady_clock::now();
        cublasSgemm(
            handle, CUBLAS_OP_N, CUBLAS_OP_N,
            n, n, n,
            &alpha,
            A.data().get(), n,
            B.data().get(), n,
            &beta,
            C.data().get(), n);
        cudaDeviceSynchronize();
        const auto stop = chrono::steady_clock::now();
        const auto duration = chrono::duration_cast<duration_type>(stop - start);
        const auto flops = (2.0 * n * n * n) / duration.count();
        const auto timestamp = get_current_epoch();
        // printf("%.9f\t%.3f\n", timestamp, flops * 1e-9);
    }

    cublasDestroy(handle);
    return 0;
}

ファイルを準備できたらコンパイルして実行する。

$ nvcc -lcublas -o sgemm sgemm.cu
$ pip install py3nvml
$ ./sgemm 0 & ./sgemm 1 & ./sgemm 2 &
$ python watchGPU.py

測定結果(空冷マシン)

gpu01_graph.jpg

上からGPUの温度、クロック数、電力です。

①で示したところで一番上のGPUの温度が82℃に達し、出力が押さえられてクロック数が1,670MHzに減少します。といってもbaseクロックのスペック値がこの値なので、まぁ正常というところですが。その後②のところで真ん中のGPUの温度も82℃に達し、クロック数が1,670MHzとなります。さらに時間が立つと③のところで一番上のGPUの温度が93℃に達し、リミッターが発動するのか、出力が更に低下して不安定になり、それに伴ってクロック数も同様に低下して不安定になります。今回は30分弱で測定を終えましたが、さらに長時間の計算になると真ん中のGPUもリミッターが発動していた可能性が高いです。ちなみに、一番下のGPUは温度が67℃で1,898MHzを最後までキープしていました。

一番上と真ん中のGPUは吸気に十分な隙間がないことと、上に行くに従って下のGPUからの排熱が影響するので、GPUの冷却が十分に行われずリミッターが発動する温度まで上昇したと考えられます。一枚でもこのような状況になるとそれが足を引っ張って全体の計算時間を遅くしてしまうので、これではよくありません。

水冷化

ということで水冷化することで改善を目指します。

水冷パーツは怪しげな中華製パーツをAmazonで購入することで低価格を実現しています。あとせっかくなのでCPUも水冷化しました。

これを、
_MG_0182.JPG
こうして、
_MG_0186.JPG
こうだ!
_MG_0187.JPG
VRAMやVRMはヒートシンクをつけて空冷です。

水冷マシンとして生まれ変わった姿がこちら。
_MG_0190.JPG
チューブやフィッティングも格安のものを選定し、リザーバーはそのへんに落ちていたアクリルのケースに穴を開けて代用することで、トータルで3万円を大幅に下回る金額で水冷化を実現できました。いい時代になったもんです。

測定結果(水冷マシン)

gpu01_WC_graph.jpg

一番上のGPUで、最高温度58℃でサチっており、クロック数も1,911MHzと空冷のときに比べて劇的な改善を見せました。Boost時のスペック値1,809MHzを大幅に上回っています。10分強の測定ですが、さらに長時間の計算になってもこれ以上温度は上がらなさそうです。一番上のGPUが少し温度が高いのは下のGPUからの排熱と、水路を直列につないでいることによると思われます。

結論

やはりGPUを3枚密集させていたことでGPUの温度が上がり本来の性能が発揮されていなかったことがわかりました。水冷化することによって劇的な改善がなされ、なんとスペック値を大きく上回る爆速PCが爆誕しました。ただし、水漏れ=死を意味するため、水漏れの恐怖とは常に戦っていかなければなりません。ケースに収めることにとらわれず、ライザーカードを使ったマイニングPCのようなラック運用が心臓には良さそうです。

参考

https://proc-cpuinfo.fixstars.com/2017/10/gpu-temperature/
https://chimolog.co/bto-gpu-fan-types/

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

"Rethinking Softmax Cross-Entropy Loss for Adversarial Robustness (ICLR2020)"の解説とPytorchによる実装 

ICLR2020においてposter発表された、"Rethinking Softmax Cross-Entropy Loss for Adversarial Robustness" 1の解説と実装を行っていきたいと思います!
この論文は、著者の前の論文"Max-Mahalanobis linear discriminant analysis networks"(ICML2018) 2の進化版となっています。

pytorchによる実装はgithub4に載せてあります。

論文の要旨

  • 画像分類タスクにおいて用いられるCrossEntropyLossの代わりとして新たにMax-Mahalanobis Center(MMC)Lossを定義
  • クラスごとにあらかじめ設計されたベクトルに特徴ベクトルが近づくように、モデルを学習させる
  • 敵対的サンプル(AE:Adversarial Examples)に対するロバスト性が大幅に向上!

何がすごい?

  • AEに対する脆弱性が課題とされる中、モデルのclassifierの部分(feature map以降の部分)に注目した論文は少ない
  • 数学的理論に基づいて、しっかり考えられたロス関数である(数学的な分析自体がとても有益)
  • 計算量はほとんど変えずに済む
  • 実装が難しくない

解説

以下、論文についてざっくり解説をしていきます。

MMC Loss (Max-Mahalanobis Center Loss)とは?

まずよく用いられる、SoftmaxCrossEntropyロスは以下のように表されます。
スクリーンショット 2020-08-05 1.23.06.png
特徴ベクトルは、Linear層を通ったのちにSoftmax関数によって合計1に変更され、正解ラベルに対応する値の対数の負をとったものがロスとなります。
x,yはそれぞれinput,labelであり、z=Z(x)は特徴ベクトルです。

一方、MMCは以下のようになります。
スクリーンショット 2020-08-05 1.34.58.png

非常にシンプルなロス関数ですね。
特徴ベクトルをいきなり、あるベクトルμと比較して二乗誤差をとっています。

ここで、あるベクトルμとは何者でしょう。

論文には、
スクリーンショット 2020-08-05 1.35.55.png
と書いてあり、「MMDの中心ベクトル」と言っています。

このベクトルが、「あらかじめ設計しておくベクトル」であり、特徴ベクトルが正解ラベルに対応するベクトルμ_yに近くなるようにモデルを学習させます。

このベクトルμが、この論文のカギであり、全てです。

あらかじめ設計しておくベクトルμとは? → Max-Mahalanobis Distribution (MMD)

μは、「Max-Mahalanobis Distribution(MMD)の中心」とあります。

以下の画像は、クラス数L=2,3,4の場合におけるMMDの中心位置を立体的に図示したものです。
スクリーンショット 2020-08-05 1.39.28.png

ざっくりいうと、このようにしてクラス間分布の距離がそれぞれで最大になるように特徴ベクトルを設計するのです。

Max-Mahalanobis Distribution(MMD)のざっくりとした数学的理論

ここで、数学的に説明されている理論について軽く解説していきます。

難しいので、興味がない人は読み飛ばしましょう。

<前提>
各クラスの分布が、混合ガウス分布になっていると仮定する。

この仮定は以下で表される。
スクリーンショット 2020-08-05 2.00.24.png
スクリーンショット 2020-08-05 2.02.55.pngであり、共分散行列Σは全クラスで共通していると仮定する。

<目的>
クラスごとのガウス分布のマハラノビス距離を最大化したい。

前提に基づけば、クラスi、jの分布のマハラノビス距離は以下の式によって表すことができる。
スクリーンショット 2020-08-05 2.07.11.png

<手法>
クラスi,jからのサンプルxi,xjの距離の期待値を最大化する問題を解く。

まず、この問題を特に当たって問題を標準形に変換する。
共分散行列Σは、これをnonsingularだとすればコレスキー分解によって、
スクリーンショット 2020-08-05 2.37.14.png
と下三角行列Qに分解することができる。このQを用いて、
スクリーンショット 2020-08-05 2.38.56.png
という線形変換を行うことで、問題設定は以下の標準形になる。
スクリーンショット 2020-08-05 2.40.28.png
この変換では、クラス間のマハラノビス距離は不変となっている。

この設定の元で、さらにクラスi,jの出現確率πが等しいと仮定する。
このクラスi,jのマハラノビス距離の期待値は、
スクリーンショット 2020-08-05 2.44.35.png
と計算できる。(証明は論文へ2

ここで、分類器のロバストネスRBを以下のように定義した時、
スクリーンショット 2020-08-05 2.48.58.png
RBをどうにかして近似したRBバーは、次の上限をもつ。(証明は論文へ2
スクリーンショット 2020-08-05 2.49.53.png (なお、 スクリーンショット 2020-08-05 3.12.05.png

そしてこの式における等号条件は、以下の式で表される。
スクリーンショット 2020-08-05 2.54.34.png

<MMDを計算する>
等号条件を用いて、クラスごとのMMDの中心を計算する。

コレスキー分解を考える。この記事3を見るとわかりやすいかと思う。

\mu = (\mu_0, \mu_1, ... \mu_L )^T \\

を求めるに当たって、μをコレスキー分解して考えると、等号条件を用いてμを逐次的に計算していくことができる。

実装

以下、実際に実装してみたので紹介します。

MMD(=あらかじめ設計しておくベクトル)の計算

def generate_opt_means(C, p, L): 
    """
    input
        C = constant value
        p = dimention of feature vector
        L = class number
    output
        MMD (shape=(L,p))
    """
    opt_means = np.zeros((L, p))
    opt_means[0][0] = 1
    for i in range(1,L):
        for j in range(i): 
            opt_means[i][j] = - (1/(L-1) + np.dot(opt_means[i],opt_means[j])) / opt_means[j][j]
        opt_means[i][i] = np.sqrt(1 - np.linalg.norm(opt_means[i])**2)
    for k in range(L):
        opt_means[k] = C * opt_means[k]

    return opt_means

ここでは、前述した数学的理論の部分より導出された式によってMMDを求めています。
実際に出てきた等号条件をコレスキー分解の式に代入してみるとわかると思います。

MM_LDAレイヤーの実装

class MM_LDA(nn.Module):
    def __init__(self, C, n_dense, class_num, device, Normalize=False):
        super().__init__()
        self.C = C #hyperparam for MMD
        self.class_num = class_num
        opt_means = generate_opt_means(C, n_dense, class_num)
        self.mean_expand = torch.tensor(opt_means).unsqueeze(0).double().to(device) # (1, num_class, num_dense)
        self.Normalize = Normalize

    def forward(self, x):
        b, p = x.shape # batch_size, num_dense
        L = self.class_num
        if self.Normalize: # 正規化する
            x = (x / (torch.norm(x, p=2, dim=1, keepdim=True) + 1e-10)) * self.C

        x_expand =  x.repeat(1,L).view(b, L, p).double() # (batch_size, num_class, num_dense)

        logits = - torch.sum((x_expand - self.mean_expand)**2, dim=2) # (batch_size, num_class)

        return logits

CNN層から出力されるfeature mapは、Linear層によってfeatureベクトルとなります。
そのfeatureベクトルをinputとして、それと、あらかじめ用意したMMDの「差」を計算するのがMM_LDA層です。
差は二乗誤差を計算しています。

loss計算

class dot_loss(nn.Module):
    def __init__(self):
        super(dot_loss, self).__init__()

    def forward(self, y_pred, y_true):
        y_true = F.one_hot(y_true, num_classes=y_pred.size(1)).double()
        loss = - torch.sum(y_pred * y_true, dim=1) #batch_size X 1
        return loss.mean()

MM_LDA層からの出力logitsは、(batch_size, num_class)の形をしています。
その出力のうち、正解ラベルに該当する値をLossとして取ります。

したがって例えば、ミニバッチのうちの1つ目のデータのラベルが5、2つ目のデータのラベルが3の場合は、

Loss = logits[0][5] + logits[1][3] + ...

となります。

ここでMM_LDA層からの出力(logits)はMMDとの近さを表すので、「特徴ベクトルが、正解ラベルのMMDに近くなるように」Lossをとっているということです。

実験

今回、実際にAEに対してロバストになるか簡単な実験しました。

比較内容

ベースモデル:ResNet34
比較分類器:SoftmaxCrossEntropy(SCE)Loss, MMC
比較攻撃手法:なし, PGD, FGSM

SoftmaxCrossEntropy(SCE)Lossは従来のクロスエントロピーロスによる分類を指し、
MMCが本論文1で2020に提案された、論文2の修正版です。

敵対的サンプルAEの生成方法として、PGD,FGSMを試しました。

結果

モデル Clean PGD FGSM
SCE 86.54 41.85 14.21
MMC 80.68 76.94 77.05

単位はパーセント[%]です。
論文で用いられたハイパーパラメータが全てはわからなかったので論文とは正確な数値は異なりますが、明らかにロバスト性が向上していることがわかります!

複雑な実装をせずに、精度が向上しているという結果は非常に喜ばしい結果と言えます。

(論文では通常画像に対する精度が90%以上まで学習されていたので、そこまで上がるとまた結果はずれてくると思います。)

終わり

ここまで読んでいただきありがとうございました!

理論を完全に理解できたわけでもなく、また実装においてミスがあるかもしれませんが、参考になれば幸いです。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

pythonの基礎: 条件と繰り返し

次は条件や繰り返しについて

if文

日本語でもしという意味
プログラミングに置いてかなり重要な位置になります

# フォーマット
if # 第一条件

elif # 第二〜n条件

else # 第n条件まで以外
# 使用例
#条件の後の「:」と、出力のインデントを忘れないように

n = 3
if n == 1: 
    print("1番処理") 
elif n == 2:
    print("2番処理") 
elif n == 3: 
    print("3番処理") 
else: # 上記条件式が全て成立しない場合
    print("上記以外の処理")

# 出力: 3番処理

比較演算子

基本条件嵌ればtrue
出なければfalsaを返します。

コード 内容
a==b 等しい
a!=b 等しくない
a>b aはbより大きい
a>=b aはbと同じかそれ以上
a<b aはbより小さい
a<=b aはbと同じかそれ以下

ブール演算子(and・or・not)

A and B # A、B両方の条件式成立
A or B # A、Bどちらかの条件式成立
not 条件式 # 結果の反転
使用例
A = 1
B = 2

print(A==1 and B==2)
# true

print(not B < A)
# true

while文

条件成立中繰り返す処理

while
n = 5
while n >2: # nが0より大きい場合、下記の処理を行う
    print(n)
    n -= 2 # nを-1する

# 出力結果 5 3

while+if文

x = 5
while x != 0:
    x -= 1
    if x != 0:
        print(x)
    else:
        print("end")

for文

リストについては後ほど投稿で
変数に複数入っている、内容を順次行って行きます。

moji = ["A", "B", "C"]
for ji in moji: # animalsに含まれる要素の数=3回処理を繰り返す
    print(ji)
# 出力結果
A
B
C

break

繰り返しの終了

break
li = [1, 2, 3]
for n in li:
    print(n)
    if n >= 3: 
        print("3以上確認")
        break # for文処理終了

continue

処理をスキップしたい場合に使用

continue
li = [10, 20, 30, 40] # storagesに含まれる要素の数=6回処理を繰り返す
for n in li:
    if n < 30: #nが30より小さい場合、処理を行わない(スキップする)
        continue
    print(n)

# 出力結果
3
4
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

pythonの基礎: 出力編

思うところがあったので内容は改造して
再投稿しています。

基本

出力

print("Hello World")
#  文字列は""か''で囲む必要あり

コメントアウト

# 一行コメント

"""
複数行
コメントアウト
"""

計算

数式 コード
足し算 +
引き算 -
掛け算 *
割り算 /
割った余り %
乗算 **

変数

n=1
print(n)
# 出力: 1
print(n+2)
# 出力: 3

使える変数名

① 半角アルファベット(大文字、小文字)
② 半角数字
③ _(アンダースコア)

注意点

①先頭文字に数字不可
②printなどの関数名不可
③予約後(forなどのコード)不可
④日本語は好まれない

削除

動作後の都合による削除

del 変数名

型と連結

出力のさい
int型(数字)
str型(文字列)
などは混ぜて出力できないので
分けるか、変換して出力する

n =1 

print("これは"+n)
# エラー
print("これは"+str(n))
# 出力: これは1
print(1+n)
# 出力: 2

型を知りたい時

print(type(変数))
age = 20
print(type(age))
# 出力: <class 'int'>

型の変換

コード 内容
str() 文字列
int() 整数値
float() 小数点込み
  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

GPSマルチユニットSORACOM Edition で位置情報(Googleマップ)をLINEに通知する

やったこと

GPSマルチユニットSORACOM Editionのデータを、SORACOM Funk経由でAWS Lambdaに送り、位置情報をLINE Notifyを使用して通知する。位置情報はGoogleマップのリンクで。使用する言語は、Python。

GPS マルチユニット SORACOM Edition とは

以下、公式サイトより引用

GPS マルチユニット SORACOM Editionは、「位置情報(GPS)」「温度」「湿度」「加速度」の4つのセンサーと充電式バッテリーを内蔵し、 セルラーLPWAであるLTE-M通信がご利用可能なデバイスです。

詳細については、以下を参照ください。
(公式)GPS マルチユニット SORACOM Edition とは
GPSマルチユニット SORACOM Editionで遊ぶ

SORACOM Funkとは

クラウドサービスの Function を直接実行できるサービスです。
今回は、AWS Lambdaを実行します。

以下参照ください
(公式)SORACOM Funk とは
SORACOM Funkを使ってみた。

LINE Notifyとは

以下、公式サイトより

Webサービスからの通知をLINEで受信
Webサービスと連携すると、LINEが提供する公式アカウント"LINE Notify"から通知が届きます。
複数のサービスと連携でき、グループでも通知を受信することが可能です。

以下参照
Python で LINE にメッセージを送信(LINE Notify)

AWS LambdaでLINE Notifyを呼び出す

SORACOM、AWS Lambda、LINE Notifyの設定については、省略します。

以下を AWS Lambdaに。
Python 3.6
時刻も通知してます。

lambda_function.py
import os
import requests
import datetime

def lambda_handler(event, context):
    lat = event['lat']     #緯度
    lon = event['lon']     #経度

# 現在日時を取得(日本時間)
    now = datetime.datetime.now(datetime.timezone(datetime.timedelta(hours=9))) 

# 位置情報が取得できない場合
    if lat == None or lon == None:
      msg = now.strftime('%Y-%m-%d') + " " + now.strftime('%H:%M:%S') + " " + "位置情報を取得できませんでした"
      line_notify(msg)
      return

# Google マップで表示
    mapurl = "https://maps.google.co.jp/maps?q=" + str(lat) + "," + str(lon)  # google map用
    msg = now.strftime('%Y-%m-%d') + " " + now.strftime('%H:%M:%S') + " " +  "現在地はここです" + " " + mapurl
    line_notify(msg)

# LINE Notifyに通知
def line_notify(msg):
    url = "https://notify-api.line.me/api/notify"
    headers = {"Authorization" : "Bearer "+ "<LINEのTOKENを設定>"}
    data = {"message" : msg}
    s3 = requests.Session()
    r3 = s3.post(url, data=data, headers=headers)

結果

IMG_2719.jpg
※文字列[SORACOM GPS]は、LINE Notify内で設定

位置情報が取得できない場合は以下

IMG_2720.jpg

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

2020年における各Python処理系の状況

2020年1月1日をもってPython2系列のサポートが終了しました(一部の長期サポート環境を除く)。Pythonは完全にPython3時代に移行し、安定期を迎えているように思います。しかしながら、Pythonは何もCPythonだけではありません。JythonやIronPythonといった他の処理系の現状はいったいどうなっているのでしょうか。気になったので少しだけ調べてみました。

CPython

python-logo.png

公式サイト
リポジトリ

言わずと知れた、オリジナルにして最も有名Python処理系です。C言語で実装されています。

2020年1月1日にPython2系列のサポート終了(EOL)を行いました。
2020年7月21日には最新バージョンの3.8.5が公開されました。その他3.7系列では3.7.8が、3.6系列では3.6.11がそれぞれ6月28日にリリースされています。
そして、次期バージョンの3.9.0が現在最終ベータ版(b5)となっており、この後約2ヵ月程度のRC(Release Candidate)を経て、10月5日にリリースされる予定となっています(PEP596)。
3.9の新機能が気になる方はこちらへ ⇒ Python3.9の新機能 (まとめ)

PyPy

bitmap.png

公式サイト
リポジトリ

大半がPure Pythonで実装されたPython処理系で、JIT(Just In Time)コンパイラによりCPythonより高速に動作するケースが多いのが特徴です(どんな場合でも速いわけではない)。

最新版は2020年4月5日にリリースされたバージョン7.3.1です。CPython3.6相当とCPython2.7相当の2バージョンが公開されています。現在の動向としてはCPython3.7相当の開発ブランチが切られて開発が続けられていますが、リリースについては未定です。

Jython

jython.png

公式サイト
リポジトリ

Javaで実装され、JDK等のクラスを使用することができるPython処理系です。

2015年3月にCPython2.7相当のバージョン2.7.0がリリースされ、2020年3月21日にバージョン2.7.2に更新されています。
しかし、バージョン3系列への対応については、専用リポジトリが用意されているものの、ここ3年ほどコミットがない状態が続いています。主要コントリビュータのJeff Allen氏は、Python3の新たな機能への対応と、古くなったJython実装を考慮して新たな設計・新たな実装を行う必要があるとして、The Very Slow Jython Projectを立ち上げ、課題を整理しようと試みています。その名前が示す通り、これは時間のかかる試みになると考えられています。

Graal Python

graal.png

リポジトリ

GraalVMというJava VM上で動作する新興のPython処理系です。Python3.7の文法が使用できること、SciPyとその関連するライブラリを使用できることを目標に掲げています。現時点ではexperimantalであると明記されています。また、Jythonとの互換性も考慮しているそうです。
2020年3月20日にGraalVM 20に対応したバージョン20.1.0が、2020年8月5日にGraalVM 19に対応したバージョン19.3.3がリリースされています。Python3.8.2相当の文法を実装しているということです。
JVMで動作するのでJITが働き、CPythonやJPythonよりも高速であるという情報もあります。今後の発展に期待したい処理系です。

IronPython

ironpython.png

公式サイト
リポジトリ

C#で実装され、.NET Frameworkのライブラリを使用することのできるPython処理系です。

最新版は2020年4月27日にリリースされたバージョン2.7.10です。CPython2.7相当の機能に対応しています。
バージョン3系列への対応については専用のリポジトリが作成されていますが、「まだ使える段階にはない」とはっきり記述されています。issueにPython3の新機能リストが列挙されていますが、作業量があまりに膨大でリリースまでの道のりは依然遠いと考えられます。

Brython

brython.png

公式サイト
リポジトリ

JavascriptによるPython処理系で、ブラウザ上でPythonコードを実行させることができます。インタプリタ(brython.js)のサイズは約700KBです(ライブラリは別)。

最新版は2020年3月20日にバージョン3.8.9がリリースされていて、これはCPythonの3.8相当の機能を実装しています(筆者環境にてセイウチ演算子の動作は確認済み)。
本家(CPython)への追従スピードも速く、安定してコミットが行われており、勢いのあるPython処理系プロジェクトと言えます。

MicroPython

micropython.png

公式サイト
リポジトリ

組み込み環境で動かすことを目的としたPythonのサブセット実装です。最小構成では128KBのROMと8KBのRAMで動作するとされており、ESP32搭載のボードや専用のpyboard上で動作させることができます。PIC16やJavascriptへのポートもあります。

最新版は2019年12月20日にリリースされたバージョン1.12です。これはCPython3.4相当の機能に加え、3.5の機能の一部(async/await)を追加したものです。様々なアーキテクチャやペリフェラルへの対応について膨大な数のissueが寄せられており、活発な活動が続けられています。

Numba

bitmap.png

公式サイト
リポジトリ

NumbaはPythonコードを高速化するためのJITコンパイラです。特にNumPyの配列や関数を使ったコードに対しての最適化が考慮されています。

最新版は2020年6月24日にリリースされたバージョン0.50.1です。CPythonは3.6~3.8に対応、NumPyは1.15~1.18に対応しています。オープンなissueは1000件を超えており、プロジェクトに対する人々の期待の高さが伺えます(そして人的リソースの足りなさも)。平均して毎週4~50程度のコミットが行われており、非常に活発な処理系であると言えます。

おわりに

メジャーどころの処理系は速度の違いはありますが、いずれも開発は継続されているようです。JythonのPython3対応はやや厳しい状況にあるようですが。

いろいろな処理系がありますが、本家の開発がものすごいスピードで進むので、他の処理系はそれに対応するのに結構リソースを割かれている現状が垣間見えます。そのうえで処理系独自の特色を磨き上げていかなければならないので、開発者の皆さんは本当にお疲れ様ですという気持ちです。

他におもしろい処理系をご存知の方はコメントで教えていただけると嬉しいです。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む