快速搜索这个关联数组的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会更快吗？或者它们的速度大致相同？

Answer 1

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);

Answer 2

您不能在数据结构上使用array_search()。你的foreach解决方案的时间复杂度为O(n)（因此也会有array_search()）。

你说记录按其id排序。然后你就可以用binary search做更好的O(log(n))。

Answer 3

您可以使用这样的二进制搜索算法：

$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 );
}

Answer 4

如果您要进行许多此类搜索，最好创建反向查找数组。

也就是说，你做一次慢线性工作，之后，它是一个快速哈希（关联数组）查找。

一度：

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

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

$index = $id2index[$id];