Быстрый способ поиска по этому массиву php ассоциативных массивов

Question

Быстрый способ поиска по этому массиву php ассоциативных массивов

У меня есть следующий массив 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 будет быстрее? Или они примерно одинаковой скорости?

2

arrays associative-array php search

Решение

Другие решения

Вы можете использовать алгоритм поиска binairy следующим образом:

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

1

Вы не можете использовать array_search() на вашей структуре данных. Ваш foreach Решение имеет временную сложность O(n) (и так бы array_search() также).

Вы сказали, что записи упорядочены по его идентификатору. Тогда вы можете сделать бинарный поиск который работает намного лучше с O(log(n)),

0

Источник

Accepted Answer

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

2