public class MyQueue
{
public class Node
{
public Node(object data)
{
Data = data;
} public Node NextNode = null;
public Node UpNode = null;
public object Data = null;
}
Node beginNode = null;
Node endNode = null; public override string ToString()
{
return count.ToString();
} int count = 0; public int Count
{
get
{
return count;
}
set
{
count = value;
}
} public Node Dequeue()
{
if (beginNode.NextNode == null && count>1)
{
return null;
}
Node Rerurn = beginNode;
if (Rerurn != null)
{
beginNode = beginNode.NextNode;
--count;
Rerurn.NextNode = null;
Rerurn.UpNode = null; } return Rerurn;
} public void Enqueue(Node node)
{
if (beginNode == null)
{
beginNode = node;
endNode = node;
}
else
{
node.UpNode = endNode;
endNode.NextNode = node;
endNode = node;
endNode.NextNode = null;
}
++count;
}
}
这是我的代码,这段代码我是应用在基数排序中的...作为基数排序的桶应该是插入,以及移出的操作都是O(1)的操作,
经过我的测试ArrayList,Queue,LinkedList的插入以及移出的的操作近似为O(nLogn),这不是我需要的..包括上面的代码.我不清楚这是为什么,因此向大家提问.
To:jinjazz
.net奇怪吗？如果你学过基础的数据结构应该知道，链表的时间负责度不可能是o(1)的，hashtable才有可能
以上这是你的回复
我原贴写的是
"如何用C#实现一个添加,移出操作的时间复杂度为O(1)的双向链表"
添加移出操作的时间复杂度为O(1)的双向链表这个在数据结构与算法里早有定论,见<<数据结构与算法-面向对象的C++设计模式>> ISBN 7-5053-8339-6 P122
原贴见:
http://topic.csdn.net/u/20071115/15/de9587d8-aad9-4dd8-9a5d-73769068c167.htmlTo:viena你把http://topic.csdn.net/u/20071115/15/de9587d8-aad9-4dd8-9a5d-73769068c167.html移到非技术区我非常不满意,我已经向CSDN投诉了见
http://topic.csdn.net/u/20071119/10/c7787dd1-e5d7-4a59-8852-e37745cb0dec.html我可以很明确的说这个帖子不是作业贴,是我在讨论技术的帖子,如果你要是还挪,我会继续发,并且继续投诉...
添加只是理论上可以 实际达不到
因为碰撞折射消耗太大
请教可以告诉我双向链表应该如何写啊,谢谢了..
数据为guid，数据量依次为1000000、2000000...6000000
测试环境为Core2 2.33G，内存2G，win2003Server
测试的时候同时又很多软件在运行，对结果有一定的影响下面是测试结果，基本上是线性增长的，
所以说，不论以前队列的数据量为多少，每次进入队列的耗时基本是个常量也就是O(1)
MyQueue测试
610
1406
2078
2719
3609
4625
MyQueue第二次测试
625
1297
2172
2937
3469
4312
System.Collections.Queue测试
546
954
1390
2000
2328
2844
System.Collections.Queue第二次测试
453
969
1390
1969
2297
2875
另外,,,时间复杂度是理论上的.
并不可能完全的O(1).
------------------------------------------------------
我的测试是和C++比较过的.
在C++中双向链表在1000W整数测试中用P95统计中的确是O(1);
在.Net中这段代码只作了10W性能就急剧下降介于O(n)到O(nLogn),
个人猜测是垃圾回收的时候按链表顺序查找引用造成的性能损失,因此想禁用GC看看,不知道如何禁用GC.请教可以告诉我双向链表应该如何写啊,谢谢了..
---------------------------------------- 它不具备一般双向链表的任意位置插入删除操作.
你的这种特殊链表称之为队列, 我想你不会有什么疑问. 正如树是一种图, 但是我们都说 "查找树 ",没人说 "查找图 ". 特殊化就有特殊名称. 钻牛角尖没有什么意思.
------------------------------------------------------
我不想钻牛角尖,不论队列也好,链表也好,可以实现添加和移出操作是O(1)就好..你的代码, 将class声明成sealed class, 取消虚函数表.
将Data声明为范型.
-------------------------------------------------------
这些建议看不出和O(1)有什么关系,以前用的是范型,但是发现范型在单个添加的时候效率更低,因为每添加一个item都要进行类型测试,因此改为了obj总之这段代码要求极有效率,看代码不存在非O(1)的操作,可是实际测试数据又不能让人满意,希望大家帮看一下,谢谢了^_^
问题是我这个MyQueue没有用数组阿.性能还是不行...我晚上将测试结果以及方法放上来看看..
还要:把你那句endNode.NextNode = null;删除掉.=null操作实际就是回收的操作了.
顺注:你这个根本不是什么算法,而且很糟糕.你一旦不允许内存回收,你做这个测试的话,很快你的内存就会
爆满.我很同意jinjazz的说法,你把System.Collections.Queue初始capacity设置足够大的话,
System.Collections.Queue的性能是无可置疑的.还告诉你一个问题,System.Collections.Queue
是会满的..具体数量多少我忘记了,以前做的时候遇到过.但数量绝对不是int.MAX;
看楼主的标题,似乎对System.Collections的算法充满鄙视,看楼主的介绍,开发经验足足10年,看起来
我觉得很好笑.
关于垃圾回收GC的问题是这样的,当使用MyQueue,并且保存100W的数据时,GC进行垃圾回收的时候会查找引用,根据GC的工作原理,查找这100W数据的引用的时间
就至少是O(n)时间,因此在执行的时候就应该禁用GC,更何况是在密集运算的时候频繁调用GC...性能损失更是不可以控制的...
实现空方法Dispose()...禁用GC的目的不是阻止垃圾回收,是连查找引用都不可以.
不知道flarejune是谁的马甲阿?...上来的第一个回复就给我了...真是荣幸阿...
如果没有继承 IDisposable.Dispose的话,就不存在终结器.所以你的说法是错误的,不信可以自己测试下,不实现IDisposable接口然后使用
GC.SuppressFinalize,看看你的对象会不会被回收...
CSDN本来就是新手娱乐的地方,你一个扮演高手的人物存在.实在看得恶心,主要是看了你的
标题才进来的,说得那么牛.还害我特意看了你的所有帖子,想了解下到底高手是什么概念呢,
也把这里的处女贴送给了你.以前我的ID是vscharp的,在4年前吧..现在都忘记密码了,4年后
从来来这个地方看看,一来就遇到高手在叫嚣了.
------------------------------------------
看到你这句话 就生气
这能 证明C++不行吗
System.Collections.Queue是通过一个内置的数组实现的，当队列的初始容量不够大，在大数据量情况下，处理边界的时候队列会自动扩容，这时候涉及到一个array copy的操作，这可能是System.Collections.Queue一个比较大的性能损失的地方。但应该和gc没有关系，你把System.Collections.Queue的初始容量设到足够大，可能效果会好很多
将Queue初始化数量都设为和预期数量一致..Queue<int> myQueue = new Queue<int>(a);Queue myQueue = new Queue(a);
Thread testThread;
private void button3_Click(object sender, EventArgs e)
{
progressBar1.Minimum = 1000;
progressBar1.Maximum = 160000;
//MyQueue
//testThread = new Thread(new ThreadStart(test));
//Queue
//testThread = new Thread(new ThreadStart(test1));
//Queue<int>
testThread = new Thread(new ThreadStart(test2));
testThread.Priority = ThreadPriority.Highest;
testThread.Start();
} List<string> RETURN = new List<string>(); delegate void UpdateText(); void updateText()
{
textBox1.Lines = RETURN.ToArray();
progressBar1.Value = Count;
}
int Count = 0;
void test2()
{ for (int a = 1000; a < 160000; a += 1000)
{
Count = a;
int[] test = new int[a];
for (int b = 0; b < a; b++)
{
test[b] = b;
}
Queue<int> myQueue = new Queue<int>(a);
//以上是初始化代码 long bl2 = 0; for (int d = 0; d < 10; d++)
{
long bl1 = DateTime.Now.Ticks;
for (int c = 0; c < 1000; c++)
{ foreach (int item in test)
{
myQueue.Enqueue(item);
}
while (myQueue.Count > 0)
{
myQueue.Dequeue();
} }
bl1 = DateTime.Now.Ticks - bl1;
bl2 += bl1;
} //以上是运行测试代码
bl2 = (bl2 / 10) / a;
RETURN.Add(a.ToString() + " " + bl2.ToString());
this.Invoke(new UpdateText(this.updateText)); }
}
void test1()
{ for (int a = 1000; a < 160000; a += 1000)
{
Count = a;
int [] test = new int[a];
for (int b = 0; b < a; b++)
{
test[b] = b;
}
Queue myQueue = new Queue(a);
//以上是初始化代码 long bl2 = 0; for (int d = 0; d < 10; d++)
{
long bl1 = DateTime.Now.Ticks;
for (int c = 0; c < 1000; c++)
{ foreach (int item in test)
{
myQueue.Enqueue(item);
}
while (myQueue.Count > 0)
{
myQueue.Dequeue();
} }
bl1 = DateTime.Now.Ticks - bl1;
bl2 += bl1;
} //以上是运行测试代码
bl2 = (bl2 / 10) / a;
RETURN.Add(a.ToString() + " " + bl2.ToString());
this.Invoke(new UpdateText(this.updateText)); }
} void test( )
{
for (int a = 1000; a < 160000; a += 1000)
{
Count = a;
MyQueue.Node[] test = new MyQueue.Node[a];
for (int b = 0; b < a; b++)
{
test[b] = new MyQueue.Node(b);
}
MyQueue myQueue = new MyQueue();
//以上是初始化代码 long bl2 = 0; for (int d = 0; d < 10; d++)
{
long bl1 = DateTime.Now.Ticks;
for (int c = 0; c < 1000; c++)
{ foreach (MyQueue.Node item in test)
{
myQueue.Enqueue(item);
}
while (myQueue.Count > 0)
{
myQueue.Dequeue();
} }
bl1 = DateTime.Now.Ticks - bl1;
bl2 += bl1;
} //以上是运行测试代码
bl2 = (bl2 / 10) / a;
RETURN.Add(a.ToString() + " " + bl2.ToString());
this.Invoke(new UpdateText(this.updateText)); }
}
Count MyQueue Queue Queue<int>
1000 314 608 386
2000 240 561 280
3000 271 573 283
4000 245 580 280
5000 269 580 280
6000 237 489 279
7000 269 465 278
8000 230 469 281
9000 225 470 289
10000 263 469 278
11000 251 479 280
12000 260 472 300
13000 217 409 283
14000 253 403 285
15000 219 407 278
16000 221 455 280
17000 247 420 291
18000 220 410 285
19000 217 410 277
20000 244 428 280
21000 221 425 280
22000 224 417 283
23000 230 429 282
24000 225 427 421
25000 224 403 281
26000 224 445 281
27000 223 513 284
28000 220 527 278
29000 228 611 281
30000 227 765 290
31000 226 885 301
32000 229 941 349
33000 220 813 342
34000 221 664 418
35000 221 552 438
36000 218 470 580
37000 221 870 615
38000 223 489 618
39000 228 486 563
40000 234 566 433
41000 232 640 382
42000 229 909 337
43000 217 1340 312
44000 216 818 278
45000 225 619 288
46000 217 522 288
47000 228 457 281
48000 256 459 280
49000 290 459 286
50000 299 488 285
51000 325 608 291
52000 366 1025 288
53000 496 1348 298
54000 700 859 769
55000 598 591 534
56000 445 492 601
57000 360 464 476
58000 328 460 384
59000 259 476 318
60000 234 505 280
61000 235 652 292
62000 238 1117 288
63000 241 979 282
64000 253 605 282
65000 251 489 296
66000 272 450 286
67000 291 497 328
68000 402 585 402
69000 685 920 589
70000 741 961 647
71000 605 607 424
72000 398 454 329
73000 345 457 284
74000 250 490 236
75000 234 639 241
76000 237 1145 243
77000 274 1084 241
78000 230 604 260
79000 272 470 276
80000 334 448 328
81000 492 496 407
82000 610 727 701
83000 615 1050 618
84000 365 610 372
85000 299 471 305
86000 250 458 263
87000 242 526 256
88000 249 880 266
89000 330 912 261
90000 428 541 257
91000 580 482 322
92000 753 520 462
93000 478 880 720
94000 321 1293 479
95000 268 327
96000 246 276
97000 240 261
98000 279 252
99000 410 263
100000 623 259
101000 898 325
102000 608 466
103000 317 646
104000 269 446
105000 291 708
106000 359 256
107000 534 260
108000 966 289
109000 680 395
110000 404 522
111000 405 439
112000 289 302
113000 321 258
114000 432
115000 798
同意 测试这玩意不要加ui操作，直接console.write，ui很慢的
因此计时单元 bl2 bl1 都没有UI..在UI操作的时候都不计时..
long bl2 = 0; for (int d = 0; d < 10; d++)
{
long bl1 = DateTime.Now.Ticks;
for (int c = 0; c < 1000; c++)
{ foreach (MyQueue.Node item in test)
{
myQueue.Enqueue(item);
}
while (myQueue.Count > 0)
{
myQueue.Dequeue();
} }
bl1 = DateTime.Now.Ticks - bl1;
bl2 += bl1;
} //以上是运行测试代码
bl2 = (bl2 / 10) / a;
先不要生气了..图表的曲线是什么算法的曲线。。是O(1)吗?是O(n)吗?
请解释一下那是什么啊?
先别在一边笑了..看看图表的曲线是什么?,4年前就上CSDN了这样的曲线没见过吧?
顺注:这个你看来不是算法的,或者说很糟糕的东西,不过看曲线比System.Collections的还是强一点阿...
60000 425
61000 453
62000 444
63000 444
64000 446
65000 437
66000 412
67000 415
68000 420
69000 430
70000 417
71000 432
72000 438
73000 449
74000 439
75000 433
76000 436
77000 434
78000 427
79000 431
80000 418
81000 432
82000 440
83000 425
84000 432
85000 430
86000 435
87000 447
88000 444
89000 451
90000 442
91000 435
这样的,考虑到cpu切片和内存读写也有不稳定因素，应该可以认为是平稳的了，毕竟我们不是搞航天飞机的。你应该尽可能的把耗费资源的应用关掉。
图表曲线可以用数组存点 然后用连结相邻两点 所以时间复杂度 O(n)
还有 内存管理 是在你这个线程使用多了 会启用 是不定期的 谁知道启用多少次
希望你把这150个数据跑完在看看,我的也是双核,不过上面的测试数据不是在线程优先级为高的情况下跑得,是普通.
谢谢你的回答,我想这个帖子还是先结了吧,我在问问别人.
to:li45214521
谢谢你的回答,不过你说的问题总不是重点.
using System;
using System.Collections.Generic;
using System.Text;namespace test
{
struct node
{
public int[] Data;
public int front;
public int rear;
}
public class MyQueue
{
private node temp;
private int count;
public MyQueue()
{
temp.Data = new int[160000];
temp.front = 159999;
temp.rear = 159999;
count = 0;
}
public void Enqueue(int a)
{
if (temp.front == (temp.rear+1)%160000)
{
Console.WriteLine("queue is full");
}
else
{
temp.rear = (temp.rear + 1) % 160000;
temp.Data[temp.rear] = a;
count++;
}
}
public int Dequeue()
{
if (temp.rear == temp.front)
{
Console.WriteLine("queue is empty");
return 0;
}
else
{
temp.front = (temp.front + 1) % 160000;
count--;
return temp.Data[temp.front];
}
}
public int Count
{
get
{
return count;
}
}
}
class Program
{
static void Main(string[] args)
{
test();
}
private static void test()
{
for (int a = 1000; a < 160000; a += 1000)
{
MyQueue myQueue = new MyQueue();
//以上是初始化代码 long bl2 = 0; for (int d = 0; d < 10; d++)
{
long bl1 = DateTime.Now.Ticks;
for (int c = 0; c < 10000; c++)
{
myQueue.Enqueue(c);
}
for (int c = 0; c < 10000; c++)
{
myQueue.Dequeue();
}
bl1 = DateTime.Now.Ticks - bl1;
bl2 += bl1;
} //以上是运行测试代码
bl2 = (bl2 / 10) / a;
Console.WriteLine(a+", "+bl2.ToString());
}
Console.Read(); }
}
}