SitePoint Sponsor

User Tag List

Results 1 to 7 of 7
  1. #1
    SitePoint Guru OfficeOfTheLaw's Avatar
    Join Date
    Apr 2004
    Location
    Quincy
    Posts
    636
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Examples of real world application of data structures?

    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. #2
    eschew sesquipedalians silver trophy sweatje's Avatar
    Join Date
    Jun 2003
    Location
    Iowa, USA
    Posts
    3,749
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    database? specifically indexes
    Jason Sweat ZCE - jsweat_php@yahoo.com
    Book: PHP Patterns
    Good Stuff: SimpleTest PHPUnit FireFox ADOdb YUI
    Detestable (adjective): software that isn't testable.

  3. #3
    SitePoint Guru
    Join Date
    Dec 2003
    Location
    oz
    Posts
    819
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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. #4
    Mlle. Ledoyen silver trophy seanf's Avatar
    Join Date
    Jan 2001
    Location
    UK
    Posts
    7,168
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    This thread has been cleaned

    Sean
    Harry Potter

    -- You lived inside my world so softly
    -- Protected only by the kindness of your nature

  5. #5
    ********* Victim lastcraft's Avatar
    Join Date
    Apr 2003
    Location
    London
    Posts
    2,423
    Mentioned
    2 Post(s)
    Tagged
    0 Thread(s)
    Hi...

    Quote Originally Posted by OfficeOfTheLaw
    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.
    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...
    PHP Code:
    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...
    PHP Code:
    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.

    2) 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
    Marcus Baker
    Testing: SimpleTest, Cgreen, Fakemail
    Other: Phemto dependency injector
    Books: PHP in Action, 97 things

  6. #6
    SitePoint Zealot
    Join Date
    Jun 2004
    Location
    Bogota
    Posts
    101
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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

    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
    If I have wings, why am I walking?

  7. #7
    Resident Java Hater
    Join Date
    Jul 2004
    Location
    Gerodieville Central, UK
    Posts
    446
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •