Probably you can make separate *multimap *for each of the attribute and while retrieval, taking intersection of sets associated with each of the attribute.
The three tables could be: multimap<string, yourResultDataType> contentsContainingTopic; multimap<string, yourResultDataType> contentsContainingLocation; multimap<string, yourResultDataType> contentsContainingLocale; For any occurrence of content, populate each of these tables accordingly, this will give you the ease of populating even with missing attributes. -- Abhay Prakash IV Year (B.Tech + M.Tech Dual Degree) Computer Science And Engineering Indian Institute of Technology, Roorkee. On Tue, Apr 15, 2014 at 11:49 AM, Narsimha Raju <[email protected]>wrote: > Hi Abhay, > Thanks for your solution, seems good as it is covering all the 3 > attributes. Nesting of Hashmap to 3 layers is little clumsy. For Example if > we increase from 3 to 4 attributes we can see the complexity of handling > the things. I would like to know, do we have any other solutions. > > > > > On Mon, Apr 14, 2014 at 9:36 AM, Abhay Prakash > <[email protected]>wrote: > >> 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]. >> > > > > -- > 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].
