2
\$\begingroup\$

I'm dealing with huge amount of data. I've written following code into a function to find out similar questions. It's working perfectly but it is taking too much time in execution. Can anyone help me to optimize the function code so that the execution time will be less?

<?php

  class QuestionMatch {

    var $mError = "";
    var $mCheck;
    var $mDb;
    var $mValidator;
    var $mTopicId;
    var $mTableName;

    function __construct() {
      global $gDb;
      global $gFormValidation;

      $this->mDb        = $gDb; 
      $this->mValidator = $gFormValidation;
      $this->mTableName = TBL_QUESTIONS;
    }

    /**
 * This function is used to get all the questions from the given subject id and topic id
     */
    function GetSimilarQuestionsBySubjectIdTopicId($subject_id, $topic_id) {

        /*SQL query to find out questions from given subject_id and topic_id*/
        $sql  = " SELECT question_id, question_text FROM ".TBL_QUESTIONS." WHERE question_subject_id=".$subject_id;
        $sql .= " AND question_topic_id=".$topic_id;

        $this->mDb->Query($sql);
        $questions_data = $this->mDb->FetchArray();

  /*Array of words to be excluded from comparison process*/
        $exclude_words = array('which','who','what','how','when','whom','wherever','the','is','a','an','and','of','from');  

  /*This loop removes all the words of $exclude_words array from all questions and converts all 
   *questions' text into lower case
  */
  foreach($questions_data as $index=>$arr) {
    $questions_array = explode(' ',strtolower($arr['question_text']));
    $clean_questions = array_diff($questions_array, $exclude_words);
    $questions_data[$index]['question_text'] = implode(' ',$clean_questions);

    /*Logic to find out the no. of count question appeared into tests*/
    $sql  = " SELECT count(test_que_id) as question_appeared_count FROM ".TBL_TESTS_QUESTIONS." WHERE test_que_id=";
    $sql .= $arr['question_id'];

    $this->mDb->Query($sql);
    $qcount = $this->mDb->FetchArray(MYSQL_FETCH_SINGLE); 

    $question_appeared_count = $qcount['question_appeared_count'];
    $questions_data[$index]['question_appeared_count'] = $question_appeared_count;
  } 

  /*Now the actual comparison of each question with every other question stats here*/
        foreach ($questions_data as $index=>$outer_data) {
    /*Crerated a new key in an array to hold similar question's ids*/
    $questions_data[$index]['similar_questions_ids_and_percentage'] = Array(); 

    $outer_question = $outer_data['question_text'];

    $qpcnt = 0;     

    /*This foreach loop is for getting every question to compare with outer foreach loop's 
    question*/
    foreach ($questions_data as $secondIndex=>$inner_data) { 
        /*This condition is to avoid comparing the same questions again*/
      if ($secondIndex <= $index) {
        /*This is to avoid comparing the question with itself*/
          if ($outer_data['question_id'] != $inner_data['question_id']) {

          $inner_question = $inner_data['question_text'];  

            /*This is to calculate percentage of match between each question with every other question*/
            similar_text($outer_question, $inner_question, $percent);
            $percentage = number_format((float)$percent, 2, '.', '');

            /*If $percentage is >= $percent_match only then push the respective question_id into an array*/
            if($percentage >= 85) {
            $questions_data[$index]['similar_questions_ids_and_percentage'][$qpcnt]['question_id']       = $inner_data['question_id'];
            $questions_data[$index]['similar_questions_ids_and_percentage'][$qpcnt]['percentage']        = $percentage;
            $qpcnt++;
        }
      }
    }   
  }
  if(!empty($outer_data['similar_questions_ids_and_percentage'])) { 
    $return_url  = ADMIN_SITE_URL.'modules/questions/match_question.php?';
    $return_url .= 'op=get_question_detail&question_ids='.$outer_data['question_id'];

    foreach($outer_data['similar_questions_ids_and_percentage'] as $secondIndex=>$inner_data) {
      $return_url = $return_url.','.$inner_data['question_id'];
    }      
    $questions_data[$index]['return_url'] = $return_url.'#searchPopContent';
  }
}         
      /*This will return the complete array with matching question ids*/
  return $questions_data;
  }

  function GetAllErrors() {
    return $this->mValidator->mErrorMsg;
  }
}
?>

If you want any further details I can provide you the same. Waiting for your precious help and valuable replies.

\$\endgroup\$
  • 1
    \$\begingroup\$ sql injection alert \$\endgroup\$ – ratchet freak Nov 26 '13 at 14:09
  • \$\begingroup\$ How does similar_text() work ? Can we see the code on that. Also, what kind of data size do you have? \$\endgroup\$ – Kami Nov 26 '13 at 18:23
  • \$\begingroup\$ @Kami php.net/manual/en/function.similar-text.php it counts the percentage of common characters. \$\endgroup\$ – Quentin Pradet Nov 27 '13 at 9:49
1
\$\begingroup\$

Unfortunately there's not much you can do here. Unless you try the difficult but efficient approach at the end of my answer, your for loops won't go away and you will need to understand what takes you time inside those loops to get small wins.

Micro-optimizations

You need to profile the code to understand what takes time:

  • Is it the SQL query?
  • Is it excluding words from the stop word list? (Those lists already exist for English and other languages, by the way.)
  • Is it similar_text()?
  • Is it building the array?

You don't need $percentage and number_format: $percent is already a float.

Context

Another thing to consider is the 'context' of this function: is it called only once, or do you call it for every subject and topic? If that's the case, then it would be better to do the similarity search for all topics and questions, and then display only questions with the same topic and subject. You would go from many SQL queries (one per topic and subject combination) to only one.

All Pairs Similarity Search

The problem you're trying to solve is called All Pairs Similarity Search. There is a scientific paper and an implementation from Google if you're interested in the research problem. The research applies to sparse vectors but it's possible to turn your sentence into a vector of the size of your vocabulary: a cell i is 1 if the word corresponding to cell i is in your cell, and 0 otherwise. Such a vector is sparse because most cells are 0 for a given sentence. Feel free to ask more questions if you want to try this out.

\$\endgroup\$
  • \$\begingroup\$ Thats fasinating reading thanks I really enjoyed that. \$\endgroup\$ – Dave Nov 28 '13 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.