编程领域---试验性项目---太极１号

前言

以前听说，sun公司提了一个理念：ＮＣ(网络计算机)．觉得很好，可是一直没有找到一种实现架构，在我苦苦思索中想到了一种架构，并斗胆把它提出来，供大家ＸＸＸ．

 

ＮＣ架构－－太极１号

 

数据库　－－＞　内存

操作系统　－－＞　ＣＰＵ

网络　－－＞　主板

 

数据结构－无侵害链表

目前的链表有两种典型实现：指针，数组；它们都具有侵害性质；

在插入或删除时指针要修改两次next的指向，数组就有整体往后挪

而采用三叉树实现链表,可以做到无侵害的, 实现方式如下:

 

node{index,value}

 

index采用三叉树编码:

 

最初一个是   2

 

在它之前插入 编码值是  12

在它之后插入 编码值是  32

 

在12之前插入  编码值是  112

在12之后插入  编码值是  132

 

 

在132之前插入  编码值是  1312

在132之后插入  编码值是  1322

 

 

规律就是,

在之前插入, 末尾-1, 并且附加2

在之后插入, 末尾+1,并且附加2

 

为此插入时只需要改变自身的index编码, 就可实现插入, 这是无侵害的.

 

如果要遍历, 需要按index的字典编码排序, 你可能说这把问题变复杂了.

但是如果, 这个是存在数据库的table中,  然后用一个order by, 就轻松搞定排序问题.

 

然后遍历,插入,删除, 都很容易实现.

 

这个就当成太极1号的第一个数据结构吧!

 

评论

4 楼 suifeng 2009-04-07  

歆渊 写道

三叉树这个原理性比较强，我做过一个类似的实用工具类，在开源的 wow.dev.java.net 里面，av.wow.util.Designator 这个类，当时做过评测： Firing 30000 random insert session with each 100 records at max. Designator length exceeds 250 after fired 23486 insert sessions and inserted 1178115 records. ------------------------------------------------- Total inserted designators: 1504340 Longest one is [257]: +}}}}}}}}}}}}}}v03000000000000030000000F0E}}}}}{F00000}}}}}}y000000300000EU}}}}}}}x}}}Vw}{00002}}}}}}}}}}}x{00002}}}}}}}}}}}}}W00000000000000102l0000000002}}}}}}}}}}}x}}Vw{000000000000002}}}{00000V000030000000000}}{000000E}}}}}}}}}}t}}}}}}}}}}}000000000000V Average length: 117 Length above 2: 349 => 0‰ Length above 4: 1457 => 0‰ Length above 8: 7511 => 4‰ Length above 16: 41436 => 27‰ Length above 32: 145931 => 97‰ Length above 64: 657302 => 436‰ Length above 128: 650346 => 432‰ Length above 256: 8 => 0‰ Length above 512: 0 => 0‰ Errors: 0结论是用这个算法，随机插入100万以上的条目后才会让这里所说的“index”的长度超过250。基本够WoW实用了。其实做到这个份上，原理上更像是类似小数的表示法了，只要后面追加个数字，就可以得到介于两个没法不延长位数就有中间值的两个数字之间的数值了。

多谢指点, 并给出试验数据, 受用了.

3 楼 歆渊 2009-04-07  

三叉树这个原理性比较强，我做过一个类似的实用工具类，在开源的 wow.dev.java.net 里面，av.wow.util.Designator 这个类，当时做过评测：

Firing 30000 random insert session with each 100 records at max.
Designator length exceeds 250 after fired 23486 insert sessions and inserted 1178115 records.
-------------------------------------------------
Total inserted designators: 1504340
Longest one is [257]: +}}}}}}}}}}}}}}v03000000000000030000000F0E}}}}}{F00000}}}}}}y000000300000EU}}}}}}}x}}}Vw}{00002}}}}}}}}}}}x{00002}}}}}}}}}}}}}W00000000000000102l0000000002}}}}}}}}}}}x}}Vw{000000000000002}}}{00000V000030000000000}}{000000E}}}}}}}}}}t}}}}}}}}}}}000000000000V
Average length: 117
Length above 2: 349 => 0‰
Length above 4: 1457 => 0‰
Length above 8: 7511 => 4‰
Length above 16: 41436 => 27‰
Length above 32: 145931 => 97‰
Length above 64: 657302 => 436‰
Length above 128: 650346 => 432‰
Length above 256: 8 => 0‰
Length above 512: 0 => 0‰
Errors: 0

结论是用这个算法，随机插入100万以上的条目后才会让这里所说的“index”的长度超过250。基本够WoW实用了。

其实做到这个份上，原理上更像是类似小数的表示法了，只要后面追加个数字，就可以得到介于两个没法不延长位数就有中间值的两个数字之间的数值了。

2 楼 suifeng 2009-02-18  

嗯,
大数据量是个问题,
如果1000个都插入到最后就有 10000个3, 跟一个2
是比较长了, 在想是否用二进制代替

1 楼 litchi 2009-02-18  

那我里面要是有1000个元素，最后一个元素的index得是啥样啊。。。