Jump to content


This topic is now archived and is closed to further replies.


slow algorithm execution time

Recommended Posts

Any algorithum junkies out there?

My algorithm I wrote takes about 20 seconds to run, but from what I can tell, it only goes though a few iterations. I'm pretty knew to PHP so maybe there are things I need to be carful of when iterating? Would anyone mind sanity checking it for me?

Here is what I'm doing:

The objects
  private $myDisks = array(); #array of Disks

  var $myDiskName; #device name of disk
  var $myCyls; #number of cyllinders on disk
  var $myHeads; #number of heads on disk
  var $mySects;  #number of sectors per track
  var $mySize;  #size of disk in bytes
  var $myPartitions = array(); #array of partitions

  var $myInfo = array();

DriveList Contains an array of Disks which contains an array of partitions:

The algorithm
The DriveList constructor reads in the partition table from the disk and fills in the info accordingly. This part works fine (only takes 1 - 2 seconds to run). The problem is, I need the array of Partitions (contained in Disk) to be sorted by location on the Disk, not the device name. So I wrote a sorting algorithm but it greatly reduces the execution time.

Note: the throwError function is just an error parsing routine I wrote for this project. Also note the following definitions:
#define info we can get from partition. #'s represent array elements
define('PNAME', 0);  # PNAME = Partition Name
define('SCYL', 1);  # SCYL = Start Cyllinder
define('ECYL', 2);  # ECYL = End Cyllinder
define('PSIZE', 4);  # PSIZE = Partition Size in Kb (Blocks)
define('FSTYP', 6);  # FSTYPE = File System Type

#move new partition into correct place
    $length = count($this->myPartitions);
    if ( $this->myPartitions[$length-1]->myInfo[FSTYP] != 'Empty' ) { #if not Empty, sort by start cyllinder
      $end = $length-1;
      throwError("Primary Partition found at end = $end ".$this->myPartitions[$end]->myInfo[PNAME], DBG);
      #sift partition down until SCYL of $end-1 is not larger
      while ( ($end > 0) &&
              ($this->myPartitions[$end]->myInfo[SCYL] < $this->myPartitions[$end-1]->myInfo[SCYL] ||
              $this->myPartitions[$end-1]->myInfo[FSTYP] == 'Empty') # keep empty partitions at end of table
            ) {
        throwError("Primary Partition at end = $end ".$this->myPartitions[$end]->myInfo[PNAME].
                  " is now end = ". ($end-1), DBG);
        $tmpPart = $this->myPartitions[$end-1];
        $this->myPartitions[$end-1] = $this->myPartitions[$end];
        $this->myPartitions[$end] = $tmpPart;
    else { #if Empty partition, see if we can place it in some free space
      $end = $length-1; $strt = -1;
      throwError("Empty Partition found at end = $end ".$this->myPartitions[$end]->myInfo[PNAME], DBG);
      do {
        throwError("Checking for empty space at strt = $strt ".$this->myPartitions[$strt]->myInfo[PNAME], DBG);
        #if this is the last item, see if space available at end of disk
        if ( $this->myPartitions[$strt]->myInfo[FSTYP] == 'Empty' ) {
          if ( $this->myPartitions[$strt]->myInfo[ECYL] < $this->myCyls - BUF ) {
            throwError("end of disk is empy strt = $strt", DBG);
            $this->myPartitions[$strt]->myInfo[SCYL] = $this->myPartitions[$strt-1]->myInfo[ECYL];
            $this->myPartitions[$strt]->myInfo[ECYL] = $this->myCyls;
            $this->myPartitions[$strt]->myInfo[FSTYP] = "Free Space";
            break; #found what we were looking for
        else if ( $this->myPartitions[$strt]->myInfo[ECYL] <  #if current partitions's end cyl is < the next partition's start cyl
            $this->myPartitions[$strt+1]->myInfo[SCYL] - BUF ) {  #then must be free space (BUF is tollerance on misalignment)
          throwError("Free space found after partition $strt ".$this->myPartitions[$strt]->myInfo[PNAME], DBG);
          #start at the end and shift up to make room for insertion
          $tmpPart = $this->myPartitions[$length-1];
          for ($end = $length-1; $end > $strt+1; $end-- ) {
            throwError("Sifting p $end " ." " .$this->myPartitions[$end]->myInfo[PNAME].
                      " is now p " .($end-1), DBG);
            $this->myPartitions[$end] = $this->myPartitions[$end-1];
          #now that it's in place, update it's information
          $this->myPartitions[$end] = $tmpPart;
          $this->myPartitions[$end]->myInfo[SCYL] = $this->myPartitions[$end-1]->myInfo[ECYL];
          $this->myPartitions[$end]->myInfo[ECYL] = $this->myPartitions[$end+1]->myInfo[SCYL];
          $nSize = ($this->myPartitions[$end]->myInfo[ECYL] - $this->myPartitions[$end]->myInfo[SCYL])
                  * ($this->myHeads) * ($this->mySects);
          $this->myPartitions[$end]->myInfo[PSIZE] = $nSize;
          $this->myPartitions[$end]->myInfo[FSTYP] = "Free Space";
          break; #found what we were looking for
      } while ( $strt < $length ); #failsafe if something goes wrong

[code] ** Debug: Primary Partition found at end = 0 /dev/hda1 **

** Debug: Primary Partition found at end = 1 /dev/hda2 **

** Debug: Primary Partition found at end = 2 /dev/hda3 **

** Debug: Primary Partition at end = 2 /dev/hda3 is now end = 1 **

** Debug: Empty Partition found at end = 3 /dev/hda4 **

** Debug: Checking for empty space at strt = 0 /dev/hda1 **

** Debug: Checking for empty space at strt = 1 /dev/hda3 **

** Debug: Free space found after partition 1 /dev/hda3 **

** Debug: Sifting p 3 /dev/hda4 is now p 2 ***[/code]

This is the partition table this output is based on:  from 
popen( "sudo /usr/sbin/sfdisk -l | grep dev", "r" )[code]Disk /dev/hda: 19485 cylinders, 16 heads, 63 sectors/track
/dev/hda1          0+    16463-  16464-  8297541  83  Linux
/dev/hda2      18407+  19484    1078-    542902+  82  Linux swap
/dev/hda3      16463+  18013-  1550    781200    83  Linux
/dev/hda4          0              -      0          0        0    Empty

Thanks for your time!

Share this post

Link to post
Share on other sites


Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.