bouzuya.hatenablog.com

ぼうずやのにっき

FieldValue.serverTimestamp は setToServerValue REQUEST_TIME か

疑問: Cloud Firestore の Node.js API の FieldValue.serverTimestamp は FieldTransform の setToServerValue REQUEST_TIME か。

結論: おそらくそう

https://firebase.google.com/docs/reference/js/firestore_.md#@firebase/firestore

https://www.npmjs.com/package/firebase

https://github.com/firebase/firebase-js-sdk

https://github.com/firebase/firebase-js-sdk/tree/v4.5.1/packages/firestore

https://www.npmjs.com/package/@firebase/firestore

If you are developing a Node.js application that requires administrative access to Cloud Firestore, use the @google-cloud/firestore Server SDK with your developer credentials.

https://www.npmjs.com/package/@google-cloud/firestore

https://github.com/googleapis/nodejs-firestore

https://github.com/googleapis/nodejs-firestore/blob/ce9abfd8cd65d0d2be4dd7f6a56fb679a100296a/dev/src/field-value.ts#L85-L87

  static serverTimestamp(): FieldValue {
    return ServerTimestampTransform.SERVER_TIMESTAMP_SENTINEL;
  }

https://github.com/googleapis/nodejs-firestore/blob/ce9abfd8cd65d0d2be4dd7f6a56fb679a100296a/dev/src/field-value.ts#L312-L366

/**
 * A transform that sets a field to the Firestore server time.
 *
 * @private
 * @internal
 */
class ServerTimestampTransform extends FieldTransform {
  /**
   * Sentinel value for a server timestamp.
   *
   * @private
   * @internal
   */
  static SERVER_TIMESTAMP_SENTINEL = new ServerTimestampTransform();


  private constructor() {
    super();
  }


  /**
   * Server timestamps are omitted from document masks.
   *
   * @private
   * @internal
   */
  get includeInDocumentMask(): false {
    return false;
  }


  /**
   * Server timestamps are included in document transforms.
   *
   * @private
   * @internal
   */
  get includeInDocumentTransform(): true {
    return true;
  }


  get methodName(): string {
    return 'FieldValue.serverTimestamp';
  }


  validate(): void {}


  toProto(
    serializer: Serializer,
    fieldPath: FieldPath
  ): api.DocumentTransform.IFieldTransform {
    return {
      fieldPath: fieldPath.formattedName,
      setToServerValue: 'REQUEST_TIME',
    };
  }
}

toProto は https://cloud.google.com/firestore/docs/reference/rest/v1/Write#fieldtransform の FieldTransform の setToServerValue と一致している。おそらく setToServerValue: 'REQUEST_TIME' を取得しているものだろうと判断した。

ABC106 : AtCoder Beginner Contest 106 の A, B, C, D を解いた。

  • A - Garden https://atcoder.jp/contests/abc106/tasks/abc106_a
  • B - 105 https://atcoder.jp/contests/abc106/tasks/abc106_b
  • C - To Infinity https://atcoder.jp/contests/abc106/tasks/abc106_c
    • 提出: https://atcoder.jp/contests/abc106/submissions/34441075
    • 先頭から K 文字目までを見ていく
    • 1 以外が出現した場合は 5000 兆日後にはその文字が続いているところを K は指すのでそれを出力する
    • 仮に K 文字目まで 1 が続く場合は K <= 10^18 なのでまずそうだが |S| <= 100 で 5000 兆日後の長さは K 以上なのですべて 1 の場合は 100 にしかならないため問題ない
  • D - AtCoder Express 2 https://atcoder.jp/contests/abc106/tasks/abc106_d
    • 提出: https://atcoder.jp/contests/abc106/submissions/34441508
    • Q 個のクエリのそれぞれで M 個の区間を調べると O(QM) になる
    • Q <= 10^5 で M <= 2*10^5 なので O(QM) では間に合わない
    • 試行 1: L で昇順に並べておくことを考えてみる
    • p..=q におさまるためには q <= L の位置を二分探索できる、これは速い
    • しかし q <= L な区間の中で R <= q な位置を探そうとすると順に走査すると遅い
    • かといって q <= L な区間の中から R でソートしては間に合わないのでダメ
    • 試行 2: 今度は p で昇順に並べることを考えてみる
    • その時点で p <= L なものを……これではあまり変わらないのでダメ
    • 全体から区間を絞る (減らす) のは難しいので、走査しながら足せば良いのではと思いつく
    • 試行 3: 区間を L の昇順、クエリを p の昇順に並べて、クエリを後ろから走査する
    • p <= L の区間を Vec に追加する
    • これで L の条件を満たすものだけを取り出せているので、もう L は気にしなくて良い
    • これでは R のソートが必要なので間に合わない (Vec ではダメ)
    • ただ R の集合のうち q 以下のものの個数を高速に取れれば良い
    • これは FenwickTree (BIT: Binary Indexed Tree) に適している
    • R の集合への追加は 1 点更新で、クエリは区間和だ
    • まとめ:
    • 区間を L の降順、クエリを p の昇順に並べる (クエリは答えのために添え字を残しておく)
    • クエリを後ろから走査する (p の降順に走査する)
    • 各クエリの p 以上の L を持つ区間を走査する (毎回区間を先頭から走査せず走査開始位置を保持しておく)
    • 各区間の R について、 FenwickTree の R の位置に区間の個数 1 を加算する
    • FenwickTree の 1..=q の区間和を得て、答えを保持する
    • 最後まで走査して答えを保持し終えたら添え字順に出力して終わり
    • ソートが O(NlogN) と O(QlogQ) で走査は O(Q + M logN) かな
    • 自力で解けた。解説では累積和で解いている

今日のコミット。