Time complexity
Monday, 8 July 2019 · 3 messages
JC
Jordan Castillo8 Jul 2019 17:40 #
Hello BaseX Staff,
Question regarding why the time complexity of my query is dramatically different in these 2 situations. I'm building a map inside a function that is called many times, and this function receives an ID and then has to retrieve some values to store inside the map.
In case #1, I check if the values exists first, otherwise I store '()':
"lowerValue" : if
(exists($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2
+ $mult]]/lowerValue[@value]))
then
data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2
+ $mult]]/lowerValue/[@value])
else (),
"upperValue" : if
(exists($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2
+ $mult]]/upperValue[@value]))
then
data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2
+ $mult]]/upperValue/[@value])
else ()
Total Time: 1526.0
In case #2:JC
Jordan Castillo8 Jul 2019 17:44 #
I accidentally sent the message prematurely.
In case #2, I simply search for the values and save the result into the map (the exact same result I now realize):
"lowerValue" :
data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 + $mult]]/lowerValue/[@value]),
"upperValue" :
data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 + $mult]]/upperValue/[@value])
Total Time: 19.98 ms
I see that I am performing the same query twice the amount of times in case #1, but I'm failing to see how this exponentially increases the time complexity.
Any explanation or reference to reading material to help me understand this situation would be greatly appreciated.
Thanks,
Jordan Castillo
Quoted text · Jordan Castillo · 29 lines
On Mon, Jul 8, 2019 at 6:40 AM Jordan Castillo < jordantcastillo1992 at gmail.com> wrote: > Hello BaseX Staff, > > Question regarding why the time complexity of my query is dramatically > different in these 2 situations. I'm building a map inside a function that > is called many times, and this function receives an ID and then has to > retrieve some values to store inside the map. > > > > In case #1, I check if the values exists first, otherwise I store '()': > "lowerValue" : if > (exists($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 > + $mult]]/lowerValue[@value])) > then > data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 > + $mult]]/lowerValue/[@value]) > else (), > "upperValue" : if > (exists($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 > + $mult]]/upperValue[@value])) > then > data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 > + $mult]]/upperValue/[@value]) > else () > Total Time: 1526.0 > In case #2: >
JC
Jordan Castillo8 Jul 2019 18:26 #
I feel very silly but I figured out the problem and it was my own doing.
In the very slow version of the function, I am opening the context using: let $context := db:open(...)
In the new and fast version, I am sending the context to the function: declare function local:propGenerator($propList, $currID, $context) {...}
I changed this without testing the differences and mistook the change in time for the "if else" statements rather than repeatedly opening the database.
Hope I didn't waste anyones time!
Jordan Castillo
Quoted text · Jordan Castillo · 55 lines
On Mon, Jul 8, 2019 at 6:44 AM Jordan Castillo < jordantcastillo1992 at gmail.com> wrote: > I accidentally sent the message prematurely. > > In case #2, I simply search for the values and save the result into the > map (the exact same result I now realize): > "lowerValue" : > data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 > + $mult]]/lowerValue/[@value]), > "upperValue" : > data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 > + $mult]]/upperValue/[@value]) > Total Time: 19.98 ms > > I see that I am performing the same query twice the amount of times in > case #1, but I'm failing to see how this exponentially increases the time > complexity. > Any explanation or reference to reading material to help me understand > this situation would be greatly appreciated. > > Thanks, > > Jordan Castillo > > On Mon, Jul 8, 2019 at 6:40 AM Jordan Castillo < > jordantcastillo1992 at gmail.com> wrote: > >> Hello BaseX Staff, >> >> Question regarding why the time complexity of my query is dramatically >> different in these 2 situations. I'm building a map inside a function that >> is called many times, and this function receives an ID and then has to >> retrieve some values to store inside the map. >> >> >> >> In case #1, I check if the values exists first, otherwise I store '()': >> "lowerValue" : if >> (exists($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 >> + $mult]]/lowerValue[@value])) >> then >> data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 >> + $mult]]/lowerValue/[@value]) >> else (), >> "upperValue" : if >> (exists($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 >> + $mult]]/upperValue[@value])) >> then >> data($context//packagedElement[@xmi:id=$currID]/ownedAttribute[@xmi:id=$propList[2 >> + $mult]]/upperValue/[@value]) >> else () >> Total Time: 1526.0 >> In case #2: >> >
Written for BaseX 9.2. BaseX may have changed since: please check the current documentation.
⚡Generated with XQuery