Returning value by nearest key

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
mrcoffee
Forum Commoner
Posts: 31
Joined: Tue Nov 10, 2009 3:03 pm
Location: Wyoming, USA

Returning value by nearest key

Post by mrcoffee »

To best explain what I'm trying to achieve I'll use a simplified example similar of what I'm doing:

$x changes over time, and there is an record for each time it changed:

Code: Select all

$x_throughout_time = array(
     0 => 5,
     mktime(0,0,0,8,1,2010) => 6,
     mktime(0,0,0,3,15,2011) => 2,
     mktime(0,0,0,7,1,2011) => 8,
);
I want to be able to look up what $x was for a given time. Currently I use a function like this:

Code: Select all

function get_x_for_given_time($timestamp) {
     global $x_throughout_time;
     $last_value = current($x_throughout_time); // first value, applicable for all times before 8/1/2010 (declare now in case $timestamp is before 1/1/1970)
     foreach($x_throughout_time as $implemented_time => $value) {
          if($timestamp < $implemented_time)
               return $last_value;
          $last_value = $value;
     }
     return $last_value; // if timestamp was after latest $x_throughout_time
}
This seems horribly inefficient, which is evident in execution time when $x_throughout_time contains many entries.

Any suggestions on a better way to do this?

Thank you in advance for your input.
User avatar
twinedev
Forum Regular
Posts: 984
Joined: Tue Sep 28, 2010 11:41 am
Location: Columbus, Ohio

Re: Returning value by nearest key

Post by twinedev »

Here is a function that will work, and actually giving what the title of this post says, "Nearest Key", not "Next lowest key" which your function is doing:

Code: Select all

	function get_x_closest_time($timestamp) {
		global $x_throughout_time;

		if (array_key_exists($timestamp,$x_throughout_time)) {
			return $x_throughout_time[$timestamp];
		}

		$time_keys = array_keys($x_throughout_time);

		$time_keys[] = $timestamp;
		sort($time_keys);
		$high_key = count($time_keys) - 1;
		$this_key = array_search($timestamp,$time_keys);

		if ($this_key == 0) {
			// Was before any tracked times, so return earliest
			$nearest_time = $time_keys[1];
		}
		elseif ($this_key == $high_key) {
			// Was after any tracked times, so return latest
			$nearest_time = $time_keys[$high_key - 1];
		}
		else {
			// Was in between other entries - See if it is closer to the one before or after
			if (($time_keys[$this_key]-$time_keys[$this_key-1]) > ($time_keys[$this_key+1]-$time_keys[$this_key])) {
				$nearest_time = $time_keys[$this_key+1];
			}
			else {
				$nearest_time = $time_keys[$this_key-1];
			}
		}

		return $x_throughout_time[$nearest_time];
	}
Broken down here is what is doing:

Code: Select all

		if (array_key_exists($timestamp,$x_throughout_time)) {
			return $x_throughout_time[$timestamp];
		}
If there is an exact matching timestamp, just return it, no need to do more

Code: Select all

		$time_keys = array_keys($x_throughout_time);

		$time_keys[] = $timestamp;
		sort($time_keys);
		$high_key = count($time_keys) - 1;
		$this_key = array_search($timestamp,$time_keys);
Take all of the keys from the main data array, and place them in an array of their own
Now, add another element to that array with the time stamp we are looking for.
Sort this array, so that they are in order by timestamp
Setting a variable to indicate the highest index for this array (for later use)
Setting $this_key to be the index of the array for the timestamp we are looking for.

Code: Select all

		if ($this_key == 0) {
			// Was before any tracked times, so return earliest
			$nearest_time = $time_keys[1];
		}
The index for the timestamp we are searching for is 0, which means that chronologically it is before any timestamp in the data, so we give back the earliest timestamp we have, which is $time_keys[1] (for your example data, since you set a timestamp of 0, this would never hit, but better safe than sorry)

Code: Select all

		elseif ($this_key == $high_key) {
			// Was after any tracked times, so return latest
			$nearest_time = $time_keys[$high_key - 1];
		}
The index of the timestamp we are searching for is the highest, so this means no data's timestamp is after it, so we give back the last time for the data, which is $time_keys[$hight_key-1]

Code: Select all

		else {
			// Was in between other entries - See if it is closer to the one before or after
			if (($time_keys[$this_key]-$time_keys[$this_key-1]) > ($time_keys[$this_key+1]-$time_keys[$this_key])) {
				$nearest_time = $time_keys[$this_key+1];
			}
			else {
				$nearest_time = $time_keys[$this_key-1];
			}
		}
Ok, since the index of the timestamp we are looking for is not the lowest nor the highest, we know it is between two given timestamps for data.
The if statement compares what value is larger, the difference to the previous timestamp, or the difference to the next timestamp. Whichever is less, that is the timestamp we are giving back

Finally we return the value from the original data array, using the timestamp from one of the three conditions above.

From my testing of it using the sample data you gave, running it through a loop, here are the results, the first number is what your function returned followed by what my function returned. ( I just gave the output where the numbers changed to save space)
[text]Checking for 07/20/2010 = 5 | 6
Checking for 08/03/2010 = 6 | 6
Checking for 11/15/2010 = 6 | 6
Checking for 11/22/2010 = 6 | 2
Checking for 03/07/2011 = 6 | 2
Checking for 03/15/2011 = 2 | 2
Checking for 05/03/2011 = 2 | 2
Checking for 05/10/2011 = 2 | 8
Checking for 06/28/2011 = 2 | 8
Checking for 07/05/2011 = 8 | 8[/text]
As you can see, your function gives that the closest LOWER (timestamp) value, not the overall closest. If you are still wanting the functionality of yours, in the final ELSE statement, instead of comparing which one is closer, just do

Code: Select all

		else {
			// Was in between other entries - Return the next lowest
			$nearest_time = $time_keys[$this_key-1];
		}
-Greg
mrcoffee
Forum Commoner
Posts: 31
Joined: Tue Nov 10, 2009 3:03 pm
Location: Wyoming, USA

Re: Returning value by nearest key

Post by mrcoffee »

I think you have my vote for Most Thorough Response, thank you. I was not able to think out of the box for this problem but your explanation was more than sufficient. Indeed my post title was faulty; I meant closest lower value. Thank you for providing the explanation for retrieving that as well.

Cheers.
User avatar
twinedev
Forum Regular
Posts: 984
Joined: Tue Sep 28, 2010 11:41 am
Location: Columbus, Ohio

Re: Returning value by nearest key

Post by twinedev »

Now that I'm awake, for the closest lower value (and assuming you will always have a 0 index):

Code: Select all

        function get_x_closest_time($timestamp) {
                global $x_throughout_time;

                if (array_key_exists($timestamp,$x_throughout_time)) {
                        return $x_throughout_time[$timestamp];
                }

                $time_keys = array_keys($x_throughout_time);
                $time_keys[] = $timestamp;
                sort($time_keys);
                $this_key = array_search($timestamp,$time_keys);
                return $x_throughout_time[$time_keys[$this_key-1]];
        }
Post Reply