php - Ways to optimize my MySQL database -


i have mysql database contains words in standard english alphabet, using create simple scrabble word generator. database separated 26 tables: 1 each letter in alphabet. each table contains 2 columns:

  • "word" column: column primary key, of type char(12), , not accept null values.
  • "length" column: column contains unsigned tinyint value , not accept null values.

in application, user enters in number of letters textbox (indicating tiles) , query database using code:

// looped on 26 times, , $char letter between 'a' , 'z' // check if user entered in character $char or blank tile (signified ? in app) // check prevents me having query useless tables if (in_array($char, $lettersarray) || $blanks) { // if so, select words have length that's possible make $query = 'select word '.$char.'words length <= '.strlen($letters); $result = $db->query($query); $num_results = $result->num_rows; ($j = 0; $j < $num_results; $j++) { // determine if it's possible create word based on letters input // if so, perform appropriate code } }

everything working, application takes long time compared competition (theoretical competition, is; more of learning project created myself , doubt i'll release on internet), despite fact application on local computer. tried used automatic optimization feature of phpmyadmin, provided no noticeable speed increase.

i don't think performance problem database. structure of data store going have significant impact on performance of algorithm.

one easy-to-understand approach problem handle problem anagrams. alphabetize of letters in each of words, , store column index on it.

word dorw -------- ------- dale adel lead adel led del hello ehllo ehlp

then, given set of letters, query database matching anagrams. alphabetize set of letters passed in, , run query.

select word dictionary dorw = 'aert' rate tare tear

then, query subsets of letters:

select word dictionary dorw in ('aer','aet','art','ert')

this approach longest words returned first.

this isn't efficient approach, it's workable.

handling "blank" tile going more work, you'd need substitute possible letter it, , checking 26 possibilities done in 1 query,

if have letters abcd , blank tile, example...

select word dictionary dorw in ('aabcd','abbcd', 'abccd' , 'abcdd', 'abcde', 'abcde', 'abcdf', ..., 'abcdz')

that gets more painful when start dealing subsets...

(in crossword , jumble puzzles, there aren't blank tiles)

so may not appropriate algorithm scrabble.

there other algorithms may more efficient, @ returning shorter words first.

one approach build tree.

the root node "zero" letter word. child of root node, nodes of one-letter words. each node marked whether represented valid word or not. children of nodes, have possible three-letter words, again marked whether valid or not.

that lot of nodes. words 12 letters in length, that's total possible space of 1 + 26 + 26**2 + 26**3 + 26**4 + ...

but wouldn't need store every possible node, you'd store branches result in valid word. wouldn't have branches below ->z->z or ->x->q

however, have branch under ->x->y->l, though xyl not word, beginning of branch leading 'xylophone'

but that's tree traversal algorithm, fundamentally different.


Comments

Post a Comment

Popular posts from this blog

javascript - backbone.js Collection.add() doesn't `construct` (`initialize`) an object -

<!doctype html public "-//w3c//dtd xhtml 1.0 strict//en" "http://www.w3.org/tr/xhtml1/dtd/xhtml1-strict.dtd"> <html> <head> <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script> <script src="http://documentcloud.github.com/underscore/underscore-min.js"></script> <script src="http://documentcloud.github.com/backbone/backbone-min.js"></script> </head> <body> <button id="cmd_create_event" name="cmd_create_event" type="button">create new `event`</button> <script type="text/javascript"> var eventmodel = backbone.model.extend({ initialize : function() { console.log("`event` initialized. id: " + this.cid); this.bind("change:status", function() { console.log(this.get("status") + " value `status`"); }); this.bind("error", function(model, e...
Read more

php - Get uncommon values from two or more arrays -

is there function in php give array of uncommon values 2 or more arrays? for example: $array1 = array( "green", "red", "blue"); $array2 = array( "green", "yellow", "red"); .... $result = function_needed($array1, $array2,...); print_r($result); should give output: array("blue", "yellow", ...); use array_diff , array_merge : $result = array_merge(array_diff($array1, $array2), array_diff($array2, $array1)); here's demo. for multiple arrays, combine callback , array_reduce : function unique(&$a, $b) { return $a ? array_merge(array_diff($a, $b), array_diff($b, $a)) : $b; } $arrays = array( array('green', 'red', 'blue'), array('green', 'yellow', 'red') ); $result = array_reduce($arrays, 'unique'); and here's demo of that.
Read more

Adding duplicate array rows in Php -

i create function in php adds rows of array shared column value. so input. $test = array( array("c", 5, 6), array("c", 2, 3), array("test", 5, 6) ); and output. $testduplicatefree = array( array("c", 7, 9), array("test", 5, 6) ) ); i'm thinking function combine_duplicates($array,$col){ ... ... return $duplicatefreearray; } where $col duplicate free array. so, in case, combine_duplicates($test,0); would me desired output. this. <?php function combine_duplicates($array,$col) { $index = array(); foreach ($array $row) { $key = $row[$col]; if (!isset($index[$key])) { $index[$key] = $row; } else { ($i = 0; $i < count($row); ++$i) { if ($i != $col) { $index[$key][$i] += $row[$i]; } } } } return array_values($index); } $array = array( array("c", 5, 6), array("c", 2, 3), array("test", 5, 6) ); print_r(combine_duplicates($array, 0)); try here: http://codepad.org/mdhesqhi
Read more