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 <abhay.praka...@gmail.com>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
> <cnarsimhar...@gmail.com>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 algogeeks+unsubscr...@googlegroups.com.
>>
>
>
--
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 algogeeks+unsubscr...@googlegroups.com.
