深入了解过PHP的都知道,PHP底层设计和实现有很多可取之处.
就拿array这个PHP中最强大的数据结构来说,其底层实现独树一帜,有很多精妙绝伦的细节设计.
数组和字典有序的实现,打包数组优化(普通数组将被视为C数组处理),数组的动态扩容策略,哈希的实现和哈希冲突的解决.
全在这张图展示的数据结构中.
透过PHP的array,可以实现更多高级数据结构.
比如Redis的有序集合,用PHP array实现的话,只需两步:
1.插入时,用二分查找找到插入位置.
2.然后用array_splice把元素插入到数组中.
同理,用PHP array也可以轻松实现定时器的管理,而不需要实现小根堆,跳表,红黑树这些复杂的数据结构.
binary_search(找位置) + array_splice(插入删除) + array_pop(弹出最小)- <?php
- public function timer_pos($ele, $arr) {
- $min = 0;
- $max = count($arr)-1;
- while ($min <= $max) {
- $mid = floor(($min+$max)/2);
- $value = $arr[$mid][&#39;time&#39;];
- if ($ele === $value) {
- return $mid;
- }
- if ($ele > $value) {
- $max = $mid - 1;
- } else {
- $min = $mid + 1;
- }
- }
- $mid = floor(($min+$max)/2) + 1;
- return $mid;
- }
- public function timer_add($after_ms, $func, $tick = 0, $timer_id = false) {
- // ...
- $pos = $this->timer_pos($timer[&#39;time&#39;], $this->timers);
- array_splice($this->timers, $pos, 0, array($timer));
- // ...
- }
复制代码 不过需要注意的是,数组这种内存线性连续分布的基础数据结构,虽然拥有有序支持二分查找和O(1)性能的随机访问速度,但相比跳表和树这些内存分布离散的数据结构,数组在扩容时成本比较高.
动态大小的数组在扩容时非常简单粗暴,底层数组大小不够时,会申请一块比原来更大(涉及策略,PHP底层是原来的2倍)的内存,然后把原来的数组复制到新的数组里.
除了PHP的array,PHP的字符串设计得也很好,了解过的都知道,PHP底层字符串(zend_string/smart_str)跟Redis的SDS字符串设计上基本是一样的.
菜鸡只会低头啄米,而雄鹰却能看到优秀的软件之间的共通之处. |