#15609 closed enhancement (fixed)
IntegerVectors_nk.rank() specialization
Reported by: | f.poloni | Owned by: | |
---|---|---|---|
Priority: | trivial | Milestone: | sage-6.1 |
Component: | combinatorics | Keywords: | integervectors, rank |
Cc: | ncohen | Merged in: | |
Authors: | Federico Poloni | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | u/f.poloni/ticket/15609 (Commits, GitHub, GitLab) | Commit: | 06856f64cb051c2068d2d6e70f9b4a55f6b87622 |
Dependencies: | Stopgaps: |
Description
Currently IntegerVectors_nk inherits the generic rank()
implementation for its parent; it's a very generic method that generates all its members and checks for equality. I needed a faster implementation in my code, so I wrote a specialized version that uses an ad-hoc algorithm (nothing fancy, essentially it's just adding up a bunch of binomials).
I plan to upload the code using git and the standard dev tools. I'm a new contributor, so it could take me a while to set everything up and commit code -- I am currently in the process of building a dev version for the first time.
Attachments (1)
Change History (16)
Changed 9 years ago by
comment:1 Changed 9 years ago by
- Cc ncohen added
comment:2 Changed 9 years ago by
- Branch set to u/f.poloni/ticket/15609
- Created changed from 12/30/13 18:02:50 to 12/30/13 18:02:50
- Modified changed from 12/30/13 21:39:55 to 12/30/13 21:39:55
comment:3 Changed 9 years ago by
- Commit set to f616301fefa44762f90fe7cc54aab3d78d842b9e
- Status changed from new to needs_review
comment:4 Changed 9 years ago by
- Status changed from needs_review to needs_work
Hellooooooooooooooo Federico !
Well, I don't know what you went through, but the patch looks nice in the end ;-)
It's a cool improvement, and it is well documented and tested. I have only one thing to add :
sage: IV = IntegerVectors(4,5) sage: IV.rank((0,0,4,0,0)) 55 sage: IV.rank((0,1,-1,4,0)) 55
That's because you check manually whether the given vector belongs to IV
instead of using the __contains__
method, i.e. x in self
.
The problem with this x in self
is that it also computes the sum of the vector, and that you will compute it a second time in your function because you need it too. But that may not be soooo troublesome anyway, it's not that costly. Especially compared with the current implementation.
Could you fix that ? Also, could you replace
- ``x`` - any sequence with sum(x) == n and len(x) == k
i
n the docstring with that ?
- ``x`` - any sequence with ``sum(x) == n`` and ``len(x) == k``
This way it will all appear properly in the html documentation. Which you can obtain with sage -b && sage -docbuild reference/combinat html
Thanks !
Nathann
comment:5 follow-up: ↓ 6 Changed 9 years ago by
Thanks for taking a look at the patch. You are correct about the negative entries, good catch; I'll fix it.
Actually there is another point I was considering. The members of IntegerVectors
are lists; what should we do when another sequence type such a tuple is passed to rank()
?
The implementation in the current patch returns the same result for any sequence type, however using __contains__
would require them to be lists or else it would throw an error.
Combinations.rank()
throws TypeError
when passed a tuple; Derangements.rank()
returns nothing (no error thrown).
This is an issue of strict type correctness vs. user convenience. For instance, you inadvertently used a tuple in your example in the previous comment. :)
It is ultimately a developer decision; please let me know what I should return in case a tuple is entered and I shall code it.
comment:6 in reply to: ↑ 5 Changed 9 years ago by
Hellooooooooooooooo !!!
Thanks for taking a look at the patch. You are correct about the negative entries, good catch; I'll fix it.
Actually there is another point I was considering. The members of
IntegerVectors
are lists; what should we do when another sequence type such a tuple is passed torank()
?
Hmmmmmmm....
The implementation in the current patch returns the same result for any sequence type, however using
__contains__
would require them to be lists or else it would throw an error.
Well, I think that it would make sense anyway to only return the rank of objects on which __contains__
return True. But indeed tuples make sense too. Well, why don't we also allow tuples in __contains__
? It doesn't look that crazy :-)
Combinations.rank()
throwsTypeError
when passed a tuple;Derangements.rank()
returns nothing (no error thrown).
I hate this code. This has to be *FIXED*. I will create a ticket for that and add you in Cc (it should only take a couple of seconds to review).
What has to be known about this code is that it is inconsistent in many places, and that we should never feel forced to respect what is done elsewhere, for I learned it was mistakes most of the time :-P
I think rank should throw a ValueError
when __contains__
returns False
on the input. What's your opinion ? Returning nothing is just plain bad programming.
This is an issue of strict type correctness vs. user convenience. For instance, you inadvertently used a tuple in your example in the previous comment.
:)
It is ultimately a developer decision; please let me know what I should return in case a tuple is entered and I shall code it.
Well, I really feel that what should be called there is __contains__
, and that we should play with what __contains__
allow if it is not convenient. But let's be consistent with ourselves for a start.
Please code it this way only if it makes sense to you. Otherwise let's talk about it. And I will write this quick patch for the other problem you found.
Have fuuuuuuuuuuuuun !
Nathann
comment:7 Changed 9 years ago by
I asked a question on sage-combinat-devel about this .rank function that returns nothing.
https://groups.google.com/forum/#!topic/sage-combinat-devel/YUEVBIUzOv4
Turns out it is a deliberate choice.
Nathann
comment:8 Changed 9 years ago by
- Commit changed from f616301fefa44762f90fe7cc54aab3d78d842b9e to 06856f64cb051c2068d2d6e70f9b4a55f6b87622
Branch pushed to git repo; I updated commit sha1. New commits:
06856f6 | test for membership with `x in self`; minor doc formatting change
|
comment:9 Changed 9 years ago by
- Status changed from needs_work to needs_review
I agree with you on all respects (except maybe that I think that for most sequences the generic inherited rank
implementation is still better than no implementation, but that's a minor unrelated issue).
"Return NULL or raise an exception on failure" is an old programming style debate, but I agree that it should be more Pythonic to raise an exception.
As for the choice of sequences, also in my view it would be good not to force a specific one on the user, at least in methods that take them as inputs, but that's a different and broader issue.
Anyway, I have applied your suggested changes (testing for membership with x in self
, and that formatting correction in the docs).
New commits:
06856f6 | test for membership with `x in self`; minor doc formatting change
|
comment:10 Changed 9 years ago by
Okayyyyyyyyyyyyyyyyyyyy ! Then it can go. Thanks for that patch ! ;-)
Nathann
comment:11 Changed 9 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to positive_review
comment:12 Changed 9 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
comment:13 Changed 9 years ago by
Wow. From created to merged in 5 days. That was fast :-P
Nathann
comment:14 Changed 9 years ago by
See #15639 for a bug that was most likely introduced here.
comment:15 Changed 9 years ago by
Weird O_o
Nathann
Committed using git and the dev-tools the code in the attached patch, after many difficulties setting up the environment as a first-time contributor. :(
New commits:
Implemented IntegerVectors_nk.rank(). Fixes #15609