Redis

NoSQL Redis key-value store

Redis とは

Redis は、キーバリューストアなインメモリデータベースです。
Redis

Redis は、キャッシュやセッションストアなど、データベースとアプリケーションの間で一時的なデータ格納場所やデータブローカーとして活用されます。
また、ソート済みリストの保持など、データベースでは遅い処理を代行するために活用されています。

キーバリューとは、データをキーとバリューの形式で格納するデータ構造です。
様々な言語で同様のデータ構造が利用されており、C++ なら連想配列 (std::map)、Python なら辞書型 (dict)、Rust なら HashMap (std::collections::HashMap) として実装されています。
(数学だと、ただの写像です)
形式的には、バリューに対して一意な識別子 (キー) を対応させるデータ構造と説明されます。
例えば、以下のようになります。

*key *value
name kamojiro
age 27
hobby AtCoder
skill AtCoder

このように、key である name や age に対して、value が対応しています。
key が重複することや、key が存在するが対応する value が存在しないことは許されません。
しかし、value については重複しても問題ありません。

インメモリデータベースとは、メモリ (RAM) 上にデータを保存するデータベースのことです。
一般にデータベースは、ディスク (HDD や SSD) にデータを保存します。
有名どころだと、PostgreSQL や MySQL、Apache Kafka などはディスクにデータを保存します。
今回のインメモリデータベースである Redis ではデータをメモリ上に保存します。
一般にディスクとのデータの交換よりもメモリとのデータの交換のほうが高速であるため、データの更新・読み取りを高速に行うことができます。

以下にコンポーネントごとのデータI/Oの目安が記載されています。
Numbers Every Programmer Should Know By Year

Redis の特徴

キーバリューストアやインメモリデータベースとしての特徴は以下のようなものがあります。

  • 読み書き操作が高速

キーバリューなインメモリストアとしては、memcached がよく比較されます。
memcached は Redis と比べてシンプルなものになっています。
Redis は様々なユースケースに対応できるように設計されいます。

  • 様々なデータ型
  • データの永続化
  • データの冗長化
  • 高可用性構成とスケーラビリティ

様々なデータ型

Redis では、以下のデータ型を利用できます。
Redis | AWS

データ型 *説明
Strings 最大 512MB のテキストまたはバイナリデータ
Lists 追加された順に並べられた文字列の集合
Sets 順序なしの文字列の集合で他の Set 型と交差、和集合、差集合演算を行うことができる
Sorted Sets 値ごとに並べられた Set
Hashes フィールドと値のリストを保存するデータ構造
Bitmaps ビットレベルの演算を実行できるデータタイプ
HyperLogLogs データセット内の一意の項目を推定する確率的データ構造

一部補足します。
String はバイナリデータを格納できるため、画像データなども格納できます。
Sorted Sets はデータを順序を保って保持できるため、高速なランキングボードを実現できます。
HyperLogLogs はユニークユーザー数の概算などに利用されますが、それ自体でも面白い話なので参考文献を記載しておきます。

HyperLogLog in Presto: Faster cardinality estimation - Facebook Engineering
http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

簡単に説明すると、一意なユーザー情報から生成されるハッシュ値の連続した 0 の長さを元にユニークユーザー数を概算します。
例えば、ある長さのビット列の場合、先頭から 0 が3つ連続する確率は \frac{1}{8} となります。
具体的に書き出すと、以下のようになります。

000
001
010
011
100
101
110
111

大雑把ですが、先頭から 0 が3つ連続するためには大体 8 つのビット列が必要なため、ユニークユーザー数はおよそ 8 と概算することができます。
これの精度を向上させたものが、HyperLogLog になります。

データの永続化

Redis のデータの永続化機構は、スナップショット形式の RDB と、ログ追記型の AOF があります。
RDB は一定時間（と一定の更新）ごとにデータをディスクに保存します。
AOF は書き込みごと（正確には、短時間ごと）に、実行コマンドをディスクに保存します。

RDB は AOF よりもデータ保存に必要なディスク容量が小さいです。
しかし、スナップショットとスナップショットの間のデータは保存していないため、障害時にデータが失われる可能性があります。
AOF は RDB よりも細かくディスクへのデータの保存を行うため、RDB と比べて障害時に失われるデータを少なくできます。

RDB は定期的なバックアップや大規模な障害に対応するために、AOF は一時的な障害からの復旧に利用されます。

データの冗長化

Redis では、マスターレプリカ形式のレプリケーションを利用できます。
マスターでデータの更新が行われ、変更がレプリカにも反映されます。
読み込みは、マスターとレプリカのどちらに対しても行うことができ、参照を負荷分散できます。
Redis のレプリケーションでは、データの同期は非同期となっているため、マスターとレプリカのデータが差異があることがあります。

高可用性構成とスケーラビリティ

Redis の高可用性構成には、Redis Sentinel と Redis Cluster があります。

Redis Sentinel は、レプリケーション構成とそれを監視する Redis Sentinel たちから構成されます。
マスターに障害が発生した場合に、レプリカをマスターに昇格させる（自動フェールオーバー）などを行います。

Redis Cluster は、データを分散して保持するマルチマスター構成です。
各マスターが別々に更新処理を行えるため、更新を負荷分散できます。
特に、大規模な Redis クラスターを構成したい場合に利用されます。
各マスターにレプリカを追加することもできます。

LSP :: could not find `Cargo.toml`

うまく行かなかったメモ。

目的

emacs で rust-analyzer を LSP ってやつを使って使えるようにするぜ。

init.el の変更

以下とか、いろいろ参照しつつ、init.el を編集する。

Rustプログラミングのための環境構築 | Emacs JP

関連部分はこちら。

(leaf lsp-mode
  :ensure t
  :init (yas-global-mode)
  :custom ((lsp-rust-server . 'rust-analyzer))
  :hook ((web-mode-hook rust-mode-hook) . lsp)
  :config
  (leaf lsp-ui :ensure t)
  (leaf lsp-ivy :ensure t))

(leaf rust-mode
  :ensure t
  ;; :custom ((rust-format-on-save . t))
  :config
  (leaf cargo
    :ensure t
    :hook (rust-mode . cargo-minor-mode))
  )

なんか失敗したときのエラーは以下。
.rs ファイルを開くときに、Cargo.toml よりも遡ったところを監視するぜって言っているような気がする。

LSP :: Connected to [rls:14780/starting].
LSP :: rls:14780 initialized successfully in folders: (/home/ochir/atcoder)
Watching all the files in <home directory>/competitive_programming/atcoder/ would require adding watches to 1773 directories, so watching the repo may slow Emacs down.
Do you want to watch all files in <home directory>/competitive_programming/atcoder/? (y or n) y
LSP :: You can configure this warning with the `lsp-enable-file-watchers' and `lsp-file-watch-threshold' variables
LSP :: could not find `Cargo.toml` in `<home directory>/atcoder` or any parent directory

ディレクトリ構造はこちら。
abc195以下は、`cargo atcoder new abc195`で生成されています。
GitHub - tanakh/cargo-atcoder: Cargo subcommand for AtCoder

competitive_programming/
└── atcoder
    └── rust
        └── abc195
            ├── Cargo.lock
            ├── Cargo.toml
            ├── src
            │   └── bin
            │       ├── a.rs
            │       ├── b.rs
            │       ├── c.rs
            │       ├── d.rs
            │       ├── e.rs
            │       └── f.rs
            └── target
                ├── CACHEDIR.TAG
                ├── debug
                │   ├── build
                │   │   ├── getrandom-38ff49cfcf8d31ca

本当は、abc195 を監視してほしいけど、atcoder のとこを監視している。
新しく別のところに abc195 以下を作成するとうまくいくので、LSP の設定から変更できないか調べてみたけど分からず・・・。
分からなかったというメモだけ残しておく。

なんかヒントになりそうな issue だけおいとく。
github.com

workspace

workspace がいかれていることが分かってきた。
というか、これが workspace っていうことがわかった。

M-x lsp-workspace-folders-remove

でよくわからんやつを消して、emacs を再起動したら、直った。OK。
多分、connection を再確立すればええんやろうけど。

Can't Stop の確率

python プログラミング game

Can't Stop の確率とか求めた。
https://boardgamearena.com/gamepanel?game=cantstop

確率が大きい順

連続してサイコロをふれる回数のうち、確率 \frac{1}{2} 以上のうち最大のものも記載（右端）。

目 目 目 確率 回数
6 7 8 0.9197530864197531 8
5 7 8 0.9143518518518519 7
6 7 9 0.9143518518518519 7
4 6 8 0.9112654320987654 7
6 8 10 0.9112654320987654 7
4 7 8 0.9027777777777778 6
6 7 10 0.9027777777777778 6
5 6 8 0.8950617283950617 6
6 8 9 0.8950617283950617 6
3 7 8 0.8927469135802469 6
4 7 9 0.8927469135802469 6
5 7 10 0.8927469135802469 6
6 7 11 0.8927469135802469 6
2 7 8 0.8904320987654321 5
6 7 12 0.8904320987654321 5
5 6 7 0.8865740740740741 5
7 8 9 0.8865740740740741 5
4 6 7 0.8858024691358025 5
7 8 10 0.8858024691358025 5
2 6 8 0.8834876543209876 5
4 6 10 0.8834876543209876 5
4 8 10 0.8834876543209876 5
6 8 12 0.8834876543209876 5
4 7 10 0.8765432098765432 5
5 6 9 0.8665123456790124 4
5 8 9 0.8665123456790124 4
3 6 7 0.8649691358024691 4
7 8 11 0.8649691358024691 4
2 6 7 0.8641975308641975 4
4 6 9 0.8641975308641975 4
5 8 10 0.8641975308641975 4
7 8 12 0.8641975308641975 4
4 8 9 0.8626543209876543 4
5 6 10 0.8626543209876543 4
3 6 8 0.8533950617283951 4
5 7 9 0.8533950617283951 4
6 8 11 0.8533950617283951 4
4 5 7 0.8479938271604939 4
7 9 10 0.8479938271604939 4
4 5 8 0.845679012345679 4
6 9 10 0.845679012345679 4
3 7 9 0.8425925925925926 4
5 7 11 0.8425925925925926 4
2 7 9 0.8356481481481481 3
3 7 10 0.8356481481481481 3
3 8 9 0.8356481481481481 3
4 7 11 0.8356481481481481 3
5 6 11 0.8356481481481481 3
5 7 12 0.8356481481481481 3
2 6 9 0.8333333333333334 3
2 7 10 0.8333333333333334 3
3 8 10 0.8333333333333334 3
4 6 11 0.8333333333333334 3
4 7 12 0.8333333333333334 3
5 8 12 0.8333333333333334 3
2 5 8 0.8287037037037037 3
6 9 12 0.8287037037037037 3
3 6 9 0.8263888888888888 3
5 8 11 0.8263888888888888 3
2 8 9 0.8225308641975309 3
3 6 10 0.8225308641975309 3
4 5 10 0.8225308641975309 3
4 8 11 0.8225308641975309 3
4 9 10 0.8225308641975309 3
5 6 12 0.8225308641975309 3
2 4 8 0.8155864197530864 3
2 8 10 0.8155864197530864 3
4 6 12 0.8155864197530864 3
6 10 12 0.8155864197530864 3
2 6 10 0.8109567901234568 3
4 8 12 0.8109567901234568 3
2 5 7 0.8094135802469136 3
7 9 12 0.8094135802469136 3
3 5 8 0.8078703703703703 3
6 9 11 0.8078703703703703 3
2 4 7 0.8070987654320988 3
7 10 12 0.8070987654320988 3
4 5 9 0.7986111111111112 3
5 9 10 0.7986111111111112 3
3 4 8 0.7962962962962963 3
4 5 6 0.7962962962962963 3
6 10 11 0.7962962962962963 3
8 9 10 0.7962962962962963 3
3 4 7 0.7908950617283951 2
7 10 11 0.7908950617283951 2
3 5 7 0.7870370370370371 2
7 9 11 0.7870370370370371 2
2 7 12 0.7808641975308642 2
2 7 11 0.7785493827160493 2
3 4 9 0.7785493827160493 2
3 7 12 0.7785493827160493 2
3 9 10 0.7785493827160493 2
4 5 11 0.7785493827160493 2
5 10 11 0.7785493827160493 2
3 5 9 0.7762345679012346 2
3 7 11 0.7762345679012346 2
5 9 11 0.7762345679012346 2
3 5 6 0.7708333333333334 2
8 9 11 0.7708333333333334 2
2 5 6 0.7700617283950617 2
8 9 12 0.7700617283950617 2
2 5 9 0.7600308641975309 2
5 9 12 0.7600308641975309 2
2 4 6 0.7584876543209876 2
3 5 10 0.7584876543209876 2
3 6 11 0.7584876543209876 2
3 8 11 0.7584876543209876 2
4 9 11 0.7584876543209876 2
8 10 12 0.7584876543209876 2
2 3 8 0.7561728395061729 2
2 4 9 0.7561728395061729 2
2 5 10 0.7561728395061729 2
2 6 11 0.7561728395061729 2
3 4 10 0.7561728395061729 2
3 8 12 0.7561728395061729 2
4 9 12 0.7561728395061729 2
4 10 11 0.7561728395061729 2
5 10 12 0.7561728395061729 2
6 11 12 0.7561728395061729 2
2 3 7 0.7523148148148148 2
7 11 12 0.7523148148148148 2
3 4 6 0.7422839506172839 2
8 10 11 0.7422839506172839 2
2 4 10 0.7384259259259259 2
2 6 12 0.7384259259259259 2
2 8 12 0.7384259259259259 2
4 10 12 0.7384259259259259 2
2 8 11 0.7361111111111112 2
3 6 12 0.7361111111111112 2
2 3 9 0.7121913580246914 2
2 5 11 0.7121913580246914 2
3 9 12 0.7121913580246914 2
5 11 12 0.7121913580246914 2
2 9 10 0.7098765432098766 2
3 5 11 0.7098765432098766 2
3 9 11 0.7098765432098766 2
4 5 12 0.7098765432098766 2
2 3 6 0.683641975308642 1
8 11 12 0.683641975308642 1
3 4 5 0.6689814814814815 1
9 10 11 0.6689814814814815 1
2 4 5 0.6574074074074074 1
9 10 12 0.6574074074074074 1
3 4 11 0.6566358024691358 1
3 10 11 0.6566358024691358 1
2 9 11 0.6365740740740741 1
3 5 12 0.6365740740740741 1
2 3 10 0.6342592592592593 1
2 4 11 0.6342592592592593 1
2 5 12 0.6342592592592593 1
2 9 12 0.6342592592592593 1
3 10 12 0.6342592592592593 1
4 11 12 0.6342592592592593 1
2 3 5 0.5841049382716049 1
9 11 12 0.5841049382716049 1
2 10 11 0.5787037037037037 1
3 4 12 0.5787037037037037 1
2 4 12 0.5516975308641975 1
2 10 12 0.5516975308641975 1
2 3 11 0.5254629629629629 1
3 11 12 0.5254629629629629 1
2 3 4 0.5216049382716049 1
10 11 12 0.5216049382716049 1
2 3 12 0.4382716049382716 0
2 11 12 0.4382716049382716 0


導出方法

プログラム

from itertools import combinations, product
def main():
    Probability = []
    for c in combinations( range(2,13), r=3):
        cnt = 0
        for p in product( range(1,7), repeat=4):
            s = set()
            for w in combinations( range(4), r=2):
                s.add(p[w[0]]+p[w[1]])
            for b in c:
                if b in s:
                    cnt += 1
                    break
        Probability.append((cnt/(6**4), c))
    Probability.sort(reverse=True,key=lambda x:x[0])
    for probability in Probability:
        print(probability)
    Count = []
    threshold = 0.5
    for p, c in Probability:
        cnt = 0
        q = p
        while q >= threshold:
            cnt += 1
            q *= p
        Count.append((cnt, c))
    Count.sort(reverse=True,key=lambda x:x[0])
    for count in Count:
        print(count)
    
if __name__ == '__main__':
    main()

NVIDIA: Failed to initialize the NVIDIA kernel module. Please see the

PC関連 備忘録

環境

困ったこと

PCを起動するとログイン画面にたどり着けなかった。
Ctrl-Alt-F2で、/var/log/Xorg.0.logを見ると以下の記述があった。

NVIDIA: Failed to initialize the NVIDIA kernel module. Please see the

やったこと

いろいろやったが、結論でいうとNVIDIAのドライバーが古くなっていた。
前にインストールした方法も覚えていないので、調べ直した。
NVIDIAのドライバーを入れていない場合も、同様の手順でできる。

ということで、

$ sudo wget http://jp.download.nvidia.com/XFree86/Linux-x86_64/450.57/NVIDIA-Linux-x86_64-450.57.run

ドライバーは最新バージョンを選択。
公式ドライバー | NVIDIAから調べる。

実行する。

$ sudo sh NVIDIA-Linux-x86_64-450.57.run

失敗。

ERROR: Unable to find the kernel source tree for the currently running kernel. Please make sure you have installed the kernel source files for your kernel and that they are properly configured; on Red Hat Linux systems, for example, be sure you have the 'kernel-source' or 'kernel-devel' RPM installed. If you know the correct kernel source files are installed, you may specify the kernel source path with the '--kernel-source-path' command line option.

以下のようなことを書いていたので、linux-headersをインストール。

https://www.nvidia.com/en-us/geforce/forums/geforce-graphics-cards/5/285883/problem-to-install-driver/

$ sudo apt -y install linux-headers-amd64

再度、実行するとうまく行った・

$ sudo sh NVIDIA-Linux-x86_64-450.57.run

NVIDIAのドライバのインストール | 逆襲のSlackware
を参考に設定した。

再起動して、完了。
うまくいった。
終わってから、はじめにNVIDIAのドライバーをインストールした記憶が蘇ってきた。

追記

$ sudo apt dist-upgrade

したのが原因かな

追記2

GPU の確認。

lspci | grep -i nvidia

AtCoder Beginner Contest 027 C 倍々ゲーム

atcoder python プログラミング

ABC027のCが面白かったので。

問題概要

A, Bがゲームをする。正整数Nが与えられる。
x=1 で初期化する。

  • x を 2 倍するか、2 倍した後、1 を加算する

Aさんから行い、N を超える操作を行った方が負け。

解説

操作を言い換えると、次のようになります。

  • x \mapsto x<<1
  • x \mapsto (x<<1) + 1

ここから、 n \, (n \geq 0) 回目の操作の後の x は以下を満たすことがわかります。

  • 100\ldots 000 = 2^n \leq x < f^n(1) = 111\ldots 111 = 2^{n+1}-1

ここで、f(x) = 2x+1 とします。

x = N のときの、 n を固定します。

つまり、このゲームの決着がつくのは、n 回目か、n+1 回目ということになります。

n 番目の人は、 x の範囲は変えられませんが、x が N を超えなければ勝てます。

従って、n 番目の人は x の値ができるだけ小さくなる操作( x \mapsto 2x )を、
そうでない人は、x の値ができるだけ大きくなるような操作( x \mapsto 2x+1 )を行うことが最適となります。

解答

解答

from math import log2
def main():
    N = int( input())
    M = int( log2(N))
    x = 1
    for i in range(M):
        if M%2 == 0:
            if i%2 == 1:
                x = 2*x
            else:
                x = 2*x+1
        else:
            if i%2 == 0:
                x = 2*x
            else:
                x = 2*x+1
    if M%2 == 0:
        if x <= N:
            print("Aoki")
        else:
            print("Takahashi")
    else:
        if x <= N:
            print("Takahashi")
        else:
            print("Aoki")
        
if __name__ == '__main__':
    main()

AtCoder Beginner Contest 129 F Takahashi's Basics in Education and Learning

備忘録 atcoder プログラミング python

ABC129 F を解いた。
問題はこれ。
F - Takahashi's Basics in Education and Learning。

解説

行列累乗を使う問題。

各桁に何個あるかを間違えたので、解説をつけておく。

少し一般化した形で書きます。

a \leq h を整数とし、 d を正整数とする。
このとき、初項 a 、公差 d の数列のうち、 h より小さいものの個数を求める。

以下、\sharp A により、集合 A の元の個数を表すものとする。（数え上げ測度）

\sharp\{x + d\times i | i \geq 0,\ x + d \times i < h\}
=\sharp\{i| i \geq 0,\ d \times i < h - x\}
=\max\{i+1| i \geq 0,\ d \times i< h - x\}
= (\lceil \frac{h-x}{d} \rceil - 1) + 1
= \lceil \frac{h-x}{d} \rceil

ここで、 \lceil b \rceil は b 以上の最小の整数とする。
python だと、

(h-x+(d-1))//d

となります。

解答

解答

def productMatrix(N, A, B):
    Ret = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                Ret[i][j] += A[i][k]*B[k][j]
    return Ret
def modMatrix(N, A, Q): #N×N行列のmod
    for i in range(N):
        for j in range(N):
            A[i][j] %= Q
    return

def powOfMatrix(N, X, n, Q): #N×N行列のn乗
    Ret = [[1,0,0],[0,1,0],[0,0,1]]
    power = '{:060b}'.format(n)[::-1] #log2(pow(10,18)) < 60
    for p in power:
        if p == "1":
            Ret = productMatrix(N,Ret, X)
            modMatrix(N, Ret, Q)
        X = productMatrix(N,X,X)
        modMatrix(N, X, Q)
    return Ret

def main():
    L, A, B, M = map( int, input().split())
    s = A
    ANS = [[1,0,0],[0,1,0],[0,0,1]]
    for i in range(1, 37):
        if s >= pow(10,i):
            continue
        P = [[pow(10, i, M), 0, 0], [1,1,0], [0,B,1]]
        step = (pow(10,i)-s+B-1)//B
        if L <= step:
            ANS = productMatrix(3,ANS,powOfMatrix(3,P,L,M))
            modMatrix(3,ANS,M)
            break
        ANS = productMatrix(3,ANS, powOfMatrix(3,P, step,M))
        modMatrix(3,ANS, M)
        L -= step
        s += step*B
    print( (ANS[1][0]*A + ANS[2][0])%M)

if __name__ == '__main__':
    main()


おまけ

python の関数は参照渡しなことを最近知ったので、使ってみた。
数値型以外は参照渡しらしい。これは違うっぽい。
文字型も参照渡しじゃないみたい。

今回のコードは、pypy より python のほうが速い。
何が原因か分からない。