c# - Optimal data structure for lookup within nested scopes -


say, there's tree data structure, each leaf of defines set of keys lookup:

* |- = 1, b = 2 |- *    |- c = 4    |- *       |- d = 5       |- d = 6, e = 7

i need way of finding value of key given leaf while tree being traversed depth-first.

there 2 approaches have thought of:

  1. if value not found in current leaf, check dictionary of parent , on root of tree.

  2. there global dictionary , each leaf inserts/removes keys when being traversed. lookup in performed in global dictionary.

it's there many leafs few keys in each, , 3-4 lookups each key.

which approach more efficient? or, maybe, there's way of doing better both?

the programming language implementing sure define exact rules name resolution. don't think lead depth-first search. name resolution rules, fruequently, somethink this:

  1. search current scope, considering has been declared “up” current position in source code;
  2. when specific rules met, e.g. there form of using / import or whatever other construct linking other scope, perform search in other scope (all of such scopes, sequentially), , recurse within it:
    1. search given scope,
    2. recurse relevant nested scopes;
  3. go immediatelly enclosing scope;
  4. repeat (1), 'current' scope determined in (3).

in other words, gradually go in tree of enclosing scopes, , decide whether search 'foreign' referenced scopes. statements such using / import lead references among scopes, in turn cause viewed tree of scopes in fact directed graph.

regarding lookup table construction, i'd start simple hashtable. prefix trees (tries) work these scenarios, too.

last not least, wouldn't care of lookup performance unless i'd face real performance problem when compiling tens or maybe hundreds of thousands of lines of code.


Comments

Post a Comment

Popular posts from this blog

android - Get AccessToken using signpost OAuth without opening a browser (Two legged Oauth) -

i using signpost oauth access data magento server. have read various tutorials on same , reach point open browser user can enter credentials. however, per requirement have automate part. hence, user should not browser page. have set-up done on server side ( magento ), hit url , returned call page. same through program in android. i have tried below, consumer = new commonshttpoauthconsumer(key, secret); provider = new commonshttpoauthprovider(oauth_init_url,access_token_url, authorize_url); try { provider.retrieverequesttoken(consumer, oauth.out_of_band); log.d("tokens" , consumer.gettoken() + " -- " + consumer.gettokensecret()); } and request tokens. dont know how bypass next step. tried directly accessing accesstoken (stupid of me) provider.retrieveaccesstoken(consumer, "mycallback://callback"); no luck, ends in oauth.signpost.exception.oauthnotauthorizedexception: authorization failed (server replied 401). ...
Read more

org.mockito.exceptions.misusing.InvalidUseOfMatchersException: mockito -

getting error org.mockito.exceptions.misusing.invaliduseofmatchersexception: invalid use of argument matchers! 1 matchers expected, 2 recorded. exception may occur if matchers combined raw values: //incorrect: somemethod(anyobject(), "raw string"); when using matchers, arguments have provided matchers. example: //correct: somemethod(anyobject(), eq("string matcher")); at when( getprogramservice .callservice(any(getprogramtype.class))) .thenreturn(jaxbresponse); please explain error , possible resolution the code posted looks fine; don't see problem it. code before or above causing exception. key here: invalid use of argument matchers! 1 matchers expected, 2 recorded. any , used above, doesn't return "special kind of null" or "special kind of getprogramtype"; don't exist. instead, returns null , side effect puts matcher on stack. whe...
Read more

google shop client API returns 400 bad request error while adding an item -

i'm working on solution add items in google shopping market java application. following tutorial real mess because of missing classes of laste release, after setting 1.5-beta maven managed make base example typecheck correctly classes. still can make simple task of adding 1 item. instead of posting whole code i'm posting part creates product feed. private product createproduct(string id) { product product = new product(); product.title = "red wool sweater"; product.content = new content( "text", "comfortable , soft, sweater keep warm on " + "cold winter nights. red , blue stripes."); product.appcontrol = new appcontrol(); product.appcontrol.addrequireddestination("productads"); product.externalid = id; product.lang = "it"; product.country = "it"; product.condition = "nuovo"; product.price = new price("eu...
Read more