PHP Ağırlık Algoritma

2 Cevap php

Bu ağırlıklı sistem ile en iyi değeri bulmak için yeterli bir algoritma olup olmadığını merak ediyorum. Ben daha iyi yapmak eklemek bir şey var mı?

Bu örnekte, I-$object->get() testi 1 geri bunun olasılığı 4 kat daha büyük olduğu TEST4 dönme olasılığını istiyoruz.

class weightCalculator { 
    var $data = array();
    var $universe = 0; 

    function add( $data, $probability ){ 
        $this->data[ $x = sizeof( $this->data ) ] = new stdClass; 
        $this->data[ $x ]->value = $data; 
        $this->universe += $this->data[ $x ]->probability = abs( $probability ); 
    } 

    function get(){ 
        if( !$this->universe ){
            return null; 
        }
        $x = round( mt_rand( 0, $this->universe ) ); 
        $max = 0;
        $i = 0; 

        while( $x > $max ){
            $max += $this->data[ $i++ ]->probability;
        }
        $val=-1;
        if($this->universe==1){
            $val = $this->data[$i]->value;      
          } else {
            $val = $this->data[$i-1]->value;                
        }
        return $val;
    } 
}

$object = new weightCalculator; 
$object->add( 'test1', 10 );
$object->add( 'test2', 20 ); 
$object->add( 'test3', 30 ); 
$object->add( 'test4', 40 ); 

2 Cevap

Streetpc cevabı üzerinde durmak; veri dizinin yanında, add() sizin aralığında üst sınır saklamak aynı büyüklükteki tuşları dizi korumak için kullanmak; örnek için, bu dizi {10, 30, 60, 100} gibi görünecektir. (Ya da, nesneleri veya veri ve anahtarı hem de içeren yapılar içeren bir dizi kullanın.) Ardından, sizin get() yöntemi sadece $x daha büyük ilk elemanı için bir sıralı liste arıyor ; İkili arama yöntemi sizin için O (N) göre, (N ln) O o yapabilirdi. Biraz ekstra bellek çiğnemek olacak - ama çoğu uygulama için, iyi bir değiş tokuş gibi görünüyor.

Yeterince adil görünüyor, kullanıma bağlıdır. Eğer get() yöntemi için daha iyi performans gerekiyorsa, add() yöntemi ve kullanım ikilemi içinde aralık değerlerini inşa olabilir.