performance - SQL anagram efficiency and logic? -


i have sql db 200,000 words. need query able solve anagram kind of. difference need possible words made input characters. example, if input ofdg, should output words: do, go, , dog. can estimate amount of time query take. how can make faster , more efficient? also, in general how long take sql parse 200000 row database.

to solve problem, first thing need reduce every word scrabble players call alphagram. is, letters in word in alphabetical order. do, go , dog make do, go , dgo. of course, given alphagram may correspond more 1 word, so, example, alphagram dgo corresponds both words dog , god.

the next thing need construct table key alphagram-sequence number , single attribute field word.

word lists tend static. example, 2 scrabble word lists in english-speaking world change every 5 years of so. construct lookup table beforehand. performance o( n ) , sunk cost. is, once , store it, not counted against cost of query. have beforehand. makes absolutely no sense build such index on fly every time query comes in.

you may wondering "what scrabble?" answer figure of 200,000 words falls neatly between 2 approved tournament word lists in english-speaking world. national scrabble association's official tournament , club word list (2006) contains 178,691 words, , international list, maintained world english scrabble players' association, contains 246,691.

when query reduce supplied word bunch of alphagrams. input odfg makes alphagrams od fo go df dg fg dfo dgo fgo dfg dfgo (which pretty programming problem in pure sql, have assume there php or python or javascript front-end you). lookup in database. cost of each query should approximately o(log2 n), in other words pretty damn immediate. sort of query relational databases at.

btw, example output poor. alphagram dfgo scrabble players call 'build' (all possible subsets) makes do od of go dog god fog.

(i hate have rigmarole, hasbro's lawyers touchy, so: scrabble registered trademark owned in usa hasbro, inc.; in canada hasbro canada corporation; , throughout rest of world j. w. spear & sons, mattel company.)


Comments

Post a Comment

Popular posts from this blog

c++ - Is it possible to compile a VST on linux? -

for class project i'm attempting write vst plugin backed cuda. current cuda workflow on linux box, i'd prefer compile , link there. according wikipedia , should possible (i couldn't find steinberg documentation relevant linux) can't find makefile or instructions on how build if aren't using xcode or visual studio. i'm vst 3 sdk doesn't support linux. when try compile plugin under linux, error: ./base/source/fatomic.cpp:39:30: fatal error: libkern/osatomic.h: no such file or directory this issue caused following code in "vst3 sdk/base/source/fatomic.cpp" #if mac #include <libkern/osatomic.h> #if mac_os_x_version_min_required > mac_os_x_version_10_4 #define native_atomic_type (volatile int32_t*) #else #define native_atomic_type (int32_t*) #endif #elif windows #include <windows.h> #endif but hope compiling under linux work vst sdk 2.4. reading. jvstwrapper seems run on lin...
Read more

java - Output of Eclipse is rubbish -

i want write program in eclipse language different english. when display output using system.out program, displays output correctly in console editor. when accept input console , output it, output rubbish. how can solve it. many thnaks i'm not sure if problem, have character encoding problem. make sure you're using unicode, utf-8. you can read more @ official docs converting non-unicode text .
Read more

jquery - Confused with JSON data and normal data in Django ajax request -

i read json internet still have not got grasp of it. reading article http://webcloud.se/log/ajax-in-django-with-jquery/ i not understood first part function using json def xhr_test(request, format): if request.is_ajax(): if format == 'xml': mimetype = 'application/xml' if format == 'json': mimetype = 'application/javascript' data = serializers.serialize(format, examplemodel.objects.all()) return httpresponse(data,mimetype) # if want prevent non xhr calls else: return httpresponse(status=400) my main problems are from function getting format variable does format json mean data given function json or data recived json can give me simple example ouput of function data = serializers.serialize(format, examplemodel.objects.all()) how use data when response in jquery function if don't use json in above function how input , response chnage thanks ...
Read more