0

Tengo una clase en PHP7 para crear emparejamientos de emails que estoy probando en Windows.

Cada email tiene asociado otro del grupo como destinatario, sin que haya parejas repetidas ni un email pueda tenerse como pareja a si mismo, es decir, que todos los emails tienen un destinatario y son a su vez el destinatario de uno de los otros emails.

Estoy guardando los emparejamientos en una array asociativo, como parejas de clave-valor, así obtengo por ejemplo:

Array
(
    [[email protected]] => [email protected]
    [[email protected]] => [email protected]
    [[email protected]] => [email protected]
    [[email protected]] => [email protected]
)

El emparejamiento funciona, pero en algunas ocasiones, el script no finaliza y acaba dando un error fatal por excederse el tiempo de ejecución (ver más abajo el código para "test de ejecución" con resultados en navegador). Al lanzar en la terminal los test unitarios pasan pero algunas veces el proceso no finaliza, permanece en ejecución indefinidamente.

Hay algunos bucles y creo que el problema está en los métodos getPosition() y isAssigned() pero los he analizado y no veo que está mal.

Esta es la clase:

<?php namespace ironwoods\php_classes;

final class PairSelector
{
    private $assigned_pairs;
    private $emails;
    private $total_emails = 0;

    private $err_no_emails = 'No emails registered or less of two!';

    /**
     * Gets pairs of emails in an associative array
     *
     * @param  array        $arr_emails
     * @return array
     */
    public function getPairs(array $arr_emails)
    {
        $this->emails = $arr_emails;

        /**
         * Is necesary setted at least two emails to use this class
         *
         */
        if (! $this->searchForMinimalCondicion()) {
            die('ERR -> ' . $this->err_no_emails);
        }

        $total_emails = count($arr_emails);
        $this->total_emails = $total_emails;

        $i = 0;
        $this->assigned_pairs = array();
        while ($i < $total_emails) {

            $pos = $this->getPosition($i); //for email 2

            $email_1 = $arr_emails[$i];     //Take each email of array one time
            $email_2 = $arr_emails[$pos];   //Take each email of array one time
            $this->assigned_pairs[$email_1] = $email_2;

            $i++;
        }

        return $this->assigned_pairs;
    }

    /**
     * Gets a value from the array different to actual and unassigned before
     *
     * @param  int      $actual_pos
     * @return int
     */
    private function getPosition(int $actual_pos)
    {
        $pos = $actual_pos;
        $max = $this->total_emails - 1;
        while ($pos === $actual_pos || $this->isAssigned($pos)) {

            $pos = rand(0, $max);
        }

        return $pos;
    }

    /**
     * Searches an email between the destinataries already assigned
     *
     * @param  int      $pos
     * @return boolean
     */
    private function isAssigned(int $pos)
    {
        $email = $this->emails[$pos];
        foreach ($this->assigned_pairs as $destinatary) {

            if ($email === $destinatary) {
                return true;
            }
        }

        return false;
    }

    /**
     * Searches if the number of emails are at least two
     *
     * @return boolean
     */
    private function searchForMinimalCondicion()
    {
        return ($this->emails && (count($this->emails) > 1));
    }
} //class

Test de ejecución:

<?php namespace ironwoods\php_classes\tests;

require '../pairselector.php';
use \ironwoods\php_classes\PairSelector;


$arr_emails = [
    '[email protected]',
    '[email protected]',
    '[email protected]',
    '[email protected]',
];

$ps = new PairSelector();
$res = $ps->getPairs($arr_emails);

echo '<pre>';
print_r($res);

echo '<hr>';

$res = $ps->getPairs(['[email protected]']);
print_r($res);

Test unitarios (PHPUnit):

<?php namespace ironwoods\php_classes\tests;
/*
cd c:/xampp/htdocs/php__classes/tests
phpunit PairSelectorTest.php --colors=always --repeat 10
*/
use \PHPUnit\Framework\TestCase;
use \ironwoods\php_classes\PairSelector;

$_BASE_PATH = dirname( __FILE__, 2 ) . '/'; //Only PHP 7
require $_BASE_PATH . 'pairselector.php';


class PairSelectorTest extends TestCase
{
    private $emails = [
        '[email protected]',
        '[email protected]',
        '[email protected]',
        '[email protected]',
    ];


    /**
     * @coversDefaultClass \ironwoods\php_classes
     * @covers PairSelector::getPairs
     */
    public function testIfReturnPairs()
    {
        $arr_pairs = $this->getPairs();

        self::assertTrue(is_array($arr_pairs)); //we have an array
        self::assertFalse(empty($arr_pairs));   //our array has elements

        return $arr_pairs;
    }

    /**
     * @coversDefaultClass \ironwoods\php_classes
     * @covers PairSelector::getPairs
     * @depends testIfReturnPairs
     */
    public function testIfReturnEqualNumberOfPairsThatEmailsInOrigin(
        Array $arr_pairs
    )
    {
        self::assertEquals(
            count($arr_pairs),
            count($this->emails)
        );

        return $arr_pairs;
    }

    /**
     * @coversDefaultClass \ironwoods\php_classes
     * @covers PairSelector::getPairs
     * @depends testIfReturnEqualNumberOfPairsThatEmailsInOrigin
     */
    public function testIfReturnAsKeysSameEmailsThatEmailsInOrigin(
        Array $arr_pairs
    )
    {
        $i = 0;
        foreach ($arr_pairs as $key => $value) {

            $email = $this->emails[$i];
            $msg = 'Email from pairs-key and origin-emails are different';
            self::assertEquals( $email, $key, $msg );

            $i++;
        }

        return $arr_pairs;
    }

    /**
     * @coversDefaultClass \ironwoods\php_classes
     * @covers PairSelector::getPairs
     * @depends testIfReturnAsKeysSameEmailsThatEmailsInOrigin
     */
    public function testIfKeysAndValuesAreDifferentsInArrayOfPairs(
        Array $arr_pairs
    )
    {
        foreach ($arr_pairs as $key => $value) {

            $msg = 'Email in key is the same that email in value';
            self::assertNotEquals($key, $value, $msg);
        }

        return $arr_pairs;
    }

    /**
     * @coversDefaultClass \ironwoods\php_classes
     * @covers PairSelector::getPairs
     * @depends testIfKeysAndValuesAreDifferentsInArrayOfPairs
     */
    public function testIfReturnArrayValuesAreAllDifferent(
        Array $arr_pairs
    )
    {
        $arr_pairs = array_unique($arr_pairs); //Filters duplicate elements
        $msg = 'Values in array of pairs have duplicate mails';
        self::assertEquals(
            count($this->emails),
            count($arr_pairs),
            $msg
        );

        return $arr_pairs;
    }

    /**
     * Runs "PairSelector->getPairs()" to get the pairs of emails
     *
     * @return      array
     */
    private function getPairs()
    {
        $ps = new PairSelector();

        return $ps->getPairs($this->emails);
    }
} //class
2
  • Tu problema es la ubicacion usando rand. No mire todo, pero usar rand para poner las cosas en determinados lugares puede ser peligroso porque algunos valores retornados, que ya usaste, se empiezan a repetir y el codigo no termina nunca. deberias utilizar otra forma para generar posiciones aleatorias.
    – gbianchi
    el 27 dic. 2017 a las 1:09
  • @gbianchi si sospechaba de rand(), vere si encuentro otro modo de generar las posiciones
    – Orici
    el 27 dic. 2017 a las 9:54

1 respuesta 1

1

Primero, tu uso de rand es ineficiente porque a medida que se van agotando los destinatarios no asignados, tú sigues haciéndole buscar entre todos los destinatarios posibles.

Segundo, tu método isAssigned también es ineficiente porque recorre todos los mails asignados. Sería un poco mejor hacer una búsqueda en el array de mails ya asociados usando in_array sobre los valores de los pares asignados (que es la salida de la función array_values):

private function isAssigned(int $pos)
{
    $email = $this->emails[$pos];
    return in_array($email, array_values($this->assigned_pairs));
}

Pero sería aún más eficiente buscar por llave array_key_exists sobre la salida de la operación array_flip (visto que array_key_exists busca en un hash table en vez de recorrer un array)

private function isAssigned(int $pos)
{
    $email = $this->emails[$pos];
    return array_key_exists($email, array_flip($this->assigned_pairs));
}

Tomándonos de eso, en realidad getPosition podría devolver de por sí un email disponible:

/**
 * Gets a value from the array different to actual and unassigned before
 *
 * @param  int      $actual_pos
 * @return string
 */
private function getPosition(int $actual_pos)
{
    $current_email    = $this->emails[$actual_pos];
    $assigned_pairs   = $this->assigned_pairs;
    $available_emails = array_filter($this->emails,function($email) use ($current_email,$assigned_pairs) {
        return $email !== $current_email && !array_key_exists($email, array_flip($assigned_pairs));
    });

    $max = count($available_emails) - 1;
    $pos = rand(0, $max);

    return array_values($available_emails)[$pos];
}

De manera que pudieses hacer:

$email_1 = $arr_emails[$i];     //Take each email of array one time
$email_2 = $this->getPosition($i); //for email 2

Sin embargo, tu verdadero problema no va específicamente en la optimización del código, puesto que tu ejemplo falla incluso con una muestra de 4 correos.

La razón de esto queda en evidencia si al asignar imprimes una línea:

echo "Assign $email_1 to $email_2<br>";
$this->assigned_pairs[$email_1] = $email_2;

En algunas de las corridas obtuve esto:

Assign [email protected] to [email protected]
Assign [email protected] to [email protected]
Assign [email protected] to [email protected]

¿Resultado? Los tres primeros se asignaron entre sí, dejando a [email protected] sin destinatarios posibles.

El caso de borde es:

  • quedan dos mails a quienes no se ha asignado destinatario
  • estamos asignando el destinatario del penúltimo origen
  • el último mail de origen no figura como mail de destinatario de nadie
  • el método getPosition devuelve el primero de los dos mails disponibles

Cuando se cumplen todas estas condiciones, el último mail no tiene destinatario ni es destinatario de nadie, y el algoritmo no converge. Para manejar este caso, habría que obligar a que en este escenario getPosition devuelva el segundo valor disponible:

$available_count = count($available_emails) ;
$pos = rand(0, $available_count-1);

if($available_count===2 && 
   $actual_pos===($this->total_emails-2) &&
   !array_key_exists($this->emails[$actual_pos+1], array_flip($assigned_pairs))) {
    $pos=1; // forzamos la elección del último mail como destinatario del penúltimo
}

return array_values($available_emails)[$pos];

Al forzar que el penúltimo mail reciba al último como destinatario, ya no puede ocurrir que el último se quede solo.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.