Bin de manera uniforme: el espacio para el resto es desigual
https://stackoverflow.com/questions/7811075
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy escribiendo un guión para reducir uniformemente un número arbitrario $epi en un número arbitrario de contenedores $dpi. EPI significa extremos por pulgada. DPI significa abolladuras por pulgada. Hay 3 requisitos:
- El número de contenedor debe reducirse por el factor común más bajo si es posible
- por ejemplo, 10 EPI en 6 ppp debe estar representado por 5 EPI en 3 dpi
- La población de contenedores debe ser lo más uniforme posible
- por ejemplo, 2-2-1 es mejor que 3-1-1
- Los contenedores cortos deben distribuirse uniformemente a través de la matriz de bins
- por ejemplo, 1-0-1-0-1 es mejor que 1-1-1-0-0
Esto es lo que tengo hasta ahora. Principalmente hace lo que necesito pero cuando el space() se ejecuta el método, si es foreach Loop tiene que ejecutarse más de una vez, la distribución de $ EPI no es uniforme.
<?php
class ReedSubstitution{
public $epi;
public $dpi;
function substitute($e,$d){
$this->epi=is_numeric($e)?$e:0;
$this->dpi=is_numeric($d)?$d:0;
if(empty($this->epi)||empty($this->dpi)) throw new Exception('Both desired ends per unit and available dents per unit must be specified.');
if($this->epi%$this->dpi ==0) return array($this->epi/$this->dpi);//short circuit for easy case
$this->unfraction();//make equivalent integers if dpi or epi are fractional
$gcd= ($this->epi < $this->dpi) ? $this->euclid($this->epi,$this->dpi) : $this->euclid($this->dpi,$this->epi);
$e=$this->epi/$gcd;
$d=$this->dpi/$gcd;
$q=floor($e/$d);//count that every dent gets
$r=$e%$d;//extra to be spread out over array
$reed=array_fill(0,$d,$q);
$this->space($reed,$r);
return $reed;
}
protected function unfraction(){
$emult=1;
$dmult=1;
if($this->epi-intval($this->epi)){ //epi has a fractional component
list($tmp,$er)=explode('.',$this->epi);
$emult=pow(10,strlen($er));
}
if($this->dpi-intval($this->dpi)){//dpi has a fractional component
list($tmp,$dr)=explode('.',$this->dpi);
$dmult=pow(10,strlen($dr));
}
$mult=($emult>$dmult)?$emult:$dmult;
$this->epi*=$mult;
$this->dpi*=$mult;
}
/**
* @desc evenly distribute remaining ends over entirety of dents
* @param Array $reed, dents in one pattern repeat
* @param Integer $r, remaining ends to be distributed
*/
protected function space(&$reed,$r){
$c=count($reed);
$i=0;
$jump=($r < $c-$r) ? $r : $c-$r;//use the smallest jump possible to reduce the looping
do{
for($i; $i<$c; $i=$i+$jump, $r--){
if($r==0)break;
$reed[$i]++;
}
$i=array_search(min($reed),$reed);//begin next loop (if necessary) at position with fewest ends
}while($r>0);
}
/**
* @desc return greatest common divisor as determined by Euclid's algorithm
* @param integer $large
* @param integer $small
* @return integer
*/
protected function euclid($large, $small){
$modulus=$large%$small;
if($modulus==0) {
return $small;
} else if($modulus==1){
return 1;
} else {
return $this->euclid($small,$modulus);//recursion
}
}
}
?>
Mala salida:
$r=new ReedSubstitution();
$arr=$r->substitute(9,28);
/* BAD DISTRIBUTION
Array
(
[0] => 1
[1] => 1
[2] => 1
[3] => 0
[4] => 0
[5] => 0
[6] => 0
[7] => 0
[8] => 0
[9] => 1
[10] => 1
[11] => 1
[12] => 0
[13] => 0
[14] => 0
[15] => 0
[16] => 0
[17] => 0
[18] => 1
[19] => 1
[20] => 0
[21] => 0
[22] => 0
[23] => 0
[24] => 0
[25] => 0
[26] => 0
[27] => 1
)
*/
Cómo debería ser la distribución anterior:
/* GOOD DISTRIBUTION
Array
(
[0] => 1
[1] => 0
[2] => 0
[3] => 1
[4] => 0
[5] => 0
[6] => 1
[7] => 0
[8] => 0
[9] => 1
[10] => 0
[11] => 0
[12] => 1
[13] => 0
[14] => 0
[15] => 1
[16] => 0
[17] => 0
[18] => 1
[19] => 0
[20] => 0
[21] => 1
[22] => 0
[23] => 0
[24] => 1
[25] => 0
[26] => 0
[27] => 0
)
*/
¿Cómo puedo arreglar el space() ¿Método para que el binning que requiere más de un bucle producirá una distribución aceptable?
Solución
Espero que esto ayude o al menos te indique la dirección correcta:
protected function space(&$reed, $r)
{
$totalReeds = count($reed);
$f = floor($r/$totalReeds);
$d = ($r % $totalReeds) / $totalReeds;
$c = 0;
for ($i = 0; $i < $totalReeds; $i++)
{
$add = round($f + $d + $c);
$reed[$i] += $add;
$c = $c + $f + $d - $add;
}
}
Sin embargo, puede producir no exactamente Lo que podrías esperar:
Array
(
[0] => 2
[1] => 1
[2] => 2
[3] => 2
[4] => 1
[5] => 2
[6] => 1
[7] => 2
)
Aunque el resultado es una distribución uniforme.
PD: No entendí el problema real relacionado con el sitio web con el que se enfrenta, pero espero haber captado el concepto de matemáticas bien.
Otros consejos
¿Puedes probar la siguiente función para el espacio?
protected function space(&$reed, $r)
{
$totalReeds = count ($reed);
$postion = floor($totalReeds/$r);
for ($i=0; $i<=$totalReeds; $i=$i+$postion, $r--) {
if ($r <= 0) break;
$reed[$i]++;
}
}
Solo lo intenté con algunas entradas y funcionó para mí. Además, me dio la salida correcta para el ejemplo anterior que dio.
¿Puede intentar usar esta función y avisarme si funciona para toda su entrada?
-- EDITAR --
Prueba este código.
protected function space(&$reed, $r)
{
$totalReeds = count ($reed);
$postion = floor($totalReeds/$r);
$postion = $postion == 1? 2 : $postion;
for ($i=0; $i<=$totalReeds; $i=$i+$postion, $r--) {
if ($r <= 0) break;
if (isset($reed[$i])) $reed[$i]++;
}
}
Espero que esto funcione. No estoy seguro de los resultados esperados de las otras entradas que dijo en su comentario. Entonces supongo que lo siguiente es correcto. Si me equivoco, publique los resultados esperados de las otras entradas.
Saludos,
Wow, este código es horrible, en mi humilde opinión :) Recursion para encontrar un uso común divisivo y loco de IS_NUMERIC e INTVAL, una exepción solitaria, etc. La arquitectura de clase también es extraña, lo habría hecho como clase estática.
Honestamente, no tuve el problema de las matemáticas al respecto, ya que todo lo que encontré sobre contenedores y abolladuras es tejer (no soy un hablante nativo, así que podría haber perdido algo obvio), pero creo que entendí sus requisitos (si esto es no es un problema matemático estricto).
De todos modos, lo limpié un poco, así que publico un código de clase completo, pero puedes usar espacio () separadamente si no te gusta. Mi algoritmo se puede optimizar mucho (se puede eliminar el segundo ciclo), pero soy demasiado vago para hacerlo.
class ReedSubstitution {
private $epi;
private $dpi;
public function substitute($e, $d) {
$this->epi = floatval($e);
$this->dpi = floatval($d);
if (empty($this->epi) || empty($this->dpi)) {
throw new Exception('Both desired ends per unit and available dents per unit must be specified.');
}
//make equivalent integers if dpi or epi are fractional
$this->unfraction();
if ($this->epi % $this->dpi == 0) {
return array($this->epi / $this->dpi);
}
$gcd = $this->euclid($this->epi, $this->dpi);
$e = $this->epi / $gcd;
$d = $this->dpi / $gcd;
$r = $e % $d; //extra to be spread out over array
$q = ($e - $r) / $d; //count that every dent gets
$reed = array_fill(0, $d, $q);
$this->space($reed, $r);
return $reed;
}
protected function unfraction() {
//Find fraction start position
$epi_fract_pos = strpos($this->epi, '.');
$dpi_fract_pos = strpos($this->dpi, '.');
//Find fraction length
$epi_fract_len = $epi_fract_pos ? (strlen($this->epi) - $epi_fract_pos - 1) : 0;
$dpi_fract_len = $dpi_fract_pos ? (strlen($this->dpi) - $dpi_fract_pos - 1) : 0;
//Calculate max fraction length
$fraction_len = max($epi_fract_len, $dpi_fract_len);
//Unfraction variables
$mult = pow(10, $fraction_len);
$this->epi*=$mult;
$this->dpi*=$mult;
}
/**
* @desc evenly distribute remaining ends over entirety of dents
* @param Array $reed, dents in one pattern repeat
* @param Integer $r, remaining ends to be distributed
*/
protected function space(&$reed, $r) {
$c = count($reed);
$base = $reed[0];
for ($i = 0; $i < $r; $i++) {
$reed[$i]++;
}
while ($reed[$c - 1] === $base) {
$reed[$c] = $base;
//Find the longest $base+1 array with least $base behind it
$max_base_plus_size = -$c;
$cur_base_plus_size = 0;
$cur_base_plus_pos = array(NULL, NULL);
$max_base_plus_pos = NULL;
for ($i = 0; $i <= $c; $i++) {
if ($reed[$i] != $base) {
if($cur_base_plus_pos[0]===NULL) {
$cur_base_plus_pos[0] = $i;
}
if ($reed[$i + 1] == $base) {
$cur_base_plus_pos[1]=$i;
if ($max_base_plus_size < $cur_base_plus_size) {
$max_base_plus_size = $cur_base_plus_size;
$max_base_plus_pos = $cur_base_plus_pos;
}
$cur_base_plus_size = 0;
$cur_base_plus_pos = array(NULL, NULL);
}
else {
$cur_base_plus_size++;
}
} else {
$cur_base_plus_size--;
$cur_base_plus_pos[1] = $i - 1;
}
}
$insert_pos=ceil(($max_base_plus_pos[1]+$max_base_plus_pos[0])/2);
array_splice($reed,$insert_pos,0,$base);
}
array_splice($reed,$c);
$reed=array_reverse($reed);//Optional, just to get the same output as you submitted
}
/**
* @desc return greatest common divisor as determined by Euclid's algorithm
* @param integer $x
* @param integer $y
* @return integer
*/
protected function euclid($x, $y) {
while ($x) {
$temp = $x;
$x = $y % $x;
$y = $temp;
}
return $temp;
}
}
