快速搜索包含关联数组的php数组的方法

Question

我有以下的PHP数组：

array(
    (int) 0 => array(
        'records' => array(
            'id' => '25',
            'parent_id' => '1',
            'address' => '896167',
        )
    ),
    (int) 1 => array(
        'records' => array(
            'id' => '26',
            'parent_id' => '2',
            'address' => '890812',
        )
    ),
    (int) 2 => array(
        'records' => array(
            'id' => '28',
            'parent_id' => '16',
            'address' => '8A3813',
        )
    ),
    (int) 3 => array(
        'records' => array(
            'id' => '29',
            'parent_id' => '17',
            'address' => '8A3914',
        )
    )
)

假设我想找到包含 'id' => '29' 的键，有什么快速的方法可以搜索该数组并返回正确的键？在这种情况下，正确答案是3。

编辑：请问使用foreach循环遍历数组还是使用array_search会更快？或者它们的速度差不多？

- guagay_wk

---

它们是否总是按照ID排序？ - Mooseman

@Mooseman：id是该表中使用的主键。 - guagay_wk

如果这不需要非常复杂，只需遍历每个“对象”（具有键0、1、2、3），但如果有很多对象，则应使用快速算法。 - beeef

哇，最快的关键字呢？你为什么没有尝试呢？你为什么要追求最快呢？ - Kevin

如果你想要一个明确的答案，那就进行基准测试吧。使用foreach、for、while和数组函数，测试它们的微秒级时间开始和结束。 - Kevin

Answer 1

如果你需要做很多这样的搜索，最好创建一个“反向查找”数组。

也就是说，你只需要进行一次缓慢的线性工作，之后就可以快速进行哈希（关联数组）查找。

仅需一次：

$id2index = array();
foreach ($data as $index => $value) {
    $id2index[$value->id] = $index;
}

多次使用 - 找到给定id的索引：

$index = $id2index[$id];

- ToolmakerSteve

Answer 2

您的数据结构无法使用array_search()。您的foreach解决方案的时间复杂度为O(n)（array_search()也是如此）。您说记录按其id排序。然后，您可以使用二分查找算法，它的性能要好得多，具有O(log(n))的时间复杂度。

- Markus Malkusch

Answer 3

foreach ($data as $key => $value) {
    if ($value['records']['id'] == '29') break;
}
echo $key;

能够在线性时间内完成。

如果您的数组按ID排序，可以使用二分搜索，这将在对数时间内完成。

function binary_search($needle, $haystack) {
    $min = 0;
    $max = count($haystack);
    while ($max >= $min)
    {
        $mid = (int) (($min + $max) / 2);
        if ($haystack[$mid]['records']['id'] == $needle) return $mid;
        else if ($haystack[$mid]['records']['id'] < $needle) $min = $mid + 1;
        else $max = $mid - 1;
    }
    // $needle was not found
    return false;
}

echo binary_search('29', $data);

- user3942918

Answer 4

你可以像这样使用二分搜索算法：

您可以使用二分搜索算法，如下所示：

$searchableArray = array(
                    0 => array(
                        'records' => array(
                            'id' => '25',
                            'parent_id' => '1',
                            'address' => '896167',
                        )
                    ),
                    1 => array(
                        'records' => array(
                            'id' => '26',
                            'parent_id' => '2',
                            'address' => '890812',
                        )
                    ),
                    2 => array(
                        'records' => array(
                            'id' => '28',
                            'parent_id' => '16',
                            'address' => '8A3813',
                        )
                    ),
                    3 => array(
                        'records' => array(
                            'id' => '29',
                            'parent_id' => '17',
                            'address' => '8A3914',
                        )
                    )
                );

$foundKey = findKey( $searchableArray, 29 );
echo "Found key: " . $foundKey;

function findKey( $searchableArray, $key ){
    $splittedArray = splitArray( $searchableArray );
    if( isInLeftChunk( $splittedArray[0], $key ) ){
        if( ! isOnlyElement( $splittedArray[0] ) ){
            return findKey( $splittedArray[0], $key );
        }
        return key( $splittedArray[0] );
    }
    elseif( isInRightChunk( $splittedArray[1], $key ) ){
        if( ! isOnlyElement( $splittedArray[1] ) ){
            return findKey( $splittedArray[1], $key );
        }
        return key( $splittedArray[1] );
    }

    // Element not found
    return false;
}

function isOnlyElement( $arrayChunk ){
    return count( $arrayChunk ) == 1;
}

function isInLeftChunk( $arrayChunk, $key ){
    end( $arrayChunk );
    $latestKey = key( $arrayChunk );
    if( is_int( $latestKey )){
        return $arrayChunk[ $latestKey ]['records']['id'] >= $key;
    }
    return $arrayChunk[ $latestKey ]['id'] >= $key;
}

function isInRightChunk( $arrayChunk, $key ){
    reset( $arrayChunk );
    $firstKey = key( $arrayChunk );
    if( is_int( $firstKey )){
        return $arrayChunk[$firstKey]['records']['id'] <= $key;
    }
    return $arrayChunk[ $firstKey ]['id'] <= $key;
}

function splitArray( $unsplittedArray ){
    $arrayLenght = count( $unsplittedArray );
    if( $arrayLenght == 1 ){
        return array_chunk( $unsplittedArray, $arrayLenght, true );
    }

    $odd = $arrayLenght % 2 != 0;
    if( $odd ){
        $arrayLenght += 1;
    }
    $arrayLenght = $arrayLenght * 0.5;

    return array_chunk( $unsplittedArray, $arrayLenght, true );
}

- Malcolm Kindermans