XML parsing speed up. PHP

Question

I'm here to ask about some concepts that can make this process faster:

foreach($xml->results->concepts->concept as $value2){//This is the original game.
    $total_concepts++;
    foreach($xml1->results->concepts->concept as $value1){//This is similar game. 
        $total_similar_concepts++;
        if(strcmp($value2->name, $value1->name)==0){
            $comparisons++;
            break;
        }
    }
}

Essentially, I'm comparing each 'concept' of the original game to each 'concept' of each 'similar' games.

This algorithm takes about 11.6 seconds on average to complete. Is there something I can do to make this run faster? I was thinking that perhaps parsing it as xml wasn't the best I could do.

You algorithms time complexity is O(n^2). Thats why it is slow. — Josnidhin
– Josnidhin, Commented Jun 13, 2012 at 2:22
How long are the concepts? Is using a database an option? If you are dealing with datasets, parsing xml with php will usually be slower than using a sql database. — Nick Maroulis
– Nick Maroulis, Commented Jun 13, 2012 at 2:26

yankee · Accepted Answer · 2012-06-13 03:40:29Z

4

The XML parsing is very unlikely the reason for your problem. If it has to do with XML that it's probably I/O, meaning that it takes to long to fetch data from disk.

What you are doing is combining all elements in $xml with all elements in $xml2 which is an O(n^2) complexity problem. You can try to reduce complexity by making use of a hashmap, which is easy in php because you got associative arrays which are essentially hashmaps:

foreach($xml->results->concepts->concept as $value2) {
  $total_concepts++;
  $map[(string)$value2->name] = true;
}
foreach($xml1->results->concepts->concept as $value1) {
  $total_similar_concepts++;
  if (isset($map[(string)$value1->name]))
    $comparisions++;
}

In best case this gives you O(2n) complexity, much better than the previous version.

edited Jun 13, 2012 at 3:40

answered Jun 13, 2012 at 2:20

yankee

41.3k17 gold badges113 silver badges169 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Adola Over a year ago

I'm not sure what mapping here means. And this code seems to yield different results from what my previous code did. Could you help me understand it a bit better?

yankee Over a year ago

@Adola: Hashmaps aka Hashtables is a concept for fast access to non-continuous indexed data structures. Read more on it here: en.wikipedia.org/wiki/Hash_table. Actually the concept is quite simple, but I can't find a simple explanation on google. Feel free to ask a seperate questions on how hash maps work if you have trouble understanding. I'll give you a simpler explanation if I find it. And please elaborate on how the results are different.

Adola Over a year ago

Yeah, $comparisions never gets iterated in this version.

Adola Over a year ago

I'm actually pretty sure I get how this works just fine, now I'm confused as to why it doesn't work. It's a pretty simple and elegant solution, but I'm still unsure of why it's not working.

Adola Over a year ago

So, I just did a test, and this isn't yielding anything. foreach($xml->results->concepts->concept as $value2){ $map[$value2->name] = true; if(isset($map[$value2->name])){ echo "TEST!"; } } Shouldn't it under every situation always print TEST! ? I mean, it's being set, then being asked if was set.

|

Collectives™ on Stack Overflow

XML parsing speed up. PHP

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related