PHP: önbelleğe alma sipariş tamsayı bölme algoritması

3 Cevap php

Birincisi: Wikipedia Sorunun adı "bir dizi bölümü emretti" dir.

Ben mümkün bölümleri sayar bir algoritma var. Bunu hızlandırmak için, ben bir önbellek kullanın:

function partition($intervalSize, $pieces) {
	// special case of integer partitions: ordered integer partitions
	// in Wikipedia it is: ordered partition of a set
	global $partition_cache;
	// CACHE START
	$cacheId = $intervalSize.'-'.$pieces;
	if (isset($partition_cache[$cacheId])) { return $partition_cache[$cacheId]; }
	// CACHE END
	if ($pieces == 1) { return 1; }
	else {
		$sum = 0;
		for ($i = 1; $i < $intervalSize; $i++) {
			$sum += partition(($intervalSize-$i), ($pieces-1));
		}
		$partition_cache[$cacheId] = $sum; // insert into cache
		return $sum;
	}
}
$result = partition(8, 4);

Ayrıca, ben bu olası bölümlerin bir listesini gösterir başka bir algoritma var. Ama henüz bir önbelleği kullanmak değildir ve bu yüzden oldukça yavaş:

function showPartitions($prefix, $start, $finish, $numLeft) {
	global $partitions;
	if ($numLeft == 0 && $start == $finish) { // wenn eine Partition fertig ist dann in Array schreiben
		$gruppen = split('\|', $prefix);
		$partitions[] = $gruppen;
	}
	else {
		if (strlen($prefix) > 0) { // nicht | an Anfang setzen sondern nur zwischen Gruppen
			$prefix .= '|';
		}
		for ($i = $start + 1; $i <= $finish; $i++) {
			$prefix .= chr($i+64);
			showPartitions($prefix, $i, $finish, $numLeft - 1);
		}
	}
}
$result = showPartitions('', 0, 8, 4);

So I have two questions: 1) Is it possible to implement a cache in the second algorithm, too? If yes, could you please help me to do this? 2) Is it possible to write the results of the second algorithm into an structured array instead of a string?

Bana yardımcı olur umarım. Şimdiden çok teşekkür ederiz!

PS: Teşekkürler iki fonksiyonları, simonn ve Dan Dyer için!

3 Cevap

  1. Aslında iki kez aynı hesaplama performans asla çünkü Hayır, ben bir önbellek burada size yardımcı olacaktır sanmıyorum. ShowPartitions her çağrı () farklı parametreler var ve farklı bir sonuç üretir.
  2. Evet, tabii ki. Bu temelde boru karakterleri ile ayrılmış bir karakter dize yerine tamsayılar işaret iç içe diziler başka seviyesini kullanarak ediyoruz. (Yerine "A | B | C". Sahip olacak array(array(1), array(2), array(3)))

showPartitions() gibi değiştirmeyi deneyin:

if ($numLeft == 0 && $start == $finish) { // wenn eine Partition fertig ist dann in Array schreiben
	$partitions[] = $prefix;
}
else {
	$prefix[] = array();
	for ($i = $start + 1; $i <= $finish; $i++) {
		$prefix[count($prefix) - 1][] = $i;
		showPartitions($prefix, $i, $finish, $numLeft - 1);
	}
}

ve $ yerine öneki için boş bir dize ile çağırmak, boş bir dizi ile çağrı:

showPartitions(array(), 0, 8, 4);

Off topic: Ben biraz daha hızlı olması için ilk fonksiyonunu yeniden yazdı.

function partition($intervalSize, $pieces) {
    // special case of integer partitions: ordered integer partitions
    // in Wikipedia it is: ordered partition of a set

    // CACHE START
    static $partition_cache = array();
    if (isset($partition_cache[$intervalSize][$pieces])) { 
    	return $partition_cache[$intervalSize][$pieces];
    }
    // CACHE END

    if ($pieces === 1) {
    	return 1;
    }	
    if ($intervalSize === 1) {
    	return 0;
    }

    $sum = 0;
    $subPieces = $pieces - 1;
    $i = $intervalSize;
    while (--$i) {
    		$sum += partition($i, $subPieces);
    }
    $partition_cache[$intervalSize][$pieces] = $sum; // insert into cache
    return $sum;
}

Although this is a bit old, nevertheless, a PHP Class which implements various combinatorics/simulation methods including partitions/permutations/combinations etc.. in an efficient way

https://github.com/foo123/Simulacra/blob/master/Simulacra.php

PS: Ben yazar değilim

etiketler