コロナ時代を生き抜くデータサイエンティストのキャリアビジョン：まとめ
表題の、以下勉強会が自分が考えていたことにタイムリーにミートしていたので、参加しました。
data-learning-guild.connpass.com
示唆に富んでいたので、私見も混じってますが、まとめます。
アジェンダ
- Withコロナ時代のデータサイエンティスト
- 長期化した際の変化
- データサイエンティストが活躍できる場所
- これからデータサイエンティストになりたい未経験者のキャリア戦略
- Afterコロナ時代のデータサイエンティスト
- Afterコロナ時代の予想
- コロナが終わった後に元に戻るもの・戻らないもの
- Afterコロナに向けてデータサイエンティストが準備しておくべきこと
まとめ
Withコロナ, Afterコロナという分解能はあまりなく、議論が盛り上がりました。
総じてコロナが当たり前になる現代以降、データサイエンティストに求められる能力のうち、特に対人スキルについての議論が盛り上がりました。
要点をまとめると以下３点と思います。
「価値を出せること」の重要性が増す
- リモートになったことで人月単位のチャージ体制が崩壊する。アウトプットの質で評価されるようになる。「真面目にやりました」はこれまで以上に通用しない
- リアルでただ座っていただけの上司は完全に空気になるし、アウトプットの出ないデータサイエンティストは完全に価値がなくなる。「身を取る流れ」が加速する
- 発注側も、受注側も、ROIの出せる・出せないで二極化が進む。ROIが出せないクライアントは発注を止める。逆にROIを出せない受注側も発注を切られる
要件を詰め切れる力の重要性が増す
- zoomの30-60分で要件を詰め切れる人でないとリモートワークは厳しい
- オンラインでマネジメントできる力がある人が強い
- リアルでマネジメントできていなかった人はオンラインでもできない。オンラインでもリアルでも要件を詰め切る能力は同じものが必要
オンラインでのブランディングの重要性が増す
- オフラインで会って話して信用を得て、という営業シナリオが厳しくなる
- Webでのブランディングの重要性が増す
- （私見）オフラインで会って判断、という意思決定が難しくなることによって、無形の信用がある、つまりブランド力がある組織がより強くなり、フリーランスなど個人には厳しい時代になる。個人としては、自分に能力があることを客観的に示すことの重要性が増す（データサイエンスコンペや競技プログラミングの成績、ポートフォリオの重要性）
他の論点
他にも様々な論点でWithコロナ、Afterコロナの影響について語られました。雑多ですが、以下にメモします。
ネガティブな影響
- ビジネス面
- 企業のコスト削減が進むので、モデルの断捨離が進む
- 現地に行かないと会話ができない業種では話が止まる。製造業系とか
- 金融、製造業R&D、医薬などでは、セキュリティエリアを切り離せないので現地環境で分析しないといけない。まずクライアント自身のリモート化をしないといけない状況なので、取組が止まる
- キャリア面
- これからデータサイエンティストになる人には厳しい。データサイエンティストは手法を知ってるだけでなく実務をどれだけ体験しているかが重要だが、その経験が積みにくくなる
- データサイエンスの需要は変わらずあるし、今後も伸びるだろう。ただ未経験は厳しいという話があるので、人材不足が加速しそう
ポジティブな影響
- ビジネス面
- 働き方面
- 今までは客先に同行できなかったメンバーが、ミーティングがオンラインになったことで参加しやすくなった。クライアントの考え方、気にするポイントを学びやすくなった
- 生産性は人によってはメチャクチャ上がっている。移動の時間が減った。クライアントとのミーティングセットも柔軟にできるようになった
- その他
- リモートになったことで時間を作りやすくなっている。自己研鑽に励める
- 勉強会やセミナーがオンラインになったことで参加の敷居が下がった。「データサイエンティストってどんな人？」が知ってもらいやすくなった
VGG16アーキテクチャについて知りたい情報を１記事で
何だか、なろう系作品の語呂のタイトルになってしまいましたが、VGG16について軽いメモ記事です。
経緯
画像認識で使われる代表的なCNNモデルであるVGG16を扱っている中で、
- kerasのmodel.summary()だと、Output Shapeとパラメタ総数は分かるが、フィルタのサイズやストライド、パディングの情報が分からない。後、完全な形での層の重ね方が分からない（活性化関数として何を使っているのか、までは分からない）
- pytorchのprint(model)だと、フィルタのサイズやストライド、パディングの情報は分かり、層の重ね方も詳細に分かるが、Output Shapeやパラメタ総数は分からない
ということで、両者の情報を併せたテーブルがどうしても欲しくなり、作成しました。
テーブルを作成し終わったとき、そもそもVGG16について（How to codeではなく）知りたい情報が1つにまとまっている記事がないかもなと思い、プチ案内板的な役割の記事を作成しようと思い至りました。
本題
まず、アーキテクチャの詳細情報について作成したテーブルの1枚絵を載せます。
このテーブルでは、前述の通りkerasとpytorchで見られるモデル情報を統合したのに加え、パラメタ総数の計算式の中身を分解して示しました。
基本的には、
パラメタ総数 = インプットチャネルの数 × アウトプットチャネルの数 * フィルタの高さ * フィルタの幅 + バイアスの数(=アウトプットチャネルの数)
で計算されます。
こちらの説明は、名著「ゼロから作るDeep Learning Pythonで学ぶディープラーニングの理論と実装」の第7章に詳しいです。ビジュアルも踏まえて詳しく説明されていますので、ご参考あれ。
これで、kerasとpytorchを行ったり来たり（そんなことをわざわざする人はいないと思いますが。。。）する必要はなくなるはずです。
さらに併せて、ビジュアル化したイメージも載せておきます。
こちらの画像は、以下記事より拝借させていただきました。
注記
この記事を書いている途中で、torchsummaryというライブラリでOutput Shapeやパラメタ総数を表示できることを知りました。
というわけでpytorchユーザーであれば、難なく詳細情報を知ることができますね。
データサイエンス特化Q&Aサービスで解決したい2つの不幸
COVID-19により、猛烈な社会の変化に晒されている今日この頃、皆様如何お過ごしでしょうか。
弊社含めスタートアップ界隈もなかなかの逆風が吹いていますが、そんな中、昨日、Nishikaの2つ目のサービスであるデータサイエンス特化のQ&Aサービスをリリースしました。
この記事では、データサイエンス特化のQ&Aサービスをリリースした背景について述べたいと思います。
Q&Aサービスは、データサイエンスを課題解決の手段として提供する側、活用する側の両方に役立てていただけるサービスにしていきたいと考えています。
具体的には、以下2つの不幸がなくなることを目指しています。
データサイエンティストが、自分の専門外の領域で途方にくれたり、あるいは不正確な認識や実装で課題を解きに行ってしまうこと
データサイエンスを活用する側が、技術が分からないが故に世の中のスタンダードが分からず、技術の分かる人間に騙されてしまうこと
解決したいこと１：データサイエンティストが、自分の専門外の領域で途方にくれたり、あるいは不正確な認識や実装で課題を解きに行ってしまうこと
正直なところ、これは前職時代の自分が欲しかったサービスでした。
前職時代、多くの異なる部門のお客様の対面に立ち、要望を伺い、主にデータサイエンスを武器に解決手段を提案・実装するという仕事をしていた中で、
実装を未経験であることはおろか、理論的な勉強もしたことがない領域の課題を解かなければいけない機会が少なからずありました。
もちろんお客様にとっては技術が重要なのではなく、手段はどうあれ課題を解決してくれることだけが重要なので、多少の不正確、非効率は強引に押し通り乗り越えていたことも多かったのですが、
技術を武器に仕事をする人間の端くれとして、これではいけない、という反省が常にありました。
今後の「データサイエンティスト」のあり方について、ビジネス/サイエンス/エンジニアリングの3つの領域があるなど様々な見方がされていますが、
ことビジネスサイドから見える景色を考えてみると、データを使って課題解決してくれる人が目の前の一人しか周囲にいない、なので何でもかんでもその人に解決をお願いする、というシーンが多く発生するのは容易に想像がつきます。
自分がその領域の専門家であろうとなかろうと、とにかく目の前の課題解決を求められる、という立場におかれる方は、この先一層増えていくのではないかと推測しています。
そんなときに使う手段として、Twitterも良いし、Slackのkaggle-jaチャネルも良いし、Cross Validated（Stack Overflowのデータサイエンス版）も良いのですが、
先人の疑問とそれに対する回答が蓄積され、それを活用し、さらに新たな疑問とそれに対する回答が蓄積され、、という循環が周る場があっても良いのではないかと思い、このサービスをリリースしました。
データが蓄積されることが場を作ることのメリットの1つなので、将来は例えば
- 自然言語処理分野のAnswerが多く知識が豊富だ
- 最適化分野のQuestionが多く熱心に勉強している
など、様々な角度でデータの蓄積を可視化し、データサイエンスの学習や仕事のモチベートに繋げていければと考えています。
解決したいこと２：データサイエンスを活用する側が、技術が分からないが故に世の中のスタンダードが分からず、技術の分かる人間に騙されてしまうこと
こちらは果たして上手くいくか、手探りなのですが、このQ&Aはデータサイエンスを活用する側、つまりビジネス側の方々にも使っていただけたらな、と思っています。
特に機械学習周りの世界はそうだと思うのですが、SOTAがどんどん更新されていくような目覚ましい技術進捗の中で、技術の分かる人と分からない人のリテラシーギャップが開く一方になっている、と考えています。
技術が分からない人間が分からないことに甘んじている状況も、個人的には嫌なのですが、
それ以上に、技術が分からない人間に対してフワッとした言葉でごまかし、あたかもさほど技術的価値がないものを価値があるように見せかけ、対価を取っていく行動が、何より好きではありません。
とは言え、すぐに技術的キャッチアップができる人ばかりではない中で、
世の中のスタンダードってどうなの？という疑問を解決できる場が提供できないか？と思ったことも、Q&Aサービスをリリースした背景にあります。
データサイエンスコンペティションには、特定の企業に開発を委託するよりも、多数の優秀なデータサイエンティストに競い合ってもらうことで精度の高いモデルを作ることができるという側面がありますが、
Q&Aでも、特定の人・企業からの意見だけでなく、幅広い意見を元に意思決定できる材料を提供する、という側面を打ち出せるよう、サービスの改善を行っていきたいと考えています。
最後に
コンペティションに続いてQ&Aという、共通点はデータサイエンスというだけ、基本的に大きく異なる2つのサービスを一介のスタートアップがマネージできるのか、なかなかチャレンジングだとは思っています。
しかし、私が大企業を離れて一番に学んだことである、行動量は裏切らないを信じて、理想を体現すべく引き続き突っ走れればと思っています。
ご利用・ご意見のほど、よろしくお願いいたします！
Cousera / Production Machine Learning Systems / Architecting Production ML Systems まとめ
プロダクション環境の機械学習システムを構築・運用する機会がなかなかないので、まずは座学から入ることにして、CourseraでGoogle Cloudが提供しているProduction Machine Learning Systemsを受講してみました。
Courseraは受講から1週間過ぎると月額課金に切り替わるシステムなので、金欠な私は怒涛のようにカリキュラムを消化してみました。 スピードを重視した弊害であまり頭に入った気がしないので、ここでまとめてみます。 本記事の内容について、正確性、詳細を求める場合は是非受講してみていただければと思います。
全体構成
プロダクション環境の機械学習システムというお題ですが、内容は幅広いです。その分1つ1つの深い掘り下げは他に譲る、という感じです。
- Architecting Production ML Systems
- プロダクション環境のMLシステムが持つべき構成要素、トレーニング・推論を静的or動的のどちらで行うかの判断基準
- Ingesting data for Cloud-based analytics and ML
- クラウド環境へのデータ投入方法
- Designing Adaptable ML Systems
- データの予期せぬ変化などに適切に対応できるMLシステム
- Designing High Performance ML Systems
- ハイパフォーマンスのMLシステム
- Hybrid ML Systems
- クラウド/エッジ/オンプレミスで稼働するハイブリッドMLシステム
一通り学習はしましたが、元々関心があったのがプロダクション環境のMLシステムの全体像だったので、ここではArchitecting Production ML Systemsを中心にまとめます。
Architecting Production ML Systems
What percent of system code does the ML model account for?という問いかけから講義が始まります。
Factはともかく、5%という答えが提示されます。なぜ5%しかないかと言えば、プロダクション環境でシステムを動かし続けるには、インプットに対してモデルがアウトプットする以上に様々な機能が必要だから。具体的には以下の機能が必要です。
確かに、サービスインまで持っていくことだけを考えると工数の割合は感覚に合います。
MLシステムの構成要素は以下のように整理されています。本講義はこの絵の1つ1つの要素を説明する形で進みます。
Data Ingestion
データをシステムに投入する工程です。データの投入元はアプリであったり、デバイスであったり、DBであったりします。 ingestされるデータによって、GCPでは3つのサービスが使い分けられます。大きくはストリーミングデータかバッチデータかによって分かれるところです。
- ingestされるのがストリーミングデータならPub/Sub
- 構造化データを直接モデル構築に使うならBigQuery
- 後で加工する予定のデータならCloud Storage
Data Analysis + Validation
1度MLシステムを構築したと言って安心してしまい、日々投入されるデータを確認しないと、データの予期せぬ変化に気づかずMLモデルが汚染され、おかしな学習や推論結果を吐き出してしまう可能性があります。 例えば、以下のようにカテゴリ変数として扱っていた製品番号が割り当て直された場合や、カテゴリ変数のカテゴリ数が変わった状態で改めてOne-Hotエンコーディングを行い、エンコーディングのされ方が変わった場合など、学習や推論結果が好ましくない方向に変化する可能性があります。
MLモデルのアウトプットは、推論結果の悪化という形で状況を知らせてくれても、それがなぜかは教えてくれません。 データの変化に気がつくには、インプットデータの分布の確認が重要です。典型的には、以下のような明らかな変化が認められれば、異常に気づくべきです。
データの変化がもたらすバグについては、Designing Adaptable ML Systemsのモジュールで詳しく言及されています。
データが健全かどうかをチェックする観点として、以下6つが挙げられています。
- 新たなデータの分布は以前の分布と同様か
- 5 number summariesをチェックする
- 歪度や尖度を比較するためにユニークな値の数をカウントする
- 元の分布のもとで新たな分布が観測される確率を計算する
- 期待される全ての特徴量は存在しているか
- 期待しない特徴量は存在していないか
- 特徴量は期待する型になっているか
- 特徴量を有するサンプルの割合は期待される程度か
- 特徴量を有するサンプルにおいて、特徴量の値は期待される程度か
analysis, validationを行うサービスとして、GCPでは以下3つを提供しています。
Data Transformation
データ加工の工程です。当然ながら、学習と推論で同じデータ加工経路を辿るようにフローを設計することが重要です。
GCPでは3つのサービスを提供しています。
- Dataflow
- Dataproc
- Dataprep
これらの詳細はEnd-to-End Machine Learning with Tensorflow on GCPで言及されているようです。
Trainer, Tuner
学習およびパラメータチューニングの工程です。
GCPでは2つのサービスを提供しています。
- ML Engine: Tensorflowのマネージドサービス
- GKE(Kubeflow): KubeflowにおけるハイブリッドMLモデルのマネージド環境
ML Engineは以下の特徴を備えています。
- Scalable: 数百のワーカーまでスケールアップ可能
- Integrated with Tuner, Logging, Serving components: 他の3つの構成要素の機能も備える
- Experiment-oriented: 実験ベースの考え方で、モデルの取捨選択が可能。ABテストによるモデルの比較ができ、特定モデルによるロックインは当然なし
- Open: 構築したモデルはどこでも運用可能
ハイブリッドMLモデルおよびKubeflowは、Hybrid ML Systemsのモジュールで言及されています。
Model Evaluation and Validation
EvaluationとValidation、近しい言葉に見えますが、工程としては全く異なるものを指します。 Evaluationは、予め決めたmetricについてモデルを評価し、一定水準を超えたらプロダクションへpushする工程を指します。多くの場合人が介在するプロセスです。 Validationは、予め決めたmetricについてモデルを検証し、一定水準を下回ったらアラートを出す工程を指します。基本的に人は介在せず自動で行われるプロセスです。
尚、Evaluationではモデルを評価しますが、評価するには良いモデルとは何かを定義しなくてはいけません。 予測精度が高いものが良いモデルであることはもちろんですが、モデルがSafeであるという観点も重要です。 データをロードしたり、データを受け取って推論するときにクラッシュしない、期待している以上のリソース(メモリなど)を使わない、といったモデルはSafeだと言えます。
Serving
モデルをデプロイし、推論する工程です。 モデルの推論において重要なのは、一言で言えばスループットを最大化し、レスポンスのレイテンシを最小化することとなります。 より詳細に言えば、システム上で推論を担う構成要素に求められるものは、以下4つになります。
- Low-latency: 早く推論できる
- High efficient: 多くのインスタンスを同時実行できる
- Scale horizontally: 起こる問題に対してロバストで信頼できる
- Easy to update versions: 柔軟にモデルのバージョンをアップデートできる
GCPのサービスはこの4つの観点を充足できるぞ、というアピールですね。
Orchestration
なぜorchestrationが重要かと言えば、MLシステムは一部の構成要素に変更があっただけで他のほとんどの要素も影響を受けるためです。
具体的には、全ての構成要素がリソースとコンフィギュレーションフレームワークを共有することが重要です。
共有がなかったときのことを想像してみれば、その重要性が分かります。 共有がなければ、大量のglue codeが生み出されることになります。確かに、想像したくない（けど容易に遭遇する）事態ですね。
glue codeが発生する典型例は、researchとengineeringが組織的に分断されているケースです。 research側の独自環境でプロダクションで動かすことを想定していないコードが生み出されると、glue codeがなければプロダクションで動かない、という状況に陥ってしまいます。
この問題に対する処方箋は、システム面ではR&Dとproduction deploymentで共通のアーキテクチャーを用いること、組織の面では両チームを束ねること、とまとめられています。 当たり前じゃないかと思われるかもしれませんが、この点に言及した勉強会やLTをよく拝見することから、実はそう簡単なことではなく、思った以上に重要性は高いと言えると思います。
GCPでは2つのサービスが提供されています。
- Cloud Composer: managed Apache airflow
- Argo on GKE: container management tool
Cloud Composerでワークフローを定義する手順は以下の通りです。
- オペレーションフローを定義
- フローをDAGとして作成
- DAGを環境にアップロード
- Web UIでExplore DAG Run
この講義ではCloud Composerの詳細には立ち入らないということでしたが、サンプルコードを示してくれていました。
# BigQuery training data query t1 = BigQueryOperator(params) # BigQuery training data export to GCS t2 = BigQueryToCloudStorageOperator(params) # ML Engine training job t3 = MLEngineTrainingOperator(params) # App Engine deploy new version t4 = AppEngineVersionOperator(params) # Establish dependencies t1 >> t2 >> t3 >> t4
Training Design Decisions
トレーニングのデザインというタイトルですが、静的トレーニングと動的トレーニング、どちらを選ぶか？という論点について議論されています。
| 静的トレーニング済みモデル | 動的トレーニング済みモデル |
|---|---|
| 学習は一度、オフラインで良い | 時間と共に学習データが追加される |
| ビルド、テストが容易 | エンジニアリングがより大変、より積極的なvalidationが求められる |
| 容易に古くなる | 定期的にアップデートされ変化にも対応していく |
具体的なユースケースでどちらを選ぶべきか見てみましょう。
| ユースケース | トレーニングスタイル |
|---|---|
| スパムメールの検知 | 静的or動的（スパムの変化速度による） |
| スマーフォトンのVoice2Text機能 | 静的（グローバルに使うモデルなら）、動的（パーソナライズするモデルなら） |
| 広告のConversion Rate | 静的（多くの場合ユーザーの購買間隔は長く、購買行動の変化も緩やかなので、頻繁な再トレーニングの必要性は低い） |
多くのケースで動的トレーニングはより好ましいものだが、エンジニアリングに工数がかかるので、まず静的トレーニングから始めるのが多くの場合現実的ではないか、と結ばれています。
静的トレーニングのアーキテクチャは以下の通りシンプルなものになります。
一方で動的トレーニングのアーキテクチャは、GCP上では3つ候補があるとされています。
Serving Design Decisions
学習のデザインに続いて、推論のデザインについてです。
静的な推論は、分類問題であれば予めラベルを推論しインプットをkeyとしてテーブル化しておき、新たなインプットが来たらkeyが合致するレコードを探して値を返す、というものになります。動的な推論は、新たなインプットに対して都度推論を行います。
静的推論と動的推論のどちらを選ぶかは、一言で言えばspace-time trade-offになります。
| 静的推論 | 動的推論 |
|---|---|
| ストレージコストが高い | ストレージコストが安い |
| レイテンシが低く、固定 | レイテンシが変動 |
| メンテナンスは低工数 | メンテナンスは高工数 |
| 空間計算量が大きい | 時間計算量が大きい |
ただ、このトレードオフを持ってどちらの推論にすべきか判断しきれない場合もあります。 そこで、別の観点から2つの推論スタイルを比較します。
その観点は、インプットデータに関するPeakednessとCardinalityです。 Peakednessは、インプットデータの分布がどれだけ集中しているかを意味します。Cardinalityはユニークなインプットデータのセットの数を意味します。
Cardinalityが低い、つまり限られたインプットデータのパターンしか想定されない場合は、静的推論で十分となります。 Cardinalityが高い、つまりインプットデータのパターンが多岐に渡り、かつPeakednessが高くない、つまり特定のインプットの割合が高いわけではない場合は、動的推論が必要となります。 実用的には、CardinalityもPeakednessも高い場合がほとんどです。その場合、頻度が高い特定のインプットについての推論は静的にキャッシュしておき、残りのロングテールの推論を動的に行う、というハイブリッドの推論方法が有力になります。
既出のユースケースについて、どちらの推論スタイルが適切か見てみましょう。
| ユースケース | 推論スタイル |
|---|---|
| スパムメールの検知 | 動的（Cardinalityは高く、Peakesnessは高くない） |
| スマーフォトンのVoice2Text機能 | 動的orハイブリッド（Cardinalityは高いが、挨拶など定型的な文句もあるのでPeakednessは比較的高い） |
| 広告のConversion Rate | 静的（Cardinalityは低い） |
終わりに
まさに全体像の把握に主眼が置かれていて、実際に使いこなすには足りず、受講後は実データで一度構築してみる必要があるな、と思わされる内容でした。
もちろん内容が悪いわけではなく、私のように局所的な学習を重ねてきた人間にとっては、各パーツをglueする感じでとても勉強になるものでした。
コース中のissueについて
コース中には、QwiklabsというGCPのコンソールや各サービスを触りながら構築を体験するカリキュラムがあるのですが、カリキュラムが古いようでいくつかエラーに遭遇しました。対処方法をメモしておきます。 尚、スタッフにエラーを報告したところ、対応は非常に迅速で的確だったことも付記しておきます。
Predict Babyweight with TensorFlow using AI Platform
train_deploy.ipynbの中で、ai-platformのtraining jobを実行するセルで、runtime-versionが1.4になっていますがdeprecatedのようです。1.14に変更する必要があります。
%%bash
OUTDIR=gs://${BUCKET}/babyweight/trained_model
JOBNAME=babyweight_$(date -u +%y%m%d_%H%M%S)
echo $OUTDIR $REGION $JOBNAME
gsutil -m rm -rf $OUTDIR
gcloud ai-platform jobs submit training $JOBNAME \
--region=$REGION \
--module-name=trainer.task \
--package-path=$(pwd)/babyweight/trainer \
--job-dir=$OUTDIR \
--staging-bucket=gs://$BUCKET \
--scale-tier=BASIC \
--runtime-version 1.14 \
-- \
--bucket=${BUCKET} \
--output_dir=${OUTDIR} \
--pattern="00001-of-" \
--train_steps=2000
Serving ML Predictions in batch and real-time
学習済みモデルをコピーしデプロイするところで、指定されているtensorflowのversionが合っていないようです。TFVERSIONを2.1に変更する必要があります。
REGION=us-central1
BUCKET=$(gcloud config get-value project)
TFVERSION=2.1
gsutil mb -l ${REGION} gs://${BUCKET}
LeetCode / Palindrome Linked List
最近、ニュースを見る度に過剰反応が報道されていていらついていたのでテレビを全く見なくなり、Youtube視聴に退避していたのですが、
ついに好きな旅行系Youtuberの方が投稿を休止される事態となり、残念、うんざりな思いが蓄積されていっている今日この頃です。
現実逃避に、LeetCodeの解説をします。
https://leetcode.com/problems/palindrome-linked-list/
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
左右対称のlinked listかどうか判定する問題。Follow upに書かれている空間計算量の制約をクリアするのが骨です。
解法1
空間計算量のことを忘れれば、逆順のリストを用意し、一致を見ればよいだけなので簡単です。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def isPalindrome(self, head: ListNode) -> bool: vals = [] while head: vals += head.val, head = head.next return vals == vals[::-1]
これでは手応えがないので、空間計算量をに減らす方法を考えます。
解法2
空間計算量をとする方法となると、必然的に1つ1つのnodeを走査する方法しかない、となります。
結論から言えば、以下の手順をとります。
- 真ん中のnodeを求める
- 真ん中のnode以降のlinked listを逆順にしたlinked listを得る
- 元のlinked listと2で得た逆順のlinked listが一致しているか確認する
class Solution: def isPalindrome(self, head: ListNode) -> bool: fast = slow = head # 1. 真ん中のnodeを求める while fast and fast.next: fast = fast.next.next slow = slow.next # 2. 真ん中のnode以降のlinked listを逆順にしたlinked listを得る rev_half_head = None while slow: tmp = slow.next slow.next = rev_half_head rev_half_head = slow slow = tmp # 3. 元のlinked listと2で得た逆順のlinked listが一致しているか確認する while rev_half_head: if rev_half_head.val != head.val: return False rev_half_head = rev_half_head.next head = head.next return True
特に手順2のlinked listを空間計算量で逆順にするところがややこしいのですが、これはもう覚えてしまった方が良いかなと個人的には思っています。
COVID-19についてFactを抑えよう
COVID-19について、データを扱う人間の端くれならFactは抑えておきたいなーと思っていたら素晴らしい報告書が。
内容もさることながら、地道な現地調査を遂行した調査団のご尽力には恐れいる。。
一番気になる致死率のチャートもあった。
- 累積では3.8%
- 流行初期は17.3%だったが2/1以降の発症では0.7%（致死率の減少は医療水準の向上によるものと推察されている）
- Wuhanでは5.8%に対し中国の他エリアでは0.7%
因みに以下論文によれば、中国におけるインフルエンザに起因する致死率は2003-2008は0.6-0.7%だったとのこと。
まあいくらFactを並べても、視界に入らない人はなぜか入らないので放っとくかと思っていたけど、
トイレットペーパーが売り切れるという謎の傍迷惑な現象を受けて、情報発信した方が良いのかと思い直す今日この頃。
というわけで、まだタイトルほどのFactは集められていないけど、少し漁ってみることとします。
ちなみに日本語記事もあるようですね。NHKグッジョブ。
LeetCode / Power of Two
https://leetcode.com/problems/power-of-two/
Given an integer, write a function to determine if it is a power of two.
Example 1:
Input: 1
Output: true
Explanation: 20 = 1
Example 2:
Input: 16
Output: true
Explanation: 24 = 16
Example 3:
Input: 218
Output: false
与えられた値が２の階乗かどうかを判定する問題。ビット演算を使った解法を初めて知ったときにはほーっと思いました。
解法1
ビット演算で解く方法。
2進法で表すと、2の階乗の値となるごとに桁が上がることを利用します。以下の通りですね。
0 0 1 1 2 01 3 11 4 100 5 101 6 110 7 111 8 1000
具体的には、値nとn-1をAND演算すると、nが2の階乗のときのみ0となることを利用します。3&4や7&8は0になりますね。
class Solution: def isPowerOfTwo(self, n: int) -> bool: if n == 0: return False elif n & (n-1) != 0: return False else: return True
解法2
シンプルなIterativeな解法も示しておきます。これでもTLEにはなりません。
class Solution: def isPowerOfTwo(self, n: int) -> bool: if n == 0: return False else: while n % 2 == 0: n /= 2 return n == 1
