Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#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:

Status badges

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)

integer_vector_ranking.patch (1.4 KB) - added by f.poloni 8 years ago.

Download all attachments as: .zip

Change History (16)

Changed 8 years ago by f.poloni

comment:1 Changed 8 years ago by ncohen

  • Cc ncohen added

comment:2 Changed 8 years ago by f.poloni

  • 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 8 years ago by f.poloni

  • Authors set to Federico Poloni
  • Commit set to f616301fefa44762f90fe7cc54aab3d78d842b9e
  • Status changed from new to needs_review

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:

f616301Implemented IntegerVectors_nk.rank(). Fixes #15609

comment:4 Changed 8 years ago by ncohen

  • 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: Changed 8 years ago by f.poloni

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

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 to rank()?

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() throws TypeError 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 8 years ago by ncohen

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

  • Commit changed from f616301fefa44762f90fe7cc54aab3d78d842b9e to 06856f64cb051c2068d2d6e70f9b4a55f6b87622

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

06856f6test for membership with `x in self`; minor doc formatting change

comment:9 Changed 8 years ago by f.poloni

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

06856f6test for membership with `x in self`; minor doc formatting change

comment:10 Changed 8 years ago by ncohen

Okayyyyyyyyyyyyyyyyyyyy ! Then it can go. Thanks for that patch ! ;-)

Nathann

comment:11 Changed 8 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

comment:12 Changed 8 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:13 Changed 8 years ago by ncohen

Wow. From created to merged in 5 days. That was fast :-P

Nathann

comment:14 Changed 8 years ago by vbraun

See #15639 for a bug that was most likely introduced here.

comment:15 Changed 8 years ago by ncohen

Weird O_o

Nathann

Note: See TracTickets for help on using tickets.