Examples of real world application of data structures?

PHP
1

I was bored last night, and started thumbing through my Advanced Algorithms in C++ book from college a bit, experimenting implementing them in PHP, and I was wondering… what are some real world applications for structures such as binary trees, linked lists, etc?

I mean, sure, the sorting, path mapping, and encryption algorithms make sense, but I kind of fail to see an application of linked list or binary tree structures in the real world, and I’ve been trying to come up with one.

2

database? specifically indexes

3

For apps that deal with massive amounts of data (eg Google), you need extremely specialised and effieicnt data strcuturs that allow maximum speed for processing. N-ary-Trees (most commonly binary trees) are extremely efficient in many situations.

Linked lists are very useful if you are inserting elements into the middle of a list many times, whereas an array would have to move all the above elements up one for every entry. As you data gets large, this is a huge problem.

The reason you fail to see a use for it in common day apps, is that your apps are probably so small that inefficincies cause no noticable problems with small amounts of data.

4

This thread has been cleaned

Sean :tdown:

5

Hi…

You use them all of the time, in PHP hashes, in databases (as Jason points out). The optimisation has been done for you, but it is behind the scenes. In fact if you can pck your data into a B-tree, a hash or a modern full text engine it is pretty much job done. It is unlikely you will beat these systems with your homebrew versions.

The knowledge is useful though. A couple of recent examples (this week) were…

  1. making sure an array scan was converted to a hash lookup. Loading an array like this…

foreach (next_phrase() as $phrase) {
    $phrases[] = $phrase;
}

…and doing an array look-up with in_array() will result in a linear scan. We had tens of thousands of these lookups in a big loop and it was taking about ten seconds to process. After the third run I changed it to…


foreach (next_phrase() as $phrase) {
    $phrases[$phrase] = true;
}

Now looking it up with an isset($phrases[$phrase]) turns it into a hash lookup. The script time dropped to a second.

  1. We had a large number of regexes to apply, again tens of thousands againts every line of a ten gig data set. That would have taken days. However only a few of these regexes were matching less than three letters. We run those short ones first and the longer regexes we sorted into three letter groups by the first three consecutive letters. We collect these and do a strstr() search on each letter group. If we get a hit we look up the regex list in a hash and apply just those regexes. Result: 1 our of processing.

So you may not use the actual algorithms and structures (although composite pattern and tree are related), but you will make use of the mindset.

yours, Marcus

6

A very interesting use of trees is in Genetic Algorythms.

Imagine this expression:
f(a,b,c) = (a + b) * (c - 3b)

And it’s representation with a binary tree.

*edit (I cant seem to geit to look right)

Now, imagine that for some reason this function is not approximate enough to model our situation, but there’s no evident way to tweak it. You’d basically have to play around with the terms and see if f(a,b,c) outputs a better result.

A genetic algorythm would come into the picture by randomly tweaking your tree, then comparing the output to the one you’d expect and selecting the best suited. Then you could try and trade some branches between the selected offsprings… repeat until you get a better formula for your model :slight_smile:

This is just a trivial example of what Genetic Algorythms is all about and it might not seem like it but it is handy for certain situations. It’s also so much fun.

  • Andres

Pd. In theory, you could have code generators using this same technique, pretty interesting for some of us, so I thought I’d metion it

7

As markus said…

Things like arrays use hashtables etc. Likewise with PHP arrays you can use them as any sort of container you like,

e.g.

  • array_pop, array_push for implementing stacks.
  • next(), end(), reset(), prev() can be used to make arrays simulate doubley linked lists.
  • hash (more specificly string) based array keys

B Trees are used in DBs, and though not a PHP things, things like 3D games/apps will use similar structures for culling and allsorts.

PHP does this all behind the scenes, along with garbage collection. People who haven’t used C++ and the mad syntax of things like …

std::vector<std::string, ContainerDatatypeHere> p;

(OK, you might use the namespace keyword to remove the std:: but still it’s a mouthful and you need to stick to using that datatype for objects inside it).

Likewise there is no easy foreach() in C++ so you end up declaring an itterator and using a long winded for command, along with the confusing fact that you need to use the dereference operator in C to get the object contained in the iterator object.

Basically, there are uses for this algorithms, you use them all of the time without realising in PHP so it doesn’t become as obvious. As a result it would be pointless implementing things like Hashtables in PHP.

As markus points out with hash lookups, it illustrates how optimising in PHP or any high level language is not always as direct as you think, especially if you have recently come from a background of using something like BASIC.