Opened 7 years ago
Closed 7 years ago
#17042 closed enhancement (fixed)
Improvement to subsets_with_hereditary_property
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  combinatorics  Keywords:  
Cc:  vinceknight, kcrisman, dimpase, jdemeyer, nthiery, vdelecroix, jhpalmieri  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  b6c4211 (Commits, GitHub, GitLab)  Commit:  b6c4211b1df9f99084eeab017de2cd34189a0dfd 
Dependencies:  #16994  Stopgaps: 
Description
I just noticed something useful I could use for my current problem, and it may also be useful to others. I hope it's not too "custom".
It can also be applied to Dima's example in the doc, as in his case the obstructions have size 3.
Nathann
Change History (29)
comment:1 Changed 7 years ago by
 Branch set to u/ncohen/17042
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
 Commit set to 381cfeff4c3661aa71d46514f231f6926d0b7d40
comment:3 followup: ↓ 4 Changed 7 years ago by
In the same vein, don't you want to have min_obstruction_size
, too? I.e. if you know that your function returns true on any set of size at most that, you shouldn't even call it.
comment:4 in reply to: ↑ 3 Changed 7 years ago by
Yo !
In the same vein, don't you want to have
min_obstruction_size
, too? I.e. if you know that your function returns true on any set of size at most that, you shouldn't even call it.
Well, it is true but in this case you can change the function itself to always return True on <min_size input. While if you do the same with the max_size, your function is not monotone anymore.
Well, it cannot hurt. Add a commit if you like.
Nathann
comment:5 followup: ↓ 6 Changed 7 years ago by
 Status changed from needs_review to needs_work
You haven't added max_obstruction_size
parameter to the SimplicialComplex
constructor.
(and as soon as it is there, you can speed up the long doctest I added)
comment:6 in reply to: ↑ 5 ; followup: ↓ 10 Changed 7 years ago by
You haven't added
max_obstruction_size
parameter to theSimplicialComplex
constructor.(and as soon as it is there, you can speed up the long doctest I added)
I did not intend to. You can also see I did not expose the 'ncpus' argument. Just thought I would keep the constructor simple... What do you think ?
Nathann
comment:7 Changed 7 years ago by
That's also why I put a link from the constructor to this function, so that interested users can find it.
Nathann
comment:8 Changed 7 years ago by
By the way
sage: %time l1=list(subsets_with_hereditary_property(lambda S:not any(Set(S).intersection(x).cardinality()>2 for x in l), range(21))) CPU times: user 7.98 s, sys: 36 ms, total: 8.02 s Wall time: 7.96 s sage: %time l2=list(subsets_with_hereditary_property(lambda S:not any(len(set(S).intersection(x))>2 for x in l), range(21))) CPU times: user 436 ms, sys: 60 ms, total: 496 ms Wall time: 426 ms sage: l1==l2 True
Set>set
. never use combinat code if you can avoid it.
Nathann
comment:9 Changed 7 years ago by
This being said the combinat code is better to observe the speedups :D
sage: %time l1=list(subsets_with_hereditary_property(lambda S:not any(Set(S).intersection(x).cardinality()>2 for x in l), range(21))) CPU times: user 7.97 s, sys: 72 ms, total: 8.04 s Wall time: 7.96 s sage: %time l2=list(subsets_with_hereditary_property(lambda S:not any(Set(S).intersection(x).cardinality()>2 for x in l), range(21),max_obstruction_size=3)) CPU times: user 2.46 s, sys: 44 ms, total: 2.51 s Wall time: 2.43 s sage: l1==l2 True
comment:10 in reply to: ↑ 6 ; followup: ↓ 11 Changed 7 years ago by
Replying to ncohen:
You haven't added
max_obstruction_size
parameter to theSimplicialComplex
constructor.(and as soon as it is there, you can speed up the long doctest I added)
I did not intend to. You can also see I did not expose the 'ncpus' argument. Just thought I would keep the constructor simple... What do you think ?
OK, then keep it as it is. But could you do the changes Set>set in that doctest?
comment:11 in reply to: ↑ 10 Changed 7 years ago by
OK, then keep it as it is. But could you do the changes Set>set in that doctest?
Of course !
Nathann
comment:12 Changed 7 years ago by
It still takes a LONG time afterwards, because SimplicialComplex removes nonmaximal faces _
sage: %time SimplicialComplex(from_characteristic_function=(f, range(21))) CPU times: user 6.2 s, sys: 184 ms, total: 6.38 s Wall time: 6.34 s Simplicial complex with 21 vertices and 168 facets
Nathann
comment:13 followup: ↓ 19 Changed 7 years ago by
Fixed
sage: l=map(Set, designs.ProjectiveGeometryDesign(2,1,GF(4,name='a'))) sage: f = lambda S: not any(len(set(S).intersection(x))>2 for x in l) sage: %time SimplicialComplex(from_characteristic_function=(f, range(21))) CPU times: user 584 ms, sys: 4 ms, total: 588 ms Wall time: 587 ms Simplicial complex with 21 vertices and 168 facets
It is like everybody has gave up thinking of algorithms.
Maybe I should change my job. I would be more useful to the world going over other people's loops.
Anyway, the constructor is now faster. It could be made faster, but at the cost of trying to understand why there is a sort_faces
flag in this constructor, and I am convinced that it would make me angry.
Just to illustrate the speedup:
Before
sage: S=list(Subsets(range(13))) sage: %time SimplicialComplex(S) CPU times: user 6.72 s, sys: 64 ms, total: 6.79 s Wall time: 6.72 s Simplicial complex with 13 vertices and facets {(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)}
After
sage: %time SimplicialComplex(S) CPU times: user 172 ms, sys: 12 ms, total: 184 ms Wall time: 172 ms Simplicial complex with 13 vertices and facets {(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)}
Nathann
comment:14 Changed 7 years ago by
 Commit changed from 381cfeff4c3661aa71d46514f231f6926d0b7d40 to 5dd79bbe16d339eb5269601b27c1ec7162983a5a
Branch pushed to git repo; I updated commit sha1. New commits:
5dd79bb  trac #17042: Bad code. Bad code everywhere.

comment:15 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:16 Changed 7 years ago by
just one more Set to go, in
sage: l=map(Set, designs.ProjectiveGeometryDesign(2,1,GF(4,name='a')))
comment:17 Changed 7 years ago by
What's the point ?.. It costs nothing.
Nathann
comment:18 Changed 7 years ago by
 Commit changed from 5dd79bbe16d339eb5269601b27c1ec7162983a5a to 528ec2fb916ea2bb3ef36ecb2c377fd27dd0ba54
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
528ec2f  trac #17042: Bad code. Bad code everywhere.

comment:19 in reply to: ↑ 13 ; followup: ↓ 20 Changed 7 years ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
Replying to ncohen:
Maybe I should change my job. I would be more useful to the world going over other people's loops.
you'd ran into the problem of what to do with about 10fold increase in income :)
comment:20 in reply to: ↑ 19 ; followup: ↓ 21 Changed 7 years ago by
you'd ran into the problem of what to do with about 10fold increase in income :)
Honestly, do you know who I could do such a job for ? I am getting tired of working alone in my office, day after day.
Nathann
comment:21 in reply to: ↑ 20 ; followup: ↓ 22 Changed 7 years ago by
Replying to ncohen:
you'd ran into the problem of what to do with about 10fold increase in income :)
Honestly, do you know who I could do such a job for ? I am getting tired of working alone in my office, day after day.
name your favourite Evil Empire... Oh, wait, you can also teach practical CS to undergrads  you'll see so much bad code it will make your head spin :)
At least you should go to Sage Days more often, I presume...
comment:22 in reply to: ↑ 21 ; followup: ↓ 23 Changed 7 years ago by
At least you should go to Sage Days more often, I presume...
I am paid to do research, not to take holidays.
I should take holidays, though. But the plane tickets are expensive too.
Nathann
comment:23 in reply to: ↑ 22 Changed 7 years ago by
Replying to ncohen:
At least you should go to Sage Days more often, I presume...
I am paid to do research, not to take holidays.
I guess you only went to "wrong" in this respect Sage Days... One in Seattle I went to was like working 12+ hours a day on Sage code...
comment:24 Changed 7 years ago by
Hmmm... Perhaps I should go next time..
Nathann
comment:25 followup: ↓ 27 Changed 7 years ago by
 Status changed from positive_review to needs_work
You shouldn't use assert
to validate user input:
assert (maximal_faces is None) or (from_characteristic_function is None)
as any assertion being raised is supposed to indicate a bug (plus they can be turned off). Instead raise an error
if maximal_faces is None and from_characteristic_function is None: raise ValueError("maximal_faces and from_characteristic_function cannot both be specified")
(with perhaps a better error message).
However I do like the speedup of SimplicialComplex
.
PS  This made me chuckle :p
:
I am convinced that it would make me angry.
comment:26 Changed 7 years ago by
 Commit changed from 528ec2fb916ea2bb3ef36ecb2c377fd27dd0ba54 to b6c4211b1df9f99084eeab017de2cd34189a0dfd
Branch pushed to git repo; I updated commit sha1. New commits:
b6c4211  trac #17042: New rules keep on appearing

comment:27 in reply to: ↑ 25 ; followup: ↓ 28 Changed 7 years ago by
You shouldn't use
assert
to validate user input:
Whyyyyyyyyyyyyyyyyyyyy had it been declared bad ?.... How can it hurt anybody ?...
We should have rules about rules.
However I do like the speedup of
SimplicialComplex
.
Yep, that's cool !
Branch updated.
Nathann
comment:28 in reply to: ↑ 27 Changed 7 years ago by
 Status changed from needs_work to positive_review
Replying to ncohen:
You shouldn't use
assert
to validate user input:Whyyyyyyyyyyyyyyyyyyyy had it been declared bad ?.... How can it hurt anybody ?...
We should have rules about rules.
Assert statements are to check statements within the code that are (suppose to be) always true, and hence, should not depend on (the always potentially bad) user input. Thus if an assertion error is raised, there's a bug in the code. It's more of a general programming thing. (It was also something Jeroen enforced when he was release manager; IDK if Volker continues this.) Also they can be turned off (IDR offhand if it's at compile or run time) to encourage programmers to use them (or leave them in code) more.
comment:29 Changed 7 years ago by
 Branch changed from u/ncohen/17042 to b6c4211b1df9f99084eeab017de2cd34189a0dfd
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #16994: Subsets with hereditary property
trac #16994: cleaner input for SimplicialComplex
trac #16994: Bugfix
adding a hard example
'exists > any', and some doc
trac #17042: Improvement to subsets_with_hereditary_property