Help with recursion
Friday, 20 December 2024 · 5 messages · last reply 27 Dec 2024
NR
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
CB
Chuck Bearden20 Dec 2024 17:57 #
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
NR
Nico Verwer (Rakensi)20 Dec 2024 20:12 #
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
CB
Chuck Bearden21 Dec 2024 02:36 #
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 > > > > >
CB
Chuck Bearden27 Dec 2024 19:27 #
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,
ChuckWritten for BaseX 11.6. BaseX may have changed since: please check the current documentation.
⚡Generated with XQuery