Opened 8 years ago
Closed 8 years ago
#14668 closed task (fixed)
Move functions from sage.matroids.bitset_tools to sage.misc
Reported by: | Stefan | Owned by: | jason |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.11 |
Component: | misc | Keywords: | |
Cc: | Merged in: | sage-5.11.beta1 | |
Authors: | Rudi Pendavingh, Stefan van Zwam | Reviewers: | Volker Braun |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
There are several bitset tools in the matroid code:
- pickling/unpickling
- rev_lex comparison
- bitset_morph
These should be moved into sage.misc.
apply trac_14668_bitsets.patch
Attachments (1)
Change History (16)
comment:1 Changed 8 years ago by
- Dependencies 7477 deleted
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
comment:3 Changed 8 years ago by
comment:4 Changed 8 years ago by
Hellooooooooooooooo !!
Just a couple of comments :
I thought at first that your bitset_rev_lex_cmp
function was wrong, and I noticed later that I had read "reverse lexicographic order" as "co-lex order" (i.e. the lexicographic order on words when you read them from right to left instead). Turns out that this "reverse lexicographic order" can be obtained by adding a "-" to a call to the previous function.
I personally think that risking this confusion is not worth saving a -
in a source code, and that this '-' is not worth the space it takes to store the code of this function in bitset.pxi either. Well, that's just my advice, I don't mind much, I just say it aloud, do as you wish.
I also did not understand from its docstring what bitset_morph
does, and so I read the code. First, I think that "function" would be better than "morphism" in this context. And as this actually computes the image of a bitset by a function, renaming it to bitset_image
or bitset_function_image
would make sense to me... What do you think ?
Anyway, have fuuuuuuuuuuuuuuuuuuuuuuuuuuuunnn !!!
Nathann
comment:5 follow-up: ↓ 6 Changed 8 years ago by
- bitset_rev_lex_cmp was removed
- bitset_morph is now called bitset_map with hopefully better docstring
comment:6 in reply to: ↑ 5 Changed 8 years ago by
- bitset_morph is now called bitset_map with hopefully better docstring
Oh right ! Good choice :-)
Nathann
comment:7 Changed 8 years ago by
Hello,
I'm giving here some comments that could either be used to improve this patch or be considered for a future patch.
With path #13352, I tried to speed-up the bitset_len
method using popcount. I have not finalized the patch because the solution I have proposed is not satisfactory. In particular, it has been suggested to use the low level __builtin_popcount()
method, but my trials were not successful. Another remark was that GMP has functions like mpz_popcount()
for mpz_t
.
In fact, the mpz_t
type of GMP is similar to the bitset_s
type we have here, and the bitset_lex_cmp
method proposed in this patch corresponds to the mpz_cmp
method of GMP.
Since GMP is optimized for most processors (and used for arbitrary length numbers in sage), it would be nice to use it here. But may be this is relevant for (Frozen)Bitset only?
David.
comment:8 Changed 8 years ago by
Indeed. I wonder how much of a speedup it would be to move to mpz_t as the base format. That sounds interesting to look at.
comment:9 Changed 8 years ago by
It looks like polymake has a bitset C++ class based on mpz_t: http://modular.math.washington.edu/home/wstein/www/home/cswiercz/sage-4.6/spkg/build/polymake-2.2.p5/src/lib/PTL/include/Bitset.h
comment:10 follow-up: ↓ 12 Changed 8 years ago by
comment:11 Changed 8 years ago by
Sure, it's better to have a dedicated ticket for possibly moving to gmp.
comment:12 in reply to: ↑ 10 Changed 8 years ago by
comment:13 follow-up: ↓ 14 Changed 8 years ago by
- Reviewers set to Volker Braun
- Status changed from needs_review to positive_review
I was hoping that somebody would have set this to positive review by now, come oooon.
And no endless feature request on tickets that obviously improve what we have... can you reimplement all of bitsets using foo? Sure, great idea! :-P
comment:14 in reply to: ↑ 13 Changed 8 years ago by
Replying to vbraun:
I was hoping that somebody would have set this to positive review by now, come oooon.
Yes, it has been more than 24 hours. I was about to cruise the documentation and code style, etc. But I'm late to the party again, apparently. ;-)
comment:15 Changed 8 years ago by
- Merged in set to sage-5.11.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
Just uploaded a patch adding functionality to bitset.pxi and tests to misc_c.pyx. I took the liberty to clean up some of the docstrings and trailing whitespace; I hope that's ok.