Simple implementation of LRU caching in PHP

Question

This is my implementation of LRU caching in PHP.

It works fine when I tested as. What are the things that I miss or need attention?

<?php
class Cache{
 private $cache;
 private $size;
 public function __construct($size)
 {
 $this->cache = [];
 $this->size = $size;
 }
 public function put($item)
 {
 if($this->isFull())
 {
 if(in_array($item, $this->cache))
 {
 $this->cache = array_diff($this->cache, [$item]);
 }
 else
 {
 array_pop($this->cache);
 }
 } 
 array_unshift($this->cache,$item); 
 }
 public function display()
 {
 var_dump($this->cache);
 }
 private function isFull()
 {
 if(count($this->cache) >= $this->size)
 {
 return true;
 } 
 }
}
$cache_size = 4;
$entries = [3,4,4,5,6,7,4,4,3,5,2,3,1,1,4];
$cache = new Cache($cache_size);
$cache->display();
foreach($entries as $entry)
{
 $cache->put($entry);
}
$cache->display();

Output for above provided data

//blank cache
array(0) {
}
//insertion of all entries
array(4) {
 [0]=>
 int(4)
 [1]=>
 int(1)
 [2]=>
 int(3)
 [3]=>
 int(2)
}

• Holger: I think, even if the array !is_full(), the $item has to be removed, if it is in_array().

Answer 1

This implementation is quite simple. I compared it with some others in PHP as well as other languages like C++, Java and JavaScript. Some use a node class to store a key and value separately (e.g. this PHP implementation) but for a simple implementation your approach seems fine.

I noticed that the method isFull() only explicitly returns a value when true is returned. While it works because the conditional that calls that method would this implicitly evaluate the empty return to a false-y value, some would argue that methods that return a value should do so in every case, for the sake of readability. That could be achieved by simply returning the conditional:

private function isFull()
{
 return count($this->cache) >= $this->size);
}

And one other simplification would be to set the property/instance variable $cache to an empty array when it is declared, since it can be evaluated at compile time and does not depend on any run-time information to be evaluated, instead of inside the constructor:

private $cache = [];

• Shobi: Thanks, @SAM, I was trying to prepare for an interview and this seemed to be a common question in the organization. It was really helpful

Answer 2

Another thing I thought about was the technique for removing the element if it exists in the array i.e.:

if(in_array($item, $this->cache))
{
 $this->cache = array_diff($this->cache, [$item]);
}

Obviously this works but it requires re-assigning the array to a new array constructed by computing the diff of that array and an array with the item to be found. An alternate approach might be to store the index of the element using array_search() and as long as that doesn't return FALSE (explicitly, since 0 would be a falsey value), use array_splice() to remove the element at the given index.

$index = array_search($item, $this->cache);
if($index !== FALSE)
{
 array_splice($this->cache, $index, 1);
}

The reason for the explicit check of FALSE is explained in the documentation for array_search():

Warning

This function may return Boolean FALSE, but may also return a non-Boolean value which evaluates to FALSE. Please read the section on Booleans for more information. Use the === operator for testing the return value of this function.¹

With this approach, there is no need to create an array just to contain the item, compute the diff or re-assign the array. While it may require a slight amount of more memory for the index, it could in theory take less memory overall when the array doesn't need to be re-assigned. I did try comparing the memory usage between the original code and updated code and the memory and time consumption appears to be negligibly different... perhaps for larger data sets it might be more noticeable. I tried to research if in_array() is noticably faster than array_search() and didn't find much in a cursory search, though the answers to which is best array_search or in_array? on SO are interesting. One answer suggests flipping the array and checking if the key is set using isset(), but you would have to flip the array each time just to check and that might slow things down dramatically.

While some may argue this is less readable, the assignment of $index can be combined into the conditional:

if(($index = array_search($item, $this->cache)) !== FALSE)
{
 array_splice($this->cache, $index, 1);
}

¹_{http://php.net/manual/en/function.array-search.php#refsect1-function.array-search-returnvalues}

• Shobi: if(($index = array_search($item, $this->cache))) I think this is enough to produce the falsy value, which will prevent the if's body from executing. array_splice was good though. Thanks @SAM
• Sᴀᴍ Onᴇᴌᴀ: But if the element to find is in the first (I.e. 0^th) position then that would also evaluate to FALSE in a conditional context. See the quote I added from the documentation
• Shobi: yes. you are right