サブロウ丸

主にプログラミングと数学

【Matlab】 ビルトイン関数を表示する

Matlabでビルトイン関数(標準関数)は edit 関数名 で表示できます。 こんな感じ。

Newtonの差分商補間(後編)

inarizuuuushi.hatenablog.com これの後編です。 実際に簡単な関数でいくつか補間による近似を行なってみたいと思います。 fが近似したい関数、gがデータ点(0, 0) (1, 1) (2, 2)から構成した差分商補間になります。 fは2次式でかつ、前編の最後の定理「剰余…

Newtonの差分商補間(前編)

Newtonの差分商補間の理論についてです。内容は高校レベルでしょうか。 最後の定理は強力ですね。 補間といえば、他にはLagrange補間が有名ですが、 Lagrange補間よりも計算量が少ないことが特徴です。 一番最後の証明は、「n点を補間するn-1次の多項式はLag…

PythonユーザーのためのMatlab対応表

PythonユーザーのためのMatlab対応表を作っていこうと思います。 Matlabのドキュメントは初心者殺しっぽいところがありますよね… 徐々に増やしていく予定です。 list 宣言・要素の追加 python a = [1, 2] a.append(3) # a = [1, 2, 3] a.append(4) # a = [1,…

線形計画問題における、とある条件を持つバイナリ変数の表現方法について - その2

この記事の続きです。 inarizuuuushi.hatenablog.com この記事の中で2通りの方法を載せていますが、どちらの方が良いか調べてみたのでその報告です。 上の問題を解きます。 それぞれ制約の入れ方は 以前の記事では、2つ目のパターンでは分数の形で記述してい…

brewでpython3をupgradeするとpip3が使えなくなった件

件名がルー大柴みたいになってしまいました。 python3.6.2にupgradeすると、なぜかpip3が使えなくなってしまいました。 $ pip3 -bash: pip3: command not found 一旦brew uninstall --ignore-dependencies python3 でpython3をアンインストールした後で もう…

opencv3.3.0 インストール エラー

brewにてopencv3のupgradeがあったのですが homebrew/science/opencv3 3.3.0_1 ==> Upgrading homebrew/science/opencv3 --with-python3 ==> Downloading https://github.com/opencv/opencv/archive/3.3.0.tar.gz Already downloaded: /Users/tateiwanariaki…

python pulp 変数和

pulpです。 変数の和を表現するときにsumよりもlpSumを使った方が高速にプログラムが動くという話です。 この簡単な最小化問題を例に。aは定数、bは実変数です。 import pulp from random import randint # A new Lp problem prob = pulp.LpProblem('sample'…

線形計画問題における、とある条件を持つバイナリ変数の表現方法について

最近、線形計画問題に取り組んでいまして、以下のようなバイナリ変数xを定義する必要が出てきました。 バイナリ変数とは0と1の2値のみをとり得る変数のことです。 これがなかなか難しくて、いろいろ調べてみて、 2通りの定式化を行いました。 1つ目は以下の…

【Mac】パスワード付きzipファイルの作成

パスワード付きのzipファイルをコマンドライン上(ターミナル)で作成する方法です。 文法は zip -e (圧縮後ファイル名) (圧縮対象のファイルパス) あとは指示に従うだけです。 $ zip -e sample.zip sample.txt Enter password: (パスワードを入力) Verify pas…

【Matlab】【Python】ディレクトリ内のファイルに対し反復処理を行う

python from glob import glob files = glob('パス名'); for file_name in files: pass file_nameにはファイルパスが代入されます。 matlab files = dir('パス名’) numfiles = length(files); for i =1:numfiles file = files(i); file_name = file.name; fo…

Hornerの公式

Hornerの公式という多項式の計算を高速に行う方法があります。 と言っても仕組みは簡単で以下のような式変形を行うだけです。 単純に項ごとを足し合わせるよりも、掛け算の回数が減っていることが分かりますね。 計算量はそれぞれ となっています。 実験 # P…

homebrew でインストールできるモジュール

typespeed タイピングゲームが楽しめます tldr (too long, don’t read)の略で manコマンドを簡潔にしたコマンドです。 man は長すぎるので「tldr」

最短路問題を線形計画法で解く2

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回も線形計画法で解いてみたいと思います。(あえてね) が定式化となります。(とするとが続いているところは無視してください) 路の制約として、フロー整合条件を使用しました。 この定式化で…

最短路問題を線形計画法で解く (Python)

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回は線形計画法で解いてみたいと思います。(あえてね) 定式化は こうなります。 最短路を解く問題なのに目的関数が最大化になっているところが面白いですね。 ad(j)については、jの隣接ノード…

AppleScript で Excelでグラフ描写と保存を自動化

どーしても、Excelでグラフを大量に作成したいときには AppleScriptで書かせましょう。 (サンプルコード) tell application "Finder" --theListにファイルパスのリストを代入 set theList to {"ファイルパス,ファイルパス,....."} --for文 repeat with file_…

最短路計算における、楕円を用いたグラフの枝刈り

上記のグラフのstartからgoalまでの最短路を求めたいとします。 (グラフの枝の重みは枝の長さ) 直感的には、startとgoalから離れた点や枝を考える必要はない(i.e.最短路にそれらの点や枝が含まれることがない)ように思えますが、 それをどう厳密に表現するか…

Mac MobileBackups

Mac book air のストレージ容量が溜まってきたなーと思ったので、 sudo du -sh /* で、ルート下のディレクトリについてその容量を計算させてみると (オプション-sは「ファイルやディレクトリの総計を表示する」、-hは「容量を適当な単位で表示する」という意…

brew cleanup

brew cleanup homebrewでインストールしたパッケージの古いバージョンのキャッシュの削除を行います。 容量整理に

【Python】 newton法(非線形計画)

newton法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 関数fと勾配、初期点を問題に合わせて入力する必要があります。

【Python】 最急降下法(非線形計画)

最急降下法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 目的関数fと勾配、初期点を問題に合わせて入力する必要があります。

Java charのインクリメント

アルファベットが1文字ずつ入った配列の作り方です。 class Sample{ public static void main(String []args){ char []alphabet = new char[26]; char c = 'a'; for (int i = 0; i < 26; i++){ alphabet[i] = c++; } } } charクラスのオブジェクトにもインク…

Pulp Overwriting previously set objective エラー

Pythonの線形計画法ソルバーライブラリであるpulpを使っていると、突然以下のエラーが。 warnings.warn("Overwriting previously set objective.") 目的関数を上書きしているぞ、との警告のようですが身に覚えがなかったので、調べていくと、 a = [変数 for …

三角形の合同条件と、それに対応する面積公式

ある二つの三角形について、その形と大きさが等しいとき、それらは「合同である」と言います。 この合同についてみなさん、中学校で以下の三つの合同条件を習ったと思います。 ・三辺相等 ・二辺狭角相等 ・二角狭辺相等 例えば三辺相等について、 三角形の…

対称グラフの完全マッチング数について

完全マッチングについて面白い定理を見つけたので、ご紹介します。 まず、完全マッチングについて、 グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング…

【Mac】 jad を homebrew からインストールする

jad を使えば、javaのclassファイルのデコンパイル(コンパイルをする前のソースコードを復元すること)ができます。 homebrewを使ってインストールするには brew tap caskroom/cask brew install caskroom/cask/jad を実行してやれば良いです。 homebrew/bina…

Java 配列をクラスオブジェクトの要素に

いつもはPythonの記事ばかり書いていますが、今回はJavaです。 Javaで、整数と配列と二次元配列の3つを一度に返す関数を作りたかったのですが、 Javaの関数は基本的に返り値が一つだけなので、 関数の返り値を保存するためだけのクラスを作ることにしました…

フロー分解

以下のグラフのフロー分解を考えます。 まず、フローとは何かという話ですが、 始点(図s)から終点に(図t)に水を流すことを考えます。 そのときの"水の流れ"のことをフローと呼びますが、それにはいくつか条件があります。 図のノード(丸)とノードを結ぶ矢印…

劣モジュラ2

今回は Chapter2 劣モジュラ最適化の基礎 2.4 列もジュラ最適化と多様体の 貪欲解の最適性についてです。 ラグランジュ緩和については以下のPDFが分かりやすくまとまっていると思います。 http://www.bunkyo.ac.jp/~nemoto/lecture/opt-model/2008/duality1-…

劣モジュラ1

「劣モジュラ最適化と機械学習」という河原先生と永野先生が書かれた本を最近勉強しています。 https://www.amazon.co.jp/劣モジュラ最適化と機械学習-機械学習プロフェッショナルシリーズ-河原-吉伸/dp/4061529099/ref=sr_1_fkmr0_1?ie=UTF8&qid=1492411085…

Python 要素1のタプルの宣言

要素が一つのタプルを作りたいときに a = (1) としても, >>> a 1 >>> type(a) <class 'int'> でaは整数型になっていることが分かります。 じゃあ、どうすればいいかというと a = (1, ) もしくは a = 1, としてやれば、いいです。 なんか気持ち悪いですね。</class>

Python 数独を解く

pythonのpulpモジュールを用いて、数独を線形計画法で解きます。 pulpはpip3 install pulpでインストールできます。

Python multiprocessingで並列処理

pythonの標準モジュールmultiprocessingを使用すれば、並列処理を行うことができます。 Pool map 基本的な使い方は from multiprocessing import Pool with Pool(processes=None) as pool: pool.map(func, iter) Poolの引数であるprocessesには並列処理に使…

Python ジェネレーター内包表記

普通にリストの内包表記の感覚でタプルの内包表記を書こうとすると a = (i for i in range(10)) type(a) > <class 'generator'> と、ジェネレータが作成されてしまいます。 タプルが欲しいのに….と言うときは、 b = tuple(a) とtupleでジェネレーターをラップさせればokです。 </class>…

Python pickle プロトコルの指定

今までpickleファイルを作成するときは、 with open(file, 'wb') as f: pickle.dump(obj=obj, file=f) としていましたが、プロトコルバージョンを高いものに指定してやると、より速く読み込めるpickleファイルが作れるらしい。。 最新のプロトコルバージョン…

【Mac】【豆】ターミナル上で、クリップボードに保存、から出力する。

標準出力をpbcopyに渡すと、クリップボードに保存されます。 # ls の出力結果をコピー ls | pbcopy # カレントディレクトリの絶対パスをコピー echo -n `pwd` | pbcopy 逆にpbpasteを使えば、クリップボードからペーストができます。 echo `pbpaste` 等..

【Mac】 ターミナルでスリープ、その他

ターミナル上からスリープ、シャットダウン、システム終了等を行うことができます。 osascriptというAppleScript を実行するためのコマンドを使用します。 スリープ osascript -e 'tell application "Finder" to sleep' 【豆】 逆にスリープを防ぐには caffe…

Python reduce関数

functoolsのreduce関数を使って、リストの中身を全て足したり掛けたり、といった操作を行えます。 from functools import reduce from operator import add, mul a = [1, 2, 3, 4] # 適当なリスト reduce(add, a) # 総和 > 10 reduce(mul, a) # 総乗 > 24 こ…

Python osmnxのインストール

pythonでopen street mapのデータを読み込めるosmnxという便利なモジュールがあるのですが、 pip3 install osmnxとインストールしようとすると、 fiona/_transform.cpp:473:10: fatal error: 'cpl_conv.h' file not found #include "cpl_conv.h" ^ 1 error g…

Python format形式の中で{}を使う。

pythonのformat形式で例えば{ゴリラ} という文字列を作りたいときは animal = 'ゴリラ' print('{{}}'.format(animal)) print('{{animal}}'.format(animal=animal)) と{を2つ重ねます。

Cython その3 配列の型付け

Cython その2 - サブロウ丸の続きです。 今回はCythonでの配列の型付けの話をします。 配列の要素が全て同一の型の場合、(当然ですが)そのことを宣言した方がより高速になります。 Cythonで上記を実現するにはメモリービューと呼ばれるものを使用します。 nu…

Cython その2 変数の型付け

Cython その1 - サブロウ丸 前回からの続きです。 cython tsp.pyx --annotate もしくは cython tsp.pyx -a を実行すると tsp.html というファイルが作られます。 tsp.html · GitHub これをブラウザ等で開くと という、画面が出てきます。 簡単に言うと、濃い…

Cython その1

Cythonを使ってPythonのコードを高速化します。 Cythonのインストール pip3 install cython コンパイル cythonのインストールが終わったら、スクリプトをc言語にコンパイルするために、以下のsetup.pyを用意します。 (ext_modules = [Extension('tsp', ['tsp…

Python 巡回セールスマン問題

巡回セールスマン問題をpythonで解きます。 問題の概要はwikipediaをご覧ください。 巡回セールスマン問題 - Wikipedia 01整数計画法を使っても解けますが、今回は動的計画法を使用します。 擬似コード (字が汚くて、ごめんなさい) pythonコード DPは配列で…

numpy.array の dtype ..

下記のような、csvファイルをnumpyのarrayに読み込ませるスクリプトを書いていました。 from csv import reader as csv_reader # データの読み込み print('data reading...') data = np.array([ [0 for ii in range(num_column)] for i in range(num_row)]) …

Python と OpenCV で 類似画像検索

全く同じ画像だけではなく、より幅広く'似てそう'な画像を探します。 OpenCVのインストール OpenCVのインストールに関するページがネット上に多数あることから、OpenCVのインストールの難しさ(というより、やっかいさ?)が伺えますが、例に違わず僕もOpenCVの…

Python 集合と自然数との対応付け

下記のような、集合と自然数の対応付けを考えます。 {0, 1, 2, 3} <—> 15 基本的な考えは2進数表記です。 {0, 1, 2, 3} <—> 20 + 21 + 22 + 23 = 15 {0, 1, 3} <—> 20 + 21 + 23 = 11 これをそのまま関数にすると、 def set2int(_iter): res = 0 for i in _i…

【Mac】ターミナル ショットカットキー

ターミナルでpythonと打ち込むときに pyhtonになっていたりpyてょんになったりしますよね。 これが煩わしいので、ショットカットキーを設定しようと思います。 ターミナルの環境設定から右のキーボードを選択し、「+」を押してキーとアクションを設定します…

Pythonスクリプト内でシェルコマンドを使う

subprocess シェルの中で他のプログラムを起動し、そのプログラムが生成した出力を知りたいだけなら、getoutput()関数を使う。 import subprocess as sp ls = sp.getoutput('ls') ls > 'Applications\nDesktop\nDocuments\n...(略)' オプションとパイプ、リ…

Python collections の Counterオブジェクト

下記の問題を解きます。 kamipeipaa君は新しいものが大好きです。 kamipeipaa君はある日N個の整数A1,A2,A3,....,ANを見つけました。 整数Aiに対して,Ai=Ajとなるjがi以外に存在しなければ,Aiは新規性があるのではないかとkamipeipaa君は考えました。 上記…