[Python-ideas] Addition to fnmatch.py
I’d like to propose a simple addition to the 'fnmatch' module. Specificity a function that returns a list of names that match a pattern AND a list of those that don't. In a recent project I found that I wished to split a list of files and move those that matched a pattern to one folder and those that didn't to another folder. I was using fnmatch.filter to select the first set of files and then a list comprehension to generate the second set. For a small number of files (~ 10) this was perfectly adequate. However as I needed to process many files (>>1) the execution time was very significant. Profiling the code showed that the time was spent in generating the second set. I tried a number of solutions including designing a negative filter, walking the file system to find those files that had not been moved and using more and more convoluted ways to improve the second selection. Eventually I gave in and hacked a local copy of fnmatch.py as below: def split(names, pat): """Return the subset of the list NAMES that match PAT.""" """Also returns those names not in NAMES""" result = [] notresult = [] pat = os.path.normcase(pat) pattern_match = _compile_pattern(pat) if os.path is posixpath: # normcase on posix is NOP. Optimize it away from the loop. for name in names: if not pattern_match(name): result.append(name) else: notresult.append(name) else: for name in names: if not pattern_match(os.path.normcase(name)): result.append(name) else: notresult.append(name) return result, notresult The change is the addition of else clauses to the if not pattermath statements. This solved the problem and benchmarking showed that it only took a very small additional time (20ms for a million strings) to generate both lists Number of tests cases 100 Example data ['Ba1txmKkiC', 'KlJx.f_AGj', 'Umwbw._Wa9', '4YlgA5LVpI’] Search for '*A*' TestTime(sec) PositiveNegative WCmatch.filter 1.953125 26211 0 filter 0.32812514259 0 split 0.34375014259 85741 List Comp. 270.468751 14259 85741 The list comprehension [x for x in a if x not in b]*, was nearly 900 times slower. ‘fnmatch’ was an appropriate solution to this problem as typing ‘glob’ style search patterns was easier than having to enter regular expressions when prompted by my code. I would like to propose that split, even though it is very simple, be included in the 'fnmatch' module. John *a is the original and b is those that match. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/EZEGFGJOHVHATKDBJ2SWZML62JWT2VE2/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Addition to fnmatch.py
This is exactly the problem solved by set difference. E.g. `{a, b, c} - {a,
c}`.
This operation is linear on the size of the removed set.
On Sun, Jun 5, 2022, 11:01 AM John Carter wrote:
> I’d like to propose a simple addition to the 'fnmatch' module. Specificity
> a function that returns a list of names that match a pattern AND a list of
> those that don't.
>
> In a recent project I found that I wished to split a list of files and
> move those that matched a pattern to one folder and those that didn't to
> another folder. I was using fnmatch.filter to select the first set of files
> and then a list comprehension to generate the second set.
>
> For a small number of files (~ 10) this was perfectly adequate. However as
> I needed to process many files (>>1) the execution time was very
> significant. Profiling the code showed that the time was spent in
> generating the second set. I tried a number of solutions including
> designing a negative filter, walking the file system to find those files
> that had not been moved and using more and more convoluted ways to improve
> the second selection. Eventually I gave in and hacked a local copy of
> fnmatch.py as below:
>
> def split(names, pat):
> """Return the subset of the list NAMES that match PAT."""
> """Also returns those names not in NAMES"""
> result = []
> notresult = []
> pat = os.path.normcase(pat)
> pattern_match = _compile_pattern(pat)
> if os.path is posixpath:
> # normcase on posix is NOP. Optimize it away from the loop.
> for name in names:
> if not pattern_match(name):
> result.append(name)
> else:
> notresult.append(name)
> else:
> for name in names:
> if not pattern_match(os.path.normcase(name)):
> result.append(name)
> else:
> notresult.append(name)
> return result, notresult
>
> The change is the addition of else clauses to the if not pattermath
> statements. This solved the problem and benchmarking showed that it only
> took a very small additional time (20ms for a million strings) to generate
> both lists
>
> Number of tests cases 100
> Example data ['Ba1txmKkiC', 'KlJx.f_AGj', 'Umwbw._Wa9', '4YlgA5LVpI’]
> Search for '*A*'
> TestTime(sec) PositiveNegative
> WCmatch.filter 1.953125 26211 0
> filter 0.32812514259 0
> split 0.34375014259 85741
> List Comp. 270.468751 14259 85741
>
> The list comprehension [x for x in a if x not in b]*, was nearly 900 times
> slower.
>
> ‘fnmatch’ was an appropriate solution to this problem as typing ‘glob’
> style search patterns was easier than having to enter regular expressions
> when prompted by my code.
>
> I would like to propose that split, even though it is very simple, be
> included in the 'fnmatch' module.
>
> John
>
> *a is the original and b is those that match.
> ___
> Python-ideas mailing list -- python-ideas@python.org
> To unsubscribe send an email to python-ideas-le...@python.org
> https://mail.python.org/mailman3/lists/python-ideas.python.org/
> Message archived at
> https://mail.python.org/archives/list/python-ideas@python.org/message/EZEGFGJOHVHATKDBJ2SWZML62JWT2VE2/
> Code of Conduct: http://python.org/psf/codeofconduct/
>
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/72KFWQJHIFUJJRH32WIGEZ64BRN7UK6E/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Addition to fnmatch.py
Le 05/06/2022 à 16:52, John Carter a écrit :
I’d like to propose a simple addition to the 'fnmatch' module. Specificity a
function that returns a list of names that match a pattern AND a list of those
that don't.
In a recent project I found that I wished to split a list of files and move
those that matched a pattern to one folder and those that didn't to another
folder. I was using fnmatch.filter to select the first set of files and then a
list comprehension to generate the second set.
For a small number of files (~ 10) this was perfectly adequate. However as I needed
to process many files (>>1) the execution time was very significant.
Profiling the code showed that the time was spent in generating the second set. I
tried a number of solutions including designing a negative filter, walking the file
system to find those files that had not been moved and using more and more convoluted
ways to improve the second selection. Eventually I gave in and hacked a local copy of
fnmatch.py as below:
def split(names, pat):
"""Return the subset of the list NAMES that match PAT."""
"""Also returns those names not in NAMES"""
result = []
notresult = []
pat = os.path.normcase(pat)
pattern_match = _compile_pattern(pat)
if os.path is posixpath:
# normcase on posix is NOP. Optimize it away from the loop.
for name in names:
if not pattern_match(name):
result.append(name)
else:
notresult.append(name)
else:
for name in names:
if not pattern_match(os.path.normcase(name)):
result.append(name)
else:
notresult.append(name)
return result, notresult
The change is the addition of else clauses to the if not pattermath statements.
This solved the problem and benchmarking showed that it only took a very small
additional time (20ms for a million strings) to generate both lists
Number of tests cases 100
Example data ['Ba1txmKkiC', 'KlJx.f_AGj', 'Umwbw._Wa9', '4YlgA5LVpI’]
Search for '*A*'
TestTime(sec) PositiveNegative
WCmatch.filter 1.953125 26211 0
filter 0.32812514259 0
split 0.34375014259 85741
List Comp. 270.468751 14259 85741
The list comprehension [x for x in a if x not in b]*, was nearly 900 times
slower.
‘fnmatch’ was an appropriate solution to this problem as typing ‘glob’ style
search patterns was easier than having to enter regular expressions when
prompted by my code.
I would like to propose that split, even though it is very simple, be included
in the 'fnmatch' module.
John
*a is the original and b is those that match.
Searching an element in a list scans the elements
one by one, so [x for x in a if x not in b]
has quadratic complexity. Try list(set(a) - set(b))
instead.
>>> import timeit
>>> timeit.timeit('[x for x in a if x not in b]', setup='a =
list(range(10_000)); b = list(range(1000))', number=100)
5.258457429998089
>>>
>>> timeit.timeit('list(set(a)-set(b))', setup='a =
list(range(10_000)); b = list(range(1000))', number=100)
0.07163406799372751
Jean
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/VPWSYBDEW7HZBLU3JBDPFPO6KI3VM4LC/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Addition to fnmatch.py
On 2022-06-05 16:12, David Mertz, Ph.D. wrote:
This is exactly the problem solved by set difference. E.g. `{a, b, c} -
{a, c}`.
This operation is linear on the size of the removed set.
You don't have to use a set difference, which might matter if the order
was important, but just make a set of the ones found:
s = set(b)
And then the list comprehension:
[x for x in a if x not in s]
On Sun, Jun 5, 2022, 11:01 AM John Carter > wrote:
I’d like to propose a simple addition to the 'fnmatch' module.
Specificity a function that returns a list of names that match a
pattern AND a list of those that don't.
In a recent project I found that I wished to split a list of files
and move those that matched a pattern to one folder and those that
didn't to another folder. I was using fnmatch.filter to select the
first set of files and then a list comprehension to generate the
second set.
For a small number of files (~ 10) this was perfectly adequate.
However as I needed to process many files (>>1) the execution
time was very significant. Profiling the code showed that the time
was spent in generating the second set. I tried a number of
solutions including designing a negative filter, walking the file
system to find those files that had not been moved and using more
and more convoluted ways to improve the second selection. Eventually
I gave in and hacked a local copy of fnmatch.py as below:
def split(names, pat):
"""Return the subset of the list NAMES that match PAT."""
"""Also returns those names not in NAMES"""
result = []
notresult = []
pat = os.path.normcase(pat)
pattern_match = _compile_pattern(pat)
if os.path is posixpath:
# normcase on posix is NOP. Optimize it away from the loop.
for name in names:
if not pattern_match(name):
result.append(name)
else:
notresult.append(name)
else:
for name in names:
if not pattern_match(os.path.normcase(name)):
result.append(name)
else:
notresult.append(name)
return result, notresult
The change is the addition of else clauses to the if not pattermath
statements. This solved the problem and benchmarking showed that it
only took a very small additional time (20ms for a million strings)
to generate both lists
Number of tests cases 100
Example data ['Ba1txmKkiC', 'KlJx.f_AGj', 'Umwbw._Wa9', '4YlgA5LVpI’]
Search for '*A*'
Test Time(sec) Positive Negative
WCmatch.filter 1.953125 26211 0
filter 0.328125 14259 0
split 0.343750 14259 85741
List Comp. 270.468751 14259 85741
The list comprehension [x for x in a if x not in b]*, was nearly 900
times slower.
‘fnmatch’ was an appropriate solution to this problem as typing
‘glob’ style search patterns was easier than having to enter regular
expressions when prompted by my code.
I would like to propose that split, even though it is very simple,
be included in the 'fnmatch' module.
John
*a is the original and b is those that match.
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/FRQJT7AWCVQXYJPC4IDWA3LZGVLX765A/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Addition to fnmatch.py
On Sun, Jun 5, 2022, 12:08 PM MRAB wrote:
> On 2022-06-05 16:12, David Mertz, Ph.D. wrote:
> > This is exactly the problem solved by set difference. E.g. `{a, b, c}
> - {a, c}`.
> >
> > This operation is linear on the size of the removed set.
> >
> You don't have to use a set difference, which might matter if the order
> was important, but just make a set of the ones found:
>
> s = set(b)
>
> And then the list comprehension:
>
> [x for x in a if x not in s]
>
Sure, that's nice enough code and has the same big-O complexity. I suspect
set difference is a little faster (by a constant multiple) because it hits
C code more, but I haven't benchmarked.
The OP said the elements were from fnmatch though, which explicitly does
not promise order. So really it's just whether you like your code or this
better aesthetically:
list(set(b) - set(a))
Personally I like my (somewhat shorter) version as more clear. But YMMV.
>
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/FD3JEDTKB4COFBRSLGIT53Y2GFW6MTZF/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Addition to fnmatch.py
Op 5/06/2022 om 18:47 schreef David Mertz, Ph.D.:
Sure, that's nice enough code and has the same big-O complexity. I
suspect set difference is a little faster (by a constant multiple)
because it hits C code more, but I haven't benchmarked.
The OP said the elements were from fnmatch though, which explicitly does
not promise order. So really it's just whether you like your code or
this better aesthetically:
list(set(b) - set(a))
I benchmarked it and indeed the list difference is a little faster.
>>> timeit.timeit('s=set(b); [x for x in a if x not in s]', setup='a =
list(range(1)); b = list(range(1000))', number=1000)
0.6156670850032242
>>> timeit.timeit('list(set(a)-set(b))', setup='a = list(range(1));
b = list(range(1000))', number=1000)
0.43649216600169893
And what's more, it seems to also preserve order. I guess because a set
is implemented like a dict, and will preserve order of you only remove
some elements from the set.
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/YBEQ6TZ6CQDGRLZ6HFIV4HJ7LCFUW4UA/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Addition to fnmatch.py
On 6/5/2022 1:22 PM, Benedict Verhegghe wrote:
Op 5/06/2022 om 18:47 schreef David Mertz, Ph.D.:
Sure, that's nice enough code and has the same big-O complexity. I
suspect set difference is a little faster (by a constant multiple)
because it hits C code more, but I haven't benchmarked.
The OP said the elements were from fnmatch though, which explicitly
does not promise order. So really it's just whether you like your
code or this better aesthetically:
list(set(b) - set(a))
I benchmarked it and indeed the list difference is a little faster.
>>> timeit.timeit('s=set(b); [x for x in a if x not in s]', setup='a =
list(range(1)); b = list(range(1000))', number=1000)
0.6156670850032242
>>> timeit.timeit('list(set(a)-set(b))', setup='a =
list(range(1)); b = list(range(1000))', number=1000)
0.43649216600169893
And what's more, it seems to also preserve order. I guess because a
set is implemented like a dict, and will preserve order of you only
remove some elements from the set.
A set doesn't guarantee order at all, and indeed it does not preserve
creation order:
>>> s = set([10, 20, 1])
>>> s
{1, 10, 20}
You're seeing an accidental byproduct of the implementation.
Eric
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/WZFC3WAOMTQ2UQIMGBJ2VTBBOE5XUWBR/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Add .except() and .only(), and .values_at(). instance methods to dict
I think these are an extremely common needs that are worth having standard
methods for. If adding instance methods seems like a bad idea, then maybe add
functions to the standard library that perform the same operations.
m = {'a': 123, 'b': 456, 'c': 789}
m.except(('a', 'c')) # {'b': 456}
m.only(('b', 'c')) # {'b': 456, 'c': 789}
m.values_at(('a', 'b')) # [123, 456]
…or…
from mappings import except, only, values_at
m = {'a': 123, 'b': 456, 'c': 789}
except(m, ('a', 'c')) # {'b': 456}
only(m, ('b', 'c')) # {'b': 456, 'c': 789}
values_at(m, ('a', 'b')) # [123, 456]
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/SMHI3ABM4XLASYYDGSTY45BKHTM7QMK2/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add .except() and .only(), and .values_at(). instance methods to dict
These are all far too easy to do with comprehensions to merit new methods
or stdlib functions.
m = {'a': 123, 'b': 456, 'c': 789}
>
m.except(('a', 'c')) # {'b': 456}
> m.only(('b', 'c')) # {'b': 456, 'c': 789}
> m.values_at(('a', 'b')) # [123, 456]
>
{k:m[v] for k in m if k not in ['a','c']}
{k:m[v] for k in m if k in ('b','c')}.
[m[k] for k in m if k in {'a', 'b'}]
The existing versions are a few characters longer, but far more general
when you want minor variations. Moreover, I have very rarely wanted to do
ANY of the things described by these hypothetical methods.
That said, I think maybe something extending PEP 584 could be reasonable,
but I'm not quite sure of the semantics.
E.g., we might provide additional set-like operators for dicts.
>>> m | {'a':"Newval"} # We have this now
{'a': 'Newval', 'b': 456, 'c': 789}
>>> m - {'a'} # Would rightval be a set or dict though?!
{'b': 456, 'c': 789}
>>> m & {'a', 'b'} # Same question, but set feels better, I think
{'a': 'Newval', 'b': 456}
--
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons. Intellectual property is
to the 21st century what the slave trade was to the 16th.
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/B23J2ABBFOOXQYHYSVHX7ILJZRRE2IKH/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Add .except() and .only(), and .values_at(). instance methods to dict
On Sun, Jun 05, 2022 at 09:11:41PM -, Steve Jorgensen wrote:
> m = {'a': 123, 'b': 456, 'c': 789}
> m.except(('a', 'c')) # {'b': 456}
> m.only(('b', 'c')) # {'b': 456, 'c': 789}
> m.values_at(('a', 'b')) # [123, 456]
Maybe I'm a bit slow because I haven't had my morning coffee yet, but I
had to read those three times before I could work out what they actually
do. Also because I got thrown by the use of the keyword `except`, and
thought initially that this was related to try...except.
And lastly because you say that these are extremely common, but I've
never used these operations in 20+ years. Or at least not often enough
to remember using them, or wishing that they were standard methods.
These operations are so simple that it is easier to follow the code than
to work out the meaning of the method from the name:
# Return a new dict from an old dict with all but a set of keys.
new = {key:value for key, value in old.items() if key not in exclusions}
# Return a new dict from an old dict with only the included keys.
new = {key:value for key, value in old.items() if key in inclusions}
# Same as above, but only those matching the included values.
new = {key:value for key, value in old.items() if value in inclusions}
# Return the values (as a set) of a subset of keys.
values = {value for key, value in old.items() if key in inclusions}
# Use a list instead, and exclude keys.
values = [value for key, value in old.items() if key not in exclusions]
# Same, but use a predicate function.
values = [value for key, value in old.items() if not predicate(key)]
# How about a list of values matching *either* a blacklist of keys
# and a whitelist of values, *or* a predicate function on both?
values = [value for key, value in old.items()
if (key not in blacklist and value in whitelist)
or predicate(key, value)]
Comprehensions are great!
Yes, they take a few extra characters to write, but code is written much
more than it is read. Once we have learned comprehensions, it is much
easier to read a simple comprehension than to try to decipher a short
name like "only". Only what? Only those that match a given list of keys,
or values, or a predicate function, or something else?
--
Steve
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/766W3IAURXW3FRTJNH2657XHIXYL7LHY/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Addition to fnmatch.py
I think y’all have addressed the OP’s problem — at least the performance
issues.
But I think this brings up a pattern that I don’t have a nifty way to
address:
How do you divide a sequence into two sequences cleanly?
The filter pattern: selectively remove items from a sequence, returning a
new sequence. There are a few ways to do that in Python.
But what if you need both the remaining items and the removed ones? Easy
enough to write a loop that populates two lists, but is there a nifty
one-liner?
Is this a known functional pattern?
-CHB
On Sun, Jun 5, 2022 at 7:39 PM Eric V. Smith via Python-ideas <
python-ideas@python.org> wrote:
>
> On 6/5/2022 1:22 PM, Benedict Verhegghe wrote:
> > Op 5/06/2022 om 18:47 schreef David Mertz, Ph.D.:
> >> Sure, that's nice enough code and has the same big-O complexity. I
> >> suspect set difference is a little faster (by a constant multiple)
> >> because it hits C code more, but I haven't benchmarked.
> >>
> >> The OP said the elements were from fnmatch though, which explicitly
> >> does not promise order. So really it's just whether you like your
> >> code or this better aesthetically:
> >>
> >> list(set(b) - set(a))
> >>
> > I benchmarked it and indeed the list difference is a little faster.
> > >>> timeit.timeit('s=set(b); [x for x in a if x not in s]', setup='a =
> > list(range(1)); b = list(range(1000))', number=1000)
> > 0.6156670850032242
> > >>> timeit.timeit('list(set(a)-set(b))', setup='a =
> > list(range(1)); b = list(range(1000))', number=1000)
> > 0.43649216600169893
> >
> > And what's more, it seems to also preserve order. I guess because a
> > set is implemented like a dict, and will preserve order of you only
> > remove some elements from the set.
> >
> A set doesn't guarantee order at all, and indeed it does not preserve
> creation order:
>
> >>> s = set([10, 20, 1])
> >>> s
> {1, 10, 20}
>
> You're seeing an accidental byproduct of the implementation.
>
> Eric
>
> ___
> Python-ideas mailing list -- python-ideas@python.org
> To unsubscribe send an email to python-ideas-le...@python.org
> https://mail.python.org/mailman3/lists/python-ideas.python.org/
> Message archived at
> https://mail.python.org/archives/list/python-ideas@python.org/message/WZFC3WAOMTQ2UQIMGBJ2VTBBOE5XUWBR/
> Code of Conduct: http://python.org/psf/codeofconduct/
>
--
Christopher Barker, PhD (Chris)
Python Language Consulting
- Teaching
- Scientific Software Development
- Desktop GUI and Web Development
- wxPython, numpy, scipy, Cython
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/P2OTU27MUOV2SY2TUVFCQ47R4KBCMPFF/
Code of Conduct: http://python.org/psf/codeofconduct/
