Низкая производительность игры в PHP Dart

Ответ 1

Я использовал генерацию основных подстановок и очень быстро (0,06 секунды). Это, безусловно, может быть оптимизировано, но я не вижу смысла, так как это уже так быстро.

<?php

class DartUtils {

    private static $possible_points;

    public static function getPossibleThrowsForScore($score) {

        // generate all possible single throws and their score
        // I didn't want to write them all out
        // but it certainly an option (and faster)
        self::$possible_points = array();
        for ($i = 1; $i <= 20; $i += 1) {
            self::$possible_points["S" . $i] = $i; // S = single
            self::$possible_points["D" . $i] = $i * 2;
            self::$possible_points["T" . $i] = $i * 3;
        }
        self::$possible_points["bull"] = 25;
        self::$possible_points["double bull"] = 50;
        // self::$possible_points["miss"] = 0;

        $throws = self::findSatisfyingThrowsForScore($score, 3, array());
        foreach ($throws as $i => $serialized_throw) {
            $throws[$i] = unserialize($serialized_throw);
        }
        return $throws;
    }

    private static function findSatisfyingThrowsForScore($score, $num_throws, $base_notation) {
        $possible_throws = array();
        foreach (self::$possible_points as $notation => $value) {
            if ($num_throws === 1) { // we've done all throws
                if ($score - $value === 0) { // we satisfied the score
                    $throw = array_merge($base_notation, array($notation));
                    sort($throw);
                    $possible_throws[] = serialize($throw);
                }
            } else {
                // so long as there are num_throws, recurse with all possible throws
                $possible_throws = array_merge($possible_throws,
                  self::findSatisfyingThrowsForScore($score - $value, $num_throws - 1, array_merge($base_notation, array($notation))));
            }
        }
        $possible_throws = array_unique($possible_throws);
        sort($possible_throws);
        return $possible_throws;
    }

}

var_dump(DartUtils::getPossibleThrowsForScore(140));

Вывод:

array(21) {
  [0]=>
  array(3) {
    [0]=>
    string(3) "D10"
    [1]=>
    string(3) "T20"
    [2]=>
    string(3) "T20"
  }
  [1]=>
  array(3) {
    [0]=>
    string(3) "D13"
    [1]=>
    string(3) "T18"
    [2]=>
    string(3) "T20"
  }
  [2]=>
  array(3) {
    [0]=>
    string(3) "D13"
    [1]=>
    string(3) "T19"
    [2]=>
    string(3) "T19"
  }
  [3]=>
  array(3) {
    [0]=>
    string(3) "D15"
    [1]=>
    string(3) "T20"
    [2]=>
    string(11) "double bull"
  }
  [4]=>
  array(3) {
    [0]=>
    string(3) "D16"
    [1]=>
    string(3) "T16"
    [2]=>
    string(3) "T20"
  }
  [5]=>
  array(3) {
    [0]=>
    string(3) "D16"
    [1]=>
    string(3) "T17"
    [2]=>
    string(3) "T19"
  }
  [6]=>
  array(3) {
    [0]=>
    string(3) "D16"
    [1]=>
    string(3) "T18"
    [2]=>
    string(3) "T18"
  }
  [7]=>
  array(3) {
    [0]=>
    string(3) "D18"
    [1]=>
    string(3) "T18"
    [2]=>
    string(11) "double bull"
  }
  [8]=>
  array(3) {
    [0]=>
    string(3) "D19"
    [1]=>
    string(3) "T14"
    [2]=>
    string(3) "T20"
  }
  [9]=>
  array(3) {
    [0]=>
    string(3) "D19"
    [1]=>
    string(3) "T15"
    [2]=>
    string(3) "T19"
  }
  [10]=>
  array(3) {
    [0]=>
    string(3) "D19"
    [1]=>
    string(3) "T16"
    [2]=>
    string(3) "T18"
  }
  [11]=>
  array(3) {
    [0]=>
    string(3) "D19"
    [1]=>
    string(3) "T17"
    [2]=>
    string(3) "T17"
  }
  [12]=>
  array(3) {
    [0]=>
    string(3) "D20"
    [1]=>
    string(11) "double bull"
    [2]=>
    string(11) "double bull"
  }
  [13]=>
  array(3) {
    [0]=>
    string(3) "D20"
    [1]=>
    string(3) "D20"
    [2]=>
    string(3) "T20"
  }
  [14]=>
  array(3) {
    [0]=>
    string(3) "S20"
    [1]=>
    string(3) "T20"
    [2]=>
    string(3) "T20"
  }
  [15]=>
  array(3) {
    [0]=>
    string(3) "T10"
    [1]=>
    string(3) "T20"
    [2]=>
    string(11) "double bull"
  }
  [16]=>
  array(3) {
    [0]=>
    string(3) "T11"
    [1]=>
    string(3) "T19"
    [2]=>
    string(11) "double bull"
  }
  [17]=>
  array(3) {
    [0]=>
    string(3) "T12"
    [1]=>
    string(3) "T18"
    [2]=>
    string(11) "double bull"
  }
  [18]=>
  array(3) {
    [0]=>
    string(3) "T13"
    [1]=>
    string(3) "T17"
    [2]=>
    string(11) "double bull"
  }
  [19]=>
  array(3) {
    [0]=>
    string(3) "T14"
    [1]=>
    string(3) "T16"
    [2]=>
    string(11) "double bull"
  }
  [20]=>
  array(3) {
    [0]=>
    string(3) "T15"
    [1]=>
    string(3) "T15"
    [2]=>
    string(11) "double bull"
  }
}

Броски, которые я добавил: 1-20 одиночный, двойной или тройной, бычий и двойной бык. Если есть больше или специальные броски, вы можете их добавить.

Серийная сортировка + сортирует, чтобы быстро удалить дубликаты. Для целей проверки броска может оказаться полезным оставить дубликаты.

Вы могли бы принять обозначение как строку, например: S10D20BULL или DBULLDBULLT20. Если вы представите S для синглов, у вас никогда не будет путаницы. D112T20 является двусмысленным, это D11S2T20 или D1S12T20? Строки легче работать, поэтому вы можете даже повысить производительность. Разделение строковой нотации на части немного немного сложно, но выполнимо.

Обратите внимание, что я не добавлял специальные проверки для >170 или 1, потому что список будет просто пустым. Это оптимизация, которую вы могли бы применить.

Вы можете дополнительно добавить бросок miss со счетом 0.

Я не совсем понимаю ваш код, он слишком сложный. Я думаю, вы теряете много времени, делая сортировку и преобразование между обозначениями. Как вы можете видеть в моем решении, я быстро создаю результирующий набор и делаю расчеты и формирование записи в одно и то же время.

Я должен также упомянуть, что я не слишком хорошо знаком с правилами дарт. Я предполагал быка и двойного быка, но если один бык и бык точны, не стесняйтесь исправлять меня.

Ответ 2

• Первое, что я обнаружил, это то, что ваш класс не возвращает все возможные броски для данного балла.
• Во-вторых, это очень медленно.

Но это меня заинтересовало, поэтому я сделал свою собственную версию класса, чтобы решить эту проблему. Поскольку существующий, который вы дали здесь, выглядит немного сложным для проблемы. Просто хотел сделать это простым, и простой также должен быть быстрым.

Я сделал некоторые предположения, чтобы начать с:

• Добавлен "промах" с 0 баллами (вы можете просто прокомментировать это, если не нужно).
• Установите максимальный результат до 170, как и вы.
• Предполагаемый класс должен возвращать все возможные выбросы.

Я устанавливаю свойство с массивом, который содержит все возможные побеги и их счет. И сделал способ вернуть все возможные броски для данного балла.

Я установил тест для своего класса, чтобы дать вам некоторые номера производительности. Я запустил все значения баллов от 1 до 170, один за другим в цикле, чтобы получить все возможные результаты проверки за каждый.

Вот результаты на моей машине:

• 170 общий счет (1 - 170).
• 250026 проверка итоговых результатов.
• Общее время выполнения 4 секунды.

Это среднее значение для результатов теста в секунду, равное 42,5, и средневзвешенных результатов за просмотр в среднем 62506,5 в секунду.

Таким образом, он возвращает все возможные результаты и намного быстрее. Надеюсь, это поможет. Если ничто другое не даст вам некоторого представления о том, как улучшить свой класс.

<?php

$darts = new Darts();

$result = $darts->possibleCheckout(60); //gives 3767 results

//var_dump($result);
echo count($result) . "\n";



/**
 * PHP Dartgame calculating class
 * @author Aleksandar Popovic
 */
class Darts
{
    /**
     * All possible shoots and score per each
     * @var array
     */
    private $shoot_score = array(
        'miss' => 0,
        '1' => 1,
        '2' => 2,
        '3' => 3,
        '4' => 4,
        '5' => 5,
        '6' => 6,
        '7' => 7,
        '8' => 8,
        '9' => 9,
        '10' => 10,
        '11' => 11,
        '12' => 12,
        '13' => 13,
        '14' => 14,
        '15' => 15,
        '16' => 16,
        '17' => 17,
        '18' => 18,
        '19' => 19,
        '20' => 20,
        'D1' => 2,
        'D2' => 4,
        'D3' => 6,
        'D4' => 8,
        'D5' => 10,
        'D6' => 12,
        'D7' => 14,
        'D8' => 16,
        'D9' => 18,
        'D10' => 20,
        'D11' => 22,
        'D12' => 24,
        'D13' => 26,
        'D14' => 28,
        'D15' => 30,
        'D16' => 32,
        'D17' => 34,
        'D18' => 36,
        'D19' => 38,
        'D20' => 40,
        'T1' => 3,
        'T2' => 6,
        'T3' => 9,
        'T4' => 12,
        'T5' => 15,
        'T6' => 18,
        'T7' => 21,
        'T8' => 24,
        'T9' => 27,
        'T10' => 30,
        'T11' => 33,
        'T12' => 36,
        'T13' => 39,
        'T14' => 42,
        'T15' => 45,
        'T16' => 48,
        'T17' => 51,
        'T18' => 54,
        'T19' => 57,
        'T20' => 60,
        'Signle-Bull' => 25,
        'Double-Bull' => 50
    );

     /**
     * Maximum score
     * @var int
     */
    private $max_score = 170; // 3 x T20 is max right?


    /**
     * Return all possible checkouts for given score
     * @param int $current_score
     * @return array
     */
    public function possibleCheckout($current_score)
    {
        if ($current_score > $this->max_score || $current_score < 1)
        {
            return false;
        }

        $checkout = array();
        foreach ($this->shoot_score as $shoot1 => $score1)
        {
            if ($score1 > $current_score)
            {
                continue;
            }

            foreach ($this->shoot_score as $shoot2 => $score2)
            {
                if ($score1 + $score2 > $current_score)
                {
                    continue;
                }

                foreach ($this->shoot_score as $shoot3 => $score3)
                {
                    if ($score1 + $score2 + $score3 == $current_score)
                    {
                        $checkout[] = array($shoot1, $shoot2, $shoot3);
                        continue;
                    }
                }
            }
        }

        return $checkout;
    }
}

Ответ 3

Если вы хотите получить дополнительный прирост производительности, вам нужно сохранить результаты для всех возможностей в базе данных или файле и просто читать значения, а не вычислять их каждый раз.

Я бы предложил следующую структуру

Table (checkout)

sum (int) | dart1 (int) | dart2 (int) | dart3 (int)

60 | 20 | 20 | 31

все дротики, указывающие на следующую таблицу

Table (dart)

pk (int) | bez (varchar)

20 | 20

31 | D10

Ответ 4

Не уверен, какова природа вашей ошибки, потому что я не знаком с правилами дартс, но строка 129 определенно неверна:

if ($x <= 20 || $x == 50 || $x == 25 || ($x % 3 == 0) || ($x <= 40 && ($x % 2 == 0))) {

Либо вы хотите тестировать $xx, либо не хотите повторно тестировать условие, которое уже привело вас к этой строке. В настоящий момент внутренняя петля всегда будет вызываться до тех пор, пока цикл $xx будет. Это убийца производительности. Конечно, наличие вложенного цикла внутри вложенного цикла, как правило, независимо от него.

Другой подход может заключаться в создании справочной таблицы с ответами на все возможные оценки, как это было предложено Арканоном.

Ответ 5

Вот моя попытка.

Результат сортируется лексикографически по возрастанию индивидуальных оценок.

• Если вы сделаете цикл foreach, вы получите результаты перемещения 1 для перемещения n.
• Если вы получаете доступ по индексу, вы получите ходы в обратном порядке (1 = последний ход, 3 = первый ход).

Это очень быстро для 3 ходов, но рушится, если вы попробуете больше, чем это.

Возможно (теоретически) вычислить возможности для любого количества ходов, хотя скоро вы достигнете максимального времени выполнения script:).

Максимально достижимый балл равен 180 (3x тройной 20). Вы можете тратить много процессорных средств на более высокий балл. Это приведет к пустым результатам.

class darts {
    const DATAFILE = "darts-scores.txt"; // score names & values database
    static $score_val;  // values of scores
    static $score_name; // names of scores
    static $score_num;  // # of score values

    static $res;        // search result
    static $tries;      // for statistics

    // internal search
    static private function moves ($score, $moves, $i=0, &$list = array())
    {
        self::$tries++; // update stats

        // search from the current scores only
        for ( ; $i != self::$score_num; $i++)
        {
            $val = self::$score_val[$i];
            if ($val > $score) break;  // no need to try these ones
            if ($moves == 1) // unrolled the recursion to improve performances
            {
                if ($score == $val)
                {
                    // found another combination
                    $list[$moves] = self::$score_name[$i];
                    self::$res[] = $list;
                }
            }
            else // go down to seek the rest of the combination
            {
                $list[$moves] = self::$score_name[$i];
                self::moves ($score - $val, $moves-1, $i, $list);
            }
        }
    }

    // public search function
    static function moves_for_score ($score, $moves=3)
    {
        self::$res = array();
        self::$tries=0;
        self::moves ($score, $moves);
        return self::$res;
    }

    // turn results into a string
    static function flatten ($res)
    {
        return implode (", ",
            array_map (
                function ($e){ return "[".implode(':',$e)."]"; },
                $res));
    }

    // initialize scores table
    static function init ()
    {
        if (!file_exists (self::DATAFILE))
        {
            // you can change the names of the scores with these two lines
            $scores = array (
                "miss" =>0, 
                "bull"=>25, 
                "double bull"=>50);
            $type = array (
                1=>"S", 
                2=>"D", 
                3=>"T");

            // generate all scores
            for ($t = 1 ; $t <= 3 ; $t++)
            for ($i = 1 ; $i <= 20 ; $i++)
            {
                $scores[$type[$t].$i] = $t * $i;
            }
            asort ($scores);
            foreach ($scores as $name=>$val) $out[] = "$name:$val";
            file_put_contents (self::DATAFILE, implode ("\n", $out));
        }

        // read score file
        $in = preg_split ("/[:\n]/", file_get_contents (self::DATAFILE));
        self::$score_num = count($in)/2;
        for ($i = 0 ; $i != self::$score_num ; $i++)
        {
            self::$score_name[$i] = $in[$i*2];
            self::$score_val [$i] = (int) $in[$i*2+1];
        }
    }
}
darts::init();

////////////////////////////////////////////////////
// basic usage
////////////////////////////////////////////////////
$score = 281;
$moves = 5;
$res = darts::moves_for_score ($score, $moves);

echo "Sequences for $score in $moves moves: "
     .darts::flatten($res)
     ."<br>";
echo "<pre>".print_r($res, true)."</pre><br>";

////////////////////////////////////////////////////
// stress test
////////////////////////////////////////////////////

echo "<br>Computing all possible sequences from 0 to 181...";
$start = microtime(true);
$tries = 0;
$max = 0;
for ($i = 0 ; $i <=180 ; $i++)
{
    $res = darts::moves_for_score ($i);
    $flat = darts::flatten($res);
    if (strlen ($flat) > $max) 
    { 
        $max = strlen($flat); 
        $res_max = $res; 
        $i_max = $i;
    }
    $tries += darts::$tries;
}
echo "done in ".(microtime(true)-$start)."s, $tries tries<br>";
echo "<br>Longest list of possibilities:<br>$i_max -> "
    .darts::flatten ($res_max)."<br>";