I think there is a correction for the time complexities: For the case when all three parameters are given, the time complexity will be *O(log(numTopics) + log(numLocations) + log(numLocale)). *Reason being it is like search on three different trees - after the key *topicValue* has been searched, only the tree associated to this key has to be searched for next parameter.
Similar analysis for missing parameter(s) case will lead to: - when topicValue is missing - O(numTopics * (log(numLocation)+log(numLocale)) ) - when locationValue is missing - O(log(numTopics) *+* numLocation ***log(numLocale)) *// note the + and * positions* - so on -- Abhay Prakash On Sun, Apr 13, 2014 at 11:25 PM, Abhay Prakash <[email protected]>wrote: > Use a B-Tree implemented using nested map<> as: > > *map<string, map<string, map<string, yourResultDataType> > > table;* > > Now for each level the complexity will be log(numOfElementsAtThatLevel). > e.g.* if you have all three parameters, the complexity of retrieval will > be O(log(numTopics)*log(numLocations)*log(numLocale)).* > > For the missing parameters iterate on that level to get all possible > results with other two parameters. Iteration on that level will obviously > be O(numOfElementsOnThatLevel). e.g.* if only location is missing > complexity will be O(log(numTopics)*numLocations*log(numLocale))* > > ------ sample code -------- > map<string, map<string, map<string, *yourResultDataType*> > > table; > > void addEntry(string topic, string location, string locale, > *yourResultDataType* rValue) > { > table*[topic][location][locale]* = rValue; > } > > yourResultDataType getResults(string topic, string location, string locale) > { > return table[topic][location][locale]; // in case this entry doesn't > exist in table, *null *will be returned > } > > vector<yourResultDataType> getResults*WithoutTopic*(string location, > string locale) // return all possibilities with given two params. > { > vector<yourResultDataType> toReturn; > map<string, map<string, map<string, *yourResultDataType*> > >:: > iterator it; > for(it = table.begin(); it != table.end(); ++it) > { > toReturn.push_back((it->second)*[location][locale]*); > } > return toReturn; > } > > vector<yourResultDataType> getResults*WithoutLocation*(string topic, > string locale) > { > vector<yourResultDataType> toReturn; > map<string, map<string, map<string, *yourResultDataType*> > > >::iterator ptr = table.find*(topic)*; > map<string, map<string, *yourResultDataType*> >:: iterator it; > for(it = ptr->second.begin(); it != ptr->second.end(); ++it) > { > toReturn.push_back(it->second*[locale]*); > } > return toReturn; > } > > ----- similarly for other combinations ------- > > -- > Abhay Prakash > IV Year (B.Tech + M.Tech Dual Degree) > Computer Science And Engineering > Indian Institute of Technology, Roorkee. > > > On Fri, Apr 11, 2014 at 10:34 AM, Narsimha Raju > <[email protected]>wrote: > >> Hi, >> I have a question and i would like to know the data structure to >> be used for this. >> >> >> You have 3 attribute >> 1. Topic >> 2. Location >> 3. Locale >> >> >> User can give any of the three or all the them to retrieve the content. >> For example. >> >> 1. Politics, Hyderabad, English >> In this case we need to show the result which satisfy all the 3 >> conditions. >> >> 2. Politics, Hyderabad >> In this case we need to show all the results of politics >> Hyderabad irrespective of language. >> >> >> -- >> Regards, >> C. Narsimha Raju >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
