不使用引用计数交换字符串

Question

不使用引用计数交换字符串

7

在快速排序算法中，大量时间花费在交换变量temp:=var[i]; var[i]:=var[j]; var[j]:=temp上。当变量为整数时，对于一个较大的随机数组，需要140毫秒的时间。当变量为字符串时，时间是750毫秒。我认为其中许多差异是由于需要在所有三个赋值语句中更新引用计数所导致的。但这是必要的吗？毕竟，在这三个赋值之前和之后，var[i]和var[j]的引用计数将保持不变。下面的代码会破坏它们吗？（注意，它并没有解决速度问题，只是出于兴趣）：

    // P : Pstring;
    move(values[i],P,sizeOf(Pstring));
    move(values[j],values[i],sizeOf(Pstring));
    move(P,values[i],sizeOf(Pstring));

没有临时变量。只有两个指向字符串的指针互换。如果这没问题，是否有一个Delphi函数用于交换两个指针？

- user3212191

使用 Pointer(...) 强制类型转换比调用 Move 更快。这是规避引用计数的惯用方式。 - David Heffernan

1

@David - 长度和引用计数存储在该指针的负偏移量处，除非编译器的最新版本发生了变化，我错过了。交换指针不会移动那些数据，除非我在这里漏掉了什么。（如果事情已经改变并且我错过了它，请您指向文档，以便我可以更新我的知识？） - Ken White

首先，创建一个指向记录数组的指针数组，每个记录包含指向字符串数据和字符串索引的指针。然后对该指针数组进行排序，移动指针位置。排序完成后，遍历记录数组以重新排列原始字符串数组，并删除记录数组。 - fpiette

2

@Ken 交换指针并不会移动元数据。但这没关系，因为这些是引用类型。交换指针就足够了。这是一个众所周知的优化，由Spring4d等库使用。 - David Heffernan

@KenWhite：类型为string的变量只是指向字符串堆对象的指针。该对象包含实际字符串以及在非负偏移处的终止空值和元数据（代码页、引用计数和长度）在负偏移处。 - Andreas Rejbrand

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Heffernan · Accepted Answer

你提出的是一个众所周知且有效的优化方法。与其调用 Move 函数，更好的做法是通过强制类型转换直接进行赋值操作，以避免生成引用计数代码。

var
  temp: Pointer;
.... 
temp := Pointer(var[i]);
Pointer(var[i]) := Pointer(var[j]);
Pointer(var[j]) := temp;

为了使这个工作正常运行，您需要确信在交换过程中不会发生任何异常。对有效内存的简单赋值不会引发异常，因此这个问题可以轻松地被解决。