SitePoint Sponsor

User Tag List

Results 1 to 5 of 5
  1. #1
    SitePoint Guru risoknop's Avatar
    Join Date
    Feb 2008
    Location
    end($world)
    Posts
    834
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Help me refactor this code

    Im sure this can be written in a much simpler way. I feel like I'm using many unnecessary loops and variables Could somebody care to help me refactor this piece of code?

    I'm trying to make it shorter and simpler but it should still remain readable:

    PHP Code:
    <?php

    /*
     * @name Lawler's algorithm PHP implementation
     * @desc This algorithm calculates an optimal schedule of jobs to be
     *       processed on a single machine (in reversed order) while taking
     *       into consideration any precedence constraints.
     * @author Richard Knop
     *
     */

    $jobs = array(=> array('processingTime' => 2,
                             
    'dueDate'        => 3),
                  
    => array('processingTime' => 3,
                             
    'dueDate'        => 15),
                  
    => array('processingTime' => 4,
                             
    'dueDate'        => 9),
                  
    => array('processingTime' => 3,
                             
    'dueDate'        => 16),
                  
    => array('processingTime' => 5,
                             
    'dueDate'        => 12),
                  
    => array('processingTime' => 7,
                             
    'dueDate'        => 20),
                  
    => array('processingTime' => 5,
                             
    'dueDate'        => 27),
                  
    => array('processingTime' => 6,
                             
    'dueDate'        => 40),
                  
    => array('processingTime' => 3,
                             
    'dueDate'        => 10));
    // precedence constrainst, i.e job 2 must be completed before job 5 etc
    $successors = array(2=>5,
                        
    7=>9);
    $n count($jobs);
    $optimalSchedule = array();

    for (
    $i $n$i >= 1$i--) {
        
        
    // jobs not required to precede any other job
        
    $arr = array();
        foreach (
    $jobs as $k => $v) {
            
            if (
    false === array_key_exists($k$successors)) {
                
    $arr[] = $k;
            }
            
        }
        
        
    // calculate total processing time
        
    $totalProcessingTime 0;
        foreach (
    $jobs as $k => $v) {
            if (
    true === array_key_exists($k$arr)) {
                
    $totalProcessingTime += $v['processingTime'];
            }
        }
        
        
    // find the job that will go to the end of the optimal schedule array
        
    $min null;
        
    $x 0;
        
    $lastKey null;
        foreach(
    $arr as $k) {
            
    $x $totalProcessingTime $jobs[$k]['dueDate'];
            if (
    null === $min || $x $min) {
                
    $min $x;
                
    $lastKey $k;
            }
        }
        
        
    // add the job to the optimal schedule array
        
    $optimalSchedule[$lastKey] = $jobs[$lastKey];
        
    // remove job from the jobs array
        
    unset($jobs[$lastKey]);
        
    // remove precedence constraint from the successors array if needed
        
    if (true === in_array($lastKey$successors)) {
            foreach (
    $successors as $k => $v) {
                if (
    $lastKey === $v) {
                    unset(
    $successors[$k]);
                }
            }
        }
        
    }

    // reverse the optimal schedule array and preserve keys
    $optimalSchedule array_reverse($optimalScheduletrue);

    // add tardiness to the array
    $i 0;
    foreach (
    $optimalSchedule as $k => $v) {
        
    $optimalSchedule[$k]['tardiness'] = 0;
        
    $j 0;
        foreach (
    $optimalSchedule as $k2 => $v2) {
            if (
    $j <= $i) {
                
    $optimalSchedule[$k]['tardiness'] += $v2['processingTime'];
            }
            
    $j++;
        }
        
    $i++;
    }

    echo 
    '<pre>';
    print_r($optimalSchedule);
    echo 
    '</pre>';

  2. #2
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    You could abstract the work out to separate functions, so that the work that's actually being done is easier to digest.

    Code php:
    $jobs = jobsList();
    $successors = successorsList();
    $schedule = calculateSchedule($jobs, $successors);
    echo showSchedule($schedule);

    The calculateOptimalSchedule function would be be similar:

    Code php:
    function calculateSchedule($jobs, $successors)
    {
        $schedule = array();
        for ($i = 0; $i < count($jobs); $i++) {
            $independentJobs = independentJobs($jobs, $successors);
            $processingTime = processingTime($jobs, $independentJobs);
            $job = findSmallestJob($jobs, $processingTime);
            moveJobToSchedule($jobs, $schedule, $job, $successors);
        }
        $schedule = reverseSchedule($schedule);
        $schedule = addTardiness($schedule);
        return $schedule;
    }

    The above code would need you to fill in the function parts, and possibly resolve some other issues (such as, referencing arrays by reference for moveJobToSchedule). It would help improve the understandability of the code.
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  3. #3
    SitePoint Guru risoknop's Avatar
    Join Date
    Feb 2008
    Location
    end($world)
    Posts
    834
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks. I actually decided to make a class out of that messy code:

    PHP Code:
    <?php

    /*
     * @name Lawler's algorithm PHP implementation
     * @desc This algorithm calculates an optimal schedule of jobs to be
     *       processed on a single machine (in reversed order) while taking
     *       into consideration any precedence constraints.
     * @author Richard Knop
     *
     */

    class LawlersAlgorithm
    {
        private 
    $jobs;
        
        private 
    $precedenceConstraints;
        
        private 
    $jobsCount;
        
        private 
    $optimalSchedule = array();
        
        private 
    $jobsWithNoSuccessor// jobs that are not required to precede any other job
        
        
    private $totalProcessingTime;
        
        public function 
    __construct(array $jobs,
                                    array 
    $precedenceConstraints)
        {
            
            
    $this->jobs $jobs;
            
    $this->precedenceConstraints $precedenceConstraints;
            
    $this->jobsCount count($jobs);
            
        }
        
        public function 
    computeJobsWithNoSuccessor()
        {
            
    $this->jobsWithNoSuccessor = array();
            foreach (
    $this->jobs as $key => $value) {
                
                if (
    false === array_key_exists($key$this->precedenceConstraints)) {
                    
    $this->jobsWithNoSuccessor[] = $key;
                }
                
            }
        }
        
        public function 
    computeTotalProcessingTime()
        {
            
    $this->totalProcessingTime 0;
            foreach (
    $this->jobs as $key => $value) {
                
    $this->totalProcessingTime += $value['processingTime'];
            }
        }
        
        
    // find the job that will go to the end of the optimal schedule array
        
    public function getLastJobKey()
        {        
            
    $min null;
            
    $x 0;
            
    $lastJobKey null;
            foreach(
    $this->jobsWithNoSuccessor as $key) {
                
    $x $this->totalProcessingTime $this->jobs[$key]['dueDate'];
                if (
    null === $min || $x $min) {
                    
    $min $x;
                    
    $lastJobKey $key;
                }
            }
            return 
    $lastJobKey;
        }
        
        private function 
    addTardinessToOptimalSchedule()
        {
            
    $i 0;
            foreach (
    $this->optimalSchedule as $key => $value) {
                
    $this->optimalSchedule[$key]['tardiness'] = 0;
                
    $j 0;
                foreach (
    $this->optimalSchedule as $k => $v) {
                    if (
    $j <= $i) {
                        
    $this->optimalSchedule[$key]['tardiness'] += $v['processingTime'];
                    }
                    
    $j++;
                }
                
    $i++;
            }
        }
        
        public function 
    compute()
        {
            for (
    $i $this->jobsCount$i >= 1$i--) {
                
                
    $this->computeJobsWithNoSuccessor();
                
    $this->computeTotalProcessingTime();
                
    $lastJobKey $this->getLastJobKey();
                
    $this->optimalSchedule[$lastJobKey] = $this->jobs[$lastJobKey];
                
    // unset the job
                
    unset($this->jobs[$lastJobKey]);
                
    // remove precedence constraint if needed
                
    if (true === in_array($lastJobKey$this->precedenceConstraints)) {
                    foreach (
    $this->precedenceConstraints as $key => $value) {
                        if (
    $lastJobKey === $value) {
                            unset(
    $this->precedenceConstraints[$key]);
                        }
                    }
                }
                
            }
            
            
    // reverse the optimal schedule array and preserver keys
            
    $this->optimalSchedule array_reverse($this->optimalScheduletrue);
            
            
    // add tardiness to the optimal schedule array
            
    $this->addTardinessToOptimalSchedule();
            
            return 
    $this->optimalSchedule;
        }
        
    }

    $LA = new LawlersAlgorithm(array(=> array('processingTime' => 2,
                                                
    'dueDate'        => 3),
                                     
    => array('processingTime' => 3,
                                                
    'dueDate'        => 15),
                                     
    => array('processingTime' => 4,
                                                
    'dueDate'        => 9),
                                     
    => array('processingTime' => 3,
                                                
    'dueDate'        => 16),
                                     
    => array('processingTime' => 5,
                                                
    'dueDate'        => 12),
                                     
    => array('processingTime' => 7,
                                                
    'dueDate'        => 20),
                                     
    => array('processingTime' => 5,
                                                
    'dueDate'        => 27),
                                     
    => array('processingTime' => 6,
                                                
    'dueDate'        => 40),
                                     
    => array('processingTime' => 3,
                                                
    'dueDate'        => 10)),
                               array(
    => 5,
                                     
    => 9));

    echo 
    '<pre>';
    print_r($LA->compute());
    echo 
    '</pre>';

  4. #4
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)

    Thumbs up

    Quote Originally Posted by risoknop View Post
    Thanks. I actually decided to make a class out of that messy code:
    Great job. That's the sort of initiative that we like to see around here.
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  5. #5
    Twitter: @AnthonySterling silver trophy AnthonySterling's Avatar
    Join Date
    Apr 2008
    Location
    North-East, UK.
    Posts
    6,111
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)
    A Job and a JobCollection Object(s) would be a nice addition too.

    Or, if you're feeling rather adventurous, an iterator for JobCollection that would auto-magically apply your chosen algorithm.
    @AnthonySterling: I'm a PHP developer, a consultant for oopnorth.com and the organiser of @phpne, a PHP User Group covering the North-East of England.


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •