使用php实现稀疏数组

场景一

在这里插入图片描述

场景二

报表的存储场景(这里暂不涉及表间取数和勾稽关系的计算)

image.png

而且此类的报表往往分类很多，例如：

image.png

---

定义

稀疏数组可以看做是普通数组的压缩，这里的普通数组特点是值无效数据量远大于有效数据量的数组

形如：

0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

稀疏数组形式：

11 11 2
1  2  1
2  4  2

---

为什么要进行压缩存储呢

• 原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少．
• 压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率 ．

备注:数据密集型结构不太适合这种解决方式

实现

第一行存储原始数据行数，列数，非0数据个数

其它每行都存储非0数行，列坐标和具体值

11 11 2  // 代表11行,11列,有2个非0值
1  2  1
2  4  2

这里分步解析,具体请看注释

具体代码如下:

image.png image.png

最终结果:

image.png

---

代码改进一下,采用文件存储,当然最终的数据是要存到db里的.

具体代码如下:

<?php

class HandelArray
{
    public $x;
    public $y;

    /**
     * 设置数组边界
     * HandelArray constructor.
     * @param $x
     * @param $y
     */
    public function __construct($x, $y)
    {
        $this->x = $x;
        $this->y = $y;
    }

    /**
     * 初始化数据
     * @return array
     */
    public function initArray(): array
    {
        $initArr = [];
        for ($i = 0; $i < $this->x; $i++) {
            for ($j = 0; $j < $this->y; $j++) {
                $initArr[$i][$j] = 0;
            }
        }
        return $initArr;
    }

    /**
     * 压缩数据(创建稀疏数组)
     * @param array $rawArr
     * @return array
     */
    public function sparseArray(array $rawArr): array
    {
        $sparseArray = [];
        $count = 0;
        $sparseArray[$this->x][$this->y] = 0;
        for ($i = 0; $i < $this->x; $i++) {
            if ($rawArr[$i] == 0) {
                continue;
            }
            for ($j = 0; $j < $this->y; $j++) {
                if ($rawArr[$i][$j] == 0) {
                    continue;
                }
                $count++;
                $sparseArray[$i][$j] = $rawArr[$i][$j];
            }
        }
        $sparseArray[$i][$j] = $count;
        return $sparseArray;

    }

    /**
     * 压缩数据恢复
     * @param array $sparseArray
     * @return array
     */
    public function recoveryArray(array $sparseArray): array
    {

        $recoveryArray = $this->initArray();

        // array_shift 会重置指针,请注意
        unset($sparseArray[$this->x]);

        foreach ($recoveryArray as $k => $v) {
            foreach ($recoveryArray[$k] as $index => $value) {
                // 获取非0值
                if (isset($sparseArray[$k][$index]) && $sparseArray[$k][$index] > 0) {
                    $recoveryArray[$k][$index] = $sparseArray[$k][$index];
                }
            }
        }
        return $recoveryArray;
    }


    /**
     * 打印压缩数据
     * @param array $data
     */
    public function printPosition(array $data): void
    {
        foreach ($data as $k => $v) {
            foreach ($data[$k] as $index => $value) {
                printf("%s %s %s" . PHP_EOL, $k, $index, $value);
            }
        }
    }

    /**
     * 打印结构数据
     * @param array $data
     */
    public function printStruct(array $data): void
    {
        foreach ($data as $k => $v) {
            foreach ($data[$k] as $index => $value) {
                printf("%s ", $value);
            }
            echo PHP_EOL;
        }
    }

    /**
     * 写入文件
     * @param string $file
     * @param array $data
     */
    public function sparseArrayToFile(string $file, array $data): bool
    {
        return file_put_contents($file, serialize($data), LOCK_EX);
    }

    /**
     * 读取文件
     * @param string $file
     * @return bool|string
     */
    public function sparseArrayFromFile(string $file)
    {
        return file_get_contents($file);
    }
}

// 1 初始化数组
$x = $y = 11;
$hArr = new HandelArray($x, $y);
$initArr = $hArr->initArray();

// 2 数据填充
$rawArr = $initArr;
$rawArr[1][2] = 1;
$rawArr[2][4] = 2;
print_r("创建原始数组" . PHP_EOL);
$hArr->sparseArrayToFile('raw_array.data', $rawArr);
$hArr->printStruct($rawArr);

// 3 创建稀疏数组
$sparseArray = $hArr->sparseArray($rawArr);
$hArr->sparseArrayToFile('sparse_array.data', $sparseArray);
$sparseArray = unserialize($hArr->sparseArrayFromFile('sparse_array.data'));

print_r("创建稀疏数组" . PHP_EOL);
$hArr->printPosition($sparseArray);

// 4 还原稀疏数组
print_r("还原稀疏数组" . PHP_EOL);
$rawArr = $hArr->recoveryArray($sparseArray);
$hArr->printStruct($rawArr);

打印输出:

image.png

我们来看下保存的文件大小.

image.png

我们在来对比文件内容:

压缩前 压缩后