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 mailto:carter.n.john@gmail.com> 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 (>>10000) 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 1000000 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.

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))

...

...

timeit.timeit('s=set(b); [x for x in a if x not in s]', setup='a =

I benchmarked it and indeed the list difference is a little faster. list(range(10000)); b = list(range(1000))', number=1000) 0.6156670850032242

...

...

timeit.timeit('list(set(a)-set(b))', setup='a = list(range(10000)); 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.

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))

...

...

...

timeit.timeit('s=set(b); [x for x in a if x not in s]', setup='a =

...

...

...

timeit.timeit('list(set(a)-set(b))', setup='a =

I benchmarked it and indeed the list difference is a little faster. list(range(10000)); b = list(range(1000))', number=1000) 0.6156670850032242 list(range(10000)); 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-leave@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/WZFC3W... 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

There’s an itertools recipe, “partition”. On Mon, 6 Jun 2022 at 08:28, Chris Angelico wrote:

On Mon, 6 Jun 2022 at 16:42, Christopher Barker wrote:

...

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?

I'd call that a "partitioning" task, and you're right, it's not particularly easy in Python.

ChrisA _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-leave@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/NEY4JK... Code of Conduct: http://python.org/psf/codeofconduct/

from collections import deque def partition(pred, iterable): results = deque([]), deque([]) def gen_split(only): for thing in iterable: if results[only]: yield results[only].popleft() results[not pred(thing)].append(thing) for thing in results[only]: yield thing return gen_split(True), gen_split(False)

oops, you're right, I have ended up with an unnecessary "not" in there, should be: from collections import deque def partition(pred, iterable): results = deque([]), deque([]) def gen_split(only): for thing in iterable: if results[only]: yield results[only].popleft() results[pred(thing)].append(thing) for thing in results[only]: yield thing return gen_split(True), gen_split(False)

On Mon, Jun 06, 2022 at 06:17:32PM +0200, Benedict Verhegghe wrote:

There still is something wrong. I get the second list twice:

odd, even = partition(lambda i: i % 2, range(20)) print(list(odd)) [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] print(list(even)) [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

Confirmed. But if you replace range(20) with `iter(range(20))`, it works correctly. The plot thickens. The duplicated list is not from the second list created, but the second list *evaluated*. So if you run: odd, even = partition(...) as before, but evaluate *even* first and odd second: print(list(even)) print(list(odd)) it is odd that is doubled, not even. -- Steve

On Tue, 7 Jun 2022 at 10:26, Steven D'Aprano wrote:

Why don't you use the version from the itertools recipes?

``` from itertools import tee, filterfalse def partition(pred, iterable): "Use a predicate to partition entries into false entries and true entries" # partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9 t1, t2 = tee(iterable) return filterfalse(pred, t1), filter(pred, t2) ```

Calls the predicate twice for every element, so it's only good for a guaranteed-deterministic predicate. You may want to read the thread before responding. ChrisA

On Tue, 7 Jun 2022 at 19:09, Ben Rudiak-Gould wrote:

This calls the predicate once per element:

def partition(pred, iterable): t1, t2 = tee((pred(x), x) for x in iterable) return (x for b, x in t1 if not b), (x for b, x in t2 if b)

It's kind of inefficient though.

Honestly, if it weren't that there's currently a recipe in itertools, I think the list-based version would be the best recipe to offer. The cost of doing the job lazily AND maintaining all the other expectations is too high; if you really need it to be lazy, it's probably worth seeing if one of the other demands can be relaxed (eg if it's fine to call the predicate twice). For the OP's task, doing the partitioning eagerly wouldn't be an issue. ChrisA

On Tue, 7 Jun 2022 at 01:58, David Mertz, Ph.D. wrote:

In [2]: def isEven(n): ...: return n/2 == n//2 ...:

Huh. That's a very strange way to write that predicate.

...

...

isEven(20000000000000000) True isEven(20000000000000001) True isEven(20000000000000002) False isEven(20000000000000003) False isEven(20000000000000004) True

Why not just "return n % 2 == 0" ? ChrisA

As Chris Angelico notes, that's only good for finite iterables. The recipe in the itertools docs is unbounded, but it's also unbounded in the cache needed if you get long strings of things the do (or don't) confirm the predicate. On Mon, Jun 6, 2022 at 7:06 AM Stephen J. Turnbull < stephenjturnbull@gmail.com> wrote:

Christopher Barker writes:

...

How do you divide a sequence into two sequences cleanly?

I don't know how to do it in a one liner, but

yes = [] no = [] for elem in seq: (yes if test(elem) else no).append(elem)

seems pretty clean to me.

_______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-leave@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/BBVBDT... Code of Conduct: http://python.org/psf/codeofconduct/

-- 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.

06.06.22 10:51, Stephen J. Turnbull пише:

Couldn't it be linear on min(len(left), len(right))? Ie,

if len(left) < len(right): for elem in left: if elem in right: left.discard(elem) else: for elem in right: left.discard(elem)

The upper loop is probably only about half as fast as the lower (two hashes needed), so maybe the length test could be tuned.

The whole idea is probably not worth it, I can't think of practical use cases at a scale where it would matter.

It is close to the current implementation: if len(left) < len(right)//8: right = left & right for elem in left: if elem in right: left.discard(elem)

Thanks for all the comments. I did consider using sets but order was important and when partitioning a list of general strings, not file names, there could be identical and important strings (strings at different positions could mean different things, especially when generating test and training sets). I also tried doing it twice (generating lists) and it took approximately twice as long though generating two iterables could defer the partitioning till it was needed, i.e. lazy evaluation. I’ve added some of the solutions to by timing test. Identified by capital letters at the end. Reference list lengths 144004 855996 Number of tests cases 1000000 Example data ['xDy7AWbXau', 'TXlzsZV3Ra', 'YJh8uD9ovK', 'aRJ2U7nWs8', 'geu.vHlogu'] FNmatch 0.671875 268756 0 268756 0 WCmatch 1.562500 264939 0 264939 0 IWCmatch 1.281250 0 0 0 1 Easy 0.093750 144004 855996 1000000 1 Re 0.328125 855996 144004 1000000 0 Positive 0.281250 144004 0 144004 1 Negative 0.328125 0 855996 855996 1 UppeeCase 0.375000 268756 0 268756 0 Null 0.000000 0 0 0 1 Both 0.328125 144004 855996 1000000 1 Partition 1.171875 855996 144004 1000000 0 IBoth 0.328125 855996 144004 1000000 0 MRAB 0.437500 144004 855996 1000000 1 METZ 0.500000 144004 855996 1000000 1 CA 0.343750 144004 855996 1000000 1 SJB 0.328125 144004 855996 1000000 1 I checked for order and interestingly all the set solutions preserve it. I think this is because there are no duplicates in the test data. Order is only checked correctly if thee are the same number of elements in the test and reference lists I also tried more_itertoolls.partition. Nearly 4 times slower. John