dackdive's blog

新米webエンジニアによる技術ブログ。JavaScript(React), Salesforce, Python など

「みんなのデータ構造」学習メモ:2.4 ArrayDeque

引き続き、「みんなのデータ構造」という本を読む。
みんなのデータ構造(紙書籍+電子書籍) – 技術書出版と販売のラムダノート

amazon

これまでのメモ

今回は「P35. 2.4 ArrayDeque 配列を使った高速な双方向キュー」。

TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/ArrayDeque.ts

続きを読む

Salesforce: 新しいTrailhead Playgroundがリリースされました

新しいTrailhead Playgroundがリリースされました。
といっても劇的なアップデートではなく、Playgroundにアプリが1つプリインストールされるようになっただけのようです。

今まで通り、ハンズオン形式の問題から「Trailhead Playgroundを作成」で作成すると、新しい組織にはプリインストールされるようになっています。

f:id:dackdive:20200120024205p:plain

新しいTrailhead Playgroundでできること

1. パッケージインストールが組織内から可能に

f:id:dackdive:20200120024533p:plain

「Install a Package」タブからは、パッケージIDを入力してボタンを押すとパッケージをインストールできるようになります。
単に別タブでインストール画面が開くだけですが、これまではこのためにログインを求められてパスワードが必要だったはずなので手間が減ったかな。

2. パスワードリセット画面

f:id:dackdive:20200120024907p:plain

「Get Your Login Credentials」からはユーザー名が確認できるほか、パスワードのリセットが可能です。
この場で新しいパスワードを入力させてもらえるのかと思いましたが、単にリセットが行われてメールが送信されるだけのようです。

余談

すでにTrailheadのモジュール内で、パッケージインストール手順やパスワードリセット手順などの記述はアップデート済みっぽい。(全部じゃないかもしれない)

f:id:dackdive:20200120025204p:plainSalesforce 組織へのサウンド効果の追加 > パッケージのインストール

f:id:dackdive:20200120025211p:plain

Trailhead Playground の管理 > Trailhead Playground のユーザ名とパスワードの取得

Salesforce: 「認証プロバイダ」と「指定ログイン情報」で外部サービス(GitHub)にOAuth2で接続する

こちらの記事を読んで、自分でも試してみたメモ。

認証プロバイダ、指定ログイン情報とはなにか

ヘルプ

認証プロバイダについては
10分でできる!SalesforceでSSO(認証プロバイダ:Google編) - TECH BLOG | 株式会社テラスカイ
などの記事にあるように、外部サービスのアカウントを使ってSalesforceへのSSOを実現することができる機能。
今回は単純にConsumer KeyやSecretといったクレデンシャル情報を登録するためだけに使う。

指定ログイン情報については、APIエンドポイントと必要な認証パラメータを登録しておくことで、登録した外部サービスのAPISalesforceから叩く際に面倒な認証認可のフローを肩代わりしてくれる機能。

手順

1. 認証プロバイダを登録する

認証プロバイダは英語だと「Auth. Providers」。
新規で作成しようとすると、プロバイダタイプにTwitterGitHubGoogleなど主要なサービスがデフォルトで存在することがわかる。

f:id:dackdive:20200120013150p:plain:w320

サービスごとに認証方式が異なるので必要な入力事項も異なるが、そこはフォームが動的に変化してよしなにやってくれる。

今回はプロバイダタイプにGitHubを選んだ。

f:id:dackdive:20200120014547p:plain

「コンシューマ鍵」と「コンシューマの秘密」はまだ発行してないので、この時点では適当な文字列を入れておく。

f:id:dackdive:20200120014738p:plain

保存すると「Salesforce設定」というセクションにいくつかURLが記載されている。
このうち、「コールバックURL」はこの後Consumer Key/Secret を発行する際に入力するのでコピーしておく。

2. 外部サービスのOAuthアプリケーションを登録し、Consumer KeyとConsumer Secretを取得する

GitHubの場合、Settings > Developer settings > OAuth AppsからNew OAuth Appを選ぶと作成できる。

f:id:dackdive:20200120014921p:plain

「Authorization Callback URL」に先ほどのコールバックURLを入力する。

また、発行した Consumer Key/Secret で先ほどの認証プロバイダの設定を更新する。

3. 指定ログイン情報を登録する

f:id:dackdive:20200120015049p:plain

URLはAPIのエンドポイントとなる。GitHubの場合は https://api.github.com
ID種別は「指定ユーザ」、認証プロバイダで先ほど登録したGitHub用の設定を選択する。
(ID種別については後述)

4. 試す

今回は Apex で試してみる。

このようなコードを書く。

HttpRequest req = new HttpRequest();
req.setEndpoint('callout:github/repos/zaki-yama/copy-title-and-url-as-markdown/issues');
req.setMethod('GET');
Http http = new Http();
HTTPResponse res = http.send(req);
System.debug(res.getBody());

setEndpoint() に指定する文字列は

callout:<指定ログイン情報の「名前」>/指定ログイン情報の「URL」以下のパス>

となる。

指定ログイン情報の「ID種別」について

今回使用した「指定ユーザ」以外に、「匿名」と「ユーザ」がある。
ヘルプによれば

f:id:dackdive:20200120023201p:plain

外部システムへのアクセスに 1 セットのログイン情報と複数セットのログイン情報のどちらを使用するかを決定します。

外部システムへのアクセスに 1 セットのログイン情報と複数セットのログイン情報のどちらを使用するかを決定します。

  • 匿名: ID がないため、認証は行われません。
  • ユーザ: コールアウトから外部システムにアクセスするユーザごとに、別個のログイン情報を使用します。このオプションは、ユーザ単位で外部システムのアクセスを制限する場合に選択します。 Salesforce の権限セットまたはプロファイルを使用してユーザアクセスを付与したら、ユーザは個人設定で外部システムの独自の認証設定を管理できます。JWT または JWT トークンの交換を使用している場合、それらに対して、ユーザごとのログイン情報が処理されます。

  • 指定ユーザ: 組織から外部システムにアクセスするすべてのユーザに対して、同じセットのログイン情報を使用します。このオプションは、すべての Salesforce 組織ユーザに外部システムの 1 つのユーザアカウントを指定する場合に選択します。

とあるので、外部サービス側でもSalesforceユーザごとにアカウントを区別したい場合は「ユーザ」を指定しつつユーザごとに追加の設定が必要になりそう。

HTTP/Tokyo #1に行ってきた

行ってきました。
中身の濃い勉強会で非常に勉強になった。

jxckさんの発表は圧巻でした。

Response Status codes 3xx @haormauyraa

資料: https://slides.araya.dev/http-tokyo-1/#slide=1 demo: https://playground.araya.dev/http-redirections/

  • 3xx系のステータスコードの話
    • 300〜308まで
  • RFC7231, 7232, 7538
  • 301, 302はHTTP/1.0
  • 300 Multiple Choices
    • 対象のリソースが複数の表現をもつ
      • サーバーはリダイレクト先として複数の選択肢を提示し、クライアント側はその中で優先するものを1つ選ぶ
    • サーバーが優先するべき選択を持っていたら、サーバーはその選択肢の URI 参照をLocaionヘッダーに含めるべき(SHOULD)。UA はその値を自動リダイレクトに利用してもよい(MAY)
  • 301 Moved Permanently
    • 対象のリソースに新しい恒久的なURIがあてられていて、このリソースへの今後の参照は同封されたURIのいずれかを利用するべきことを指示する
  • 302 Found
    • 302 Foundは301 Moved Permanentlyと異なりリダイレクト先となるURIは一時的という扱い。なので301はキャッシュ可能だが302はキャッシュすべきでない
  • 303 See Other
  • 304 Not Modified
    • "リクエストされたリソースを再送する必要がないことを示します。これはキャッシュされたリソースへの暗黙のリダイレクトです。" (MDN より)
    • リクエスト側が If-Modified-Since などを付けた条件つきのリクエストを送ったときに、「仮に条件がfalseでなければ200で応答することになる」ことを示す
    • 実際のリソースは返さない
    • 条件をつけたクライアント側が必要なリソースを(キャッシュなどで)持っている、ということをリクエストで示しているので、サーバーからはリソースそのものを返す必要がない
  • 305は非推奨、306はunused

「425 Too Early」@flano_yuki

資料: https://www.slideshare.net/yuki-f/status-425-httptokyo

f:id:dackdive:20200117221846p:plain

  • TLSハンドシェイクにはClientHello→ServerHelloを経てからHttpRequestを送るフルハンドシェイクと、1回目のClientHelloと一緒にHttpRequestを送る0-RTTハンドシェイクがあり、後者のClientHelloと一緒に送るHttpRequestがEarly Data
  • Early Dataの危険性
    • Early Dataは暗号化されているが第三者が複製することはできる
    • 冪等性のないリクエスト(POSTでデータを作成するとか)だとまずい
    • サーバーはHTTPリクエストを見て冪等でないリクエストは拒否することもできる

f:id:dackdive:20200117222159p:plain

  • HTTPでEarly Dataを安全に扱えない問題
    • 例:Proxyを介していると
      • Proxyはリクエストが冪等かわからない
      • originは元のリクエストがEarly Dataで送られてきたものかわからない
  • どうするか
    • Proxyは Early-Data: 1というヘッダーをつけてoriginに送る
    • originはリクエストが冪等でない場合は HTTPステータス425 Too Earlyをを返す
  • Firefoxでの実験
    • サーバーが425を返したとき、クライアントはTLSハンドシェイクを待ってからリクエストを送っている


Cookie @Jxck

資料はなし。ホワイトボードを使って説明。

  • RFC6265の話
  • Cookie はなぜ生まれたか
    • リクエスト・レスポンスが冪等な世界で、リクエストを送ってきたのが誰なのかを判断したい
  • Cookieとして送るのはIDであることがほとんどなので、ほとんどCredential
  • Cookieの欠点
    • SOP(Same Origin Policy)に則っていない
    • わかりやすい攻撃
      • 悪意のあるサイトが正規のサイトと同じリクエストを送る <form> を設置すると、Cookieを送ってリクエストが成立してしまう
      • はまちちゃん事件
  • 今どうやって対策しているか
    • csrf-tokenという一意の識別子を埋め込んでおき、リクエスト同時に送る
  • サーバーから Set-Cookie するときに、idの後ろに SameSite: というプロパティを付けることができるようになった
  • 3rd party cookie
    • サイトAにアクセス
    • サイトA内のiframeからADサーバーにアクセス -> cookie 456を返す
    • サイトBにアクセス
    • サイトB内のiframeから同じADサーバーにアクセス、このとき cookie 456を送る -> 同じ人だと特定できる
    • さらに、サイトAがECサイトだった場合、検索キーワードも一緒にADサーバーに送る -> サイトBを訪問したとき、サイトAの検索クエリの内容を元に適切な広告を送るといったことが可能
  • SafariのITP
  • ITPで困るのはADだけじゃなくAuthenticationサービス(SSO)
    • ITPはトラッキングをしてそうなサイトだけブロックする、と主張している
  • Cookieの原理は変えられないが、トラッキング目的のCookieは防ぎたい。Chromeはどうするか
  • Cookie
  • Cookie上書き問題への対策
    • id=xyz という Cookieに対して __Secure-id=xyzというように __Secure- prefix をつけると、httpsでの通信時のみしか送らなくなる
    • __Host-Secure; Path=/ じゃないとだめにするprefix
  • クライアント側でtokenを生成する Sec-Http-State: token=XXX
  • SameSite=Strict
    • Lax は別オリジンだったとしてもnavigation時にはCookieを付ける
    • Strict は別オリジンからは全てつけない
      • 例: connpassにログインした状態で、Google検索結果からconnpassへのリンクを開く
        • アドレスバーにconnpass.comと打ってアクセスしたときですらそうなる
    • Laxで何が問題か?
      • GET で何かするようなAPI(ログアウトリンクなど)
    • read cookieとwrite cookieを分ける
      • GitHubは実はやってるっぽい?
        • __Host-user_session_name_site
        • _gh_sess
        • user_sessionかも?

「みんなのデータ構造」学習メモ:2.3 ArrayQueue

引き続き、「みんなのデータ構造」という本を読む。
みんなのデータ構造(紙書籍+電子書籍) – 技術書出版と販売のラムダノート

amazon

前回

今回は「P32. 2.3 ArrayQueue 配列を使ったキュー」。

続きを読む

「みんなのデータ構造」学習メモ:2.1 ArrayStack

「みんなのデータ構造」という本を読み始めたので、その読書メモを。
今回は 2.1 節の「ArrayStack」というデータ構造について。


前置き:「みんなのデータ構造」という書籍について

https://sites.google.com/view/open-data-structures-ja/home より引用。

Open Data StructuresPat Morin 氏が執筆した、データ構造の入門書です。本プロジェクトでは、この本の和訳を作成し、PDF ファイルおよびそのソースコードを公開しています。

データ構造やアルゴリズムについて学びたいと思っていたので、この本で勉強することにした。
PDF版であれば日本語でもフリーで手に入るが、私はラムダノート社のサイトから紙書籍+電子書籍版を購入した。

みんなのデータ構造(紙書籍+電子書籍) – 技術書出版と販売のラムダノート

また、書籍内のサンプルコードはC++で書かれているが、C++はわからないのでTypeScriptで写経することにした。

リポジトリ


本題:ArrayStack について

ArrayStack とは

f:id:dackdive:20200106001441j:plain:w320

  • List インターフェースを実装したデータ構造の1つ
  • List インターフェースとは、値の列  x_0, x_1, ... , x_{n-1} とその列に対する以下の操作からなる(1.2.2 より)
    • size(): リストの長さ n を返す
    • get(i):  x_i の値を返す
    • set(i, x):  x_i の値を  x にする
    • add(i, x):  x i 番めとして追加し、 x_i, ... , x_{n-1} を後ろにずらす
    • remove(i):  x_i を削除し、  x_{i+1}, ... , x_{n-1} を前にずらす
  • Stack は LIFO Queue とも呼ばれ、最後に追加された要素が次に削除される
    • イメージは「皿を積んだ状態」(積み上げた皿を取るとき、上から順に持っていく)

ArrayStack の実行時間

  • get(i) および set(i, x) の実行時間は O(1)
  • add(i, x) および remove(i) の実行時間は
    • resize() を考慮しなければ O(n - i)
    • resize() を考慮すると O(1 + n - i) ただしこれは償却実行時間

f:id:dackdive:20200106002955p:plain

「償却実行時間」という言葉が出てくるが、これは「1.5 正しさ、時間計算量、空間計算量」の節に定義がある。

償却実行時間が  f (n) であるとは、典型的な操作にかかるコストが  f (n) を超えないことを意味する。より正確には、 m 個の操作にかかる実行時間を合計しても、  mf (n) を超えないことを意味する。いくつかの操作には  f (n) より長い時間がかかるかもしれないが、操作の列全体として考えれば、1 つあたりの実行時間は  f (n) という意味だ。

要するに同じ操作を m 回やったときの実行時間から1回あたりの実行時間を考えるという話。


補題2.1 resize() の実行時間について

ここがしばらくわからなかった。

空のArrayStackが作られたあと、  m \geq 1 回の add(i, x) および remove(i) からなる操作の列が順に実行されるとき、 resize() の実行時間は O(m) である。

書籍では

  1. resize() が呼ばれるとき、その前の resize() から add/remove が実行された回数は n/2 -1 以上である
  2. 1を満たすとき、 resize() の実行時間の合計は O(m) である

という2段階で説明しており、また 2 → 1 の順に証明している。
ここでは普通に1から書く。

    1. resize() が呼ばれるとき、その前の resize() から add/remove が実行された回数は n/2 -1 以上である

resize()が呼ばれるのは、add(i, x) 内で呼ばれるケースと remove(i) 内で呼ばれるケースの2通りある。


ケース1: add(i, x) 内で呼ばれる場合

f:id:dackdive:20200106004339p:plain

※書籍に倣って、「◯回めの resize() か」を表す◯に  i を使っているが、これは add(i, x)i とは無関係。ややこしい

この場合は i 回めの時点では配列 a は要素で満たされた状態、 i - 1 回めの時点では配列 a の長さは同じで、要素数は半分。
なので空いている a.length /2 = n_i / 2 分を埋めるのに、少なくとも n_i / 2 回の add() は実行されているはずである。


ケース2: remove(i) 内で呼ばれる場合

f:id:dackdive:20200106004401p:plain

逆に remove(i) 内で呼ばれる場合、要素数 n_i が配列 a のサイズの 1/3 以下になる場合なので、 n_i <= a.length / 3
1つ前の i - 1 回めの resize() が実行された直後の状況を考えると、このときは resize() によって配列のサイズの半分の要素数になっているはず。
n_(i-1) = a.length / 2 でもいいが、n = 0 && a.length = 1 という特殊ケースを考えると n_(i-1) >= a.length / 2 - 1 となる。
今度は要素数n_(i-1) から n_i になるまで remove() が実行されているはずなので、差をとって↑のように式変形すると n_i / 2 - 1 以上であることが示せる。


  • 2.1を満たすとき、 resize() の実行時間の合計は O(m) である

f:id:dackdive:20200106010721p:plain

↑では、add(i, x)Aremove(i)R と表現している。
いま、この ARをランダムに実行した一連の操作があり、その操作の合計が m 回である。
またこの間に不定期に resize() が実行されており、合計で r 回実行された。

1でわかったのは色をつけた部分で、
i - 1回めの resize() から i 回めの resize() の間に呼ばれた add/remove の数は >= n_i - 1 である」
ということ。

また、

  (1回めのresize()から2回めのresize()までのadd/removeの数)
+ (2回めのresize()から2回めのresize()までのadd/removeの数)
+ ...
+ (i - 1 回めのresize()からi回めのresize()までのadd/removeの数)
+ ...
+ (r - 1 回めのresize()からr回めのresize()までのadd/removeの数)

<= m

r 回めの resize() の後にも何回か add/remove が呼ばれている可能性があるため)

で、かつ左辺のそれぞれの項は n_i /2 - 1 よりも大きいと言っているんだから、結局

 \displaystyle
\sum_{i=1}^r ( \rm {n}_{i} / 2 - 1) \geq m

が示せたことになる。

2019年のふりかえりと2020年の抱負

初ふりかえりです。

主なできごと

現職のサイボウズに入社したのが2018年12月なので、ほぼほぼサイボウズでの最初の1年という感じだった。

ブログは22件。
https://dackdive.hateblo.jp/archive/2019

登壇は(わずか)3件。


2019年の目標のふりかえり

昨年はきちんと目標を立てていなかったが、なんとなく頭の中にあった「チャレンジしたいこと」が実際どうだったか。


2019年のKeep

TypeScript

現在、複業で react-lightning-design-system というReact製UIライブラリのTypeScript移行のお手伝いをさせてもらっており、その結果TypeScriptのお作法だったりESLint, Prettier, Jestなど周辺パッケージとの併用方法を学ぶことができた。

この記事は比較的多くの反応があったのでうれしい。


モブプログラミング

サイボウズは多くのチームでモブプログラミングという開発スタイルを採用している。
自分は現在kintoneというプロダクトチームと フロントエンドエキスパートチーム というチームを兼務しているが、kintoneチームに関しては100%モブプロ、フロントエンドエキスパートチームは個人作業とモブプロを両方取り入れた開発を行っている。

前職でもペアプロ・モブプロを取り入れてみたいなーという思いがあったのだが、実際に業務で体験してみて良い面も悪い面も知ることができた、というのが率直な感想。

入社してすぐに 社外のモブプロ体験会に参加した のは非常に良い経験だったし、モブプロに対する悩みMAXだった夏頃は自分でMeetupを主催するなどした。
またこちらの本も読んだが、これからモブプロを始めようと思っている人には有用な本だと思う。


OSSにコントリビュートできた

これまで、OSSにIssueやPRを出すというのは自分にとって非常にハードルが高かった。
ところが、今所属しているチームのメンバーは日常的にOSSにIssue・PRを出しており、その影響から自分も一歩足を踏み出すことができた。

といってもバグ報告やドキュメントなどの簡単なtypo修正だけです。こういうの。


英語のドキュメント・ブログ記事を以前よりも読むようになった

これもチームメンバーに刺激を受けて。
今までも読んでいたが、より日常的に読むようになった。
ブラウザのアップデート情報やカンファレンス動画を観るというのは、1年前はやっていなかったと思う。

個人的なおすすめは、Mozillaが昨年ぐらいから始めたこのYouTubeチャンネル。

トピックがCSSアクセシビリティというのはあるが、尺としても10分前後のものが多く英語学習も兼ねて観るのに丁度いい。


Salesforceのキャッチアップを継続することができた

転職して界隈を離れてしまったが、1年を通してSalesforceウォッチャーとしての活動は継続することができた。
さすがにリリースノートは読まないが、twitterから面白そうなアップデートを見たり、Dreamforceの発表内容を軽くチェックしたり、Meetupに顔を出すなどした。

Salesforceの動向をキャッチアップしている理由として「業務に無関係ではないこと」「今のところ開発者としての希少性を高められるのがSalesforceぐらいなこと」「キャッチアップをやめるとこれまでの経験が無になるという恐怖感」などいろいろあるが、今のところ無理なく続けられているので今年も継続したい。


2019年のProblem

フロントエンドの分野で強みといえる専門領域がない

これは転職して強く実感したことだが、ありがたいことに今同じチームにフロントエンドつよつよエンジニアしかいないので、今まで以上に自分の技術力の無さを思い知らされる。
どこかの領域では負けている、ではなく、知識・アウトプット力などさまざまな面で完全に劣っていると感じることが多々あり、恵まれた環境に感謝しつつこのままじゃやばいという危機感がある。

どこかの分野ではチームに貢献できるような強みを作りたい。今自分が興味あるのは

  • Webパフォーマンス(というか、ブラウザがどういうしくみで動いているのかとかをちゃんと理解したいみたいな欲求)
  • Web Components
  • Rust、WebAssembly(そろそろやらないとまずいという危機感に近い)

の3点だろうか。


行動を習慣化するのが苦手

昨年はいろんなことにチャレンジできて良かったと思う反面、腰を据えてやると決めたことが継続できなかったり、他の面白そうな話題に目移りしてしまうといったことが多々あったように思う。
これは昨年に限らず自分の弱みというか性格として認識しておかなければいけない。

この問題に対するTryとしては、継続できていることをちゃんと記録して可視化することだと思う。
GitHubみたく草が生えればもうちょっとモチベーションが続く気がする。Studyplusってそんな感じのアプリでしたっけ。


2020年のTry

  • 英語ブログ、今年こそ書く!目標は3本
  • 今年もどっかのカンファレンスにCfP出す
  • 「みんなのデータ構造」とあともう1冊、コンピュータサイエンスに関する本を読む
  • 本は年間で6冊読む

コンピュータサイエンス系の本については、気になっているのはこちらの本。

このブログを読んで↓