Opened 5 years ago

Closed 5 years ago

#17042 closed enhancement (fixed)

Improvement to subsets_with_hereditary_property

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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) 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 5 years ago by ncohen

  • Branch set to u/ncohen/17042
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 381cfeff4c3661aa71d46514f231f6926d0b7d40

Branch pushed to git repo; I updated commit sha1. New commits:

8fd05ectrac #16994: Subsets with hereditary property
0f49108trac #16994: cleaner input for SimplicialComplex
6f9ca0dtrac #16994: Bugfix
2308e55adding a hard example
ee38a01'exists -> any', and some doc
381cfeftrac #17042: Improvement to subsets_with_hereditary_property

comment:3 follow-up: Changed 5 years ago by dimpase

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 5 years ago by ncohen

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 follow-up: Changed 5 years ago by dimpase

  • 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 ; follow-up: Changed 5 years ago by ncohen

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)

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 5 years ago by ncohen

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 5 years ago by ncohen

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 5 years ago by ncohen

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 ; follow-up: Changed 5 years ago by dimpase

Replying to ncohen:

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)

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 5 years ago by ncohen

OK, then keep it as it is. But could you do the changes Set->set in that doctest?

Of course !

Nathann

comment:12 Changed 5 years ago by ncohen

It still takes a LONG time afterwards, because SimplicialComplex removes non-maximal 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 follow-up: Changed 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from 381cfeff4c3661aa71d46514f231f6926d0b7d40 to 5dd79bbe16d339eb5269601b27c1ec7162983a5a

Branch pushed to git repo; I updated commit sha1. New commits:

5dd79bbtrac #17042: Bad code. Bad code everywhere.

comment:15 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:16 Changed 5 years ago by dimpase

just one more Set to go, in

sage: l=map(Set, designs.ProjectiveGeometryDesign(2,1,GF(4,name='a')))

comment:17 Changed 5 years ago by ncohen

What's the point ?.. It costs nothing.

Nathann

comment:18 Changed 5 years ago by git

  • Commit changed from 5dd79bbe16d339eb5269601b27c1ec7162983a5a to 528ec2fb916ea2bb3ef36ecb2c377fd27dd0ba54

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

528ec2ftrac #17042: Bad code. Bad code everywhere.

comment:19 in reply to: ↑ 13 ; follow-up: Changed 5 years ago by dimpase

  • 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 10-fold increase in income :-)

comment:20 in reply to: ↑ 19 ; follow-up: Changed 5 years ago by ncohen

you'd ran into the problem of what to do with about 10-fold 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 ; follow-up: Changed 5 years ago by dimpase

Replying to ncohen:

you'd ran into the problem of what to do with about 10-fold 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 ; follow-up: Changed 5 years ago by ncohen

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 5 years ago by dimpase

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 5 years ago by ncohen

Hmmm... Perhaps I should go next time..

Nathann

comment:25 follow-up: Changed 5 years ago by tscrim

  • 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 5 years ago by git

  • Commit changed from 528ec2fb916ea2bb3ef36ecb2c377fd27dd0ba54 to b6c4211b1df9f99084eeab017de2cd34189a0dfd

Branch pushed to git repo; I updated commit sha1. New commits:

b6c4211trac #17042: New rules keep on appearing

comment:27 in reply to: ↑ 25 ; follow-up: Changed 5 years ago by 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.

However I do like the speedup of SimplicialComplex.

Yep, that's cool !

Branch updated.

Nathann

comment:28 in reply to: ↑ 27 Changed 5 years ago by tscrim

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

Anyways, thanks for changing it.

Last edited 5 years ago by tscrim (previous) (diff)

comment:29 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/17042 to b6c4211b1df9f99084eeab017de2cd34189a0dfd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.