Help with recursion
Hello Chuck,
Maybe I will have time to look at your code later, but the first thing that came to mind was to use group by:
map:merge(
for $pmidset at $i in $pmids
group by $chunk as xs:integer := ($i idiv 100)
return map:entry($chunk, $pmidset)
)This should give you the map you expect.
Best regards, Nico Verwer
I'm trying to ingest a sequence of 6293 strings, each 8 characters long, and create a map in which each key is an integer from 1 to 63, and each value is a subsequence of the 6293 strings, from ($key+1) * 100) to that starting value + 99.
I wrote a function to do this recursively (so I thought), but it runs and runs (I've given it over 5 minutes), and so I can see I borked something. I wrote a function to output the starting and ending sequence indices for each execution of the function, but it (as the only change to the first function) quickly causes a stack overflow:
*Error:* Stack Overflow: Try tail recursion?
Since the recursive call was the last expression in the function, I thought I was doing tail recursion.
I'm running 11.6.0. The code with explanatory comments follows. I'd be grateful for any corrections and insights.
declare function local:write_results($elems as element()*,
$count as xs:integer) {
let $dir_path := '/home/cfbearden/projects/mesh_for_pure/20241220/data/'
let $count_as_str := xs:string($count)
let $content_out := <PubmedArticleSet>{$elems}</PubmedArticleSet>
let $path := $dir_path || 'pmed2022_' || $count_as_str || '.xml'
let $params := {
'method' : 'xml',
'indent' : 'yes'
}
return file:write($path, $elems, $params)
};
declare function local:by_hundreds($pmids as xs:string*,
$pmid_map as map(*)) as map(*) {
let $key_count := count(map:keys($pmid_map))
return
(: base case: each value except the last should have 100 items
in it; the last should have <= 100; in this case we return
the map
goal is to build a map with 63 keys, with each value
a sequence of 100 or 93 (in the last case) strings :)
if ((($key_count + 1) * 100) >= count($pmids))
then $pmid_map
else
(: starting index for subsequence() :)
let $start := 1 + ($key_count * 100)
(: ending index for subsequence() :)
let $end := $start + 99
(: value of the map key for this 100 items :)
let $key := $key_count + 1
(: attempt to log all recurrent executions to files
let $foo :=
local:write_results(<res><start>{$start}</start><end>{$end}</end></res>,
$key_count)
:)
(: create a map with $key as key and the subsequence from n to n + 99
of $pmids and merge it with input accumulator map to make a new
map :)
let $pmid_map_new := map:merge($pmid_map, map {
$key : subsequence($pmids, $start, $end)
})
(: recur; the number of keys in $pmid_map_new will enable the next
execution to determine which items from $pmids to use :)
return local:by_hundreds($pmids, $pmid_map_new)
};
(:
The data format is simple:
<DATA_RECORDS>
<DATA_RECORD>
<pub_uuid>0008980a-f1f3-40bf-8c13-cb0b79dfa81e</pub_uuid>
<pmid>35732127</pmid>
</DATA_RECORD>
...
</DATA_RECORDS>
:)
let $pure_2022_db := collection('pure_2022')
(: yields a sequence of 6293 strings, all 8 characters long :)
let $pmids := (
for $drec in $pure_2022_db/DATA_RECORDS/DATA_RECORD
let $pmid := $drec/pmid/text()
return $pmid
)
let $result := local:by_hundreds($pmids, {})
return $resultAll the best, Chuck Bearden
Hello Chuck,
The reason why you have infinite recursion is, that the signature of map:merge is
map:merge($maps as map(*)*, $options as map(*)) as map(*)The first parameter is a sequence of maps, and the second parameter is a map with options. This means that in your code
map:merge($pmid_map, map {
$key : subsequence($pmids, $start, $end)
})the map containing the subsequence is interpreted as a (meaningless) map with options, and you only keep the empty map that you started with. To fix this, insert parentheses like so:
map:merge(
( $pmid_map
, map {$key : subsequence($pmids, $start, $end)}
)
)The $options parameter is optional, so I omitted it. However, there are more mistakes, which I will go into below. And a better approach is to use the /for - group by - return/ that I posted earlier. This is a lot faster, more concise, and more readable in my opinion. My comments below are only meant to highlight some learning points.
Quoted text · Chuck Bearden · 4 lines
> declare function local:by_hundreds($pmids as xs:string*, $pmid_map as > map(*)) > as map(*) { > let $key_count := count(map:keys($pmid_map))
Better is map:size($pmid_map)
Quoted text · Chuck Bearden · 7 lines
> return > (: base case: each value except the last should have 100 items > in it; the last should have <= 100; in this case we return the map > goal is to build a map with 63 keys, with each value > a sequence of 100 or 93 (in the last case) strings :) > if ((($key_count + 1) * 100) >= count($pmids)) > then $pmid_map
This means that you will miss the last 93 strings, because /$key_count *
100/ will be less then /count($pmids)/, so there are strings left.Quoted text · Chuck Bearden · 7 lines
> else > (: starting index for subsequence() :) > let $start := 1 + ($key_count * 100) > (: ending index for subsequence() :) > let $end := $start + 99 > (: value of the map key for this 100 items :) > let $key := $key_count + 1
If you pass a subsequence of $pmids as the first parameter, instead of passing the whole list every time, there is less computation to do, and the base case becomes easier to detect.
Quoted text · Chuck Bearden · 12 lines
> (: attempt to log all recurrent executions to files > let $foo := > local:write_results(<res><start>{$start}</start><end>{$end}</end></res>, > $key_count) > :) > (: create a map with $key as key and the subsequence from n to n > + 99 > of $pmids and merge it with input accumulator map to make a > new map :) > let $pmid_map_new := map:merge($pmid_map, map { > $key : subsequence($pmids, $start, $end) > })
Since there is only one key in this map, it is better to use /map:entry($key, subsequence($pmids, $start, $end))/.
Quoted text · Chuck Bearden · 4 lines
> (: recur; the number of keys in $pmid_map_new will enable the next > execution to determine which items from $pmids to use :) > return local:by_hundreds($pmids, $pmid_map_new) > };
The recursive pattern you use can be written more efficiently as a fold-left. See the excellent XQuery book by Priscilla Walmsley for examples.
But as I said, the conventional way to do this in XQuery would be
map:merge(
for $pmidset at $i in $pmids
group by $chunk as xs:integer := ($i idiv 100)
return map:entry($chunk, $pmidset)
)Happy XQuerying!
Best regards, Nico Verwer
Thank you Nico for taking the time to analyze and comment on my code. I will study your answer, but not this evening :-) Much appreciated!
All the best, Chuck
Quoted text · Nico Verwer (Rakensi) · 106 lines
On Fri, Dec 20, 2024 at 1:12 PM Nico Verwer (Rakensi) <nverwer at rakensi.com> wrote: > Hello Chuck, > > The reason why you have infinite recursion is, that the signature of > `map:merge` is > > map:merge($maps as map(*)*, $options as map(*)) as map(*) > > The first parameter is a sequence of maps, and the second parameter is a > map with options. > This means that in your code > > map:merge($pmid_map, map { > $key : subsequence($pmids, $start, $end) > }) > > the map containing the subsequence is interpreted as a (meaningless) map > with options, and you only keep the empty map that you started with. > To fix this, insert parentheses like so: > > map:merge( > ( $pmid_map > , map {$key : subsequence($pmids, $start, $end)} > ) > ) > > The $options parameter is optional, so I omitted it. > However, there are more mistakes, which I will go into below. And a better > approach is to use the *for - group by - return* that I posted earlier. > This is a lot faster, more concise, and more readable in my opinion. > My comments below are only meant to highlight some learning points. > > declare function local:by_hundreds($pmids as xs:string*, $pmid_map as > map(*)) > > as map(*) { > let $key_count := count(map:keys($pmid_map)) > > Better is map:size($pmid_map) > > return > (: base case: each value except the last should have 100 items > in it; the last should have <= 100; in this case we return the map > goal is to build a map with 63 keys, with each value > a sequence of 100 or 93 (in the last case) strings :) > if ((($key_count + 1) * 100) >= count($pmids)) > then $pmid_map > > This means that you will miss the last 93 strings, because *$key_count * > 100* will be less then *count($pmids)*, so there are strings left. > > else > (: starting index for subsequence() :) > let $start := 1 + ($key_count * 100) > (: ending index for subsequence() :) > let $end := $start + 99 > (: value of the map key for this 100 items :) > let $key := $key_count + 1 > > If you pass a subsequence of $pmids as the first parameter, instead of > passing the whole list every time, there is less computation to do, and the > base case becomes easier to detect. > > (: attempt to log all recurrent executions to files > let $foo := > local:write_results(<res><start>{$start}</start><end>{$end}</end></res>, > $key_count) > :) > (: create a map with $key as key and the subsequence from n to n + 99 > of $pmids and merge it with input accumulator map to make a new > map :) > let $pmid_map_new := map:merge($pmid_map, map { > $key : subsequence($pmids, $start, $end) > }) > > Since there is only one key in this map, it is better to use *map:entry($key, > subsequence($pmids, $start, $end))*. > > (: recur; the number of keys in $pmid_map_new will enable the next > execution to determine which items from $pmids to use :) > return local:by_hundreds($pmids, $pmid_map_new) > }; > > > The recursive pattern you use can be written more efficiently as a > fold-left. See the excellent XQuery book by Priscilla Walmsley for examples. > > But as I said, the conventional way to do this in XQuery would be > > map:merge( > for $pmidset at $i in $pmids > group by $chunk as xs:integer := ($i idiv 100) > return map:entry($chunk, $pmidset) > ) > > > Happy XQuerying! > > Best regards, > Nico Verwer > > > > >
Hi Nico,
Thank you again for your detailed responses. I'm just getting back into the office. I do appreciate your taking the time to analyze my code.
Your for loop to replace my recursive apparatus taught me two things: I was previously unfamiliar with the at clause in the for loop, and I didn't know the idiv operator before. Thank you!
Regarding the signature for map:merge(): Ouch! I have used that function many times. I should have known better.
Thank you also for the advice on using the for loop instead of the recursive approach.
Regarding
return (: base case: each value except the last should have 100 items in it; the last should have <= 100; in this case we return the map goal is to build a map with 63 keys, with each value a sequence of 100 or 93 (in the last case) strings :) if ((($key_count + 1) * 100) >= count($pmids)) then $pmid_map
I thought because I was multiplying $key_count + 1, rather than $key_count, by 100, the condition would be true after the last 93 elements of the sequence. I thought there would be 63 key/value pairs after the final 93 are added, so the base case would be triggered by
(63 + 1) * 100 >= 6293
Perhaps I'm off by one. Though I've abandoned the recursive function altogether in favor of your for loop.
Again thanks, Chuck
Written for BaseX 11.6. BaseX may have changed since: please check the current documentation.