Posts

Showing posts with the label Python3

子供が産まれて、育休を取り始めました

この度、赤ちゃんが生まれました。 めでたい。 そんでもって、10月から半年ほど育休を取って、育児に専念することになりました。 会社・部署の方々など、様々な方のサポートがあってのことです。 とても感謝しています。 休み自体は9月のシルバーウィークから取っていて、すでに絶賛育児中です。 ただね…… この時点ですでに大変なんだが? 細かいポイントを含めれば色々あるけど、しんどかったポイントをあげるなら、こんな感じ。 1. 生活リズムが不規則になる 私の担当範囲は、起きている時間のミルク、おむつ替え、沐浴、暇な時にじっと赤ちゃんの様子を見つめるなど。(あれ、意外とやってないな……) 主に昼から夜、あとは深夜から朝方(1時〜7時)に起きている感じ。 深夜に起きる前と、朝の担当が終わったあとに、それぞれ3〜4時間程度寝ている。 元々深夜に作業するのが苦じゃないタイプなので、深夜も赤ちゃんが寝ている時などは、パソコンでAIと戯れたり、スマホでダラダラとこんな感じの記事を書いたりと好き勝手やっている。 が、最初の方は生活リズムを変えるのがしんどかった。 無理やり寝るためにサプリメントを飲んだり、とにかく横になったりと色々試したが、寝れない時はとにかく寝れない。これがしんどい。 結局、慣れるまではどうにもならなかった。 人間って生活リズムを変えるのが難しい生き物なんだな、と割り切ることにした。 一方、妻の側は、今のところだいたい3時間おきに授乳がある。 母乳だったり、ミルクだったり、その併用だったり。 これがシンプルながらに、妻への負担が半端ない。 妻は授乳のたびに起きているし、赤ちゃんの空腹具合によっては泣き声と共に叩き起こされたりと、不規則な睡眠を強いられている。 授乳の間隔が空くと胸が張るし、乳腺炎になることもあるそう。 発熱などが出ることもあるので、妻の体調も気になる。 うちは基本的に母乳をあげて、足りない分はミルクを作って補う感じで運用している。 育児を始める前は、12時間ずつ分担して、私のターンはミルク、妻のターンは母乳でいいんじゃない?とか考えていた。 が、現実はそんなに割り切れるようにはなっていなかった。 赤ちゃんの都合だけじゃなく、妻の体の事情もある。 あと、沐浴とかも...

Python3とWarlus operatorの話。

Image
:= ⇦なんか可愛い ぼちぼち遊びで解いてるLeetCode。 374. Guess Number Higher or Lower を解いた後にいい感じの解き方あるかなーってDiscussを流し見していると、 こんな解答があった。 やってることは自分で実装した二分探索と同じことをやっているが、その中の解法でこんな書き方あったなってことでメモがてら残しておく。 ちなみにその書き方はこれ。 while ( res : = guess ( myGuess ) ) != 0 : 名前を知らなかったけどWarlus演算子っていうらしい。セイウチって呼んでた。 :=  ⇦目と牙に見えますよね?だからWarlus(セイウチ)ってことらしいです んで、上のコードのやっていることとしては res = guess ( myGuess ) while res != 0 : と同じで、これを1行で書けるよーってこと。 機能自体は Python3.8 のリリースノートに書いてあったので結構前に使えるようになっていたはずなのですが、そこまで最新機能を追いかけていなかったのでここでメモとして残して勉強したってことで。

BinarySearch(二分探索)を実装するときにPython3とJavaでは書き方が異なる話。

Image
二分探索の書き方 なぜこのような書き方をしなければならないのか? 二分探索の書き方 を実装するときにPythonでは中間値の宣言を mid = ( left + right ) // 2 で済みますが、Javaでは以下のような書き方をする必要があります。 mid = left + ( right - left ) / 2 ; ちなみにこれはC++にも当てはまります。 mid = left + ( right - left ) / 2 ; なぜこのような書き方をしなければならないのか? 何故このような書き方をしなければならないかというと、仮に left + right の値が 2^31-1 よりも大きければ、オーバーフローして負の値になるからです。 例えば、Javaでそのような長さの配列が与えられ、読み込んでしまった場合には例外として ArrayIndexOutOfBoundsException が発生します。 C++の場合には不正な書き込みが発生し、メモリ破壊などに繋がることもあります。 Pythonでは整数値にはオーバーフローがなく、オーバーフローを意識するような処理を書かなくても処理を行うため、とてつもなく大きな値でも計算時の精度は落ちません。 二分探索を書くときには気をつけようってことで一応メモを残しておきます。

数値の配列が与えられた時、配列の最初に偶数が現れるよう並び替える

Image
出典 Elements of Programming Interviews in Python: The Insiders’ Guide (English Edition) 問題 数値の入った配列が渡されます。 偶数の値が最初に現れるように配列の値を並べ替えなければしてください。 なお、追加で配列を用意してはなりません。 解法 # List[int] -> None def even_odd ( A ) : next_even , next_odd = 0 , len ( A ) - 1 while next_even < next_odd : if A [ next_even ] % 2 == 0 : next_even += 1 else : A [ next_even ] , A [ next_odd ] = A [ next_odd ] , A [ next_even ] next_odd -= 1 # Time Complexity O(N) # The additional space complexity O(1) 値が2で割り切れる時はイテレーションのインデックスを後ろにずらし、そうでない場合には入れ替え(スワップ)と後ろのインデックスを前にずらすことで比較的容易に実装が出来ます。

Pythonの二次元配列から最も大きい値を取得する

Image
最長部分共通問題を解いているときに 最長部分共通問題を解いているときに 気になったので調べてみた。 最長共通部分列(Common Longest Subsequence) の問題を解いている最中にこの記事を読んでいて、あれ?これだと最長の共通部分が何文字分あるのか返せてないな、でも二次元配列ってどう返すんだっけ? となったので調査。 ちなみに max(dp) や max(max(dp)) では返せませんでした。 結論としては ここ が参考になった。 大人しく従ったら上手く返せたのでメモがてら記事を書いておく。 max ( list ( map ( lambda x : max ( x ) , dp ) ) ) これで返すか、 from itertools import chain list ( chain ( * a ) ) max ( chain ( * a ) ) こう返すかの二択っぽい。 ちなみにつまづいていた最長部分共通問題は これ で、ソースコード(メモ化とDPを試した)は ここ 。 時間がある人はぜひ解いてみてください。

Pythonの基本的な組み込み型の整理①

Image
組み込み型を知ること Elements of Programming Interviews in Python: The Insiders’ Guide 数値関連 abs(x) math.ceil(x) math.floor(x) min(x,y) max(x,y) pow(x,y) sqrt(x) 組み込み型を知ること お仕事で書かないのでどうしても行き当たりばったりで書くことが多いのでたまには地味な基礎的なこととか書きたいなと。 何回かに分けて書きます。 Elements of Programming Interviews in Python: The Insiders’ Guide 以前 こちらの記事 でも紹介したいわゆるコーディングインタビュー対策用の本、 Elements of Programming Interviews in Python: The Insiders’ Guide 。 この本の中にChapter4にPrimitive Typesという章があったので、せっかくだし記事にしようとなりました。 公式の組み込み関数はこちら 数値関連 abs(x) 数値xの絶対値 |x|を求めるときに。 >> > abs ( - 10 ) 10 math.ceil(x) 公式のmath(数学関数)はこちら math.ceil は天井、引数として与えた x 以上の最小の整数を返します。 例えば、 >> > import math >> > math . ceil ( 2.17 ) 3 といったように、小数に関してもカバーしています。 math.floor(x) 対して math.floor です。 ceil(天井) と反対の床を意味することから、真逆の結果を返すような関数であることが想像できますよね。 返り値として x の「床」 ( x 以下の最大の整数) を返します。 >> > math . floor ( 2.17 ) 2 min(x,y) max(x,y) これらは書かなくても知ってるよ!となる気がするので軽く。 min(x,y) で x,y が数値型の場合、 x,y のいず...

failed: unable to get local issuer certificate (_ssl.c:1123)と出たので解決した話

Image
Webスクレイピングとか 試していたらこれが突然出た。 macOS用公式インストーラーのPython 3.6でCERTIFICATE_VERIFY_FAILEDとなる問題 という記事に解決策が書いてあったが、 python.orgで配布されているmacOS用の公式インストーラーでインストールしたPython 3.6を使い、 urllib.request.urlopen() で https:// のWebページを取得しようとすると、以下のエラーが発生します。 で、このタイトルのエラーに当たっていたよう。 私の場合はPython3.8.5を使っていたので $ /Applications/Python\ 3.8/Install\ Certificates.command というコマンドをターミナルで叩くことで事なきをえた。 読んでないのが悪いとはいえこれはハマる人が多いんじゃなかろうか。

CodeWarsの話。CreatePhoneNumber編

Image
たまたま目にしたので Create Phone Number たまたま目にしたので CodeWars なるサイトがあるとのことで試しに登録してみた。 サイトで問題を解いてコーディングスキル上げてね!みたいなサイトです。 Create Phone Number そこで2問目(3問目だったかも)で出てきた Create Phone Number についてPythonで解いていました。 この問題はリストで10桁の数字が与えられるので、それらの値を電話番号のフォーマット、下のような形式で変換して返してほしいという問題です。 create_phone_number ( [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 0 ] ) # => returns "(123) 456-7890" 僕は愚直にfor文の中で分岐を何度も挟むことで作る、という方法を取りました。 def create_phone_number ( n ) : phone_number = '(' for i , num in enumerate ( n ) : if i < 3 : phone_number += str ( num ) if i == 2 : phone_number += ') ' elif i <= 13 : phone_number += str ( num ) if i == 5 : phone_number += '-' return phone_number でもよく見たらこれって書く量も多いし、なんかあんまりいけてないなぁと思っていたところ他の方の回答を見たところ、こんな解答を見つけました。 def create_phone_number ( n ) : return "({}{}{}) {}{}{}-{}{}{}{}" . ...

djoserを使ったDjango REST Frameworkでのカスタムユーザーモデル認証機能の実装

Image
djoserとは 使い方 djoserとは djoser とはDjango REST Framework上での基本的なユーザー認証や登録などの認証周りをサポートしてくれるライブラリです。 カスタムモデルに対しても使え、Djangoのコードを再利用するような形をとるのではなく、Single Page Application(以下SPA)によりフィットするようなアーキテクチャを目指して作られています。 今回はdjoserの最もシンプルな認証機能の実装について書きます。 なお、この認証はセキュリティの面などから実際に使用するべきではなく、以下のJWT認証のようなより強固なセキュリティの設定があります。 あくまでお手軽な認証として紹介します。 ソースコードは こちら なお、以下の全てが導入後にエンドポイントとして使えます。 /users/ /users/me/ /users/confirm/ /users/resend_activation/ /users/set_password/ /users/reset_password/ /users/reset_password_confirm/ /users/set_username/ /users/reset_username/ /users/reset_username_confirm/ /token/login/ (Token Based Authentication) /token/logout/ (Token Based Authentication) /jwt/create/ (JSON Web Token Authentication) /jwt/refresh/ (JSON Web Token Authentication) /jwt/verify/ (JSON Web Token Authentication) Getting started djoser関連の記事を他にも書いています。 djoserを使ったDjango REST Frameworkでの認証機能の実装 djoserを使ったDjango REST FrameworkでのJWT認証機能の実装 なお、今回はJWT認証を用いたユーザー認証を実装することとします。 使い方 途中...

Pythonで学ぶスタック

Image
スタック スタックについて Pythonでのスタック利用例 Pythonでの表記法と注意点 連結リストの要素を逆転させる 逆ポーランド記法の計算 ディレクトリ構造の短縮化 スタック について改めて使い道を模索してみたのでメモ。 スタックについて 底のある箱の中に積み木を積んでいくイメージ。 いわゆるLIFO(last in first out)、最後に入れたものを最初に取り出す、というデータ構造。 要素を取り出す時の操作を pop 、要素を入れる時の操作を push という。 スタックを連結リスト、もしくは配列で実装した場合のpop、pushの操作はO(1)の計算量となります。 Pythonでのスタック利用例 Pythonでの表記法と注意点 他の言語と同様に、Pythonでも Stack が組み込み関数として用意されています。 ここで注意すべきなのは上記で用意したPythonでリストを用いてスタックを表す場合には push ではなく、 append を使う点です。 スタックとして使う場合は以下のように要素の出し入れを行います。 >> > stack . append ( 6 ) >> > stack . append ( 7 ) >> > stack [ 3 , 4 , 5 , 6 , 7 ] >> > stack . pop ( ) 7 >> > stack [ 3 , 4 , 5 , 6 ] >> > stack . pop ( ) 6 >> > stack . pop ( ) 5 >> > stack [ 3 , 4 ] 他にもスタックには様々な使い道があります。 連結リストの要素を逆転させる def reverse_linked_list ( head ) : nodes = [ ] while head : nodes . append ( head . data ) head = head . next 逆ポーランド記法の計算 ...

C++のstd::lower_bound()とPythonでの話。

Image
けんちょん本を読むと・・・ けんちょん本 ってAmazonで検索すると出るんですね。知らなかった。 本題に戻りますが、この本には二分探索法の章があります。 C++の話 その中でC++のライブラリである std::lower_bound() を使う際に得られる情報について記述があります。 std::lower_bound() の使用自体はソート済みの配列 a と key が存在するかという内容のライブラリです。 もう少し具体的に記述すると、 a[i] >= key という条件を満たす最小の添字 i を返す(この時の計算量は配列Nに対してO(logN))、というものなのですが、これは単に配列の中に存在するか否か、だけのライブラリではないという事みたいです。 例えば、 配列のなかに key が存在しない場合、与えた key 以上の値の範囲での最小値を取得 配列のなかに値 key が複数あった時、その内の最小の添字を取得 といったような使い方があるようで、これについて学んだ時、Pythonで似たようなライブラリは無いのかパッと思い浮かばなかったので、調べてみました。 Pythonの話 Pythonでは bisect が該当するようで、何度か使ったことはあったが詳しい仕様を思い出せなかったので、実際にドキュメントを読みながら使い方を見てみました。 import bisect a = [ 3 , 8 , 11 , 18 , 27 , 31 ] bisect . bisect_right ( a , 20 ) # 4 print ( bisect . bisect_right ( a , 11 ) ) # 3 print ( bisect . bisect_left ( a , 11 ) ) # 2 この配列に 18 を足してみましょう。すると bisect は以下のような振る舞いをします。 import bisect a = [ 3 , 8 , 11 , 18 , 18 , 27 , 31 ] bisect . bisect_right ( a , 18 ) # 5 bisect . bisect_left ( a , 18 ) # 3 lower_boundはbisect_left...

LeetCodeで学ぶ計算量の改善

Image
計算量の改善 って意外と取り組む事がないなぁと最近思い始めて、一回解いた問題の回答をより良くできる方法を考えたりしている今日この頃です。 昔に比べてメモリの性能が改善しているためよっぽど致命的なアルゴリズムを設計しない限りはなんとかなる ソートなどのアルゴリズムはライブラリのものを呼び出せばなんとかなる etc… 色々な理由はあると思いますが、だからと言ってサボっていい理由にはならないと思うのでいい例を探していたらこんな問題を見つけました。 Majority Element 整数を格納したリストが与えられるのでそのリストの中で最も多い値を返してください、という問題です。 例えば、 Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 といったような形式です。 今回はSolutionにもある通り、それぞれの問題に対する取り組み方を書きます。 例えばBruteforce。これはとにかく全パターンをしらみつぶしに実行して答えを導く、というものです。 class Solution : def majorityElement ( self , nums ) : majority_count = len ( nums ) // 2 for num in nums : count = sum ( 1 for elem in nums if elem == num ) if count > majority_count : return num 解けるものの、for文で2回走査しているため、計算量がO(N^2)とお世辞にもいいとは言えません。 では次にハッシュマップに格納して解く例です。 class Solution : def majorityElement ( self , nums ) : counts = collections . Counter ( nums ) return ...

Pythonでの_の話。

Image
意外と意識せずに使っている・・・ ということで。 この _ ってなんですかい? for _ in range ( n ) って思ったりするも深くは考えていなかったので調べてみた。 他人のコードを読むと使う人は結構使われていらっしゃるのですが、よく知らないまま使うのって気持ち悪いよね。 ループのカウンタがループ内で使用されていないことを示すために使うようで、 arr1 = [ 0 for _ in range ( 5 ) ] arr2 = [ 0 for i in range ( 5 ) ] arr1 と arr2 を比べた時に、 i よりも _ の方がループのカウンタとして使っているということが分かりやすいですよね。 他にも、 for _ in range ( 10 ) : print ( _ ) という使い方は良くないです。 なぜならば出力という形でfor文の中で使ってしまっているから。 対して、 for _ in range ( 10 ) : print ( "Hello world" ) これだとループのカウンタとして使えているので良い例かと。

Pythonで与えられた値が3の冪乗かを判定するプログラムの話。(LeetCode)

Image
冪乗のお話。 解答 冪乗のお話。 3の冪乗かどうかを判定するプログラムを求められました。 326. Power of Three 整数型の値、 n が引数として与えられた場合、それが3の冪乗かを判定し、冪乗ならば True 、冪乗でなければ False を返してください、っていう問題です。 なお、 n の値には以下の制約が存在します。 -2^31 <= n <= 2^31 - 1 さて、どうしましょう?ってことでメモ。 解答 とりあえず解ける解答。 class Solution : def isPowerOfThree ( self , n : int ) - > bool : if n == 0 : return False if n == 1 : return True for i in range ( 31 ) : if pow ( 3 , i ) == n : return True return False # Runtime: 240 ms, faster than 5.15% of Python3 online submissions for Power of Three. # Memory Usage: 14.4 MB, less than 13.91% of Python3 online submissions for Power of Three. pow関数 を使っています。 pow 関数は引数に (基数、冪乗) を取っています。ここでの使い方は、31乗までを範囲としているため、for文で1~31までの値を回します。 pow(3,1) == n pow(3,2) == n ............. といったように3の1乗から31乗までを調べます。 ただし、31という値を意識しすぎる余り、かなり遅くなっています。 遅い理由としては、正しくない場合、31回も回すことになっているからです。 しかし、解けるだけでいいのであればこれ...

Pythonでのビット操作の話(LeetCode)

Image
この記事を書く理由 問題 解答 この記事を書く理由 LeetCodeでTop Interview Questions(面接のコーディング試験で聞かれやすい問題を集めたやつ)のEasy問題を解いている時にビット操作を求められたので念のため書いておきます。 問題 Number of 1 Bits 解答は ここ 。 符号なしの整数を引数として受け取り、その整数が持つ「1」ビットの数( ハミングウェイト とも呼ばれる)を返す関数を書いてください、という問題です。 Example 1: Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits. Example 2: Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit. Example 3: Input: n = 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits. Constraints: - The input must be a binary string of length `32`. 解答 # O(N) Solution class Solution : def hammingWeight ( self , n : int ) - > int : bits = 0 for i in range ( 32 ) : ...

「問題解決力を鍛える!アルゴリズムとデータ構造」とLeetCodeで学ぶ再帰と動的計画法(メモ化)

Image
再帰とメモ化 問題 再帰とメモ化 問題解決力を鍛える!アルゴリズムとデータ構造 というアルゴリズムとデータ構造を学ぶのに良い本があります。 LeetCodeの問題を解いていた時に、この本の中で解説されていた例とすごく被っている内容があったので、記事にしてみようと思いました。 問題 1137. N-th Tribonacci Number 難易度はEasy。 再帰の入門にうってつけです。 問題解決力を鍛える!アルゴリズムとデータ構造 の4章の解説にもある通り、再帰関数のテンプレートは (戻り値の型) func(引数){ if(ベースケース){ return ベースケースに対する値; } func(次の引数) return 答え } 問題解決力を鍛える!アルゴリズムとデータ構造 第4章 設計技法(2):再帰と分割統治法より引用 といったものです。 今回解く問題は、 トリボナッチ数列Tnは次のように定義される。 T0 = 0, T1 = 1, T2 = 1, そして n >= 0 で Tn+3 = Tn + Tn+1 + Tn+2 となる。 nが与えられたとき、Tnの値を返す。 という内容です。 では、こちらをPythonでかつ再帰で解いてみましょう。 class Solution: def tribonacci(self, n: int) -> int: if n == 0: return 0 elif n == 1 or n == 2: return 1 return self.tribonacci(n-1) + self.tribonacci(n-2) + self.tribonacci(n-3) # Time Limit Exceeded しかし、これだとnが 30の時に時間切れとなり、正解とは認められません。 これは再帰で同じ処理が重複し、関数の呼び出し回数がとてつもない回数になっているためです。 ではこれを解決してみましょう。 class Solution: def tribonacci(self, n: int) -> int: memo =...

特定の値まで素数を生み出すアルゴリズム in Python3

Image
特定の値まで素数を生み出すアルゴリズムとか 以下のようにリストで真偽値を管理するやり方で書くといいらしい。 Elements of Programming Interviews in Python  より。 # Given n, return all primes up to and including n. def generate_primes(n): primes = [] is_prime = [False,False] + [True] * (n-1) for p in range(2,n+1): if is_prime[p]: primes.append(p) for i in range(p*2,n+1,p): is_prime[i] = False return primes n = 100 print(generate_primes(n)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]