1

我已经为整数实现了跳过列表。在测试方法插入时，我在带有计数器 j 的 for 循环中插入从 1 到 1000000 的自然数。我也在使用秒表。附录：在实际程序中，值是双精度值，因为我在 double.NegativeInfinity 中使用了值为 double.PositiveInfinity 的哨兵。（但这不应该是问题）伪代码：

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;
    }
}

当我制作图形时间/节点数时，它是线性的，但图形步骤/节点是预期的对数。（步骤是方法插入中的循环次数（~操作））。

方法 insert 创建额外的节点并设置一些指针。节点的实现方式如下：

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 右邻居，存储在数组中，但图形时间/数量。节点的数量仍然是线性的（并且节点的步数/数量是对数的）。

4

1 回答 1

0

^是“异或”；

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

如果你从 0 循环到 11，那么是的——它看起来很线性——你不会注意到这个大小有任何退化。您可能想要Math.Pow而不是^，但硬编码会更简单1000000。

于 2013-04-15T06:27:42.523 回答