コンテンツにスキップ

XOR List

ODSのList構造は前回ので全部終わっているが、DiscussionでXOR Listというものが書いてある.
どうせならと思い、今回はこれの実装を行う.
いままでの双方向連結リストの場合はNodeが以下のような構造になる. 

protected:
    struct Node
    {
        T m_value;
        std::shared_ptr<Node> m_prev;
        std::shared_ptr<Node> m_next;
    };

prevとnextを持たせることで双方向へのアクセスが可能になる.
できればこれを適当なbothというポインタ1つにまとめてしまえば、今までのようなポインタ2つを持たせるよりもメモリを少なく対応できる.
これを達成するようにするのが今回の目標！
そのために、今回はNodeにポインタを持たせる. 

protected:
    struct Node
    {
        T m_value;
        Node* m_both;
    };

ポインタ1つのみなので、これだと双方向へのアクセスができなさそう...
そこで使うのがXOR演算.
ポインタ同士にXORを行うことで、上手く左右の演算ができるようになる.
XORの演算は次のように定義.

protected:
    // XOR演算
    Node* XorOperate(Node* lhs, Node* rhs)
    {
        return reinterpret_cast<Node*>(reinterpret_cast<std::intptr_t>(lhs) ^ reinterpret_cast<std::intptr_t>(rhs));
    }

やってることは以下のような真理値をbit毎に計算しているだけである.

x1 x2 y
0 0 0
1 0 1
0 1 1
1 1 0

両方のビットが同じ値なら0,違うなら1というXORを取ってるだけ.

今回リスト側にはHeadとTailを持たせて、どっちからでも辿れるようにする.

protected:
    Node* m_head;
    Node* m_tail;
    int m_size;

今回作るデータはこんな感じのデータ.

XorList_01

Node Aのポインタは0101,Node Bのポインタは0010のような感じになっている.
そしてこのノードにはデータが入っているという状態.
bothは隣接したデータのポインタに対して、XORを取った状態となる.
Node BであればAのポインタとCのポインタのXOR.
Node CであればBのポインタとDのポインタのXORって感じ.

Headの場合は片方は何もない状態.
そのため、nullである0とXORを取るようにする.

これを考慮しつつまずは先頭へのNodeの追加を書いてみる.
先頭への追加なのでHead側への追加となる.
Nodeを作成して値を入れる.
その後、bothは先頭に追加するため、nullとheadに対してのXORを入れておく.
上の図で言えばB C DのNodeがある状態でAを追加するとすれば分かりやすい.
m_headはBの状態となっていて、AのbothはBとnullのXORなので、これでOKなのである.

void PushFront(T value)
{
    // node -> prevHead の形式になるように設定
    Node* node = new Node();
    node->m_value = value;
    // nullptrとxorしてもheadの値になるだけなので、そのまま突っ込む
    // ex: 110(head) ^ 000(nullptr) = 110 みたいなもの
    node->m_both = m_head;
}
    // ...

そして、Bのm_bothもAとCのXORにするために書き換えが必要.
そのためheadPrevにAと同等のものを入れて、headNextにCのものを入れる. あとはこの二つでXORを取れば、Bのm_both`も臨んだ形となる.

    if (m_head != nullptr)
    {
        // headのPrevをnodeに置き換えて計算
        Node* headPrev = node;
        Node* headNext = XorOperate(m_head->m_both, nullptr);

        // bothを更新
        m_head->m_both = XorOperate(headPrev, headNext);
    }

もしもheadがまだ何もない場合はtailに同じようなNodeを入れておく.
あくまで後ろからも1つのデータだけでも辿れるようにするための処置だね.
最後にheadに作ったNodeを登録すればOK.

    else
    {
        // nullptr <=> node <=> nullptrの構造にしておく
        m_tail = node;
    }

    // headを更新
    m_head = node;

    // Count Up
    m_size++;

次は逆にA,B,CのNodeがある状態でDを追加する場合.
この場合もDのm_bothがCとnullでXORを取って、CはB,DのポインタでXORを取るだけで全く処理は同じ.

void PushBack(T value)
{
    // node -> prevHead の形式になるように設定
    Node* node = new Node();
    node->m_value = value;
    // nullptrとxorしてもtailの値になるだけなので、そのまま突っ込む
    // ex: 110(tail) ^ 000(nullptr) = 110 みたいなもの
    node->m_both = m_tail;

    if (m_tail != nullptr)
    {
        // tailのNextをnodeに置き換えて計算
        Node* tailPrev = XorOperate(m_tail->m_both, nullptr);
        Node* tailNext = node;

        // bothを更新
        m_tail->m_both = XorOperate(tailPrev, tailNext);
    }
    else
    {
        // nullptr <=> node <=> nullptrの構造にしておく
        m_head = node;
    }

    // tailを更新
    m_tail = node;

    // Count Up
    m_size++;
}

さて、XORのデータが作れればデータを辿ることがすでに可能になっている.
Print関数を今回は作って、どうやってたどるのかを見てみよう.
今回は先頭から辿る場合を考えてみる.
currentにA,prevにnullとなるようにする. 

void Print()
{
    Node* current = m_head;
    Node* prev = nullptr;
    String prints;

    // ...
}

辿る際の関数は以下のような感じ.

    while (current)
    {
        prints += Format(current->m_value) + U",";

        // 次へ
        Node* next = XorOperate(prev, current->m_both);
        prev = current;
        current = next;
    }

    s3d::Print << prints;
    s3d::Print << U"Size: " << Size();

各Nodeには文字列でA,B,C,Dが入ってるとしてみよう.

まず最初のループ、currentがAでprevnullの場合.
A,という文字列を格納.
その後、next= 0000(null)^0010(A->m_both)=0010(B)となる.
こうして、prev=A,current=Bをいれて終了.

次のループ、prev=A,current=Bなのでループは継続.
A,B,という文字列を格納.
その後、next= 0101(A)^0001(B->m_both)=0100(C)となる.
こうして、prev=B,current=Cをいれて終了.

次のループ、prev=B,current=Cなのでループは継続.
A,B,C,という文字列を格納.
その後、next= 0010(B)^1011(C->m_both)=1001(D)となる.
こうして、prev=C,current=Dをいれて終了.

次のループ、prev=C,current=Dなのでループは継続.
A,B,C,D,という文字列を格納.
その後、next= 0100(C)^0100(D->m_both)=0000(null)となる.
こうして、prev=D,current=nullをいれて終了.

次のループ、prev=C,current=nullなのでループは終了.
文字列がA,B,C,D,となるため、ちゃんと辿れてるのが分かる！！

これ不思議な感じがするけど、ちゃんと考えてみると分かりやすい.
Bのm_bothを考えてみるとACA^Cである.
そして、実際に次に辿るときはA(AC)A^(A^C)という演算をやる.
これを実際にやると以下のようになる.

A(AC)=(AA)C=0C=C \begin{equation} \begin{split} A^(A^C) &= (A^A) ^ C \\ &= 0 ^ C \\ = C \end{split} \end{equation}

こんな感じでAとCのXORをbothに入れておけば、前の状態のポインタが上手く打ち消してくれて次のものが求まるという訳だ.

CからBという逆方向を求める場合も同じ感じだ.
Cのm_bothはBDB^Dであり,逆から辿るので(B^D)^Dという風になる.

(BD)D=B(DD)=B0=B \begin{equation} \begin{split} (B^D)^D &= B ^ (D^D) \\ &= B ^ 0 \\ = B \end{split} \end{equation}

いや～、XORを使うことで上手く求められるわけだ！賢い～.

一応削除に関しても見ておこう.
やることは先ほどと同じで、先頭を消してつなぎ合わせを変えてあげればよい.
まずcurrent=A,next=A->both=null^B=Bとして考えよう.
つまり、current=A,next=Bだ.

void PopFront()
{
    // データがないならReturn
    if (m_head == nullptr)
    {
        return;
    }

    Node* current = m_head;
    Node* next = current->m_both; // headなので、bothはnextのポインタと同じはず

    // ...

この場合BがHeadになるので,A^(B->m_both)=A^(A^C)=Cでポインタを求めて、nextNext=Cとする.
そして、B->m_both=null^C=Cのようになるため,そのままnextNextを突っ込んであげる.

    if (next)
    {
        // currentはnextから見たらprevなので、XORすると更にnextが手に入る
        // current <=> next <=> nextNext の場合、nextNextのpointerを手に入れて、
        // nullptr <=> next <=> nextNextにしてる
        Node* nextNext = XorOperate(current, next->m_both);
        next->m_both = nextNext;
    }

    // ...

もし次がない場合は今のノードを消した何も残らないので、tail側のデータも消す.

    else
    {
        // nullptr <=> nullptrの構造にしておく
        m_tail = nullptr;
    }
    // ...

あとはheadを更新して、先頭のノードを消してあげれば終わり.

    // headを更新
    m_head = next;

    // 削除
    delete current;

    // Count Down
    m_size--;
}

今回は先頭からだったけど、後ろから消すことも可能.
これは同じ流れで組んであげればよい.
説明はしないが、全く同じ流れで削除が可能！

void PopBack()
{
    // データがないならReturn
    if (m_tail == nullptr)
    {
        return;
    }

    Node* current = m_tail;
    Node* prev = current->m_both; // headなので、bothはprevのポインタと同じはず

    if (prev)
    {
        // currentはprevから見たらnextなので、XORすると更にprevが手に入る
        // prevPrev <=> prev <=> current の場合、prevPrevのpointerを手に入れて、
        // prevPrev <=> prev <=> nullptrにしてる
        Node* prevPrev = XorOperate(current, prev->m_both);
        prev->m_both = prevPrev;
    }
    else
    {
        // nullptr <=> nullptrの構造にしておく
        m_head = nullptr;
    }

    // headを更新
    m_tail = prev;

    // 削除
    delete current;

    // Count Down
    m_size--;
}

これがXOR List.
ポインタという唯一のデータとXOR演算を上手く使うことで、データ量を減らすという賢いものでした～.
これで三章も終わり.