Misunderstanding How in_array Works

Brian Moon has a post about how in_array() really, really sucks. This is not a problem with in_array per se, but failing to recognize the proper way to solve a problem like this. Some of the comments has already touched on this matter, but I’ll attempt to further expand and describe the problem.

You have two arrays; a1 and b2. You’re interested in removing all the values from a1 that also are in b2. If you’re doing the naive approach (which Brian Moon describes), you’ll simply do:

```foreach(\$a1 as \$key => \$value)
{
foreach(\$b2 as \$key2 => \$value2)
{
if (\$value == \$value2)
{
unset(\$a1[\$key]);
}
}
}
```

(ignore any potential side effects of manipulating \$a1 while looping through it for now)

This will work for small sizes of a1 and b2, but as soon as the number of entries starts to increase (let’s call them m and n), you’ll see that the growth of your function will approach O(m*n), which can be written as O(n²) as both values approach infinity. This is not good and is the same complexity that you’ll find in naive sorting algorithms. This means that for each element you add to the array, your processing time increases quadratically (since you have two loops here). in_array is simply a shortcut for the inner loop (the inner foreach loop) in this example. It loops through each element of the array and checks if it matches the needle we’re searching for.

Compare this to using array_flip on the array to search first, so that the values becomes the keys:

```foreach(\$a1 as \$key => \$value)
{
if (isset(\$b2[\$key]))
{
unset(\$a1[\$key]);
}
}
```

But why is isset(\$arr[\$key]) any faster than using in_array? Doesn’t the application just have to loop through a different set of values instead (this time, the keys instead of the values)? No. This is where hashing comes into the picture. As \$key can be any string value in PHP, the string is hashed and resolved to an internal array id. This means that internally, the following is happening:

\$arr[\$id] => find location by converting \$id to an internal array location (on the C-level) => simply index the array by using this value

Instead of going through all the valid keys, the \$id is converted once, and then checked to see if there is any value stored at that location. This is a simplification, but explains the concept. The complexity of this conversion may depend on the length of the key (depending on the choice of hashing function), but we’ll ignore this here, and simply give it a complexity of O(1). Looking up the index in the array is also an O(1) operation (it takes the same time, regardless if we’re looking at item #3 or #4818, it’s simply reading from different locations in memory).

This means that while our other loop is still looping through n elements, we’re now just doing a constant lookup in the innerloop. The amount of work done in the inner loop does not depend on the number of elements in b2, and this means that our algorithm instead grows in a linear fashion (O(n)).

Further reading can be found at Wikipedia: Hash function, Big O Notation. I’ll also suggest reading an introductionary book into the field of algorithms and datastructures. The type of book depends on your skillset, but if anyone wants any suggestions, just leave a comment and I’ll add a few as I get home to my bookshelf tonight.

Implementing a Duck Operator with Reflection

Following up on this post regarding a “duck operator” in PHP, I went ahead and wrote a very, very, very simple implementation using reflection api in php to get the same functionality.

```getMethods() as \$method)
{
\$ret[\$method->getName()] = true;
}

return \$ret;
}

function it_quacks(\$object, \$interface)
{
\$reflectionClass = new ReflectionClass(\$interface);
\$reflectionObject = new ReflectionObject(\$object);

\$reflectionClassMethods = getMethodProperties(\$reflectionClass);
\$reflectionObjectMethods = getMethodProperties(\$reflectionObject);

foreach(\$reflectionClassMethods as \$methodName => \$methodData)
{
if (empty(\$reflectionObjectMethods[\$methodName]))
{
return false;
}
}

return true;
}

if (it_quacks(new MooingGrassEater(), 'Cow'))
{
print("A MooingGrassEater can be seen as a Cow\n");
}
else
{
print("A MooingGrassEater has no hope of being recognized as a Cow\n");
}

if (it_quacks(new MooingGrassEater(), 'Sheep'))
{
print("A MooingGrassEater can be seen as a Sheep\n");
}
else
{
print("A MooingGrassEater has no hope of being recognized as a Sheep\n");
}
?>
```

Missing obvious points are of course to compare the number of arguments to the methods and wether they’re optional, so that you further ensure call safety. But hey, it’s just an example implementation. Read the original linked page for more information about the concept.

Debugging Missing Statistics in OpenAds (OpenX)

Our statistics in OpenAds had suddently gone missing in action, and I started suspecting a few errors we’d gotten earlier about fubar-ed MyISAM-tables. First, check out debug.log (or maintenance.log if you’re running a newer version than us) in the var-directory of your Openads-installation. The easiest thing to do here is to search for the string ’emergency’, which will be posted to the log each time something fails in MySQL. The MDB2 error message that is included will show you the error message from MySQL in one of the fields (about 15-25 lines down), which will give you the reason for the error (if MySQL is to blame).

Some tables had been marked as crashed in our MySQL-installation, so we had to find out what to fix. A quick run with myisamchk in the MySQL-data directory for the database gave us a few hints:

```myisamchk *.MYI > /tmp/myisamcheckoutput
```

By redirecting the normal output you’ll just get the error messages to stderr (Openads has quite a few tables, so your console will fill up quite quick otherwise) (as stdout will be redirected to /tmp/myisamcheckoutput). You’ll also be able to check the output by using less on /tmp/myisamcheckoutput.

If any tables are having problems, you can run:

```REPAIR TABLE ;
```

in your MySQL console, and the table should be repaired in the background. After doing this, it’s time to get maintenance back up and running again.

Run the maintenance.php file manually (or wait until it gets triggered within the next hour):

```php /scripts/maintenance/maintenance.php
```

Brian K. Jones has a neat list of things to look for when buying a new book. To sum it up in a few points:

• Give Any New Version 6 Months Before Buying a Book About It.
• Take reviews with several grains of salt
• Look for “Timeless Tomes”
• Look at the Copyright Date
• Be Wary of Growth in Second Editions

These are all good points, but I’d like to add a few rules of my own that help decide which books that end up in my reading queue:

• If you’re happy with the book you’re currently reading, use Amazon’s suggestion system to find more about the same subject. This has worked surprisingly well (and I’m sure Amazon is happy about that..) for me, but limit yourself to one additonal book this way.
• While reading a good book, if the author mentions another book that he found interesting or that provided insight into the content you’re now reading, add it to your wishlist. Good authors usually suggest good and insightful books.
• To further extend the point of “Look at the copyright date”; use this date to find potential “Timeless Tomes”. If a book were first published in the 1970s or 1980s and is in it’s 21st print now, I’ll personally guarantee that the book is worth reading. It might not be about a subject that you’re interested in, but it might give you new insights or a better background in something you never would have read otherwise.
• Use your wishlist on Amazon to keep track of interesting books that you stumble across. This is particularily useful for those of us who live in non-native Amazon locations, so that we’re able to combine shipping for items. I’ll never order a single book, so if I forget to add it to my wishlist, I will probably never remember it when I actually order books. Use it.
• Check out the blog of the author if you’re able to (and the author actually have a blog). Also, if a blog that you follow on a daily basis suggests a book, it’s probably worth getting.
• If you’re out travelling, buy a cheap, simple paperback book about a subject that you’re unfamiliar with. Try to get something a bit populistic (not too academic), as it will make the introduction to the subject easier and is more suitable for reading under noisy conditions. Keep it cheap, so that if you’re unhappy with the book, you can just donate it to another traveller or a local book donation program.

Strange Spambots

Recently I’ve noticed quite a few spambots submitting random comments on a few sites that I run, and while that’s not surprising, the content kind of is. The comments are simple, text only comments mentioning a product of some sort, together with a few random words or characters. No links. Nothing.

My current guess is that the message may be probes to see if there is a word filter active for the words they attempt to submit, and that when they find that the comment goes through, they submit their long list of links and other interesting stuff. The problem is that the sites filter all comments that contain more than one URL and all occurences of “[url”. This has not let a single linked comment through in two years, but now the volume of these comments are getting ridiculous. Guess I’ll have to add some new magic feature with javascript.

Spectator PHP Debugger and an Update on WebGrind

Stumbled upon Spectator – an PHP debugger written in XUL. Seems like a promising project and I’m always in favor of people who actually do what they say other people should do :-)

Also worth noting is that the first releases of WebGrind are out, and seems to be a neat tool for those who need to make sense of a few kcachegrind files (for example if you’re using xdebug and it’s profiling functionality).

Free Flash Based File Upload Applications

When I started writing Swoooosh, the main reason was that after needing a free component for a project for a customer of mine (where uploading multiple files were not an original part of the specification, but was added later), I were left with a few components with dubious licenses and weird attribution requests that left you guessing. Instead I hoped someone would release something under an MIT-based license (or LGPL, BSD, etc) to be free for all kinds of usage, and could be further extended by the community.

Luckily a few alternatives has emerged since then, and Swoooosh isn’t really that relevant any longer (it was a good exercise for writing Flex and ActionScript, tho):

And Yes, Christer, I’m going to implement one of these and commit to SVN any moment now. :-)