5
5415
Unregistered / Unconfirmed
GUEST, unregistred user!
请问这段对于TCollection的理解没有错吧？多谢！
Turbo Pascal有一个比较好的数据结构，叫TCollection，而在Delphi下，被容器类给占用了这个名字。这种结构也退出了Delphi的普通数据结构中。
他的原理很简单。其实用了内存访问中的“段”的意思。
const
ItemsCount = 100;
HalfCount = ItemsCount div 2;
SegmentCount = 10000;
type
PSegment = ^TSegment;
TSegment = array [0..ItemsCount - 1] of Pointer;
PSegmentItem = ^TSegmentItem;
TSegmentItem= record
UsedCount: Integer;
Items: PSegment;
end;
PSegmentList = ^TSegmentList ;
TSegmentList = array [0..SegmentCount - 1] of TSegmentItem;
这样，追加操作O(1)。删除操作段不为空，只做回收操作，O(1)，删除后如果段为空，是O
的算法。插入算法，如果某个段不满，那就是O(1)。如果某个段已经满了，再插入还是O的算法。但这两个操作相对于纯粹的数组消耗的时间是数组算法消耗的时间除以ItemsCount。
遍历访问，需要全局索引转换为访问Item的段索引和Item内部索引，需要遍历。但相对于链表这种纯粹一个个遍历而言，速度还是快很多。也是链表访问的时间除以ItemsCount。
这种数据结构的存在，一部分纯粹是空间换时间，一部分是对数组插入算法和链表访问算法的不足，取得一个折衷方案。对于插入删除内容访问都非常频繁的程序，这个将是上选。
可能是保存的是一个个Item，所以原来命名为TCollection。
Turbo Pascal有一个比较好的数据结构，叫TCollection，而在Delphi下，被容器类给占用了这个名字。这种结构也退出了Delphi的普通数据结构中。
他的原理很简单。其实用了内存访问中的“段”的意思。
const
ItemsCount = 100;
HalfCount = ItemsCount div 2;
SegmentCount = 10000;
type
PSegment = ^TSegment;
TSegment = array [0..ItemsCount - 1] of Pointer;
PSegmentItem = ^TSegmentItem;
TSegmentItem= record
UsedCount: Integer;
Items: PSegment;
end;
PSegmentList = ^TSegmentList ;
TSegmentList = array [0..SegmentCount - 1] of TSegmentItem;
这样，追加操作O(1)。删除操作段不为空，只做回收操作，O(1)，删除后如果段为空，是O
的算法。插入算法，如果某个段不满，那就是O(1)。如果某个段已经满了，再插入还是O的算法。但这两个操作相对于纯粹的数组消耗的时间是数组算法消耗的时间除以ItemsCount。遍历访问，需要全局索引转换为访问Item的段索引和Item内部索引，需要遍历。但相对于链表这种纯粹一个个遍历而言，速度还是快很多。也是链表访问的时间除以ItemsCount。
这种数据结构的存在，一部分纯粹是空间换时间，一部分是对数组插入算法和链表访问算法的不足，取得一个折衷方案。对于插入删除内容访问都非常频繁的程序，这个将是上选。
可能是保存的是一个个Item，所以原来命名为TCollection。