Hi Bruno,
Bruno Haible <br...@clisp.org> writes:
> The variable mentioned_files in pygnulib/GLModuleSystem.py line 599
> was a set and is now a list. Is the expression
> lib_files.difference(mentioned_files)
> therefore being evaluated more slowly (as O(n²) where it was O(n) before)?
> That is, does Python iterate through mentioned_files for each element of
> lib_files, or does Python convert the argument mentioned_files internally
> to a set first?
Oops yes. Good point, I must have overlooked that. It appears that it
will be O(n²). In this loop [1] and the else branch of
"PyAnySet_Check(other)" [2].
The lists there seem small enough that I doubt it matters too much.
Perhaps a patch like this is a better fix then just wrapping the call in
set() there:
diff --git a/pygnulib/GLModuleSystem.py b/pygnulib/GLModuleSystem.py
index 5d67c5b6df..b91406f564 100644
--- a/pygnulib/GLModuleSystem.py
+++ b/pygnulib/GLModuleSystem.py
@@ -45,14 +45,14 @@
_LIB_SOURCES_PATTERN = re.compile(r'^lib_SOURCES[\t ]*\+=[\t ]*(.+?)[\t
]*(?:#|$)', re.MULTILINE)
-def _extract_lib_SOURCES(snippet: str) -> list[str]:
+def _extract_lib_SOURCES(snippet: str) -> set[str]:
'''Return the file names specified in the lib_SOURCES variable of
a Makefile.am snippet.'''
lines = [ line.group(1)
for line in re.finditer(_LIB_SOURCES_PATTERN, snippet) ]
- return [ file_name
+ return { file_name
for line in lines
- for file_name in line.split() ]
+ for file_name in line.split() }
I want to move some other file list stuff to use sets
(GLModuleSystem.filelist particularly) since membership checks are
performed on them and there is many unnecessary sorted() calls that can
be cleaned up.
Sets would work better for GLModule objects too but sorting matters for
them because 'dummy' is always placed last. Sort of strange behavior
that is necessary to match gnulib-tool.sh output in Makefile.am. :)
Collin
[1]
https://github.com/python/cpython/blob/059be67b51717519609b29c53bf742ca4d91b68f/Objects/setobject.c#L1576
[2]
https://github.com/python/cpython/blob/059be67b51717519609b29c53bf742ca4d91b68f/Objects/setobject.c#L1430
