PHP Dart 游戏计算性能缓慢

11

我已经创建了一个用于基于得分计算出"丢镖"的类。

例如,如果当前得分是140,该类将返回一个包含可能的"丢镖"集合的数组:

[10] => Array
    (
        [0] => T18
        [1] => T18
        [2] => D16
    )

[11] => Array
    (
        [0] => T18
        [1] => T16
        [2] => D19
    )

[13] => Array
    (
        [0] => T17
        [1] => T17
        [2] => D19
    )

[14] => Array
    (
        [0] => 50
        [1] => 50
        [2] => D20

但是计算这些东西相当慢。有什么方法可以优化这个类?
<?php
/**
 * PHP Dartgame calculating class
 * @author Youri van den Bogert
 */

class Darts {

    /**
     * @var string
     */
    public static $notation_triple = 'T';

    /**
     * @var string
     */
    public static $notation_double = 'D';

    /**
     * @var int
     */
    private static $maxCheckout = 170;

    /**
     * @var string
     */
    private static $doubleBull = 'Bull';

    /**
     * @var string
     */
    private static $singleBull = 'Single';

    /**
     * @var array
     */
    private static $scoreSheet = array('1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '25', '50');

    /**
     * Get a total thrown score
     * @param $score1
     * @param $score2
     * @param $score3
     * @return array
     */
    public static function getTotalScore ($score1, $score2, $score3) {
        return array(
          'dart1' => self::getScoreOfDart($score1),
          'dart2' => self::getScoreOfDart($score2),
          'dart3' => self::getScoreOfDart($score3),
          'total' => self::getScoreOfDart($score1) + self::getScoreOfDart($score2) + self::getScoreOfDart($score3)
        );
    }


    /**
     * Get score of a single dart
     * @param $score
     * @return mixed
     */
    public static function getScoreOfDart ($score) {

        if (is_numeric($score)) {
            return $score;
        }

        if ($score[0] == self::$notation_triple) {
            $multiplier = 3;
        } elseif ($score[0] == self::$notation_double) {
            $multiplier = 2;
        } else {
            $multiplier = 1;
        }

        $correctScore = filter_var($score, FILTER_SANITIZE_NUMBER_INT);

        return ($correctScore * $multiplier);

    }

    public static function getScoreSheet () {

        return self::$scoreSheet;

    }

    public static function calculatePossibleCheckout ($currentScore) {

        // We cant checkout higher then $maxCheckout
        if ($currentScore > self::$maxCheckout || $currentScore == 1) {
            return false;
        }

        // Return bull
        if ($currentScore == 50) {
            return array(
                'dart1' => self::$doubleBull
            );
        }

        if ($currentScore == self::$maxCheckout) {
            return array(
                'dart1' => self::$notation_triple . '20',
                'dart2' => self::$notation_triple . 'T20',
                'dart3' => 'Bull'
            );
        }

        $lastScore = $currentScore;
        $lastPossibleThrow = 0;
        $checkOut = array();

        // Can current score be checked out?
        if (self::canScore($currentScore) == true) {

            return array(
                'dart1' => self::$notation_double . ($currentScore / 2)
            );

        // Current score can't be checked out - calculate what to throw
        } else {

            for ($x=60; $x >= 0; --$x) {

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

                    for ($xx=60; $xx >= 0; --$xx) {

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

                            for ($xxx=50; $xxx > 0; $xxx = $xxx - 2) {

                                if ($xxx == 48) {
                                    $xxx = 40;
                                }

                                if (self::checkIfScoreExists($xxx) == true && self::checkIfScoreExists($xx) == true && self::checkIfScoreExists($x) == true && ($xxx + $xx + $x) == $currentScore) {

                                    $score_1 = self::getCorrectDartName($xxx);
                                    $score_2 = self::getCorrectDartName($xx);
                                    $score_3 = self::getCorrectDartName($x, true);

                                    if ($score_1[0] == 'D' || $score_2[0] == 'D' || $score_3[0] == 'D') {
                                        $nextKey = (count($checkOut)+1);
                                        if ($xxx != 0) $checkOut[$nextKey][] = $score_1;
                                        if ($xx != 0) $checkOut[$nextKey][] = $score_2;
                                        if ($x != 0) $checkOut[$nextKey][] = $score_3;

                                        usort($checkOut[$nextKey], function($a, $b) {
                                            if (is_int($a) || is_float($a)) {
                                                if (is_int($b) || is_float($b)) {
                                                    return $a - $b;
                                                }
                                                else
                                                    return -1;
                                            }
                                            elseif (is_int($b) || is_float($b)) {
                                                return 1;
                                            }
                                            else {
                                                return strcmp($b, $a);
                                            }
                                        });
                                    }

                                }
                            }
                        }
                    }
                }
            }

        }

        return array_unique($checkOut, SORT_REGULAR);

    }

    public static function getCorrectDartName ($total, $isLast = false) {

        if ($total == 25 || $total == 50) {
            return $total;
        }

        if ($total < 20 && $isLast == false) {
            return $total;
        }

        if ($total %3 == 0) {
            return self::$notation_triple . ($total/3);
        } elseif ($total %2 == 0) {
            return self::$notation_double . ($total/2);
        }

        return $total;


    }

    /**
     * Check if score exists
     * @param $score
     * @return bool
     */
    public static function checkIfScoreExists ($score) {

        if ($score == 50 || $score == 25 || $score == 0) return true;

        $possibleScores = array_merge(range(1,20));

        foreach ($possibleScores as $posScore) {
            if ($score == self::getScoreOfDart(self::$notation_double . $posScore) || $score == self::getScoreOfDart(self::$notation_triple . $posScore) || $score == $posScore) {
                return true;
            }
        }

        return false;

    }

    /**
     * Check if a specific score can be thrown by one dart
     * @param $score
     * @return bool
     */
    public static function canScore ($score) {
        if ($score == 50) {
            return true;
        } elseif ($score < 40 || $score == 40) {

            if ($score % 2 == 0) {
                return true; // Score is even - so its possible to throw
            } else {
                return false;
            }
        }

        return false;
    }


} 

类的链接:https://gist.github.com/YOUR1/8509498

(Note: 此链接指向一个代码示例)


4
应该发布在CodeReview上。 - user557846
3
如果计算这个结果本身就很昂贵,可以考虑创建一个文本文件(或数据库表),存储每个分数的输出结果。由于这样的表格包含不到两百条记录,所以相比每次需要答案时都运行计算程序,使用表格可能是更高效的方式。 - Bobulous
其实我认为这将是一个相当大的文件。当你得到低于100分时,有很多出局的比分。你需要一个快速的存储和检索解决方案。内存或数据库也许可以?SQLite?memcache? - Sergiu Paraschiv
我喜欢这个问题,但是你的代码只会根据得分计算一个外线。不幸的是,你不能考虑到球员的首选组合!祝你好运。 - The Blue Dog
Arkanon,是的,那也是我第二个猜测,只需一次生成所有的输出然后将其存储在SQL表中。@PeteR 如果我将输出存储在数据库中并为玩家、特定输出和投掷次数制作关系表,则可以完成此操作 :)。 - Youri
5个回答

7
我使用了基本的排列生成方法,速度非常快(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's 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个单、双或三倍分数,以及靶心和双倍靶心。如果需要更多或特殊的投掷方式,您可以添加它们。
sort+serialization 是一种快速删除重复项的技巧。但是为了投掷验证目的,保留重复项实际上可能是有益的。
您可以考虑接受字符串表示法,例如:S10D20BULLDBULLDBULLT20。如果引入S来表示单倍,则不会造成混淆。D112T20是不明确的,它是D11S2T20还是D1S12T20?使用字符串更容易处理,因此甚至可能提高性能。将字符串表示法拆分回各部分有点棘手,但是可行。
请注意,我没有添加>1701的特殊检查,因为列表将为空。这是您可以应用的优化。
您可以选择添加得分为0miss 投掷。
我不太理解您的代码,它太复杂了。我认为您正在浪费很多时间进行排序并在表示法之间进行转换。如您在我的解决方案中看到的那样,我快速构建了结果集并同时进行了分数计算和表示法生成。
我还应该提到,我对飞镖规则不太熟悉。我假设是bulldouble bull,但如果single bullbull更准确,请随时纠正我。

谢谢你的解决方案。我稍微修改了一下,将可能的输出保存到了数据库中。 - Youri
顺便提一下,你应该将self::findThrows($score - $value, $num_throws - 1, array_merge($base_notation, array($notation))))编辑为self::findSatisfyingThrowsForScore($score - $value, $num_throws - 1, array_merge($base_notation, array($notation)))); - Youri

2
  • 我发现你的类没有返回给定分数的所有可能的丢球。
  • 其次,它非常慢。

但这让我感兴趣,所以我制作了自己的版本来解决这个问题。因为你提供的现有版本看起来有点复杂。我只想让它简单,并且简单也应该快速。

我做了一些假设:

  1. 添加了0分的“miss”投篮(如果不需要,可以将其注释掉)。
  2. 将最高分设置为170,就像你一样。
  3. 假设类应该返回所有可能的丢球。

我设置了一个属性,其中包含所有可能的投篮和它们的得分。并制作了一个方法来返回给定分数的所有可能的丢球。

我为我的类设置了一个测试,以便为您提供一些性能数据。我逐个循环运行了所有得分值,从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;
    }
}

1
此外,如果考虑到标准规则(大多数国际比赛使用的规则)规定结尾镖必须是双倍,则可以进一步缩短运行时间。 (而且 OP 已经考虑到了这一点) - Sergiu Paraschiv
抱歉,我不太熟悉规则。不知道这一点。 - Aleksandar Popovic

2
如果您想获得额外的性能提升,您需要将所有可能结果保存在数据库或文件中,然后只需读取值而不是每次重新计算。
我建议使用以下结构:
Table (checkout)

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

60 | 20 | 20 | 31

所有的箭头都指向下面这个表格。
Table (dart)

pk (int) | bez (varchar)

20 | 20

31 | D10

1

这是我的尝试。

输出按照个人得分的字典顺序升序排序。

  • 如果您使用foreach循环,将获得从第1步到第n步的结果。
  • 如果您通过索引访问,则会以相反的顺序获取移动(1 = 最后一步,3 = 第一步)。

对于3步非常快,但如果您尝试更多步骤,它会崩溃。

理论上可以计算任意步数的可能性,但您很快就会达到脚本最大执行时间 :)。

最大可实现的得分为180(3倍20)。您可以浪费很多CPU尝试更高的得分。它将产生一个空结果。

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>";

1

我不确定你的错误性质是什么,因为我不熟悉飞镖规则,但第129行肯定是错误的:

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

要么你想测试 $xx,要么你不想重新测试已经导致你到达该行的条件。目前,只要 $xx 循环存在,最内部循环就会被调用。这是性能杀手。当然,通常情况下,在嵌套循环中还有一个嵌套循环通常也是如此。
另一种方法可能是生成一个查找表,包含所有可能分数的答案,正如 Arkanon 所建议的那样。

我对他的for循环完全感到困惑。唯一看起来准确的是有3个级别(每个投掷一个)。我的解决方案使用递归生成这3个级别,这允许进行一些巧妙的变量绑定。迭代解决方案(带有3个嵌套循环)当然也是可行的。 - Halcyon
递归确实可以替代3个嵌套循环,但我不确定它是否会更有效(如果有的话)。不管怎样,我同意当前的循环代码毫无意义,并需要进行一些修订。 - Eran Boudjnah

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接