1

整数のスキップ リストを実装しました。メソッドの挿入をテストするときは、1 から 1000000 までの自然数をカウンター j の for ループに挿入します。私もストップウォッチを使っています。付録: 実際のプログラムでは、値は double です。(しかし、それは問題ではないはずです) 疑似コード:

MyList = new SkipList();
stopwatch.start();    
t1 = stopwatch.Elapsed.TotalMilliseconds;
for(int j = 0; j<1000000; j++){
    steps = MyList.insert(j);
    if(j%500==0){
        t2= stopwatch.Elapsed.TotalMilliseconds -t1;
        write j,t2 in a file1;
        write j,steps in a file2;
        t1 = t2;
    }
}

グラフの時間/ノード数を作成すると、線形ですが、グラフのステップ/ノードは予想どおり対数です。(steps は、メソッド挿入のループサイクル (~operations) の数です)。

メソッドの挿入により、追加のノードが作成され、いくつかのポインターが設定されます。ノードは次の方法で実装されます。

class Node 
{
    public Node right;//his right neighbour - maybe "null"
    public Node down;//his bottom neighbour -maybe null
    public int? value;//value
    public int depth;//level where node is present: 0, 1, 2 ...

    public Node(int i,Node rightt,Node downn,int depthh) {
        //constructor for node with two neighbours.
        value = i;
        right = rightt;
        down = downn;
        depth = depthh;
    }
   //there are some other contructors (for null Node etc.)
}
class SkipList
{
    public Node end;//upper right node
    public Node start;//upper left node
    public int depth;//depth of SkipList
    //there are left (-inf) and right sentinels (inf) in the SkipList.
}

スキップ リストはノードで構成されます。

Insert はクラス SkipList で定義され、次のように機能します。

public int Insert(int value2, int depth2)
    {
        //returns number of steps
        //depth2 is calculated like (int)(-Math.Log(0<=random double<1 ,2))
        //and works as expected - probability P(depth = k) = Math.Pow(0.5,k)

        //lsit of nodes, which will get a new right neighbour
        List<Node> list = new List<Node>();
        Node nod = start;
        int steps = 0;
        while (true) {
            if (nod.right.value >= value2)
            {
                //must be added to our list
                lsit.Add(nod);
                if (nod.down != null)
                    nod = nod.down;
                else
                    break;
            }
            else {
                nod = nod.right;
            }
            steps++;
        }

        //depth (of skipList) is maybe < depth2, so we must create
        //k = 2*(depth2-depth) new edge nodes and fix right pointers of left sentinels
        List<Node> newnodes = new List<Node>();
        for (int jj = 0; jj < depth2 - depth;jj++ )
        {
            steps++;
            //new sentinels
            Node end2 = new Node(double.PositiveInfinity, end,depth+jj+1);
            Node start2 = new Vozlisce(double.NegativeInfinity, end2,
                                                               start,depth+jj+1);
            start = start2;
            end = end2;
            newnodes.Add(start2);
        }

        //fix right pointers of nodes in the List list (from the beginning)
        Node x = new Node(value,list[list.Count-1].right,0);
        list[list.Count-1].right=x;
        int j =1;
        while(j<=Math.Min(depth2,depth)){
            steps++;
            //create new nodes with value value
            x = new Node(value,lsit[list.Count -(j+1)].right,x,j);
            list[list.Count-(j+1)].right = x;
            j++;
        }
        //if there are some new edge sentinels, we must fix their right neighbours
        // add the last depth2-depth nodes
        for(int tj=0;tj<depth2-depth;tj++){
            steps++;
            x = new Node(value,newnodes[tj].right,x,depth+tj+1);
            newnodes[tj].right = x;
        }

         depth = Math.Max(depth, depth2);           
         return steps;
    }

ノードがブロックであり、n = node.depth right neighbours が配列に格納されているスキップ リストのバージョンも実装しましたが、グラフは時間/数値です。ノード数は依然として線形です (ステップ数/ノード数は対数です)。

4

1 に答える 1

0

^「xor」です。

10 : 1010
 6 : 0110
---------
 ^ : 1100 = 12

0 から 11 までループする場合、はい - かなり線形に見えます - そのサイズ以上の劣化に気付かないでしょう。おそらくMath.Powではなく が必要です^が、ハードコードする方が簡単です1000000。

于 2013-04-15T06:27:42.523 に答える