[学习笔记] Pascal集合类型内存结构解决方案

2012-02-27

[学习笔记] Pascal集合类型内存结构个人学习笔记一篇，与大家交流探讨。顶者有分。指出错误或提出建议者，另有

[学习笔记] Pascal集合类型内存结构
个人学习笔记一篇，与大家交流探讨。顶者有分。指出错误或提出建议者，另有高分相赠。

//题目：Pascal集合类型内存结构
//作者：LihuaSoft
//日期：2007年2月3日
//链接：http://rabbitfox.blog.sohu.com/32519247.html

(* 作人要厚道，转载请注明作者及出处 *)

一、问题的起源：

2007年初，CSDN的Delphi版上有一个贴子(http://community.csdn.net/Expert/topic/5315/5315550.xml?temp=.4219171)，内容如下：
“请问两个数组或TStringList怎么进行与或非运算？比如数组是1：1,2,3；2：1,3,4,5。怎么弄呢？最好是TStringList进行运算，然后生成一个新的List。”
看到这个贴子时，我想：最常用的办法就是遍历了，也已经有人回贴：“遍历”。用TStringList甚至还不如遍历来得实在。脑中忽然闪现：“集合”运算(并集、交集等)是否可以借鉴？于是想立即实践一下。后来因为工作忙，这件事情耽搁了一段时间。今天终于可以静下心来研究了。

二、Pascal集合类型对象的内存结构：

我写了下面这段代码，看了一下集合类型的内存结构：
var
MySet : Set of Byte;
P : ^Byte;
I : integer;
begin
MySet := [1,3,5,7];
P := @MySet;
for I := 0 to SizeOf(MySet)-1 do
begin
Memo1.Text := Memo1.Text + Format( ' %.2x ',[P^]);
Inc(P);
end;
end;

结果是(16进制)： AA 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

给集合MySet赋值为[0]，那么第一个字节的显示结果就是 01 ；赋值为[1]，结果就是 02 ；赋值为[](空集)，则这32个字节全部是 00 。

由此可知：Pascal集合类型是一个有序类型，占用32个字节(SizeOf)的内存空间(256位)，集合成员也必须是有序类型，取值范围为 NULL 或[0..255]。一个集合的0～256个成员，如果存在某成员，则该成员相应的位值为1，否则为0，如下所示：

Bit: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0 0 0 0 0 0
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
元素 7 6 5 4 3 2 1 0 15141312 1110 9 8 ... 255 254 253 252 251 250 249 248
字节 | <-- 1字节 ----| | <-- 2字节 -----| ... | <------ 32字节 ---------------|

集合类型，亦遵循“高位字节在后、低位字节在前”的内存原则。

三、对前述CSDN贴子的解答：

基于对Pascal集合类型的认识，我写了下面这个程序，作为对前述贴子的解答。声明：该贴子问题的正解，仍是“遍历”，之所以提供下面这种解决方案，纯粹为了迎合“与或非运算”这种思路，以及自己“练练手”的欲望。另外，数组元素只能是有序类型，并且数组长度不能超256。

type
TArr = array of Byte;//Char数组亦可

procedure CompArraysUseSet(const A1,A2 : TArr; var A : TArr; CompType : Char);
{ 编程：LihuaSoft；做人要厚道，转载请注明作者及出处 }
var
Set1,Set2,Set3 : Set of Byte;
P : ^Byte;
I, J, Sum : integer;
begin
{ 给Set1、Set2、Set3赋空值,即:空集 }
Set1 := [];
Set2 := [];
Set3 := [];
{ A1 ---> Set1 }
for I := Low(A1) to High(A1) do
begin
P := @Set1;
Inc(P, A1[I] div 8);
P^ := P^ or ( 1 shl (A1[I] mod 8) );
end;
{ A2 ---> Set2 }
for I := Low(A2) to High(A2) do
begin
P := @Set2;
Inc(P, A2[I] div 8);
P^ := P^ or ( 1 shl (A2[I] mod 8) );
end;
{ Set1、Set2运算，结果为Set3 }
case CompType of
'+ ' : Set3 := Set1 + Set2;//并集
'- ' : Set3 := Set1 - Set2;//差集
'* ' : Set3 := Set1 * Set2;//交集
else Set3 := Set1 + Set2;
end;
{ 设定返回数组的长度 }
Sum := 0;
for I := 0 to 255 do
if I in Set3 then Inc(Sum);
SetLength(A, Sum);
{ Set3 ---> 返回数组A }
P := @Set3;
Sum := Low(A);
for I := 0 to 31 do
begin
for J := 0 to 7 do
if (P^ and (1 shl J))> 0 then
begin
A[Sum] := I*8 + J;
Inc(Sum);
end;

Inc(P);
end;
end;

//以下是测试：

procedure TForm1.Button1Click(Sender: TObject);
var
A1, A2, A : TArr;
I : integer;
begin
SetLength(A1,3);
SetLength(A2,7);
A1[0] := 1; A1[1] := 3; A1[2] := 5;
A2[0] := 2; A2[1] := 5; A2[2] := 17; A2[3] := 22; A2[4] := 23;
A2[5] := 128; A2[6] := 255;
CompArraysUseSet(A2,A1,A, '+ ');//此处用“并集”运算方式 '+ '
for I := 0 to Length(A)-1 do
Memo1.Text := Memo1.Text + IntToStr(A[I]) + ', ';
end;

结果是：1,2,3,5,17,22,23,128,255,

四、另类收获：

需要紧凑的内存格式存储一个“数”，而Int64(8字节)等类型的长度又不能满足需要时，可以参考使用“集合”类型或Byte数组。

[解决办法]
不错，mark。
[解决办法]
procedure _SetIntersect; // *
asm
{ PROCEDURE _SetIntersect( VAR dest: Set; CONST src: Set; size: Byte);}
{ EAX = destination operand }
{ EDX = source operand }
{ CL = size of set (0 < size <= 32) }

@@loop:
MOV CH,[EDX]
INC EDX
AND [EAX],CH
INC EAX
DEC CL
JNZ @@loop
end;

procedure _SetSub; // -
asm
{ PROCEDURE _SetSub( VAR dest: Set; CONST src: Set; size: Byte); }
{ EAX = destination operand }
{ EDX = source operand }
{ CL = size of set (0 < size <= 32) }

@@loop:
MOV CH,[EDX]
NOT CH
INC EDX
AND [EAX],CH
INC EAX
DEC CL
JNZ @@loop
end;

procedure _SetUnion; // +
asm
{ PROCEDURE _SetUnion( VAR dest: Set; CONST src: Set; size: Byte); }
{ EAX = destination operand }
{ EDX = source operand }
{ CL = size of set (0 < size <= 32) }

@@loop:
MOV CH,[EDX]
INC EDX
OR [EAX],CH
INC EAX
DEC CL
JNZ @@loop
end;

[解决办法]
学习

热点排行

.NET

[学习笔记] Pascal集合类型内存结构解决方案