_next_numId takes too long time when generate a big document

[MagicPwn]

in my usecase I have to generate a long document with many tables. during the process, I find that the time it takes to insert a table into a document is gradually increasing，I did a cprofile, it shows docx/oxml/numbering.py:121(_next_numId) timecost was increasing, and comes up to an unacceptable point。
after document instance added 2000 tables, next 100 table inserting will take 80 seconds, _next_numId takes 42 seconds.
_next_numId is coded as:

    @property
    def _next_numId(self):
        """
        The first ``numId`` unused by a ``<w:num>`` element, starting at
        1 and filling any gaps in numbering between existing ``<w:num>``
        elements.
        """
        numId_strs = self.xpath('./w:num/@w:numId')
        num_ids = [int(numId_str) for numId_str in numId_strs]
        for num in range(1, len(num_ids)+2):
            if num not in num_ids:
                break
        return num

when I change it to

    @property
    def _next_numId(self):
        numId_strs = self.xpath('./w:num/@w:numId')
        num_ids = [int(numId_str) for numId_str in numId_strs]
       return max(num_ids)+1

the timecost increasing was greatly relieved.
but I don't know filling any gaps in numbering between existing <w:num> elements. this logic is necessary elsewhere。
for my usecase, I need generate a document only.
if this change don't affect other place, I think I can submit a PR recently

[scanny]

How does numId come into adding tables? That id is only used for numbered lists, isn't it?

In any case, I believe the key question is whether this w:numId attribute is used strictly for identification (and therefore only need be unique) or whether it somehow implies a sequence. I expect it is the former and we originally just wanted to be conservative about exhausting the finite range of available ids.

After looking at the spec, it appears w:numId is type xsd:integer which is an integer value of arbitrary length. I expect your approach will work fine. I can't say when or if a PR that implements this would be committed, but you should feel free to monkey patch that method with your own for the purposes of your application.

[MagicPwn]

How does numId come into adding tables? That id is only used for numbered lists, isn't it?

This is because I put a list in a cell.

expect your approach will work fine. I can't say when or if a PR that implements this would be committed, but you should feel free to monkey patch that method with your own for the purposes of your application.

I got it，Thanks for your suggestion.

[Hugovdberg]

There is actually a more efficient way to find the first missing number if there is a need to fill the gaps:

    @property
    def _next_numId(self):
        numId_strs = self.xpath('./w:num/@w:numId')
        num_ids = {int(numId_str) for numId_str in numId_strs} # note we convert to a set as we know the ids are unique anyway
        missing_num_ids = set(range(1, max(num_ids)+1)).difference(num_ids)
        if missing_num_ids:
            return min(missing_num_ids)
        else:
            return max(num_ids)+1

This constructs the set of all possible values between 1 and the current maximum id and then removes the already used ids. By using the set difference the operation is quite fast even for a large number of values (see below). If there are missing values the first missing is returned, else the next one up from the max.

%%time
missing = 1000000
lst = list(range(1, missing*2))
lst.pop(missing)
missing_values = set(range(1, max(lst)+1)).difference(set(lst))
min(missing_values) if missing_values else max(lst)+1
Wall time: 355 ms
1000001