doushu8260 2014-01-19 19:12
浏览 57
已采纳

PHP Dart游戏计算性能缓慢

I've made a class to calculate the throw outs based on a score.

For example if the score is currently 140 the class returns a array with collection of possible throw outs:

[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

But calculating such things is pretty slow. Is there somehow I can optimize this class?

<?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;
    }


} 

Link to class: https://gist.github.com/YOUR1/8509498

  • 写回答

5条回答 默认 最新

  • dongzhuo3059 2014-01-27 16:17
    关注

    I've used basic permutation generation and it's super fast (0.06 seconds). It can certainly be optimized but I see no point since it's already so fast.

    <?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));
    

    The output is:

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

    The throws I added are: 1-20 single, double or triple, bull and double bull. If there are more, or special throws you can add them.

    The sort+serialization is a trick to quickly remove duplicates. For throw validation purposes it might actually be beneficial to leave the duplicates in.

    You could consider accepting the notation as a string, like: S10D20BULL or DBULLDBULLT20. If you introduce the S for singles you can never have confusion. D112T20 is ambigous, is it D11S2T20 or D1S12T20? Strings are easier to work with so you might even gain performance. Splitting the string-notation back into it's parts is a little tricky but doable.

    Note that I didn't add special checks for >170 or 1 because the list will simply be empty. This is an optimization you could apply.

    You can optionally add the miss throw with a score of 0.


    I don't quite understand your code, it's too complex. I think you're losing a lot of time doing sorting and converting between notation. As you can see in my solution I build the result set quickly and do the score calculation and notation generation at the same time.


    I should also mention that I'm not too familiar with dart rules. I assumed bull and double bull but if single bull and bull is accurate feel free to correct me.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(4条)

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题