Re: [xsl] Get the duplicates in a list

["Liam R. E. Quin liam@xxxxxxxxxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>]

On Fri, 2025-01-03 at 12:50 +0000, Martin Honnen martin.honnen@xxxxxx
wrote:
> B 
> I would hope that the map:merge is ensured to be more efficient than
> that count($fieldnames[. eq $f]) gt 1

First, Dmitrebs solution is great.

On complexity -

if a map is implemented as a hash table, insertion of a single item is
usually O(1) (which is why they are popular) although this disregards
collisions, growing the table, garbage collection, etc.

So inserting n items is O(n).

count($fieldnames) has to look at every item in $fieldnames so is O(n),
but an implementation of sequences as a finger list might store the
length at the start, in which case thatbs O(1) too, BUT
count($fieldnames[some expr]) likely has to evalauate the expression n
times, once per item, and then do a count, so is O(n).

I played with a solution that put the items inside elements and used
the preceding:: axis, but that meant for each item you looked at all
the preceding items, making it n x n, i.e. O(nB2)

Note: ordered maps are likely slower than O(n) for insertion and
deletion, but with the data structures that have been mentioned, likely
still O(n), but webll need a way to say where the insertion happens.

--
Liam Quin,B https://www.delightfulcomputing.com/
Available for XML/Document/Information Architecture/XSLT/
XSL/XQuery/Web/Text Processing/A11Y training, work & consulting.
Barefoot Web-slave, antique illustrations: B http://www.fromoldbooks.org