競プロと音ゲーと私

競技プログラミングから身を引くことにしました | Kichi's BLOG

を読んでの感想と自分語りです。原型の文章は読んだその日に書いてたけど、その後寝かせてしまった。

特定言語だとうまく正解できないやつ

わかる。
俺が使っているのはPythonであり、競技プログラミングの言語論争においては叩かれることのとても多い言語なので、気持ちはわかるわという気分である。
たまたま今回の問題はC#で特に正解しにくくなっていたに過ぎない。

あってるはずなのに通らないとキレたくなるやつ

わかる。
競技プログラミングをする理由の一つに「楽しいから」があるだろう。
AtCoder社長のchokudaiさんによる電通報の記事の中で、AtCoderに参加する理由についてアンケートを実施している。
超高度IT人材の宝庫、「AtCoder」の実態とは？ | ウェブ電通報

やはり、アルゴリズム学習などのスキルアップを期待しているユーザは数多くいます。ですが、面白いコンテストが開催されるから、という項目にも、かなり多くの票が入っています。これは、重要な要素です。 と、文中には書いてある。
しかしながら、面白いコンテストが楽しくなくなる瞬間が存在する。思うように解けなかったときだ。

「問題を解けなかった」にもいくつかの類型があると思う。
解法をまったく思いつかないとか、自分の知らない原理が使わていたとかなら、まあ解けないのも仕方ないよねと納得がいく。
（以前のことだが、解説を読んで「優先度つきキューなんて知らんがな。こりゃ正解できなくても仕方がない」と思った時があった。）
しかし、合っている（自力で解法を思いつき正しいコードを実装した）はずなのに、プログラミング言語の方の仕様で落ちたり（主にTLE）すると、ものすごくストレスがたまる。
（C++/Javaを使えばその種のストレスから解放されそうな気はするが。）

思うように実力が上がらないと趣味を続けるモチベーションが下がるやつ

わかる。
趣味については、この「思うように実力が上がらないと趣味を続けるモチベーションが下がる」という問題がある。 競技プログラミングと音ゲーを同時にあっている人はけっこう多いようだ……というか、この記事の筆者も音ゲーマーであるようだ。
しばらく音ゲーをしないでいると、昔はクリアできた曲をクリアできなくなって、やる気が落ちることが多い。
どうしたらいいんだろうねという感じである。
何事も、努力を続けて十分に強くなった人は賞賛を浴びることが多いが、その一方で、一旦このスパイラルに入ってしまうと難しい。なぜなら、失った実力を回復するのはそう簡単ではないからだ。
別に競技プログラミングや音ゲーに限った話ではなく、運動系や、楽器の演奏といった趣味にも当てはまるかもしれない。

趣味との付き合いについて

考えてみると自分は趣味全般について（主に競プロについても音ゲーについても）、浅く長くという関わり方をすることが非常に多い。
あんまりどっぷり浸かるというやり方をしないなと思う。 この間調べてみたら、AtCoderのコンテストに初めて参加したのは2014年であったことに気づき、自分でも驚いた。そんな長い時間やってたのかと。 https://twilog.org/Linus_MK/search?word=atcoder&ao=a&order=allasc 時間が長いということは、自分より後に始めて、自分が水色で停滞している間に、あっという間に青や黄色に上がった人もたくさんいるわけである。

そして趣味については、割とついブランクを空けがちである。
（あれ?「浅く長く」と矛盾してないか?） 俺のレート変動を見て分かる通り、2018年のコンテスト出場は5回、レート変動は2回のみである。
2018年の後半は全くコンテストに出場しなかった。
「競技プログラミングこそ俺の全て!!!俺は全力を競技プログラミングに賭ける!!!」になると、実力が上がらなかったときにめちゃくちゃストレスが溜まりそうなので、 ほどほどにするか―。という気持ちが働いているのかもしれない。

「辞めます!もうコンテスト出ません!!」と思い詰めるくらいなら、 趣味とほどほどの距離をおいて「まぁ今日はちょっとめんどくさいので、休むか」くらいの姿勢でいるのもいいと思う。
その一方で、熱心に心血を注ぐことができるのは羨ましいなぁとも思う。

書いているうちに何がなんだか分からなくなってきたので、このへんで。

永江朗「私は本屋が好きでした」読書感想文

永江朗「私は本屋が好きでした──あふれるヘイト本、つくって売るまでの舞台裏」を読んだので、感想文を書く。

どういう本か?

何についての本かというと、「ヘイト本」──韓国や中国をけなす本について。そのような本が書店に並ぶまでのいきさつについて、色々な人にインタビュー取材し、考察した本である。冒頭では「この本のテーマは『本屋にとってヘイト本とはなにか』を考えることです」と書かれている通り、特に本屋からの視点が多く含まれている。

何で読んだの／買ったときのこと

少々長くなるが、買ったときの話を書く。

私がこの本を最初に知ったのは、おそらく新聞の書評記事だったと思う。
普段通っている大宮ジュンク堂書店で探してみたら、「マスコミ・ジャーナリスト」の棚の最下段に1冊だけ差してあった。 隣の棚は「日本人・日本人論」でケント・ギルバートの本がズラリと並び、「おいおい、よりによってその本の近くに置くなんて、（客に対して）喧嘩売ってるのか」と思った。 （中国韓国が主題の本は「海外時事」という別の並びに置かれている）

それからしばらくして、新宿の紀伊國屋書店に行ったときにふと思いついて「私は本屋が好きでした──あふれるヘイト本、つくって売るまでの舞台裏」をもう一度探してみた。1階の「新刊・話題の本」のコーナー、2階の「文芸評論・小説の書き方」のコーナー、3階の「メディア論」のコーナーに置いてあった。

（2階のコーナーの一角に「本についての本」つまり書評の本が並んでいるので、その繋がりで入っているものと思われる。 3階のメディア論の棚に差し込まれたジャンル表示板には「出版」「編集」「書店」などがあり、その繋がりで本書も並んでいると思われる。） しかも、全部平積みである。書店としてこの本を重要視していることが窺える。 （新宿紀伊國屋では、平積みにできる台が多く、棚の高さが低い（棚差しになる本が少ない）ので、平積みになるハードルは低い。また当然ながら、大宮のジュンク堂と新宿の紀伊國屋書店とでは規模も違う。しかしそれを差し引いても、扱いに違いがあることは見て取れた）

近くに並んでいた本をよくよく見てみると、考えて本棚を作ってるな、という印象を受けた。 別に買うつもりはなかったのが、「お、新宿紀伊國屋のその心意気、やるやんけ!応援したるわ!」と思って、思わず買ってしまった。

実は、そういう「本屋がテキトーな本棚づくり・選書をするか、しっかりと考えて本棚作り・選書をするかが大事」という話が、本書の中には繰り返し出てくる。

見計らい配本制

衝撃だったのは、書店の「配本制」のことだ。本屋がこのような制度になっているなんて初めて知った。

出版界には「仕入れて売る」という他の小売業ではあたりまえの概念が存在しません。多くの本屋、とりわけ小さな本屋の場合、店頭に並んでいるのは、自発的に仕入れたわけではない、取次から見計らいで配本される本です。発注しなくても商品が自動的に送られてくるのです。それが日本の出版業界の不思議な常識です。(pp.17-18)

これは「書店には“仕入れて売る”という概念が存在しない」という言い方にもつながる。極端な言い方をすると、書店は明日どんな本が入ってくるかもわからない商売である。本当はそんなことないのだが、まあ、どんな本が入ってくるのかわからなくてもやっていける商売ではある。なぜなら、取次が配本を決めているからだ。大きな書店にはいろんな本をたくさん、小さな書店には少しの種類の本を少しずつ。（p.92）

本屋の立場で見ると、注文したわけではないけど、本は届く。この時点で、金は払わなきゃいけない。勝手に本が来て、その分の金を払えと言われるなんて、ムチャクチャじゃないかと思うけど、本屋はそうなっているらしい。即時返品ということもできるが、その場合返品で返金されるのは時間が経ってからである。棚に並べて仮に売れれば、もちろん現金収入がある。じゃあ売るか、という話になってしまう。

見計らい配本についてはなぜ書店にヘイト本があふれるのか。理不尽な仕組みに声をあげた1人の書店主 | Business Insider Japan も参照。また、同じ書店の店主が本書について論じた
あふれるヘイト本、出版業界の｢理不尽な仕組み｣に声を上げた書店のその後 | Business Insider Japan も併せて読むと良い。

もっと抽象的に言うと

出版・本屋のシステムが、だんだん立ち行かなくなった中で、巧妙に工夫して利益を出した、と言える。 つまり、抽象化すると、システムが機能不全に陥ったときにそれをハックしたケース、と考えられる。（ハックという語に悪い意味はない。ハッキング（ハック）とは - IT用語辞典 e-Words）

• 現状、マスクやトイレットペーパーが高値で取引されている。このような売買を禁止する法律が成立したが、法律論を抜きにしても避難されている。
• ナオミ・クライン「ドクトリン・ショック」の冒頭が確か「アメリカでハリケーンが置きた直後、被災して困った人たちに高値で生活必需品を売りつける」という話であった。（うろ覚え）

でもこれらは「普通の価格より著しく高い」というケースだ。

ヘイト本はその価格に問題があるわけではない。 「困ってるところに付け込んで、高値で売る」というものではない。

とすると、ヘイト本の構造と似てるのは何かなぁ。
マイケル・サンデル「それをお金で買いますか」かな。
色んなものに値段がついてしまったと。お金の取引が行われていると。 一晩あたり82ドルを払うと、刑務所の独房をもっといい部屋にできる。1時間あたり15〜20ドルを払うと、議会の公聴会に出席するために、代理の人（ホームレスなど）に列に並んでもらうことができる。（私が持っている、マイケル・サンデル「これからの『正義』の話をしよう」巻末には「それをお金で買いますか」の序章が収録されてあり、そこを参照しています。）

売る人がいて、買う人がいて、両者が合意してるなら、いいじゃん。そこに市場があるなら、いいじゃん。問題ないじゃん。と、一瞬思える。

しかし、全てが全て良いわけではない。大麻や覚醒剤なんかは、「売買してはダメです」って法律がある。法律で「ダメです」って言われてなくても、道徳的・倫理的に「それはダメだろう」ってこともあり得るよね……って話を、サンデルの本が書いてるんでしょ。読んでないけど。 うーん。システムの立場から論じようとすると、サンデルの本をちゃんと読まないとダメな気がしてきた。

「出版・本屋のシステムが、だんだん立ち行かなくなった中で、巧妙に工夫して利益を出した」例を一つ思い出した。
本といいつつ、ハンドバッグやファッション雑貨などのグッズを付けて、それを本として売る手法がある。（宝島社がよくやるやつ）これだって「システムが機能不全に陥ったときにそれをハックしたケース」の一つと言えるだろう。「出版不況の中でアイディアによって売上を伸ばしたヒット商品！」みたいに、好意的にテレビで取り上げているのも何度か見かけた。 じゃあヘイト本だってテレビが取り上げたって良いんですよねぇ。「出版不況の中で伸びている！ヘイト本！本日の特集は『差別を助長し、少数者への攻撃を扇動する、憎悪に満ちた本(p.28)』です！」とかやれば少しは問題提起になるのかもしれんけど、寡聞にして聞いたことがない。何ででしょうねぇ。

返本率

返本率は4割程度。これは金額ベースの総額なので、もちろん人気のベストセラーの返本率は0に近い。マイナーな本だと返本率はもっと上がるだろう。（p.195）

販売部数は変わらないのに、新刊点数は40年間で3〜4倍に増え、返品率は4割で高止まりしているわけです。 (p.241) *1

その他書き留めておきたいこと

買うのは一体誰なのかと疑問だったけど、下記部分によれば「男性高齢者」らしい。
「客層としては、やっぱり60代・70代の男性が、新聞広告を持って「この本はあるか」と指名買いする（p.44）」
「嫌韓反中本を買うのは圧倒的に高齢者が多いようですが。
古谷　　そうです。70歳前後が中心ですから。ネット右翼はもう少し若くて40代。彼らは動画に依拠しています。（p.151）」

本書の話は取次の責任が重いように思うけどねぇ。何も考えずに右から左に本を流して、押し売りみたいにして金をもらおうってのは、酷いやり方だと思うし、そこで流れていく本の良し悪しは知りませんってのは、あまりに無責任でしょう。
見計らい配本制度、一度解体できないのかなぁ。

関連イベントページ（現在はイベント開催を中止している） http://www.tarojiro.co.jp/news/5964/

それでは。

*1:引用部分では漢数字を適宜算用数字に直している。以下同

iftttで連携失敗、"There was an error during check process"が出た

iftttでEvernoteが関係したルールを使っていたら、いきなり動かなくなったので解決した話。

俺は長いこと、iftttのうち1つのルールだけを使っている。
todoist（Todo管理ツール）でタスクを終わらせたら、Evernoteにその内容を記録する、というものだ。

3月はじめに、突然このルールが動かなくなってしまった。todoistでタスクを完了にしてもEvetnoteが何も変化がない。
『My Applets』→該当のアプレット（ルール）を選ぶ→右上の「setting」を選ぶ→「Check now」のボタンを押す
をすると、iftttのルールが正しく他サービスと連携しているか、確認できる。
しかし、「Check now」を押すと、"There was an error during check process"というメッセージが出た。
連携がうまく行っていないようだ。

このメッセージで検索すると、以下のサイトを見つけた。
“There was an error during check process”の対処方法 | ブログ作成のツボ

これを参考に、
『My services』→Evernoteを選ぶ→右上の「setting」を選ぶ→「Account Info」の右側の「EDIT」のボタンを押す
（2022年5月追記：今は若干変わって、最後に「Reconnect」というリンクを押す必要がある）
をすると、Evernoteを再度認証することができる。
この再認証をすると、無事にルールが正しく動作するようになる。

iftttとEvernoteとは、「ずっと連携し続ける」ということはできない。連携は最大で「1年ごと」である。
したがって、1年ごとにiftttからEvernoteにログインし直して「iftttがEvernoteにアクセスすることを許可します」としなければならない。

ここでGmailを見たら、iftttから「You can fix it! Evernote is offline」というメールが来ているのを見つけた。
Evernoteとの連携ができなくなっていたことを表している。 ということは、1年前もこんなメッセージが来ていたんだろうか?と思って、検索してみたら

2018年・2019年・2020年の3月初旬に同じメールが来ていた。ピッタリ1年ごとである。
確かに再度連携してたんだわ。1年に1回だけ起こる不具合のことなんてすっかり忘れてたわ。

今日のまとめ：

• iftttの様子がおかしくなったら、まずはiftttからの通知メールがないか確認しましょう
• Evernoteは1年に1回認証せねばならないので、1年経つとiftttとEvernoteとの連携が切れて、再度認証が必要になる

それでは。

pythonのmath.acos()関数でValueError: math domain error

pythonのmath.acos()関数でValueError: math domain errorが出た話。 浮動小数点演算で誤差が乗って、定義域の範囲外の数を引数に入れていた。

2次元座標の上の3つの点から、なす角を求めようとした。
より正確に言えば、2つのベクトルのなす角θを求めようとした。 なので、
ベクトルa, bの内積と、aの長さとbの長さを求めて、最後に逆三角関数arccosを使うという方法で角度を求めた。 以下のページに詳しく説明されているので、詳細は割愛する。

３点からなる角度を求める 画像処理ソリューション

Pythonのversionは3.7.6。

math domain error 発生状況

import numpy as np
import math

def calc_angle(a, b):
    cosine_val = (a[0] * b[0] + a[1] * b[1]) / (math.sqrt(a[0]**2 + a[1]**2) * math.sqrt(b[0]**2 + b[1]**2))
    ans = math.degrees(math.acos(cosine_val))
    return ans

上記の関数を考える。 math.acosはラジアンの角度を返すので、ラジアンから度数法に変換するために、最後にdegreesを適用してから値を返している。

例えば、原点から真横に行くベクトルと、斜め右上にいくベクトルのなす角度は……

a = [1, 0]
b = [1, 1]
calc_angle(a, b)

# 45.00000000000001

45度だ。

2つ目の例として、、原点から真横に行くベクトルと、斜め左上にいくベクトルのなす角度は……

a = [1, 0]
b = [-1,  1]
calc_angle(a, b)

# 135.0

135度だ。

いいですね。

では、2次元座標上に適当にx, yを取り、その中点をmidとする。 midからxに向かうベクトルと、midからyに向かうベクトルのなす角はいくつだろうか。

下の図を見れば分かる通り、これは180度である。

ではやってみよう。

x = np.array([3, 4])
y = np.array([-2, -7])
mid = (x+y)/2
calc_angle(x-mid, y-mid)

# 180.0

期待通り。

x = np.array([0.123, 4.567])
y = np.array([3.141, 2.718])
mid = (x+y)/2
calc_angle(x-mid, y-mid)

# 179.99999914622634

数値誤差は出たけど、180度だ。

x = np.array([3.14159265, 2.71828183])
y = np.array([1.23456789, 9.8765432])
mid = (x+y)/2
print(calc_angle(x-mid, y-mid))

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-27-58af6d8dd291> in <module>
      2 y = np.array([1.23456789, 9.8765432])
      3 mid = (x+y)/2
----> 4 print(calc_angle(x-mid, y-mid))

<ipython-input-2-3bbda96d5884> in calc_angle(a, b)
      1 def calc_angle(a, b):
      2     cosine_val = (a[0] * b[0] + a[1] * b[1]) / (math.sqrt(a[0]**2 + a[1]**2) * math.sqrt(b[0]**2 + b[1]**2))
----> 3     ans = math.degrees(math.acos(cosine_val))
      4     return ans

ValueError: math domain error

ValueError: math domain errorというエラーが出た。なぜだろうか?

原因

arccosの引数を見るとエラーの理由がわかる。関数の途中にprint(cosine_val)と入れてみると、以下のようになる。

-1.0000000000000002

つまり、エラーが発生したしくみは以下の通りである。

• math.acosの引数に取れるのは-1以上1以下の引数で、それ以外だとDomain Errorを返す
• 引数は、無限精度の演算であれば-1になるはずだが、浮動小数点の演算で誤差が発生し、-1よりわずかに小さい値になった
• その結果、domain errorが発生した

再現しようと思っていろんな数で試したけど、xやyの桁数を多くしたほうが良いみたい? xやyとして、0から1までの乱数を適当に代入してやると、高確率で発生する。

---

domain errorというのは、関数の定義域から外れたエラーのことであろう。
math --- 数学関数 — Python 3.8.3rc1 ドキュメントには ValueError: math domain errorのことは特に記載がない。

ついでにmathモジュールの関数について、いくつか同様にdomain errorを発生させてみた。

sqrt（平方根）。

math.sqrt(-1)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-34-2037b8d41d70> in <module>
----> 1 math.sqrt(-1)

ValueError: math domain error

log（対数関数）。

math.log(-1)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-35-8f964a7914e2> in <module>
----> 1 math.log(-1)

ValueError: math domain error

acosh（逆双曲線関数）。

math.acosh(0.99) # 逆双曲線関数arccoshの定義域は1以上の実数

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-38-c0f54ec4e970> in <module>
----> 1 math.acosh(0.99)

ValueError: math domain error

factorial（階乗関数）。

math.factorial(-5)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-33-a46d876612ec> in <module>
----> 1 math.factorial(-5)

ValueError: factorial() not defined for negative values

いや、なんでこれだけdomain errorじゃないねん！

math.factorial(2.34)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-32-044b0561db2f> in <module>
----> 1 math.factorial(2.34)

ValueError: factorial() only accepts integral values

いや、なんでfactorialだけdomain errorじゃないねん！！

---

浮動小数点の演算でうまく行かなかった話では、以下も参照：

linus-mk.hatenablog.com

それでは。

pandasで空のDataFrameにapply()してエラーになった

pandasで、 ValueError: Cannot set a frame with no defined index and a value that cannot be converted to a Series というエラーが出ることがある。
結論をいうと、これは空のDataFrameに対してapply()をしたときに発生するエラーである。
そうなら「エラー：DataFrameが空だよ!」とか言ってくれればよいのだが、エラーから原因が推測しづらいので難しい。

空の（0行の）DataFrameにapplyをするとエラーになる

import pandas as pd

pd.__version__

'0.25.3'

適当にサンプルデータを作ります。

df = pd.DataFrame({
    'name'    : ['Alice', 'Bob', 'Charlie', 'David', 'Eve'],
    'height' : [1.66, 1.68, 1.70, 1.72, 1.75],
    'weight'    : [50, 55, 65, 75, 80]    
})

df

	name	height	weight
0	Alice	1.66	50
1	Bob	1.68	55
2	Charlie	1.70	65
3	David	1.72	75
4	Eve	1.75	80

このDataFrameにapplyを使って新しい列を追加しよう。
こういうとき、pandasで条件分岐(case when的な)によるデータ加工を網羅したい - Qiitaにはだいぶお世話になっている。
pandasで複数の列から新しい列を作りたいときにapply関数を使うが、覚えきれないので毎回参照している気がする。
今回は身長と体重を元にBMIを作って、BMIの値を元に体型が「やせ／標準／肥満」のどれなのかを返してみよう。
上の記事の中の「複数変数が条件分岐の対象＆カテゴリ化したい」に該当する。

# やせ／標準／肥満の定義は：
# https://www.e-healthnet.mhlw.go.jp/information/dictionary/metabolic/ym-002.html
def calc_shape(x):
    bmi = x.weight / (x.height ** 2)
    if bmi >= 25:
        return("Overweight")
    elif bmi >= 18.5:
        return("Normal")
    else:
        return("Thin")

df["body_shape"] = df.apply(lambda x: calc_shape(x), axis=1)

df

	name	height	weight	body_shape
0	Alice	1.66	50	Thin
1	Bob	1.68	55	Normal
2	Charlie	1.70	65	Normal
3	David	1.72	75	Overweight
4	Eve	1.75	80	Overweight

これは問題ない。

問題はここから先だ。applyを適用する前に色々選択や抽出の処理があって、DataFrameが空だった場合、エラーが発生する。

df = pd.DataFrame({
    'name'    : ['Alice', 'Bob', 'Charlie', 'David', 'Eve'],
    'height' : [1.66, 1.68, 1.70, 1.72, 1.75],
    'weight'    : [50, 55, 65, 75, 80]    
})

df2 = df[df["name"] == "Foo"]

df2  # 空のデータ

	name	height	weight

df2["body_shape"] = df2.apply(lambda x: calc_shape(x), axis=1)

---------------------------------------------------------------------------

ValueError                                Traceback (most recent call last)

/usr/local/lib/python3.7/site-packages/pandas/core/frame.py in _ensure_valid_index(self, value)
   3539             try:
-> 3540                 value = Series(value)
   3541             except (ValueError, NotImplementedError, TypeError):


/usr/local/lib/python3.7/site-packages/pandas/core/series.py in __init__(self, data, index, dtype, name, copy, fastpath)
    315 
--> 316                 data = SingleBlockManager(data, index, fastpath=True)
    317 


/usr/local/lib/python3.7/site-packages/pandas/core/internals/managers.py in __init__(self, block, axis, do_integrity_check, fastpath)
   1515         if not isinstance(block, Block):
-> 1516             block = make_block(block, placement=slice(0, len(axis)), ndim=1)
   1517 


/usr/local/lib/python3.7/site-packages/pandas/core/internals/blocks.py in make_block(values, placement, klass, ndim, dtype, fastpath)
   3283 
-> 3284     return klass(values, ndim=ndim, placement=placement)
   3285 


/usr/local/lib/python3.7/site-packages/pandas/core/internals/blocks.py in __init__(self, values, placement, ndim)
   2791 
-> 2792         super().__init__(values, ndim=ndim, placement=placement)
   2793 


/usr/local/lib/python3.7/site-packages/pandas/core/internals/blocks.py in __init__(self, values, placement, ndim)
    127                 "Wrong number of items passed {val}, placement implies "
--> 128                 "{mgr}".format(val=len(self.values), mgr=len(self.mgr_locs))
    129             )


ValueError: Wrong number of items passed 3, placement implies 0


During handling of the above exception, another exception occurred:


ValueError                                Traceback (most recent call last)

<ipython-input-10-7f0bdf7b09d6> in <module>
----> 1 df2["body_shape"] = df2.apply(lambda x: calc_shape(x), axis=1)


/usr/local/lib/python3.7/site-packages/pandas/core/frame.py in __setitem__(self, key, value)
   3485         else:
   3486             # set column
-> 3487             self._set_item(key, value)
   3488 
   3489     def _setitem_slice(self, key, value):


/usr/local/lib/python3.7/site-packages/pandas/core/frame.py in _set_item(self, key, value)
   3561         """
   3562 
-> 3563         self._ensure_valid_index(value)
   3564         value = self._sanitize_column(key, value)
   3565         NDFrame._set_item(self, key, value)


/usr/local/lib/python3.7/site-packages/pandas/core/frame.py in _ensure_valid_index(self, value)
   3541             except (ValueError, NotImplementedError, TypeError):
   3542                 raise ValueError(
-> 3543                     "Cannot set a frame with no defined index "
   3544                     "and a value that cannot be converted to a "
   3545                     "Series"


ValueError: Cannot set a frame with no defined index and a value that cannot be converted to a Series

type(df2)

pandas.core.frame.DataFrame

対処法としては、DataFrameが空でないことを判定してからapplyを適用すればよい。

df2.empty

True

len(df2)==0

True

このあたりを使えばよいだろう。

……ここまでの内容はほとんど、このStackOverflowに書いてあります。

https://stackoverflow.com/questions/48306694/valueerror-cannot-set-a-frame-with-no-defined-index-and-a-value-that-cannot-be

実はpandas1.0.1では別の挙動になる。

pandas1系になると挙動が変わるのね……メジャーアップデートは結構変更が起きるんかな……
エラーになるのは同じだけど、エラーメッセージが違ったので、こちらも載せておく。

import pandas as pd

pd.__version__

'1.0.1'

df = pd.DataFrame({
    'name'    : ['Alice', 'Bob', 'Charlie', 'David', 'Eve'],
    'height' : [1.66, 1.68, 1.70, 1.72, 1.75],
    'weight'    : [50, 55, 65, 75, 80]    
})

df2 = df[df["name"] == "Foo"]

df2

	name	height	weight

df2["body_shape"] = df2.apply(lambda x: calc_shape(x), axis=1)

---------------------------------------------------------------------------

KeyError                                  Traceback (most recent call last)

/usr/local/lib/python3.7/site-packages/pandas/core/indexes/base.py in get_loc(self, key, method, tolerance)
   2645             try:
-> 2646                 return self._engine.get_loc(key)
   2647             except KeyError:


pandas/_libs/index.pyx in pandas._libs.index.IndexEngine.get_loc()


pandas/_libs/index.pyx in pandas._libs.index.IndexEngine.get_loc()


pandas/_libs/hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()


pandas/_libs/hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()


KeyError: 'body_shape'


During handling of the above exception, another exception occurred:


KeyError                                  Traceback (most recent call last)

/usr/local/lib/python3.7/site-packages/pandas/core/internals/managers.py in set(self, item, value)
   1070         try:
-> 1071             loc = self.items.get_loc(item)
   1072         except KeyError:


/usr/local/lib/python3.7/site-packages/pandas/core/indexes/base.py in get_loc(self, key, method, tolerance)
   2647             except KeyError:
-> 2648                 return self._engine.get_loc(self._maybe_cast_indexer(key))
   2649         indexer = self.get_indexer([key], method=method, tolerance=tolerance)


pandas/_libs/index.pyx in pandas._libs.index.IndexEngine.get_loc()


pandas/_libs/index.pyx in pandas._libs.index.IndexEngine.get_loc()


pandas/_libs/hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()


pandas/_libs/hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()


KeyError: 'body_shape'


During handling of the above exception, another exception occurred:


ValueError                                Traceback (most recent call last)

<ipython-input-10-7f0bdf7b09d6> in <module>
----> 1 df2["body_shape"] = df2.apply(lambda x: calc_shape(x), axis=1)


/usr/local/lib/python3.7/site-packages/pandas/core/frame.py in __setitem__(self, key, value)
   2936         else:
   2937             # set column
-> 2938             self._set_item(key, value)
   2939 
   2940     def _setitem_slice(self, key, value):


/usr/local/lib/python3.7/site-packages/pandas/core/frame.py in _set_item(self, key, value)
   2999         self._ensure_valid_index(value)
   3000         value = self._sanitize_column(key, value)
-> 3001         NDFrame._set_item(self, key, value)
   3002 
   3003         # check if we are modifying a copy


/usr/local/lib/python3.7/site-packages/pandas/core/generic.py in _set_item(self, key, value)
   3622 
   3623     def _set_item(self, key, value) -> None:
-> 3624         self._data.set(key, value)
   3625         self._clear_item_cache()
   3626 


/usr/local/lib/python3.7/site-packages/pandas/core/internals/managers.py in set(self, item, value)
   1072         except KeyError:
   1073             # This item wasn't present, just insert at end
-> 1074             self.insert(len(self.items), item, value)
   1075             return
   1076 


/usr/local/lib/python3.7/site-packages/pandas/core/internals/managers.py in insert(self, loc, item, value, allow_duplicates)
   1179         new_axis = self.items.insert(loc, item)
   1180 
-> 1181         block = make_block(values=value, ndim=self.ndim, placement=slice(loc, loc + 1))
   1182 
   1183         for blkno, count in _fast_count_smallints(self._blknos[loc:]):


/usr/local/lib/python3.7/site-packages/pandas/core/internals/blocks.py in make_block(values, placement, klass, ndim, dtype)
   3039         values = DatetimeArray._simple_new(values, dtype=dtype)
   3040 
-> 3041     return klass(values, ndim=ndim, placement=placement)
   3042 
   3043 


/usr/local/lib/python3.7/site-packages/pandas/core/internals/blocks.py in __init__(self, values, placement, ndim)
   2587             values = np.array(values, dtype=object)
   2588 
-> 2589         super().__init__(values, ndim=ndim, placement=placement)
   2590 
   2591     @property


/usr/local/lib/python3.7/site-packages/pandas/core/internals/blocks.py in __init__(self, values, placement, ndim)
    123         if self._validate_ndim and self.ndim and len(self.mgr_locs) != len(self.values):
    124             raise ValueError(
--> 125                 f"Wrong number of items passed {len(self.values)}, "
    126                 f"placement implies {len(self.mgr_locs)}"
    127             )


ValueError: Wrong number of items passed 3, placement implies 1

それでは。

python競技プログラミングで、二項係数の計算でTLEしたので高速化した話

競技プログラミング（AtCoderなど）によくある、二項係数（コンビネーション）を10⁹+7で割った余りを求める話です。

前提条件

Pythonで実装するときに、気をつけるべきポイントを書いておきます。
C++やJavaを使ってる人は、この記事を読む意味はありません。細かい実装を気にしなくても余裕で間に合うので。
しかしPythonを使う場合は、コードの細かい違いによってTLEになる危険性が多くあります。

よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
に記載してある内容を理解していることを前提とします。

また、これは上記記事の2番（nが大きく、kが10⁵程度）のアルゴリズムの実装です。 よく使う方である、上記記事の1番（階乗テーブルを作る方の）解法は書いていません（が、間接的に参考になると思います）。

いろいろ試してみましたが、使い勝手と速度を考えると、ライブラリには「教訓2」の形で入れておくのが良いと思います。

問題設定

n <= 10⁹, k <= 2*10⁵とする。 nCkを素数pで割った余りを求めたい。

n = 10 ** 9
k = 2 * 10 ** 5
mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
    return power(x, mod-2)

modinv_table = [-1] * (k+1)
for i in range(1, k+1):
    modinv_table[i] = modinv(i)

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

print(binomial_coefficients(n, k))

こういうコードを書いた。
結論からいうと、アルゴリズムが間違っているわけではないが、このコードはTLEになる。

TLEを確認する

AtCoderのコードテスト上で以下を確認した。
（コード提出と異なり、2秒を超えてもTLEにはならないんだな。一部の問題は実行時間制限が4秒や6秒になっているから、）

n= 10**9, k = 10**5で
print(binomial_coefficients(n, k))を計算する
→1740ms程度かかった。

n= 10**9, k = 2 * 10**5で
print(binomial_coefficients(n, k))を計算する
→3480ms程度かかった。

というわけで、制限時間が2秒の場合は、10⁵でギリギリ間に合うが、2*10⁵だと間に合わない。

教訓1 python標準のpow()関数は「x^yをpで割った余りを求める」こともできる

まさかそんなことはできないだろうと思って自分で繰り返し二乗法を書いていたのだが、「x^yをpで割った余りを求める」こともできる。 これを使えば、上のコードは以下のように書ける。

n = 10 ** 9
k = 2 * 10 ** 5
mod = 10**9 + 7

def modinv(x):
    return pow(x, mod-2, mod)

modinv_table = [-1] * (k+1)
for i in range(1, k+1):
    modinv_table[i] = modinv(i)

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

print(binomial_coefficients(n, k))

n= 10**9, k = 2 * 10**5で
print(binomial_coefficients(n, k))を計算する
→870ms程度かかった。

よ、余裕で間に合うじゃん!!

組み込みのpow()のほうがもちろん最適化されているので、同じ計算をするとしても高速に動作する。

教訓2 高速に逆元を求める方法

フェルマーの小定理を使わずに逆元を求めるという、スゴイ方法がある。この方法を最初に考えた人はどういう頭の構造をしてるんだろうか? 累乗計算をする必要がないので、フェルマーの小定理に比べて高速になる。
証明は、Python で二項係数 nCr を高速に計算したい | Satoooh Blogなどに詳しい。

n = 10 ** 9
k = 2 * 10 ** 5
mod = 10**9 + 7

# def modinv(x):
# xの逆元を求める際に[mod % x]の逆元が必要なので、関数の形でxの逆元を直接求めることは難しい。再帰を使えば行けそうだけど。

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

print(binomial_coefficients(n, k))

n= 10**9, k = 2 * 10**5で
print(binomial_coefficients(n, k))を計算する
→190ms程度かかった。

よ、余裕で間に合うじゃん!! （2回目）

フェルマーの小定理から逆元を求める方法の計算量は、log(10⁹+7)程度である。しかし、pythonは遅いので、そのlogのせいでTLEになりかねない。

教訓3 逆元を求める回数を極力減らす

逆元を求めるというのは計算量の重い操作である。どうしても剰余演算をしなければいけないからだ。
したがって、同じ計算をするのでも、逆元を求める操作の回数が少ないほうが計算時間は少なくて済む。
……という点に注意して、元のコードを眺めると、何度も逆元（mod上の割り算）を計算していることに気づく。それを一回で済むように書き換えればよい。

n = 10 ** 9
k = 2 * 10 ** 5
mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
    return power(x, mod-2)

def binomial_coefficients(n, k):
    numera = 1  # 分子
    denomi = 1  # 分母

    for i in range(k):
        numera *= n-i
        numera %= mod
        denomi *= i+1
        denomi %= mod
    return numera * modinv(denomi) % mod

print(binomial_coefficients(n, k))

n= 10**9, k = 2 * 10**5で
print(binomial_coefficients(n, k))を計算する
→85ms程度かかった。

よ、余裕で間に合うじゃん!! （3回目）

注意すべきは、テーブルにしていないので毎回の計算に時間がかかることだ。
色々なkに対して二項係数nCkを何度も求める場合は不向き。

余談：python3.8では組み込みpow()関数で逆元が計算できるらしい……

python3.8では、modを取ったときの-1乗や-2乗などもできるらしい。以下は公式ドキュメントに記載されている例だ。
組み込み関数 — Python 3.8.6 ドキュメント

>>> pow(38, -1, mod=97)
23
>>> 23 * 38 % 97 == 1
True

mod 97の上で38の逆元を求めている。
これが使えるようになったら、この記事自体が無用になってしまうんじゃないか?

ただし上記は3.8以降であり、3.7以前では使えない。
手元のPython 3.7.6 ではこのようになった。

>>> pow(38, -1, 97)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: pow() 2nd argument cannot be negative when 3rd argument specified
>>> 

きっかけ

2020年2月22日のABC156 D問題でTLEから抜け出せなくて、結局C++で提出したが、レートが大きく下がってしまった。そこで今回、振り返って分析をした。
ちなみにC++だと、上記の教訓に挙げたことを考えなくても、余裕で間に合う。
Submission #10287127 - AtCoder Beginner Contest 156

関連記事

Pythonで競技プログラミングをして高速化を色々試してみた記事。

linus-mk.hatenablog.com

ヒキタクニオ「ヒキタさん！ ご懐妊ですよ」読書メモ

ヒキタクニオ「ヒキタさん！　ご懐妊ですよ」を読んだのでメモ。 何についての本かというと、不妊治療に奮闘した男性の目線から書かれたエッセイである。最初に治療を始めてから、最終的に子供が生まれるまでに、実に5年くらいかかっている。

何で読んだの

俺にしては珍しく、表紙買いである。
この本は2019年10月に映画化された。それに合わせた記念カバーがかかった状態で、本屋に並べて置いてあったのだ。きれいな満開の桜の下を男女が歩いている写真の表紙で、インパクトが強くて思わず「なんじゃこれ」と手に取った。
なお、映画化用の特別なカバーを外すと、通常のカバーが出てくる。この通常カバーは「人の顔のどアップ」であり（画像参照）、この表紙だったら買うことは無かっただろう。 本のキャンペーン中にスペシャルカバーをかけることはよくある。それを見るたびに「別にカバーを掛けかえたくらいで売上が変わらなくない?」と思っていたが……自分がスペシャルカバーにつられて買うとは思わなかった。

不妊治療ってこんなに金がかかるのか！

別に俺自身は不妊治療に関係しているわけではない。というか、子供もいなければ配偶者もいない。すなわち、独身である。
というわけで、不妊治療に関して特段の知識がない状態で読んだのだが、主な感想は「こんなに金がかかるんだな！」だ。
本書の巻末には、不妊治療にかかった金額の一覧が記載されている。しめて約217万円である。
この金額をどう考えるかは人それぞれだろうが、個人的には「こ、こんなにかかるのかー」と驚きであった。
筆者も文庫版あとがきで「不妊治療はメンタルなもの、その中でも高額な金銭面が最も大きな重圧になっている」と記している（p.280）。保険が適用されないというのが、費用が高額になる大きな原因である。筆者は健康保険適用になればいいのにと嘆いている。

雑談という訊き方

終盤で体外受精の末、とうとう妊娠して胎児が育っていく。 ところが、検診で調べたところ、胎児の頭に空洞がある、ということが分かった。 頭に空洞って、そんなことあるのかよ、という感じである。

羊水検査は体内の子供に染色体異常があるか無いか分かるが、母子への負担が大きい。それをやるべきか否か、医師に訊いても「患者さんの判断に任せる」という。

少し長くなるが、その後のやり取りの部分を引用する。

私は、ここだろうなと思った。少し考えて言った。ここから、B医師の真意をくみ取らなければならない。私は慎重に考えた。
「じゃあ、いまから雑談ですね。聞き流してもいいですから……」 と前置きした。B医師は何ごとか、という顔を私に向けてうなずいた。 「もしもですよ……、B先生の奥さんのお腹の子が、うちと同じ状態、脈絡叢嚢胞であったとして、染色体異常の可能性も同じほどであったとしたら、B先生は、羊水検査を奥さんに受けさせますか？　まあ、雑談ですから、軽く感想程度に……」 私は妻の顔を見た。あくまでも雑談であるからだ。 「しませんね、羊水検査は……」 B医師が言った。 私は妻から視線をB医師に戻した。若くて優秀な医師、雇われているので、勝手なことは言えない、しかし、これが本当の意見ですよ、って感じなのか、ちょっと笑っているようにも見えた。
（pp.226-227）

ここを読んでいて思い出したのは、以下のnote記事だ。羽田空港と成田空港を間違えた人が空港の職員に訊くシーン。

「ど、どうすればいいですかね？お姉さんだったらどうしますか！？」
何か困ったことがあってお店の人とかに聞くときわたしはいつも「あなたならどうする」って聞く。「わたしはどうすればいいですか」っていうとその人はお客さんであるこちらの行動の責任を取らないといけなくなっちゃうので、答えにくいのだ。だから「ご自分だったらどうなさいますか」って聞き方が一番いいと思っている。家電で迷ったときも、病院で複数の治療法を提示されたときも、羽田と成田を間違えたときも。
https://note.com/yurikure/n/n5bd0499da700

2つのケースとも、判断に悩んだ人が「あなただったらどうしますか」と訊いている。状況はだいぶ違うけど。
一つのやり方として覚えておこうかな。

ただ、もとの本の話から「ものの訊き方のコツ」を導き出して、はいおしまい、とするのはあまりにも安直だろう。

ストレートに訊くわけにいかないので、医者の心情の機微というものをギリギリのところで探り出そうとしている。「雑談なので、あくまで軽く……」というていで、だ。
この微妙な状況での巧さというのは、何でだろうなーと考えた。それは、筆者が「小説家として、人間の心情を描いてきたこと」「会社勤めではない人間として、自分の身を自分で守るべく生き抜いてきたこと」あたりの背景があったからではないかと推察した。

精神的な負担とネットのキュレーションメディア問題

金銭面の話だけではなく、精神的な負担もかなり大きいことが詳しく書かれている。 不安と戦いながら治療を続ける中で、「ネットで調べてみると、不確かな意見が数多くあり、不安になってくる」というような記述が見られた(p.211, 217)。
これ、要するにキュレーションメディアがアクセス数欲しさに適当な記事を書いたんじゃないかなぁ……ネットに　健康や医療の記事で不安を煽るようなのを書くのはやめようぜ、と思う。