什么是PHP for C plus加“set”的等效函数(“Set是一种存储唯一元素的关联容器,其中元素本身是键。”)?
最佳答案
没有一个,但是他们可以be emulated。
这是链接死亡之前的实现拷贝。.所有内容PHP: Arrays
和SplObjectStorage
中的一组对象
我的一个项目QueryPath执行许多任务,这些任务需要维护一组唯一的对象。在寻求优化QueryPath的过程中,我一直在研究各种有效地存储对象集的方式,这些方式可以提供方便的包含检查。换句话说,我想要一个保留唯一对象列表的数据结构,并且可以快速告诉我该列表中是否存在某些对象。循环遍历列表内容的能力也是必需的。
最近,我将候选人列表缩小为两种方法:
使用老式数组来模拟哈希集。
使用PHP 5.2及更高版本中的SPLObjectStorage
系统。
在直接在QueryPath
中直接实现任何功能之前,我首先着手设计这两种方法,然后在这两种方法上运行一些微基准测试(在Crell的帮助下)。说结果令人惊讶是轻描淡写。基准测试可能会改变Drupal
内部和外部结构我将来代码的方式。
设计作品
在介绍基准测试之前,我想快速解释一下我确定的两种设计。
模拟哈希集的数组
我一直在考虑的第一种方法是使用PHP的标准array()模拟由哈希映射支持的集合(“哈希集”)。集合是一种数据结构,旨在保留唯一元素的列表。就我而言,我有兴趣存储一组唯一的DOM对象。哈希集是使用哈希表实现的集合,其中键是存储值的唯一标识符。尽管通常会编写一个类来封装此功能,但我还是决定将实现作为裸露的阵列进行测试,顶部没有任何间接层。换句话说,我将要介绍的是哈希集实现的内部。
目标:以一种使(a)易于迭代,(b)廉价的方式检查成员身份的方式存储(唯一)一组对象。
策略:创建一个关联数组,其中键是哈希ID,值是对象。
有了相当好的哈希函数,上面概述的策略应该可以按需工作。
“相当不错的哈希函数”-这是第一个陷阱。如何为DOMDocument
这样的对象生成良好的哈希函数?一种(错误的)方法是序列化对象,然后获取其MD5哈希值。但是,这将不适用于许多对象,尤其是无法序列化的任何对象。例如,DOMDocument
实际上由资源支持并且不能序列化。
但是,需要一种这样的功能。事实证明,PHP 5中有一个对象哈希函数。它称为spl_object_hash()
,它可以接收任何对象(甚至是不是 native PHP的对象)并为其生成哈希码。
使用spl_object_hash()
,我们可以构建一个简单的数据结构,其功能类似于哈希集。这个结构看起来像这样:
array(
$hashcode => $object
);
例如,我们生成一个像这样的条目:
$object = new stdClass();
$hashcode = spl_object_hash($object);
$arr = array(
$hashcode => $object
);
那么,在上面的示例中,哈希码字符串是数组键,而对象本身是数组值。请注意,由于每次重新哈希对象时,哈希码都是相同的,因此它不仅用作比较点(“如果对象a的hashkey ==对象b的hashkey,则a == b”),它还可以用作唯一性约束。每个数组只能存在一个具有指定哈希码的对象,因此不可能将同一对象的两个拷贝(实际上是两个引用)放置在数组中。
对于这样的数据结构,我们拥有许多易于使用的函数来操纵该结构,因为我们拥有了所有PHP数组函数。因此,从某种程度上来说,这是一个有吸引力的选择。
至少在我们的上下文中,最重要的任务是确定条目是否存在于集合内部。此检查有两个可能的候选者,并且都需要提供哈希码:
使用array_key_exists()检查 key 是否存在。
检查是否使用isset()设置了 key 。
为了简化,isset()比array_key_exists()更快,并且在我们的上下文中提供了相同的功能,因此我们将使用它。 (它们对空值的处理方式不同,这对我们没有影响。将不会将空值插入到集合中。)
因此,考虑到这一点,我们将使用类似以下内容的方法进行遏制检查:
$object = new stdClass();
$hashkey = spl_object_hash($object);
// ...
// Check whether $arr has the $object.
if (isset($arr[$hashkey])) {
// Do something...
}
再次,使用模拟哈希集的数组允许我们使用所有现有的数组函数,并且还提供了简单的可迭代性。我们可以轻松地将其放入foreach循环并迭代内容。不过,在查看其性能之前,让我们看一下其他可能的解决方案。
使用SplObjectStorage
正在考虑的第二种方法使用PHP 5.2+中的新
SplObjectStorage
类(可能在5.1中)。由C实现支持的此类为类提供了一种类似于集合的存储机制。它强制唯一性;每个对象只能存储一个。由于它实现了Iterable接口(interface),因此它也是可遍历的。这意味着您可以在诸如foreach之类的循环中使用它。 (不利的一面是,PHP 5.2中的版本不提供任何随机访问或基于索引的访问的方法。PHP5.3中的版本纠正了这一缺点。)目标:以一种使(a)易于迭代,(b)廉价的方式检查成员身份的方式存储(唯一)一组对象。
策略:实例化
SplObjectStorage
类的对象,并在其中存储对对象的引用。创建一个新的SplObjectStorage很简单:
$objectStore = new SplObjectStorage();
SplObjectStorage
实例不仅保留有关对象的唯一性信息,而且还以可预测的顺序存储对象。 SplObjectStorage
是FIFO-先进先出。添加对象是使用
attach()
方法完成的:$objectStore = new SplObjectStorage();
$object = new stdClass();
$objectStore->attach($object);
应当注意,attach将只附加一个对象一次。如果将同一对象两次传递给
attach()
,则第二次尝试将被忽略。因此,没有必要在contains()
调用之前执行attach()
调用。这样做是多余且昂贵的。检查SplObjectStorage实例中是否存在对象也很简单:
$objectStore = new SplObjectStorage();
$object = new stdClass();
$objectStore->attach($object);
// ...
if ($objectStore->contains($object)) {
// Do something...
}
尽管
SplObjectStorage
的数量远不及数组可以访问的支持方法,但它允许迭代,并且对存储在其中的对象的访问有所限制。在许多用例中(包括我正在研究的用例),SplObjectStorage
提供了必需的功能。现在,我们看了两个候选数据结构,让我们看看它们的性能。
比较
任何看过Larry(Crell)Garfield的数组和
SPL ArrayAccess
对象微基准的人都可能会以与Larry和我相同的期望进入这组基准。我们期望PHP的数组能够将SplObjectStorage吹倒。毕竟,数组是PHP中的原始类型,并且已经享受了多年的优化。但是,SplObjectStorage
的文档指出,SplObjectStorage
对象的搜索时间为O(1),如果基本速度与数组的速度相似,则肯定会使其具有竞争力。我的测试环境是:
具有3.06 Ghz Intel Core 2 Duo和2G 800mhz DDR2 RAM的iMac(当前版本)。 MAMP 1.72(PHP 5.2.5)提供AMP堆栈。
配备2.4 GHz Intel Core 2 Duo和4G 667MHz DDR2 RAM的MacBook Pro。 MAMP 1.72(PHP 5.2.5)提供AMP堆栈。
在这两种情况下,性能测试的平均值大致相同。本文中的基准来自第二个系统。
我们的基本测试策略是构建一个简单的测试,以捕获有关三件事的信息:
加载数据结构所花费的时间
查找数据结构所花费的时间
数据结构使用的内存量
我们已尽力将其他因素对测试的影响降到最低。这是我们的测试脚本:
<?php
/**
* Object hashing tests.
*/
$sos = new SplObjectStorage();
$docs = array();
$iterations = 100000;
for ($i = 0; $i < $iterations; ++$i) {
$doc = new DOMDocument();
//$doc = new stdClass();
$docs[] = $doc;
}
$start = $finis = 0;
$mem_empty = memory_get_usage();
// Load the SplObjectStorage
$start = microtime(TRUE);
foreach ($docs as $d) {
$sos->attach($d);
}
$finis = microtime(TRUE);
$time_to_fill = $finis - $start;
// Check membership on the object storage
$start = microtime(FALSE);
foreach ($docs as $d) {
$sos->contains($d);
}
$finis = microtime(FALSE);
$time_to_check = $finis - $start;
$mem_spl = memory_get_usage();
$mem_used = $mem_spl - $mem_empty;
printf("SplObjectStorage:\nTime to fill: %0.12f.\nTime to check: %0.12f.\nMemory: %d\n\n", $time_to_fill, $time_to_check, $mem_used);
unset($sos);
$mem_empty = memory_get_usage();
// Test arrays:
$start = microtime(TRUE);
$arr = array();
// Load the array
foreach ($docs as $d) {
$arr[spl_object_hash($d)] = $d;
}
$finis = microtime(TRUE);
$time_to_fill = $finis - $start;
// Check membership on the array
$start = microtime(FALSE);
foreach ($docs as $d) {
//$arr[spl_object_hash($d)];
isset($arr[spl_object_hash($d)]);
}
$finis = microtime(FALSE);
$time_to_check = $finis - $start;
$mem_arr = memory_get_usage();
$mem_used = $mem_arr - $mem_empty;
printf("Arrays:\nTime to fill: %0.12f.\nTime to check: %0.12f.\nMemory: %d\n\n", $time_to_fill, $time_to_check, $mem_used);
?>
上面的测试分为四个单独的测试。前两个测试
SplObjectStorage
方法处理加载和包含检查的效果。后两个对我们的简易数组数据结构执行相同的测试。上面的测试有两点值得注意。
首先,我们测试的首选对象是
DOMDocument
。有几个原因。显而易见的原因是,此测试是出于优化QueryPath
的目的而完成的,它可以与DOM实现中的元素一起使用。但是,还有两个有趣的原因。一是DOMDocuments不是轻量级的。另一个是DOMDocuments
由C实现支持,使它们成为存储对象时比较困难的情况之一。 (例如,无法方便地对其进行序列化。)也就是说,在观察结果之后,我们对基本的
stdClass
对象进行了重复测试,发现性能结果几乎相同,并且内存使用情况成比例。值得一提的第二件事是,我们使用了100,000次迭代进行测试。这大约是我的PHP配置在内存用尽之前所允许的上限。除此之外,该数字是任意选择的。当我以较低的迭代次数运行测试时,
SplObjectStorage
肯定会线性缩放。对于较小的数据集,阵列性能的可预测性较差(标准偏差较大),尽管较小尺寸的阵列性能似乎与较大尺寸的阵列(更可预测)大致相同。结果
那么这两种策略在我们的微基准测试中表现如何?这是运行上述命令时生成的输出的代表性示例:
SplObjectStorage:
Time to fill: 0.085041999817.
Time to check: 0.073099000000.
Memory: 6124624
Arrays:
Time to fill: 0.193022966385.
Time to check: 0.153498000000.
Memory: 8524352
在多次运行中求平均值,
SplObjectStorage
执行填充和检查功能的速度是上述数组方法的两倍。我们尝试了上述测试的各种排列。例如,以下是带有stdClass object
的同一测试的结果:SplObjectStorage:
Time to fill: 0.082209110260.
Time to check: 0.070617000000.
Memory: 6124624
Arrays:
Time to fill: 0.189271926880.
Time to check: 0.152644000000.
Memory: 8524360
没有太大的不同。即使向我们存储的对象添加任意数据也不会影响
SplObjectStorage
花费的时间(尽管似乎确实稍微增加了数组的时间)。我们的结论是,
SplObjectStorage
确实是在集中存储许多对象的更好解决方案。在过去的一周中,我已将QueryPath
移植到SplObjectStorage
(请参阅GitHub上的Quark分支-现有的Drupal
QueryPath
模块可以使用此实验分支而无需更改),并且可能会继续进行基准测试。但是初步结果似乎为最佳方法提供了明确的指示。这些发现的结果是,我不太愿意将数组默认为“最佳选择”,因为它们是基本数据类型。如果
SPL
库包含的性能优于数组,则应在适当的时候使用它们。从QueryPath到我的Drupal模块,我希望这些发现会影响我的代码。感谢Crell的帮助,也感谢Frameweld的Eddie首先激发了我对这两种方法的研究。