php altında birleştirme sıralaması hakkında soru

7 Cevap php

i'v php altında birleştirme sıralama uygulamak için çalışıyorlar. ancak başarısız görünüyor: (hata kaynağını bulamadık her türlü yardımı çok takdir.!

function merge_sort(&$input, $start, $end) {
    if($start < $end) {
        $mid = (int) floor($start + $end / 2);
        merge_sort($input, $start, $mid);
        merge_sort($input, $mid + 1, $end);
        merge($input, $start, $mid, $end);
    } 
}

function merge(&$input, $p, $q, $r) { 
    $a = $q - $p + 1;
    $b = $r - $q;

    for($i = $p;$i <= $q;$i++) {
        $arr1[] = $input[$i];
    }

    for($i = $q+1;$i <= $r;$i++) {
        $arr2[] = $input[$i];
    }   

    $c = $d = 0;
    for($i = $p; $i <= $r; $i++) {
        $s = $arr1[$c];
        $t = $arr2[$d];

        if($a && (($s <= $t) || !$b)) { 
            $input[$i] = $s;
            $a--;$c++;
        } else if($b) {
            $input[$i] = $t;
            $b--;$d++;
        }
    } 
    return true;
}

Buraya geri atmak xdebug bilgiler bulunuyor:

Fatal error: Maximum function nesting level of '100' reached, aborting!

7 Cevap

Birleştirme tür üzerinde 100 yuvalama seviyeye ulaşmak için, imkansız olan, ({[) 1 (]} yaklaşık) 2^100 büyüklükte bir giriş dizisi olması gerekir. Ben senin özyineleme yanlış olduğunu sanıyorum. Örneğin, $start + $end / 2 yerine yazdı ($start + $end) / 2.

Set

xdebug.max_nesting_level=500

benim php.ini içinde

İşte benim çalışma çözüm, karşılaştırmak için çekinmeyin ...

/**
 * @param array $items array to sort
 * @param int   $l     left index (defaults to 0)
 * @param int   $r     right index (defaults to count($items)-1)
 */
function mergeSort(&$items, $l = 0, $r = null)
{
    if (!isset($r)) {
        $r = count($items) - 1;
    }

    if ($l < $r) {
        $m = floor(($r - $l) / 2) + $l;
        mergeSort($items, $l, $m);
        mergeSort($items, $m + 1, $r);
        merge($items, $l, $m, $r);
    }
}

/**
 * @param array $items array to merge
 * @param int   $l     left index
 * @param int   $m     middle index
 * @param int   $r     right index
 */
function merge(&$items, $l, $m, $r)
{
    $itemsA = array_slice($items, $l, $m + 1 - $l);
    $itemsB = array_slice($items, $m + 1, ($r + 1) - ($m + 1));

    $a = 0;
    $aCount = count($itemsA);
    $b = 0;
    $bCount = count($itemsB);

    for ($i = $l; $i <= $r; $i++) {
        if ($a < $aCount && ($b == $bCount || $itemsA[$a] <= $itemsB[$b])) {
            $items[$i] = $itemsA[$a++];
        } else {
            $items[$i] = $itemsB[$b++];
        }
    }
}

$items = array(5,3,6,1,2,3,9,10,7,2,4,8);
mergeSort($items);
echo implode(',', $items) . "\n";

Çıkışlar:

1,2,2,3,3,4,5,6,7,8,9,10

Orada '100 maksimum fonksiyon yuvalama seviye 'olduğunu ve bunu ulaşmıştır. Sizin recursive fonksiyon çok derin gider.

Dan http://www.xdebug.org/docs/all%5Fsettings:

xdebug.max_nesting_level Type: integer, Default value: 100 Controls the protection mechanism for infinite recursion protection. The value of this setting is the maximum level of nested functions that are allowed before the script will be aborted.

Bu xdebug hatayı tetikleyen sizin özyinelemeli işlevi çok derin gidiyor. Bu limiti yükseltmek ve görmek eğer yardımcı olur.

Ayrıca, burada özyineleme ve PHP ile ilgili ilginç bir makale: http://www.alternateinterior.com/2006/09/tail-recursion-in-php.html

PHP özyinelemeli algoritmalar için iyi bir dil değildir. Kimden manual:

It is possible to call recursive functions in PHP. However avoid recursive function/method calls with over 100-200 recursion levels as it can smash the stack and cause a termination of the current script.

PHP bunu yapmak gerekirse, muhtemelen algoritma yinelemeli bir sürümünü bulmak gerekecek. Sen dilinde kodlanmış bir sınıra ettik.

Cosi Dovrebbe funzionare!! www.dslpg.it

function merge ( &$a, $left,  $center, $right ) { //left = p   right = r  center = q
    $n1 = $center - $left + 1;
    $n2 = $right - $center;
    for ($i = 1; $i <= $n1; $i++) $L[$i] = $a[$left+$i-1];
    for ($i = 1; $i <= $n2; $i++) $R[$i] = $a[$center+$i];
    $L[$n1+1] = 99999;
    $R[$n2+1] = 99999; 
    $i = 1;
    $j = 1;
    for ($k = $left; $k <= $right; $k++) {
        if ($L[$i] <= $R[$j] ) {
            $a[$k] = $L[$i];
            echo $a[$k];
            $i++;
        }
        else {
            $a[$k] = $R[$j];
            echo $a[$k];
            $j++;
        }
    }
    return $a;
}
function merge_sort ( &$a, $left, $right ) { //left = p  right = r
    if ( $left < $right ) {
        $center = (int) floor(($left + $right) / 2 );

        merge_sort ($a, $left, $center);
        merge_sort ($a, $center+1, $right);
        merge ($a, $left, $center, $right);
    }
}
merge_sort ( $a, 1, $n );

etiketler