作ったのはこちら
https://github.com/doshiraki/rbtree_bygo/blob/master/rbtree.go


赤黒木

やっぱり削除は難しい。。。
ポイントは、delete case 3,4がまったく同じ結果というようにまとめられること。

	Node := delNode
	for {
		parent := Node.parent
		if parent == nil {
			//case 1
			break
		}

		dir := Node.dir()
		dirOther := dir ^ 1
		sibling := parent.children[dirOther]

		if sibling.isRed {
			//case 2
			parent.flip(dirOther)
			sibling.isRed = false
			parent.isRed = true
			sibling = parent.children[dirOther]
		}
		//sibling is Black

		nephew := sibling.children[dirOther]
		if nephew == nil || !nephew.isRed {
			//far nephew is Black
			nephew = sibling.children[dir]
			if nephew == nil || !nephew.isRed {
				//near nephew is Black
				sibling.isRed = true
				if parent.isRed {
					//case 4
					parent.isRed = false
					break
				} else {
					//case 3
					Node = parent
					continue
				}
			}
			//case 5
			//near nephew is Red and far nephew is Black
			sibling.flip(dir)
			sibling, nephew = nephew, sibling
			sibling.isRed = false
			nephew.isRed = true
		}
		//case 6
		//sibling is Black && far nephew is Red

		saveColor := parent.isRed
		parent.flip(dirOther)
		sibling.isRed = saveColor
		parent.isRed = false
		nephew.isRed = false
		break

	}

[0回]

atcoder141Eを解いていたら良い方法が思い浮かばず、解説読んでKMPアルゴリズムを知った。

E - Who Says a Pun?


KMP法(by wikipedia)
これの面白いところは、BM法と違いは何文字一致したかまで確認出きるという点かな。
勉強になったなり。
ちなみに、解説にはZアルゴリズムとあったのだけども、すべての部分文字列について知りたいわけではないので、KMPのテーブル生成のみに着目したほうがパフォーマンスは良さげ。
しゃくとり法を使うともっとシンプルに解けていることが衝撃である。

[0回]

javaでflatMapを覚えてから奇妙だなと思っていた。
これって何に使うのだろうかと。

結論から言うと直積を求めたいときに使うのである。

もし、組み合わせを求めたい場合、どのように求めるだろうか。

■pythonソース

teams = range(5)
[(x, y) for xi, x in enumerate(teams) for yi, y in enumerate(teams) if xi < yi]

■python結果

[(0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (1, 2),
 (1, 3),
 (1, 4),
 (2, 3),
 (2, 4),
 (3, 4)]

実はこれと同じことをflatMapでも行える。
■javascriptソース

range = (x)=>function*(){ for(var i = 0;i<x;i++) {yield i;}};
teams = range(5);
Array.from([[]])
.flatMap(x=>Array.from(teams()).map(y=>x.concat(y)))
.flatMap((x, xi)=>Array.from(teams()).filter((y,yi)=>xi<yi).map(y=>x.concat(y)))

■javascript結果

(10) [Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2)]
0: (2) [0, 1]
1: (2) [0, 2]
2: (2) [0, 3]
3: (2) [0, 4]
4: (2) [1, 2]
5: (2) [1, 3]
6: (2) [1, 4]
7: (2) [2, 3]
8: (2) [2, 4]
9: (2) [3, 4]
length: 10
__proto__: Array(0)

おもしろいなあ。

[0回]

グラフを作りたかったので、graphvixを使ってみました。

【参考】Boost.Graph Graphviz形式で重みを出力

#include <fstream>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct EdgeWithInfo
{
    int nodeS;
    int nodeE;
    int weight;
    std::string name;
};

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
                              boost::no_property, boost::property<boost::edge_all_t, EdgeWithInfo>>
    Graph;
typedef std::pair<int, int> Edge;

enum
{
    A,
    B,
    C,
    D,
    E,
    N
};

const std::string name[] = {"A", "B", "C", "D", "E"};

int main()
{
    const std::vector<EdgeWithInfo> edgeWithInfo =
        {
            {A, B, 3, "→B"},
            {A, C, 1, "→C"},
            {A, D, 4, "→D"},
            {B, E, 2, "→E"},
            {C, E, 5, "→E"},
            {D, E, 6, "→E"}};

    std::vector<Edge> edges;

    std::transform(edgeWithInfo.begin(), edgeWithInfo.end(), std::back_inserter(edges),
                   [](auto ei) {
                       return std::make_pair(ei.nodeS, ei.nodeE);
                   });

    const Graph g(edges.begin(), edges.end(), edgeWithInfo.begin(), N);

    std::ofstream file("test.dot");
    boost::write_graphviz(file,
                          g,
                          boost::make_label_writer(name),
                          [](auto &graph_) {
                              return [&graph_](std::ostream &out, auto edge) {
                                  const EdgeWithInfo &ewi =
                                      *reinterpret_cast<const EdgeWithInfo *>(&boost::get(boost::edge_all, graph_, edge));
                                  out << "[";
                                  out << "weight=" << ewi.weight << ",";
                                  out << "label=" << ewi.name;
                                  out << "]";
                              };
                          }(g));
}

digraph G {
0[label=A];
1[label=B];
2[label=C];
3[label=D];
4[label=E];
0->1 [weight=3,label=→B];
0->2 [weight=1,label=→C];
0->3 [weight=4,label=→D];
1->4 [weight=2,label=→E];
2->4 [weight=5,label=→E];
3->4 [weight=6,label=→E];
}

正攻法ではない気がするけど、まあ良しとしよう。

[0回]

Pythonでの不満。Python2にあったsorted関数のcmpがなくなって、keyになった。
なぜ、cmpはなくなったのだろうか？考えてみた。

まず、sortedへの不満として、複数キーの昇順・降順ができなくなった。というものがあった。
誤りである。
どうやらkeyにタプルを返すと勝手に複数キーの昇順としてソートしてくれるようだ。
つまり、文字は反転。数字はマイナスにすることで、それらしきものができる。

c=[('a', 1), ('a', 2), ('b', 2), ('b', 1)]
sorted(c, key=lambda x: (tuple(map(lambda z:(0xff-z), x[0].encode("cp932"))), -x[1]))
[('b', 2), ('b', 1), ('a', 2), ('a', 1)]

ここで気づいた。この比較用キーの作成はcmpの場合、ソート方法に依存してしまう。O(2*NlogN)の頻度で比較用キーが作成されてしまうのだ。
この点、key指定だと比較用キーはO(N)のみの作成となる。
すばらしい

ただし、文字列の降順としては可変長の場合、前述の方法は使えない。なので、classを作ってみた。

class Keys:
    def __init__(self, v, isAscs):
        self.v = v
        self.isAscs = tuple(isAscs)

    def __lt__(self, other):
        for i, s, isAsc, o in zip(range(len(self.isAscs)-1, -1, -1), self.v, self.isAscs, other.v):
            lt = [lambda p1, p2: p1 > p2, lambda p1, p2: p1 < p2][isAsc]
            ret = lt(s, o)
            if ret or i and lt(o, s):
                break
        return ret

    @staticmethod
    def of(isAscs, keymap=lambda x:x):
        return lambda item: Keys(keymap(item), isAscs)


if __name__ == "__main__":
    arr = [("a", 2), ("b", 1), ("a", 1), ("b", 2)]
    print(arr)
    #１項目め降順、２項目め昇順
    print(sorted(arr, key=Keys.of((False, True))))
    #１項目め２文字目昇順、１項目め１文字目昇順
    print(sorted(arr, key=Keys.of((True, False), keymap=lambda x:(x[0][1], x[0][0]))))

うん、素晴らしい。

[0回]