記録帳

クラウド、データ分析、ウイスキーなど。

AWS Certified Solutions Architect - Professional に合格しました

皆さんこんばんは。夏も終わり、涼しくなってきましたね。
今回は、久々のAWS試験シリーズです。SysOpsをこの夏にとって、それ以降このProfessionalを勉強してきました。
先日試験を受けて、合格したのでその記録です。

AWS SAPとは?

aws.amazon.com

AWSのProfessional資格です。
結構難しいと評判です。
そして問題文が長く、試験を受けること自体が非常に疲れることでも有名な資格です。
(全75問で180分)

結果は?

803/1000で合格しました。(SAAと同じ点数…)
750点以上が合格なので、可もなく不可もなくというところでしょうか。

よく聞くように、「回答終了」のボタンを押す瞬間は落ちたと思いました。
というのも、自信をもって選べた問題が75問中10問くらいしかなかったためです。
時間についても、180分の制限時間でほとんど余りませんでした。そのため、見直しもほぼできず。
受かってよかったです。

やっておいた方が良いものは?

TechStock(通称koiwa-club)

TechStock|AWS WEB問題集で学習しよう

まずはこれ。というかほとんどこれしかやっていません。
大体どの合格記でも、この問題集の#30-を3周くらいやれと書いてあります。
私も意気込んでそれをしたのですが、勉強時間が足りず結局#30-54, #67-70を1周しかできませんでした…。
(途中から、#70からやり始めた)
勉強時間も合計30時間くらいで、圧倒的に足りなかったですが、運よく受かりましたね。

Black Belt

サービス別資料 | AWS クラウドサービス活用資料集
koiwa-clubで理解が浅いサービスが判明するので、その時はこれ。
公式だけあって、内容が充実しています。あと網羅的でよい。

サービス以カット以外でのおすすめはこれら。

20200722 AWS Black Belt Online Seminar AWSアカウント シングルサインオンの設計と運用
めくるめくSSOの世界を説明してくれています。
個人的に、IdPとアイデンティティが別のサービスで利用できるというところが目から鱗でした。

https://d1.awsstatic.com/webinars/jp/pdf/services/20210209-AWS-Blackbelt-DirectConnect.pdf
サービスカット意外といいつつ、がっつりAWS Direct Connectの資料ですが…
オンプレからVPCへの接続パターンを挙げてくれてるのがよかったです。

クラスメソッドさんのブログ

BlackBeltがいきなり詳細すぎたときは、クラメソさんブログで理解していました。
分かりやすい。とても分かりやすい。
個人的な推し執筆者が2人います。

チバユキさん
千葉 幸宏(チバユキ) | DevelopersIO
分かりやすいし詳しいし、何といってもAWS愛が伝わってきます。
高品質の記事を高頻度で出していて、それが無料。AWS界の吉野家ですね。

たまちゃんさん
たまちゃん | DevelopersIO
記事に取り上げるトピックが、自分の興味あるものばかり。(今回の資格勉強に限らず)
記事のタイトルで選んでいたら、「え、これもたまちゃんさん?え、これも??」みたいになりました。

HackMDでメモ&見返し

以下のように、自分で分からなかったところやポイントはメモって、見返していました。
自分で書くことで記憶が定着するのでおすすめです。
あと、いろんな媒体で見れるのも推しポイント。
PCで編集して、スマホタブレットで見返すこともできます。

おわりに

ということで、合格体験記でした。
業務でもバリバリ使っているAWSの上位資格を取れたのは良かったです。
これからは、専門知識の方のAWS Data Analyticsを取ろうかと思っています。
資格勉強は習慣化していきたいですね。それでは!

AtCoderコンテスト_ABC268_C-Chinese Restaurant解説

皆さんこんばんは。ABC268お疲れさまでした。
最近、C問題が難しくないですか?
今回も私は難しいと思ったのですが、時間内に何とか解けたのがうれしかったので、解説記事を出します。

C問題の概要

C - Chinese Restaurant

問題文は↑からどうぞ。
この問題は、結局のところ
「全ての料理p_iの中で、目の前の人の番号が、料理p_i自身の数-1~+1に収まっている個数が最大となるものを求めよ」
というものでした。

例えばこの場合。
赤文字の、料理は①で人が2の場合は、±1以内なのでOKです。
逆にそれ以外は、2以上離れているのでNGで、当てはまる合計数は1となります。

次に、このテーブルを反時計回りに1つずらしてみるとこうなります。
右上の料理が⓪で人が5の場合は5離れているように見えますが、料理⓪の-1はまた5に戻るようにするため、人5,0,1のどれかであればOKです。
今回の合計数は3となります。

このように考えたとき、合計数の最大値を求めるのが今回の問題です。
普通に考えると、テーブルを1つずつずらしていき、それぞれの合計数を求めていけば答えが出そうです。
ただ、そうすると計算量がO(N^2)となってしまいます。
今回、3 <= N <= 2 * 10^5 であるため、それだと計算時間に間に合いません。

解法

まず、例えばN=6の場合を考えます。
そして、料理が
[2, 1, 5, 0, 3, 4]
である場合を考えます。
こんな感じですね。
料理①の人1、料理③の人4、料理④の人5の3つが±1以内になっています。

さて、これを、2次元の表で表してみます。
横軸が料理の番号、縦軸が人です。
料理は[2, 1, 5, 0, 3, 4]であるため、そのセルが塗りつぶされています。
[2022/9/28追記 これ以降の縦軸と横軸について、人と料理が逆です。横軸が人で縦軸が料理番号となります。]

今回は料理の数の±1までOKなのでした。それを考慮して色を塗るとこうなります。

こうなった時、±1以内になっている料理というのはどれを指すでしょうか?
すでに±1までセルを塗っているので、今回の状況に当てはまるのは、料理と人が同じ番号であるとき、つまりは左上から右下に伸ばした直線上にセルが塗られていた場合です。

少し上に戻って、今回適しているのは3通りだったことを確認してみてください。
>料理①の人1、料理③の人4、料理④の人5の3つが±1以内になっています。
この3つが表で表現されていますね。

ここまでは、ある特定の場合のみでした。
今回の問題は、テーブルを逆時計回りに回転できます。
1回転させた場合がこちらです。

反時計回りのため、全体的に1列右にずらしています。
これも同じく線を引くと、2つの場合が±1以内になっています。

さらに1つずらすとこうなります。

つまり、このように1つずつずらしていって、左上から右下に直線を伸ばした時の数を数えて、一番多いものを出力すれば答えとなります。
ここからは、どうやってプログラムに落としていくかを考えます。

まず、1つずつずらすのはプログラムで表すのが難しいですよね。
どうにか、最初の初期状態の表から考えられないものか。。。
そこから、表全体をずらすのではなく、直線自体をずらせばよいのでは?という発想に行きつきます。
つまり、こういうことです。

こうすれば、初期状態を作ってしまえば、あとはこの直線をループで回せば処理できそうです。
ただ、この直線は斜めになっているため、いまいち扱いにくいですね。
なんとか横方向の直線にしましょう。

一つ上の図とよく見比べてみてください。
p_0の列はそのまま、p_1の列は1つ上にずらす、p_2の列は2つ上にずらす…とずらしています。
つまり、p_iの場合iだけ上にずらせばいいですね。
あとは、この直線の数(=人の数)だけループを回せば最大値を得られます。
以下に、自分が書いた実装載せておきます。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <numeric>
#include <iomanip> 
#include <string>
using namespace std;
#include <map>


int main()
{
    int n;
    cin >> n;
    int p[n+10];
    for (int i=0;i<n;i++) cin >> p[i];

    int table[n+10];

    // 表で表す
    for (int i = 0; i < n; i++) table[i] = 0;
    for (int i = 0; i < n; i++) {
        int p_0,p_1,p_m1;
        // 直線を斜めから横にするため、iだけマイナスする。
        p_0 = p[i]-i;
        p_1 = (p[i]+1)%n -i;
        p_m1 = p[i]-1 -i;
        // 0未満の場合の処理
        if (p_0<0) p_0+=n;
        if (p_1<0) p_1+=n;
        if (p_m1<0) p_m1+=n;

        table[p_0]++;
        table[p_1]++;
        table[p_m1]++;
    }

    // 最大値を調べる
    int M = 0;
    for (int i = 0; i < n; i++) {
    if (M < table[i]) M = table[i];
    }

    cout << M << endl;


}

atcoder.jp

感想

dpとかいもす法とかが頭の片隅に入っていて、とりあえず2次元の表で考えられないか、と考えるようになっていました。
そこで、なんとか表にして、ずらして、あとは足し算する方法を思いついて、きれいに整理できたので記事にしてみました。
Dの文字列のやつは全く解けなかったので、何とかDの領域も解けるようになっていきたいです。

いい加減なクオラム(sloppy quorum)を良い加減に説明する

意外と暑さが控えめになってきた8月上旬、皆様いかがお過ごしでしょうか。
今日は、みんな大好きデータ指向アプリケーションデザインの第5章レプリケーションより、いい加減なクオラム(sloppy quorum)について説明しようと思います。

理由としては、ここの内容が少しわかりにくいと感じたためです。また、日本語のネーミングがなんだかダサカワな感じで気に入ったからです。
まずはそもそものリーダーレスレプリケーション、クオラムの説明をして、いい加減なクオラムの内容を説明します。

リーダーレスレプリケーション

レプリケーションアルゴリズム(*)の一つです。

(*) レプリケーション
レプリケーションとは、他のノードに同じデータをコピーしておくことです。
(ノード:DBソフトウェアを実行している各マシンor仮想マシン
そうすれば、仮にそのマシンが壊れてもコピー先のデータは生きているので可用性が高まります。
他にも、レプリケーションを地理的にバラバラなところに作ることでそれぞれの地域のユーザーからの読み取りレイテンシを下げたり、コピーをたくさん作ることで大量の読み取りアクセスの処理を分散させることでスループットを高めたりといった効果があります。
ちなみに、コピーを保存する各ノードのことを、レプリカと言います。

そんなナイスなレプリケーションですが、3つのアプローチが存在します。
シングルリーダー、マルチリーダー、リーダーレスです。今回は、このリーダーレスレプリケーションのお話です。
他のアルゴリズムには、レプリケーションを先導するリーダー(最初に書き込まれるノード)が存在しますが、リーダーレスレプリケーションには存在しません。
クライアントは、書き込みを複数のノードに送信します。そして、読み取りも複数のノードから平行に行います。
そして特徴的なのが、書き込みの際にバージョン情報を持たせておくことです。
こうすることで、もし書き込みがいくつか失敗しても、読み取りの際に1つでも更新に成功した(=バージョンが新しい)ノードから読み込めれば、正しい値を取得できます。

ちなみに、この書き込みや読み取りを誰が行うかは、実装によって異なります。
クライアント側が複数のノードに書き込みや読み取りを行う実装もありますし、コーディネータノードというノードが行う実装もあります。
Amazonの内部で使われているDynamoというデータストア(DynamoDBとはまた別)がこのリーダーレスレプリケーションを採用しているということで有名らしいです。
Dynamoについては、この方のブログや
AmazonのDynamoDB論文を眺めた | Takuya Kitazawa

実際のDynamoの論文(の和訳)など読むと理解が深まります。
Dynamo: Amazonの高可用性Key-value Store[和訳] · GitHub

クオラム

さて、このリーダーレスレプリケーションでは複数のノードに書き込みや読み取りが行われます。そのため、各ノードが個別に書き込みに成功したり失敗したりします。結局、処理全体としてはどういうことが起きるのかを見ていきましょう。
例えば、このようにx=1の値をx=2に上書きするようなレプリケーションを考えます。

読み取り失敗

今回の例では、読み取りが成功したレプリカ1,2は書き込みが失敗しています。そのため、実際はx=2を書き込んだはずですが、x=1が読み取られてしまいます。これは、処理全体としては誤った読み取りになってしまいますね。では、どういう場合なら、処理全体として読み取りが正しく行えると保証できるでしょうか?

ここで出てくるのがクオラムという考え方です。
レプリカ数をn、書き込みに成功したノード数をw、読み取りに成功したノード数をr個としたとき、
n < w + r を満たすようにそれぞれの値を自身で決めます。
この時、

  • 書き込みに成功した = w個以上のノードに書き込みが成功した
  • 読み取りに成功した = r個以上のノードに読み取りが成功した

とみなします。このような書き込み、読み取りをクオラム書き込み、クオラム読み取りと呼びます。
このクオラム書き込み、クオラム読み取りでは、最新の書き込みが最低でも1つは読み取れることが保証されます。
n < w + r なので、w個の書き込み成功したノードとr個の書き込み成功したノードの集合のベン図が、最低1つは交わるイメージです。
それでは、そのクオラムの具体例を見てみましょう。今、x=3の値をx=4に上書きしようとしています。

クオラム

この例では、n=5, w=3, r=3 と決めています。n < w + r を満たしているため、最新の成功した書き込みが最低でも1つは読み取れます。実際、レプリカ3はx=4と書き込みに成功していて、読み取りにも成功しています。
この時、(成功した読み取りのうち、2つがx=3で1つがx=4となっていて、どれを最終的な値として決めるんだ?)と思った方、ごもっともです。ここは何かしらの方法で、値を1つに決める必要があります。

例えば1つの方法として、書き込んだ値にバージョンを持っておく、という方法があります。
今回の例でいうと、x=3が書き込まれる前の状態なので、この状態をversion=1としましょう。その後、x=4が書き込まれたとき、version=2にします。
そうすると、読み取りが成功した3つは
[x=3, version=1] ,[x=3, version=1] ,[x=4, version=2]
となり、この中で一番versionが大きいものを選択すれば、正しい値を取得できますね。

このように、n, w, rの値を決めて、w,rの数だけ書き込み、読み取りが成功すれば処理全体を成功とするやり方がクオラムでした。
であれば、このクオラムの考え方を用いれば最強卍なのでしょうか。
ここからが、いよいよ分かりにくい「いい加減なクオラム」です。

いい加減なクオラム(sloppy quorum)

クオラムの考え方を用いれば、必ず1つは最新の書き込み成功したノードを読み取れました。
ただ、逆に言えば、w個の書き込み、r個の読み取りが成功しなければ、処理全体は失敗するわけです。
これは、可用性の面で問題になります。そこで出てくるのが、いい加減なクオラムです。
いい加減なクオラムを使うと、書き込みの可用性が上がります。具体例を見てみましょう。今回は、最初の具体例(誤った読み取りされてしまった例)を、いい加減なクオラムを使った場合どうなるかを見ていきます。少し複雑なので、3ステップに分けてみていきます。

STEP1. 書き込み

step_1

まずは書き込みです。レプリカ1~4は障害発生中でアクセスできません、そのため書き込みが失敗しています。
そして、いきなり右側に領域展開されたのは、レプリカとはまた別のノードたちです。いい加減なクオラムでは、n個のレプリカ以外にも書き込みを受け付けることができます。今回は別領域のノード2つに書き込みを試み成功しているため、w=3となり書き込み処理全体が成功となります。本来のレプリカの中であれば、書き込み成功したノード数は1でw=3を下回るため書き込み処理全体は失敗するはずですが、いい加減なクオラムにより成功となりました。これが、可用性向上といわれている所以です。

ただし、注意すべきは「wの数以上書き込みが成功すれば、書き込み処理全体として成功」というルールは引き続き適用される、ということです。別領域を使ったとしても、それは変わりません。
そのため、別領域のノードに書き込みに行ったが、別領域ノードが全て落ちていて書き込みが全て失敗した場合は、全体で成功した書き込みはレプリカ5の1つのままであるため、書き込み失敗となります。

STEP2. ヒント付きのハンドオフ

step_2

次は、ヒント付きのハンドオフです。一時的に書き込んでいた別領域のノードを本来のレプリカたちに転送します。
障害が起きていたレプリカ1~4のうち、レプリカ3,4は復旧したとします。その時、一時的な領域に保持していたx=2をレプリカ3,4に転送します。
こうすることで、n個のレプリカの中でw=3という条件が満たされたことになります。

また、ここでいう「ヒント」とは、「本来はどのノードに送られるべきだったか」という情報のことを指します。
STEP1で別領域のノードにx=2を書き込んだ際、じつはその値とともに「本当はレプリカ3に書き込む予定でした」という情報もメタデータとして持たせています。それをもとに、レプリカ3の状態を定期的に確認し、復旧が確認出来たらx=2をレプリカ3に転送します。

STEP3. 読み取り

step_3

最後は読み取りです。ここは別領域とは関係なく、n=5のレプリカを対象に読み取りします。別領域に読み取りに行くことはありません。
今度はレプリカ4,5が障害を起こして読み取りが失敗、レプリカ1~3の3つが成功したとします。r=3を満たしているので、読み取り処理全体も成功となります。レプリカ3を読み取っているので、最新のx=2という値を正しく読み取れていますね。(x=1が2つ、x=2が1つ読み取れていますが、先ほどの方法と同じくversionを付けて書き込んでいたため、最新のx=2を判別できたとします)

以上が、いい加減なクオラムの仕組みです。ただ、いい加減なだけあって、通常のクオラムでは起き得なかった問題が起きます。

いい加減なクオラムで起きる問題

別領域のノードに書き込めるとは言え、それは一時的な対応です。本来のレプリカはn個であり、読み取りもこのn個のレプリカを対象に行われます。そのため、ヒント付きのハンドオフが実施される前に読み取りが行われた場合、古い値を読み取ってしまう可能性があります。

例えば、先ほどのSTEP1が終わって(別領域のノード2つも含めて書き込みが成功した)すぐに、レプリカ3,4が復旧して、さらに読み取りも行われてしまった場合です。

いい加減なクオラムで生じる問題

ヒント付きのハンドオフが行われる前であるため、レプリカ3,4には古い値x=1が格納されています。この状態でレプリカ1~3で読み取りが成功すると、r=3以上のため読み取り処理全体として成功しますが、x=1が取得されてしまいます。
このように、いい加減なクオラムを使うと、障害発生/復旧タイミングによって古い値が読み取られてしまう可能性があるのです。

まとめ + ユースケース

リーダーレスレプリケーションでの書き込み、読み取りの方法として、クオラム書き込み/クオラム読み取りという手法がありました。
これは、n < w + rを満たす書き込み、読み取りで、少なくとも1つは最新の値を読み取ることが保証されます。
ただ、その保証の裏返しとして、w個の書き込み、r個の読み込みが成功しないと失敗してしまいます。
一方で、いい加減なクオラムではn個のレプリカとは別の領域のノードを一時的に書き込みのノードとして利用できました。その後、一時的な書き込みのノードからn個のレプリカにヒント付きのハンドオフで転送します。
この方法を用いることで、書き込みの可用性は向上します。しかし、読み込みに最新の値が含まれる保証はありません。

上記を考慮してユースケースを考えてみます。
クオラムは値の正確性が必要な場合に使えそうです。例えば、オンラインショッピングでカートに入っている商品の一括購入など。「最後に削除した100万円のツボの削除処理がまだ反映されていなかったので購入しました」ということは避けなければなりません。

いい加減なクオラムは、書き込みの可用性が必要な時に使えそうです。例えば、twitterのTLの読み込みなど(使われているかは知りません)。「1秒前にAさんがつぶやいた「風呂なう」というツイートが読み込めていないため、TL全体の表示もエラーとなります」となってしまうと、ユーザー的には使いにくくなってしまいます。

以上、いい加減なクオラムの説明でした。
間違っているところなどありましたら、ぜひご指摘ください。

Python用ネガポジ分析ライブラリ「oseti」をWindows+Docker Desktop+jupyter notebookで動かす

梅雨が明けたっていうのに、微妙に雨模様ですね。という季節の挨拶からこんばんは。
皆さんは、もう何年もやり取りをしているLINEグループなどはありますでしょうか。
私はあります。5年間、ほぼ毎日発言しているLINEグループです。
高校の頃の友人とのグループなのですが、しょうもない話を永遠としております。

さて、そんなLINEグループでやりとりをしていて、ふと
「めちゃくちゃ発言数がたまってるから、これを何かデータ分析できないか…」
と考えました。
まずは、人別/月別で発言のネガティブ・ポジティブ判断をして、違いを見てみよう!ということで、
簡単に使えるネガポジ判定モデルがないかなと探しておりました。

そこで、osetiという神ライブラリに出会いました。
日本語評価極性辞書を利用したPython用Sentiment Analysisライブラリ oseti を公開しました - Qiita
ただ、導入に少し手間取ったので、備忘録も含めて爆速で実行環境をセットアップする方法を書き留めておこうと思います。

osetiとは

ネガポジを判定してくれる、pythonのライブラリです。
ネガポジを判定するには、まず教師データがいりますが、osetiではこちらの日本語評価極性辞書を利用しているそうです。
Open Resources/Japanese Sentiment Polarity Dictionary - 東北大学 乾研究室 / Inui Lab, Tohoku University

使い方はかなり簡単で、importして評価したい文を以下のように記載するだけです。
最大1.0~最小-1.0でポジティブ、ネガティブ度を判定します。
評価したい文が2文以上ある場合は、1文ずつのスコアを返します。(例の2つ目)

import oseti

analyzer = oseti.Analyzer()
analyzer.analyze('天国で待ってる。')
# => [1.0]
analyzer.analyze('遅刻したけど楽しかったし嬉しかった。すごく充実した!')
# => [0.3333333333333333, 1.0]

実行環境

OS:Windows 10 Home
バージョン:21H2

Docker Desktopはインストール済み。
バージョンは以下の通り。

docker_env

実行方法

① Dockerfileとdocker-compose.ymlを作成する

以下の2つの内容をコピペして、適当なworkディレクトリ配下に2つのファイルを作成してください。

FROM python:3.9

WORKDIR /app

SHELL ["/bin/bash", "-c"]

RUN apt-get update
RUN apt-get install libmecab2 libmecab-dev mecab mecab-ipadic mecab-ipadic-utf8 mecab-utils
ENV MECABRC "/etc/mecabrc"

RUN pip install --upgrade pip 
RUN pip install notebook pandas matplotlib oseti

version: '3'
services:
  app:
    build: .
    volumes:
      - ./:/app
    ports:
      - 8888:8888
    tty: true

② コンテナに入る

PowerShellを開いて、①のworkディレクトリに移動してください。
その後、以下の2つのコマンドを実行しましょう。
1つ目のコマンドがdockerのコンテナを作成、2つ目がそのコンテナへ入るコマンドです。

docker-compose up -d
docker-compose exec app bash

③ コンテナ内でjupyter notebookを実行する

PowerSellでコンテナ内に入れているので、あとは以下のコマンドを実行すればjupyter notebookが立ち上がります。
osetiに必要なライブラリや、oseti自体もすでに入っているのでそのままosetiが使えます。

jupyter notebook --port=8888 --ip=0.0.0.0 --allow-root --NotebookApp.token=''

④ ブラウザからjupyter notebookに接続する

コンテナ内で起動しているjupyter notebookですが、docker-compose.ymlでコンテナ内のportとホストのportをつなげてあります。
そのため、ホストOS(今回はwindows)のブラウザから、以下のurlに接続すればアクセスできます。
http://localhost:8888/

そこで、最初の例を実行すると、見事にosetiが使えています。

oseti_notebook

ハマったところ

大きく2つハマりました。

1つ目は、Windows特有の問題です。
始めは、dockerではなくWindowsのJupyterLab Desktopという、Windowsのアプリ上で実行しようとしました。
そうすると、c++のライブラリがないとか、Mecabの辞書がないとか、エラーが絶えず断念しました。
やっぱりDocker最強!!!

2つ目は、Mecabの問題です。
osetiは内部でMecabを使っているので、そちらをインストールしています。
しかし、ただインストールするだけだと、osetiを実行したときに
no such file or directory: /usr/local/etc/mecabrc
というエラーが出てしまいました。
mecabrcはMecabの設定ファイルで、デフォルトで使う辞書などを指定できます。
Mecabをインストールすると作成されるのですが、これが/etc直下にできているので、上記のようなエラーが出ます。
対処法としては、環境変数で/etc/mecabrcにパスを通してあげることです。Dockerfile内でそれをしています。

おわりに

ということで、久々の備忘録記事でした。
今回色々な記事を参考にしましたが、完全に同じ状況というのがなかなかなかったので、私以外の人類の誰か1人にでも役立てばうれしいです。
色々試行錯誤したことをDockerfileにまとめれば、それをそのまま利用できるので、再現性という意味でやはりDocker最強ですね。

競プロという名の光

最近溶けそうなほど暑いですね。こんばんは。
そんな中、最近競プロ(AtCoder)始めてみました。いつまでやるかは未定です。
そこで、AtCoder始めたぜ記念カキコと、昨日解けなかったB問題の解説をしようと思います。

競プロ始めてみた件

理由

何かコンペをしたい!という欲求が湧いてきたため。
今までだったらkaggleをやっていたのだけど、
・基本チーム戦
・結果出るのが数か月と長い
・潤沢なリソースがない
という理由から、ちょっと最近出るのがおっくうになっていました。

そこで、2時間くらいで終わるし、なんかプログラミング出来たらカッケーな!
と思い、参加しました。
あ、C++の練習にもなるかな、という理由もありました。
なぜC++の練習をしたかったかというと、かっこよいからです。

大変なところ

まず、ABCという初心者歓迎コンテストに出場する時間を確保するところが大変。
毎週土曜日の21時スタートなのですが、基本土曜日というのは飲み会が入ります。
そのため、飲み会はすべて金曜日に実施するか、早く切り上げて酔ったまま参加することになります。
これは、学生の頃やっておきたかった。それか、土曜の朝にやってくれないかな。

あとは、比較的ハードルは低いかなと思います。
C++デバッグ環境も、ググればいろいろヒットします。これとか参考にしました。
【VScode+WSLで始める】競プロ用C++デバッグ環境構築 - Qiita
(私は、このやり方だとincludeパスをうまく読み込めなかったので、Remote – WSLを使う方法に一部修正しました)

ただ、これはまだ私は来ていないですが、モチベ管理が大変なのだろうなと思います。
最初の色の茶色であっても、10回程度コンテストに出ないとなれないそうです。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編:競プロを始めよう】 - Qiita

今までの戦歴

ABC 256 : ABC
ARC 142 : nothing
ABC 257 : A
ARC 143 : A
という、輝かしい成績です。

どのコンテストも、最後解けなかった問題は、解法は思いついているんだけどもプログラミング的にアウトという感じでした。
例えばABC 256は、繰り返す試行の途中の状態の持ち方を複雑にしてエラーが起きて通らなかったり、
例えばARC 142は、long longの型で扱えばよかったものintやらdoubleやらでずっとこねくり回していたり…

まぁ、このあたりは経験積んでいくしかないですかね。
とりあえずは、茶色を目指して基本的な問題を取っていく方針です。
ということで、今回は昨日のB問題を解説しようと思います。(これも、プログラミング的に知っておくべきことがあったので)

ARC143 B問題の解説

問題

B - Counting Grids

N×Nのマス目の各マスに1からN^2までの整数を1つずつ書き込む方法であって、どのマスも以下の条件のうち少なくとも一方を満たすようなものの個数を998244353で割ったあまりを求めてください。
・そのマスに書かれている数より大きい数が書かれているマスが同じ列に存在する。
・そのマスに書かれている数より小さい数が書かれているマスが同じ行に存在する。

制約:1 <= N <= 500

このような問題でした。
まず最初に見たとき、998244353ってなんや…暗号か?と思いました。

解答方針

[ARC143] B - Counting Grids|syamashi|note
この方の考え方が分かりやすいです。
軽くまとめると、問題文の中の「少なくとも一方を満たすようなものの個数」というのを直接数え上げるのは面倒(or条件だから)なので、余事象を考えます。
そうすることで、問題文の2つの条件のand条件の個数を求めて、全通り(N^2の階乗)から引けば答えが出ます。

この方針は何となくコンテスト中にできていたんですが、、途中の数が大きすぎてlong longでも収まらなくなりました。さぁ大変。
そこで、今後も覚えておくべきポイントとして、2つをここに書き記します。

知っとこポイント①:modの世界

1つ目は、modの計算についてです。
mod自体は私も知っていました。何かで割った時のあまりですよね。
11 ≡ 3 (mod 4)
です。11÷4をしたとき、余りは3なので。

ただ、桁数が大きすぎるものを扱うときに、modを使うのがプログラミングの世界では常識らしいです。
イメージとしては、10^10と10^11をかけると、10^21ですよね。
AtCoderにおいて、最強の型であるlong long型ですが、これでも10^19くらいまでしか扱えません。つまり、上の計算式は普通にやるとオーバーフローします。
ではどうするか。

10^10と10^11を掛け合わせる前に、それぞれmod 998244353 を取ります。
10^10 ≡ 17,556,470 (mod 998244353)
10^11 ≡ 175,564,700 (mod 998244353)

そして、それらを掛け算して、さらにmod 998244353を取ります。
17,556,470 × 175,564,700 = 3,082,296,388,609,000 ※ この数は非常に大きいですが、10^15オーダーなのでlong longに格納可能です。
3,082,296,388,609,000 ≡ 329,696,899 (mod 998244353)

そうして出てきた329,696,899という数字、これは何と 10^21のmod 998244353を取った数と等しいのです!!
つまり、mod 998244353を最後にどうせ求めるなら、途中の式もmod 998244353を取っておくとオーバーフローせずに計算できちゃうということです。

今は掛け算でやりましたが、足し算と掛け算はそのまま途中をmodとっても結果が変わりません。
ただ、引き算と割り算(特に割り算)はちょっと注意が必要です。
そのあたりの細かいことは、この記事がめちゃくちゃ参考になりました。この記事ではmodを別の数で取ってますが、考え方は一緒です。
コンテスト中、「998244353」でググったらフーリエ変換とか出てきて泣きそうでしたが、この記事で救われました。
「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 - Qiita

覚えること
10^19を超えるような数を扱うときは、modを使って計算しちゃおう!

知っとこポイント②:順列、階乗の計算

さて、こっちはどちらかというと実装ではまった点。
この問題を解くとき、順列や階乗の計算をします。
階乗は、5! = 5*4*3*2*1 などすべて掛け算だけで表せますね。
ただ、順列は公式通り考えると、n P r = n! / (n-r)! となります。そのため、実装で割り算を使います。
以下の記事がその実装を解説しています。
【基本C++】順列のプログラム - Qiita

これを使ってしまうと、ポイント①で触れたようにmodを考える上で注意が必要な割り算が出てきてしまいます。
その場合、ポイント①で参考に挙げた記事内に実装がありますが、さらにforループを回す必要が出てきてしまいます。
そのため、コードは複雑になり(順列のメソッドの中に、modの割り算をするような処理を加える)、forループが追加で入るので計算量も増えます。

ということで、順列の実装はこちらの方法を代わりに使いました。
こちらは、割り算ではなく、forループを後ろから考えることで掛け算だけで済ましています。
確かに、例えば7P3なら7*6*5で後ろから掛け算していけば終わりですよね。
【C++】順列を求めるプログラム - Qiita

覚えること
順列の計算は、掛け算だけで行おう!

自分の回答

私は前者の方法で最初実装していて、TLE(制限時間の2秒以内に計算が終わらない)になってしまいました。
ただ、後者の方法に変えたら、AC(すべてOK)になりました。

ACしたコードを載せておきます。自分用ですが、コメントとかもきれいにつけてみました。
ただ、おそらく競プロerの常識とは違う書き方になっているはず。
Submission #32801198 - AtCoder Regular Contest 143

・こう書いた方がより良いよ
・計算量のオーダーがこれからこれに変わったからTLEがACになったんだよ

というコメント、あれば非常にうれしいです。お待ちしております。

おわりに

ちょっと散文チックな記事になってしまいました。
昨日の復習をしていて、modで計算することに少し感動したので、こうして記事にしてみました。
こういうの、情報系の人なら大学で学ぶんだろうか。
kaggleもそうだったけど、全くの初心者から中級者になるとき、誰かコーチしてくれる人がいると効率が段違いだなぁ、とひしひしと感じております。
ただ、AtCoderは書籍とかブログも充実してるので、kaggleよりはやりやすそう。
とりあえず飽きるまでは、頑張っていきます。

UnicodeとUTF-8ってどういう関係があるんだっけ…夏。

最近暑い日が続きますね。皆さんいかがお過ごしでしょうか。
今日は、毎回ググるけど分かった気になって終わってしまう、文字コード関連です。
その中でも、UnicodeUTF-8の関係について記載していこうと思います。

まずは文字コードについて軽く説明をして、そしてUnicodeについてを解説します。
今回は、この本の内容から一部抽出してまとめています。

文字コードとは?

文字集合

文字コードの前に、まずは文字集合です。
文字集合は、文字を重複なく集めた集合のこと。
例えば、以下はひらがなの文字集合です。
これ以外にも、常用漢字文字集合やアルファベットの文字集合など、色々な文字集合があります。

ひらがなの文字集合

文字コード

では、文字コードとは何か。
文字コードは、文字集合の各文字に対するビット組み合わせを一意に定めたものです。
(符号化文字集合とも言います)
例えば、上で示したひらがなの文字集合に対してビット組み合わせを定めた、My文字コードが以下です。

My文字コード

これがPCに実装されていたとしたら、
ビット組み合わせで「000101」「000110」「000111」と入力されたら、「おかき」という文字列が生成されます。

ASCII

その文字コードの中でも、最も基本的なものはASCII(American Standard Code for Information Interchange)です。
ASCIIは7ビットの1バイト文字コードです。つまり、2^7で128個の文字が定められます。
ただ、このすべてに文字が割り当てられているわけではないです。

ASCIIの文字コードは以下です。
英数字の大文字小文字といくつかの記号が割り当てられていますね。

ASCIIの文字コード

https://www.pahoo.org/e-soul/webtech/encode/encode02-01.shtm

このように、ある文字集合があり、それにビット組み合わせを一意に決めたものが文字コードで、色々な種類があります。

UnicodeUTF-8/16/32の関係は?

Unicode

さてここまでで文字コードについてが分かりました。
「じゃあUnicodeってのは文字コードなんだね?!その亜種がUTF-8なのかな?!」
と思うかもしれませんが、落ち着きましょう。
Unicodeは、厳密には文字コード(符号化文字集合)ではありません。
wikipediaには、以下のような記載があります。

Unicodeユニコード)は、符号化文字集合文字符号化方式などを定めた、文字コードの業界規格。文字集合(文字セット)が単一の大規模文字セットであること(「Uni」という名はそれに由来する)などが特徴である。

つまりどういうことだってばよ?と思っていると思います。
私なりの解釈ですが、つまりUnicodeとは、
世界のあらゆる文字を集めた文字集合に対して、それぞれ番号を割り当てた集合
です。ビット組み合わせではなく独自の番号を割り当てているので、文字コードではないのです。

また、Unicodeはめちゃくちゃたくさんの文字を扱っています。先ほどのひらがなであれば2次元の表で表せましたが、Unicodeはなんと4次元で文字と番号を表します。
その4次元とは、群/面/区/点です。4つを指定すると、文字が一意に決まるわけです。
その4つを指定するとき、Unicodeの番号だよということでU+を頭につけて指定します。
例えば、U+306Cは「ぬ」を表します。

UTF-X

Xには8,16,32が入りますが、これは何なのか。
全て、Unicodeで表した番号をビット組み合わせに変換する方式のことを言います。
その変換する方式の違いで、8,16,32が分かれています。

例えば、先ほどの「ぬ」はUnicodeではU+306Cでした。
それが、UTFシリーズでは以下のようなビット組み合わせに変換されます。(16進数で記載)
UTF-8:E3 81 AC(3バイト)
UTF-16:30 6C(2バイト)
UTF-32:00 00 30 6C(4バイト)

さて、それぞれを軽く説明していきます。
先に言っておくと、UTF-32が一番楽に計算できます。次点がUTF-16。一番複雑なのがUTF-8です。(個人の感想)

UTF-32

UTF-32は4バイト固定です。一番容量を食います。
さて、UTF-32は簡単です。Unicodeの番号をそのままビット組み合わせにしたものが、UTF-32です。
Unicodeは群/面/区/点の4次元で文字を指定していると言いました。つまり、4バイトあれば文字を指定できます。
UTF-32は、4バイト確保しているので、そのままビット組み合わせとして指定できるのですね。
「ぬ」の例でも、U+306Cを「00 00 30 6C」と変換していました。そのままですね。

UTF-16

UTF-16は、基本2バイトなんですが一部4バイトになります。
「基本」と書いたのは、Unicodeの中のBMP基本多言語面)に当たるものは2バイトで示せ、それ以外は4バイトになるからです。

はい、BMPの説明をします。
元々Unicodeは、16ビット(2バイト)の組み合わせで生まれました。つまり、2^16通りの文字が表せますね。
ですが、途中で「あかん、これだとたりーん!」となってしまったわけです。
なので、32ビット(4バイト)に拡張しました。
ただ、大体主要な文字は16ビット(2バイト)で表せていたんですね。日本語とか、英数字とか。
そのため、主要なこの16ビット(2バイト)の組み合わせを、BMPと言います。
BMPは2バイトの組み合わせで表現可能なので、群と面が00、00固定となります。

BMP以外の文字の例は、よくこの ほっけ と読む文字が出てきます。
𩸽
これは、Unicodeで言うと「U+00029E3D」になります。群は00ですが、面が02となっています。つまり、BMP外の文字ですね。

さて、UTF-16の説明に戻ります。
このBMPに入っている文字であれば、Unicodeの番号をそのままビット組み合わせに変換できます。
つまり、BMP内であればUTF-16UTF-32も同じ(UTF-32は1,2バイト目が00 00になりますが)です。

では、BMP外の文字を表すとき…その時は、サロゲートペアという仕組みを使います。
この仕組みは、詳しく知りたい方はこの本を買うかググってください。

UTF-8

ラスボスのUTF-8です。
これは、1~4バイトで文字を表します。一番容量がお得な文字コードです。
「ぬ」の例でもありましたが、UTF-8Unicodeの番号と同じようにあらわせません。
そのため、一番複雑です。

UTF-8:E3 81 AC(3バイト)
UTF-16:30 6C(2バイト)
UTF-32:00 00 30 6C(4バイト)

ざっくりいうと、Unicodeの番号をあるルールに則ってUTF-8のバイト列に変換できます。
それが、以下の表です。

UTF-8の変換表

例えば、「ぬ」をUTF-8に変換してみましょう。
Unicodeでは「U+306C」でした。306Cはこの表で言うと3行目に当たりますね。
では次に、306Cは16進数なので、それを2進数に変換すると、こうなります。
0011000001101100
さらにそれを表の右側のバイト列のxに当てはめると、こうなります。
1110xxxx 10xxxxxx 10xxxxxx

11100011 10000001 10101100
さらにさらにこれを16進数したら…「ぬ」のUTF-8でのバイト表現の完成です!
E381AC

ここで確かめてみましたが、合ってそうですね。
【みんなの知識 ちょっと便利帳】URLエンコード/デコードツール = UTF-8

UTF-8変換ツール結果

まとめ

  • ある文字を集めた文字集合に対して、一意のビット組み合わせを割り当てたのが文字コード
  • Unicode文字コードではない。大量の文字に対してそれぞれ番号を割り当てた集合のこと。
  • UTF-8,16,32はそのUnicodeの番号をビット組み合わせに変換する方式。
  • UTF-32は、Unicodeの番号をそのままビット組み合わせにすればOK。
  • UTF-16は、BMPの文字はそのまま2バイトで表せるが、それ以外の文字はサロゲートペアという仕組みで4バイトで表す。
  • UTF-8は、Unicodeの番号をある規則で1~4バイトに変換する。

思ったこと

UTF-8は効率よく文字を表現するためによく使われているのだと思うが、今のメモリが大量に使えるこの時代、全てUTF-32で良いのではないか?と思った。
まぁでも、人間がいちいちUTF-8の計算をするわけでもないし、PCが効率よくさばける方が価値が高いのかな。
とりあえず、UnicodeとUTFシリーズの関係性は理解できた。

TCP/IPを理解する

クラウド、データ分析の熱が落ち着いて、「基本的なITの知識を知ろう」のターンが回ってきました。
となると、手を出すのはネットワークですよね。
積読になっているこの本を読んで、ざっくり理解したので記事にします。

TCP/IPとは何か?

TCP/IP」という言葉は2つの意味を持ちます。

  1. TCPとIPという2つのプロトコルのこと。
  2. TCPやIPを使うときに必要になるプロトコル群の総称のこと。

そもそもプロトコルとは、コンピュータ同士で通信する際の手順や規格、つまりは約束事のこと。
IPやTCPというプロトコルがある(そもそもIPもTCPも最後のPはProtocol)一方で、それらはインターネットにおいて代表的なプロトコルであったため、それらに関係あるプロトコル群も含めてTCP/IPと呼ぶようになったようです。

例えるなら、マクドナルドの「ハンバーガー」ですかね。
メニューとしてのハンバーガーもあれば、バーガー系を総称してハンバーガーとも呼ぶ。そういうノリでしょうか。

ちなみに、2つ目の意味で言ったときに含まれるほかのプロトコルは、以下のようなものがあります。

なぜTCP/IPは普及したのか?

今では一般的に使われているTCP/IPですが、数あるプロトコルの中でなぜこれが爆発的に普及したのでしょうか。
それは、この2つが大きな原因でした。

  • パケット通信に対するモチベがめちゃくちゃ高かったため
  • UNIXがめちゃくちゃ普及したため

パケット通信に対するモチベ

1960年代の軍事技術が始まりでした。軍事的に、戦場の人々に作戦を伝えるための通信は非常に重要です。
さらに、通信ルートを誰かが壊しても、別ルートで通信できること(今でいう可用性)が非常に重要でした。
確かに、それが自分の生死に関わるとなれば必死に研究しますよね。
またその後、軍事利用でなくとも、回線コストを下げる目的でも活発に研究されたそうです。
パケット通信ができれば、複数のユーザーが1つの回線を共有できます。これができないと、それぞれのユーザがそれぞれ専用線を引かないとやり取りできません。

さて、このようなモチベーションから、なんやかんやあって1975年にTCP/IPは誕生しました。誕生してからも具体的な仕様は検討が続き、結局1982年にTCP/IPの仕様が決まりました。
このとき、TCP/IPを生み出したのは大学や研究機関でした。同じくこのころ、大学や研究機関が開発して利用していたもの…それはUNIXというOSです。
そのため、UNIXにはTCP/IPが実装されるようになりました。これが、次の理由につながります。

UNIXの普及

1980年代は、各企業を中心にUNIXマシンをつなげてやり取りすることが広まっていった時代です。
そのUNIXにはTCP/IPが実装されているので、ネットワーク構築にはこのTCP/IPを利用するのが自然ですよね。
このようにして、TCP/IPUNIXとともに普及していったのでした。

ちなみに、このころ(1980年代)からTCP/IPによる世界的なネットワークをインターネットと呼ぶようになりました。
その後は、1990年代に入って一般家庭にもインターネットが普及していきます。利用者数は爆増しましたが、TCP/IPは研究ネットワークとして長い間運用され磨き上げられていたおかげで、利用することができています。

IPの具体的な約束事とは?

大きくは以下の3つです。

  1. IPアドレスというアドレスを用いる
  2. 経路制御(ルーティング)でパケットを終点ホストまで届ける
  3. IPパケットは分割、再構築する

IPアドレスというアドレスを用いる

これは、馴染みのある言葉だと思います。ネットワーク層であるIPでは、IPアドレスを用いて通信します。
IPアドレスの形式は、ホスト利用するデータリンクの種類によらず、同じ形式です。
(データリンク:ネットワーク層より1つ下の層。現在はイーサネットが主流)
今後、別のデータリンクが出てきても関係なくIPアドレスは利用できます。つまり、うまく抽象化ができているということです。

経路制御(ルーティング)でパケットを終点ホストまで届ける

この仕組みを使うことで、自宅から地球の裏側のブラジルのサーバまでパケット通信ができます。
そもそも、インターネットは全世界にあるたくさんのルータをバケツリレーのようにして通信しています。
そのルータは膨大な量あり、かつどんどん変化します。なので、最初から「ブラジルまでのルートは、ルータA→ルータB→…」と決められません。

そのため、ルーターごとにルーティングテーブルという表を持たせておきます。
ルーティングテーブルとは、「最終地点がxxであれば、次はルーターXに飛ぶ」という対応表です。
パケット通信をする際は、各ルーターのルーティングテーブルを見て、次はどのルーターに飛ぶかを適宜判断して、進んでいくのです。

IPパケットは分割、再構築する

パケット通信に利用するデータリンクには、最大転送単位(MTU)というのが定められています。
つまり、送信する際の最大の容量が決まっているということです。パケットがそれより大きいと、本来は送れません。
そこで、ルーターでパケットを分割して送り、最後に受信したホストが再構築して元通りにします。
ちなみに、ルーターは分割だけして、再構築は行いません。

ただ、できれば分割はしたくないのが本音です。分割すると、そのうちの1つでもかければ復元できないからです。
そのため、できるだけMTUに引っかからないギリギリの大きさで送りたい。そのギリギリの大きさを特定するために、経路MTU探索という技術が使われています。
これは、最近では多くのOSで利用されています。

TCPの具体的な約束事とは?

大きくは以下の5つです。
TCPについては少し細かいので、それぞれの内容の説明はここには書きません。
ただ、IPがとにかく相手ホストへ届けるための約束事だったのに対して、TCPきちんと届けるための約束事である、という点が重要です。

  1. ポート番号という番号を用いる
  2. 途中でパケットが喪失した場合再送させる
  3. 分割されたパケットの順序を制御する
  4. 通信相手がいるかどうかコネクションを制御する
  5. ネットワークが混雑しないようにパケットの送信料を調整する

TCPUDPの違いは?

どちらもトランスポート層プロトコルですが、一長一短があります。
そのため、利用目的に応じて使い分ける必要があります。
一言でいうと、TCPは信頼性のある通信を提供し、UDPは信頼性よりも速い通信を提供します。

この違いは、人と人とが対話するIP電話やテレビ電話を使うとわかりやすいです。
TCPはコネクション型(相手の応答を待ってから通信開始する)で、かつデータが途中で失われたときに再送処理を行ってくれます。
IP電話に利用すると、音声の再生がスムーズにいかず遅れが生じたりします。その代わり、音声品質は高いです。
UDPコネクションレス型(相手の応答確認せず通信開始する)で、再送など細かい処理はアプリケーションが担います。
IP電話に利用すると、多少パケットが失われて音声が乱れる場合がありますが、遅延は起こらず会話ができます。

このように、IP電話やテレビ電話といったリアルタイム性を重視する場合はUDPが適しています。
逆に、youtubeの動画再生など数秒遅延しても良い場合は、TCPが適しています。

所感

なんとなくTCP/IPやインターネット、イーサネットなどの言葉を使っていましたが、だいぶ理解が進みました。
特に「プロトコル」というのがずっとふわふわしていましたが、利用するアドレスの種類やヘッダフォーマット、再送やコネクションの確認方法など約束事の集合体だと理解すれば腑に落ちました。

また、初期のころ別々の規格で作っていて通信できなかった→標準化で楽にできるようになった、という流れのところは、データのサイロ化にも適用できないかな?と思いました。
今は、データがDBに入っていたりストレージに入っているという違いや、csv、parquet、ただのファイルといった違いでうまくやり取りできていません。
これらをETLなどで処理していますが、標準化することでスムーズに流通させられないものか…。これがSnowflakeの目指している世界なのかもしれません。

あとは、TCPUDPの違いは分かりやすく説明されていたかなと思いました。具体的なIP電話の例は分かりやすい。
ただ、たまに(特にgoogleのmeet?)音声は聞こえるけど10秒くらい遅延しているときがあるように思います。
この時は、TCPを使ってしまっているのか?などちょっと気になりました。

以上、私の理解まとめになります。細かいところは本を読んでチェックや!