배열에서 일치하거나 가장 가까운 값 찾기

배열에서 일치하거나 가장 가까운 값 찾기

어레이에서 지정된 목표값을 검색하여 가장 가까운 값을 찾으려면 어떻게 해야 합니까?

예를 들어 다음과 같은 배열이 있습니다.

array(0, 5, 10, 11, 12, 20)

예를 들어 목표값 0으로 검색하면 함수는 0을 반환하고, 3으로 검색하면 5를 반환하며, 14로 검색하면 12를 반환합니다.

첫 번째 매개 변수로 검색할 숫자를 입력하고 두 번째 매개 변수로 숫자 배열을 전달합니다.

function getClosest($search, $arr) {
   $closest = null;
   foreach ($arr as $item) {
      if ($closest === null || abs($search - $closest) > abs($item - $search)) {
         $closest = $item;
      }
   }
   return $closest;
}

특히 느긋한 접근법은 검색된 번호까지의 거리에 따라 PHP가 배열을 정렬하는 것입니다.

$num = 3;    
$array = array(0, 5, 10, 11, 12, 20);
$smallest = [];

foreach ($array as $i) {
    $smallest[$i] = abs($i - $num);
}
asort($smallest);
print key($smallest);

이는 정렬된 대형 어레이용으로 작성한 고성능 기능입니다.

테스트 결과 메인 루프는 20000개의 요소를 갖춘 어레이에 대해 최대 20회 반복만 필요합니다.

마인드 어레이를 정렬(상승)해야 합니다.

define('ARRAY_NEAREST_DEFAULT',    0);
define('ARRAY_NEAREST_LOWER',      1);
define('ARRAY_NEAREST_HIGHER',     2);

/**
 * Finds nearest value in numeric array. Can be used in loops.
 * Array needs to be non-assocative and sorted.
 * 
 * @param array $array
 * @param int $value
 * @param int $method ARRAY_NEAREST_DEFAULT|ARRAY_NEAREST_LOWER|ARRAY_NEAREST_HIGHER
 * @return int
 */
function array_numeric_sorted_nearest($array, $value, $method = ARRAY_NEAREST_DEFAULT) {    
    $count = count($array);

    if($count == 0) {
        return null;
    }    

    $div_step               = 2;    
    $index                  = ceil($count / $div_step);    
    $best_index             = null;
    $best_score             = null;
    $direction              = null;    
    $indexes_checked        = Array();

    while(true) {        
        if(isset($indexes_checked[$index])) {
            break ;
        }

        $curr_key = $array[$index];
        if($curr_key === null) {
            break ;
        }

        $indexes_checked[$index] = true;

        // perfect match, nothing else to do
        if($curr_key == $value) {
            return $curr_key;
        }

        $prev_key = $array[$index - 1];
        $next_key = $array[$index + 1];

        switch($method) {
            default:
            case ARRAY_NEAREST_DEFAULT:
                $curr_score = abs($curr_key - $value);

                $prev_score = $prev_key !== null ? abs($prev_key - $value) : null;
                $next_score = $next_key !== null ? abs($next_key - $value) : null;

                if($prev_score === null) {
                    $direction = 1;                    
                }else if ($next_score === null) {
                    break 2;
                }else{                    
                    $direction = $next_score < $prev_score ? 1 : -1;                    
                }
                break;
            case ARRAY_NEAREST_LOWER:
                $curr_score = $curr_key - $value;
                if($curr_score > 0) {
                    $curr_score = null;
                }else{
                    $curr_score = abs($curr_score);
                }

                if($curr_score === null) {
                    $direction = -1;
                }else{
                    $direction = 1;
                }                
                break;
            case ARRAY_NEAREST_HIGHER:
                $curr_score = $curr_key - $value;
                if($curr_score < 0) {
                    $curr_score = null;
                }

                if($curr_score === null) {
                    $direction = 1;
                }else{
                    $direction = -1;
                }  
                break;
        }

        if(($curr_score !== null) && ($curr_score < $best_score) || ($best_score === null)) {
            $best_index = $index;
            $best_score = $curr_score;
        }

        $div_step *= 2;
        $index += $direction * ceil($count / $div_step);
    }

    return $array[$best_index];
}

• ARRAY_NEAREST_DEFAULT가장 가까운 요소 찾기
• ARRAY_NEAREST_LOWER가장 가까운 요소 중 아래쪽 요소 찾기
• ARRAY_NEAREST_HIGHER가장 가까운 상위 요소 찾기

사용방법:

$test = Array(5,2,8,3,9,12,20,...,52100,52460,62000);

// sort an array and use array_numeric_sorted_nearest
// for multiple searches. 
// for every iteration it start from half of chunk where
// first chunk is whole array
// function doesn't work with unosrted arrays, and it's much
// faster than other solutions here for sorted arrays

sort($test);
$nearest = array_numeric_sorted_nearest($test, 8256);
$nearest = array_numeric_sorted_nearest($test, 3433);
$nearest = array_numeric_sorted_nearest($test, 1100);
$nearest = array_numeric_sorted_nearest($test, 700);

<?php
$arr = array(0, 5, 10, 11, 12, 20);

function getNearest($arr,$var){
    usort($arr, function($a,$b) use ($var){
        return  abs($a - $var) - abs($b - $var);
    });
    return array_shift($arr);
}
?>

팀의 구현으로 인해 대부분의 시간이 단축됩니다.단, 퍼포먼스에 주의하기 위해 반복 전에 목록을 정렬하고 다음 차이가 마지막보다 클 때 검색을 중단할 수 있습니다.

<?php
function getIndexOfClosestValue ($needle, $haystack) {
    if (count($haystack) === 1) {
        return $haystack[0];
    }

    sort($haystack);

    $closest_value_index = 0;
    $last_closest_value_index = null;

    foreach ($haystack as $i => $item) {
        if (abs($needle - $haystack[$closest_value_index]) > abs($item - $needle)) {
            $closest_value_index = $i;
        }

        if ($closest_value_index === $last_closest_value_index) {
            break;
        }
    }
    return $closest_value_index;
}

function getClosestValue ($needle, $haystack) {
    return $haystack[getIndexOfClosestValue($needle, $haystack)];
}

// Test

$needles = [0, 2, 3, 4, 5, 11, 19, 20];
$haystack = [0, 5, 10, 11, 12, 20];
$expectation = [0, 0, 1, 1, 1, 3, 5, 5];

foreach ($needles as $i => $needle) {
    var_dump( getIndexOfClosestValue($needle, $haystack) === $expectation[$i] );
}

개체 배열에서 가장 가까운 값을 검색하려면 Tim Cooper의 답변에서 이 수정된 코드를 사용하십시오.

<?php
// create array of ten objects with random values
$images = array();
for ($i = 0; $i < 10; $i++)
    $images[ $i ] = (object)array(
        'width' => rand(100, 1000)
    );

// print array
print_r($images);

// adapted function from Tim Copper's solution
// https://stackoverflow.com/a/5464961/496176
function closest($array, $member, $number) {
    $arr = array();
    foreach ($array as $key => $value)
        $arr[$key] = $value->$member;
    $closest = null;
    foreach ($arr as $item)
        if ($closest === null || abs($number - $closest) > abs($item - $number))
            $closest = $item;
    $key = array_search($closest, $arr);
    return $array[$key];
}

// object needed
$needed_object = closest($images, 'width', 320);

// print result
print_r($needed_object);
?>

Piyush Dholariya의 답변을 바탕으로 찾은 최고의 방법:

$array = [4, 9, 15, 6, 2];
$goal = 7;

$closest = array_reduce($array, function($carry, $item) use($goal) {
    return (abs($item - $goal) < abs($carry - $goal) ? $item : $carry);
}, reset($array)); // Returns 6

간단하게 사용할 수 있습니다.array_search이를 위해 하나의 단일 키가 반환됩니다. 배열 내에서 검색 인스턴스가 많이 발견되면 처음 찾은 키가 반환됩니다.

PHP에서 인용:

건초더미에서 바늘이 두 번 이상 발견되면 일치하는 첫 번째 키가 반환됩니다.일치하는 모든 값의 키를 반환하려면 대신 옵션 search_value 파라미터와 함께 array_keys()를 사용합니다.

사용 예:

if(false !== ($index = array_search(12,array(0, 5, 10, 11, 12, 20))))
{
    echo $index; //5
}

---

업데이트:

function findNearest($number,$Array)
{
    //First check if we have an exact number
    if(false !== ($exact = array_search($number,$Array)))
    {
         return $Array[$exact];
    }

    //Sort the array
    sort($Array);

   //make sure our search is greater then the smallest value
   if ($number < $Array[0] ) 
   { 
       return $Array[0];
   }

    $closest = $Array[0]; //Set the closest to the lowest number to start

    foreach($Array as $value)
    {
        if(abs($number - $closest) > abs($value - $number))
        {
            $closest = $value;
        }
    }

    return $closest;
}

입력 배열이 오름차순으로 정렬된 것을 고려합니다.asort()예를 들어, 이분법 검색을 사용하여 검색하는 것이 훨씬 빠릅니다.

다음은 DateTime 개체별로 정렬된 Itable 이벤트 목록에 새 이벤트를 삽입하기 위해 사용하는 코드를 빠르게 수정한 것입니다.

따라서 이 코드는 왼쪽에서 가장 가까운 지점(이전/작음)을 반환합니다.

수학적으로 가장 가까운 점을 찾으려는 경우: 검색 값의 거리를 반환 값과 비교하고 반환 값의 오른쪽(다음)에 있는 점을 비교해 보십시오(존재하는 경우).

function dichotomicSearch($search, $haystack, $position=false)
{
    // Set a cursor between two values
    if($position === false)
    {    $position=(object)  array(
            'min' => 0,
            'cur' => round(count($haystack)/2, 0, PHP_ROUND_HALF_ODD),
            'max' => count($haystack)
            );
    }

    // Return insertion point (to push using array_splice something at the right spot in a sorted array)
    if(is_numeric($position)){return $position;}

    // Return the index of the value when found
    if($search == $haystack[$position->cur]){return $position->cur;}

    // Searched value is smaller (go left)
    if($search <= $haystack[$position->cur])
    {
        // Not found (closest value would be $position->min || $position->min+1)
        if($position->cur == $position->min){return $position->min;}

        // Resetting the interval from [min,max[ to [min,cur[
        $position->max=$position->cur;
        // Resetting cursor to the new middle of the interval
        $position->cur=round($position->cur/2, 0, PHP_ROUND_HALF_DOWN);
        return dichotomicSearch($search, $haystack, $position);
    }

    // Search value is greater (go right)
        // Not found (closest value would be $position->max-1 || $position->max)
        if($position->cur < $position->min or $position->cur >= $position->max){return $position->max;}
        // Resetting the interval from [min,max[ to [cur,max[
        $position->min = $position->cur;
        // Resetting cursor to the new middle of the interval
        $position->cur = $position->min + round(($position->max-$position->min)/2, 0, PHP_ROUND_HALF_UP);
        if($position->cur >= $position->max){return $position->max;}
        return dichotomicSearch($search, $haystack, $position);        
}

가장 가까운 값을 찾기 위한 이진 검색(배열을 정렬해야 함):

function findClosest($sortedArr, $val)
{
    $low = 0;
    $high = count($sortedArr) - 1;
    while ($low <= $high) {
        if ($high - $low <= 1) {
            if (abs($sortedArr[$low] - $val) < abs($sortedArr[$high] - $val)) {
                return $sortedArr[$low];
            } else {
                return $sortedArr[$high];
            }
        }

        $mid = (int)(($high + $low) / 2);
        if ($val < $sortedArr[$mid]) {
            $high = $mid;
        } else {
            $low = $mid;
        }
    }

    // Empty array
    return false;
}

function closestnumber($number, $candidates) {
    $last = null;
    foreach ($candidates as $cand) {
        if ($cand < $number) {
            $last = $cand;
        } elseif ($cand == $number) {
           return $number;
        } elseif ($cand > $number) {
           return $last;
        }
    }
    return $last;
}

2개의 일시적 변수를 유지하고 조기 복귀를 실시함으로써 불필요한 반복이나 과도한 기능 호출을 회피하기 위한 늦은 답변을 제공합니다.

우아한 솔루션은 n보다 큰 시간 복잡도를 필요로 하지 않습니다.즉, 큰 O는 O(n), 작은 O는 O(1)이어야 합니다.빅 O는 건초 더미를 미리 정렬하고 다시 건초 더미를 반복함으로써 악화될 뿐입니다.o(1)를 얻으려면 동일한 일치가 발견되었을 때 조기 반환이 필요합니다. 더 이상 검색할 필요가 없습니다.

스니펫은 가장 낮은 거리를 가진 첫 번째 발생 값을 임의로 반환합니다(복수의 값이 같은 거리를 갖는 경우).기타 동작은 OP에 의해 지정되지 않습니다.

성능 은 ' 낫다'는 것입니다.abs()는 루프 내의 유일한 함수콜로 반복당 최대 1회라고 불립니다.일부 이전 답변에서는 각 반복에서 현재 값과 현재 가장 가까운 값의 거리를 재계산합니다. 이는 필요 이상의 작업입니다.

코드: (데모)

$haystack = [-6, 0, 5, 10, 11, 12, 20];

$needles = [0, 3, 14, -3];

function getNearest($needle, $haystack) {
    if (!$haystack) {
        throw new Exception('empty haystack');
    }
    $bestDistance = PHP_INT_MAX;
    foreach ($haystack as $value) {
        if ($value === $needle) {
            return $needle;
        }
        $distance = abs($value - $needle);
        if ($distance < $bestDistance) {
            $bestDistance = $distance;
            $keep = $value;
        }
    }
    return $keep ?? $value; // coalesce to silence potential IDE complaint
}

foreach ($needles as $needle) { // each test case
    echo "$needle -> " . getNearest($needle, $haystack) . "\n";
}

출력:

0 -> 0
3 -> 5
14 -> 12
-3 -> -6

이것은 마리오의 대답과 같은 접근법이지만, 나는 그것을 사용한다.array_search() ★★★★★★★★★★★★★★★★★」min()정렬하는 대신.성능은 같기 때문에 결국 선호도에 따라 달라집니다.

function findClosest(array $values, $match)
{
    $map = [];
    foreach ($values as $v) {
        $map[$v] = abs($match - $v);
    }
    return array_search(min($map), $map);
}

언급URL : https://stackoverflow.com/questions/5464919/find-a-matching-or-closest-value-in-an-array