Complement on multi-sets and sub-set iterators #1241

StevellM · 2023-10-10T10:19:31Z

Related to #1238

This is built on what was already implemented by @fieker :

Fix some non-working functions
Add more documentation and doctests
Create an html documentation
Test the different functions of the file
Add some constructors and functionalities

Not all possible functionalities are available, there are still many existing functions for Set and Dict which could be implemented for MSet; this would have to be done on-demand I guess.

I have changed the printing, to be closer to the printing of Set and Dict. The code could have been done nicer if julia offered the possibility to use their printing methods for Dict where one can choose the separator they want... Instead I wrote something which works similarly (if we see that we will get beyond the size of the screen, we cut and put some dots).

Nothing is perfect or fixed, those are my suggestions of improvements together with a template for the html documentation so that Hecke/Oscar users are aware of the existence of the functionalities for multi-sets.

thofma · 2023-10-10T10:23:50Z

I have a small question: Could you add the "sum" while you are at it? (see https://en.wikipedia.org/wiki/Multiset#Basic_properties_and_operations).

I will talk to some people about the printing (whether we want to keep : or whether we really want to drop the multiplicity if it is one).

StevellM · 2023-10-10T15:58:09Z

Now I noticed that I had to change the sum(::MSet) which was falling back into sun(::AbstractSet). Should I add then a deprecation since now we have a proper method sum(::MSet, ::MSet) ? Or maybe define sum(::MSet) as it was working before ? The latter would imply two different behaviours depending on the number arguments though.

codecov · 2023-10-10T17:03:34Z

Codecov Report

Attention: 3 lines in your changes are missing coverage. Please review.

Comparison is base (c4ffff3) 74.57% compared to head (af4893b) 74.68%.
Report is 2 commits behind head on master.

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #1241      +/-   ##
==========================================
+ Coverage   74.57%   74.68%   +0.10%     
==========================================
  Files         346      346              
  Lines      110842   110995     +153     
==========================================
+ Hits        82661    82897     +236     
+ Misses      28181    28098      -83

Files	Coverage Δ
src/Misc/MSet.jl	`96.23% <98.58%> (+46.49%)`	⬆️

... and 38 files with indirect coverage changes

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

fieker · 2023-10-11T05:26:51Z

src/Misc/MSet.jl

 Base.isempty(s::MSet) = isempty(s.dict)
 Base.length(s::MSet) = sum(values(s.dict))
 Base.IteratorSize(::Type{MSet}) = Base.HasLength()
 Base.IteratorEltype(::Type{MSet}) = Base.HasEltype()
 Base.eltype(::Type{MSet{T}}) where {T} = T
-Base.in(x, s::MSet) = haskey(s.dict, x)
+Base.in(x, s::MSet) = any(y -> x == y, keys(s.dict))


Isn't this much slower than the old version? O(n) Vs O(1)?

I haven't tried but the previous version is not practical. See for instance what could happen in a very basic example:

julia> d = Dict{QQFieldElem, Int}(2 => 2) Dict{QQFieldElem, Int64} with 1 entry: 2 => 2 julia> haskey(d, 2) false

I have not thought about about a better work-around..

fieker · 2023-10-11T05:35:17Z

src/Misc/MSet.jl

@@ -119,48 +568,92 @@ function Base.filter(pred, s::MSet)
  return t
 end

+function Base.filter!(pred, s::MSet)
+  un = unique(s)
+  for x in un


This copies everything

fieker · 2023-10-11T05:36:07Z

src/Misc/MSet.jl

+  s = similar(s1, T)
+  d = s.dict
+  for x in val
+    y = un2[findfirst(y -> x == y, un2)]


Use isequal(x)?

fieker · 2023-10-11T05:38:03Z

src/Misc/MSet.jl

+@doc raw"""
+    multiset(T::Type) -> MSet{T}
+
+Create an unitialized multi-set `M` with elements of type `T`.


It's empty, not uninitialised

fieker · 2023-10-11T05:38:43Z

src/Misc/MSet.jl

+    if !(x in val)
+      delete!(s1, x)
+    else
+      y = un2[findfirst(y -> x == y, un2)]


fieker · 2023-10-11T05:39:53Z

src/Misc/MSet.jl

-  y = x isa T ? x : T(x)
-  if haskey(s.dict, y)
-    return s.dict[y]
+function multiplicity(s::MSet, x)


Change from constant time to linear? Why?

Same as explain for the in function: if I have a MSet{QQFieldElem}, then for testing the multiplicity of 2, one needs to check for QQ(2). If we want to force this and then do not leave room for this kind of flexibility, I am ok with reverting this.

fieker · 2023-10-11T05:41:59Z

src/NumField/NfAbs/Elem.jl

@@ -462,7 +462,7 @@ function _ds(fa)
  @assert all(x->x == 1, values(fa.fac))
  T = Int[degree(x) for x = keys(fa.fac)]
  M = MSet(T)
-  return Set(sum(s) for s = subsets(M) if length(s) > 0)
+  return Set(sum(collect(s)) for s = subsets(M) if length(s) > 0)


Why collect?

fieker · 2023-10-11T05:45:05Z

I find the name terrible. Sum(mset) I'd expect a sum over the elements with multiplicity. Sum of 2 msets I've never seen, or expected

…

On Tue, 10 Oct 2023, 17:58 Stevell Muller, ***@***.***> wrote: Now I noticed that I had to change the sum(::MSet) which was falling back into sun(::AbstractSet). Should I add then a deprecation since now we have a proper method sum(::MSet, ::MSet) ? Or maybe define sum(::MSet) as it was working before ? The latter would imply two different behaviours depending on the number arguments though. — Reply to this email directly, view it on GitHub <#1241 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA36CV6QVIOMONC245HGXX3X6VWBZAVCNFSM6AAAAAA52DJJFKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTONJVG42DMNJVG4> . You are receiving this because you were mentioned.Message ID: ***@***.***>

StevellM · 2023-10-11T06:43:33Z

The naming sum for MSet is taken from what I have seen on Wikipedia. I had a look to other CAS: python apparently uses "combine" and maple uses the "+" operator. The thing with sum(::MSet{T}) is that it would only work whenever T <: RingElem or at least the types for which sum is defined. We could change sum as I defined it with something of the form multiset_sum, disjoint_union or combine and keep maybe the + operator for simplicity ? In that case the sum(::MSet) will use directly sum(::AbstractSet) as it was doing before (provided that the user know what they are doing)

fieker · 2023-10-11T07:17:02Z

On Tue, Oct 10, 2023 at 11:29:17PM -0700, Stevell Muller wrote: @StevellM commented on this pull request. > Base.isempty(s::MSet) = isempty(s.dict) Base.length(s::MSet) = sum(values(s.dict)) Base.IteratorSize(::Type{MSet}) = Base.HasLength() Base.IteratorEltype(::Type{MSet}) = Base.HasEltype() Base.eltype(::Type{MSet{T}}) where {T} = T -Base.in(x, s::MSet) = haskey(s.dict, x) +Base.in(x, s::MSet) = any(y -> x == y, keys(s.dict)) I haven't tried but the previous version is not practical. See for instance what could happen in a very basic example: ``` julia> d = Dict{QQFieldElem, Int}(2 => 2) Dict{QQFieldElem, Int64} with 1 entry: 2 => 2 julia> haskey(d, 2) false ``` I have not thought about about a better work-around..

That was a deliberate decision to not support that. I'm (un)happy to discuss this in detail: In Julia base, effort is made so that hash(1) == hash(1//1) == hash(1.0) == ... Despite them being different types. This is possible, for BigInt and BigFloat only via some memory expensive operations, the float is decomposed into a rational and then mutilated. This screws up the performance in many important algorithms. Thus we (I) decided to not support that madness hash functions should never allocate The price is that for ZZRingElem(2)^100 the hash is different to Int128(2)^100... For in: it would be better, in my opinion to coerce into the type if we want to support that. But the entire point of Dicts is to have an O(1) lookup and not an O(length(D)) in(a::T, M::MSet{T}) = haskey(M.dict, a) in(a::Any, M::MSet{T}) = haskey(M.dict, T(a)) it will still be "bad" if you put e.g. number field elements in - esp. in different fields....

…

-- Reply to this email directly or view it on GitHub: #1241 (comment) You are receiving this because you were mentioned. Message ID: ***@***.***>

fieker · 2023-10-11T07:24:43Z

On Tue, Oct 10, 2023 at 11:43:44PM -0700, Stevell Muller wrote: The naming `sum` for `MSet` is taken from what I have seen on Wikipedia. I had a look to other CAS: python apparently uses "combine" and maple uses the "+" operator. The thing with `sum(::MSet{T})` is that it would only work whenever `T <: RingElem` or at least the types for which `sum` is defined. We could change `sum` as I defined it with something of the form `multiset_sum`, `disjoint_union` or `combine` and keep maybe the `+` operator for simplicity ? In that case the `sum(::MSet)` will use directly `sum(::AbstractSet)` as it was doing before (provided that the user know what they are doing)

In the end I don't mind. I've never tried to add MSets and don't see this happening in the near future.... sum and prod for Sets I haven't tried recently. I think it was not allowed for a long time....

…

-- Reply to this email directly or view it on GitHub: #1241 (comment) You are receiving this because you were mentioned. Message ID: ***@***.***>

StevellM · 2023-10-11T07:33:58Z

Thanks for the explanation! I will revert what I have changed to keep it in linear time then. I have modified also some other parts to avoid to create unnecessary lists.

For the sum, I will just keep the + for now and if one day one comes up with an acceptable name, it will be easy to add.

StevellM · 2023-10-13T10:11:03Z

@fieker Do the last changes I have been seem good for you ?

thofma · 2023-10-17T11:58:26Z

Merci Stevell

complement on multi-sets and sub-set iterators

9011dbd

StevellM added 3 commits October 10, 2023 12:31

fix oversize printing

b163274

fix union + add sum/intersect and difference

a0a87de

further fixes

24cfca8

hopefully fix the checks + some improvements + more tests

51ecc89

fieker reviewed Oct 11, 2023

View reviewed changes

fieker requested changes Oct 11, 2023

View reviewed changes

StevellM and others added 2 commits October 11, 2023 10:24

apply suggestions and change what was requested

24f07f8

Update mset.md

af4893b

fieker approved these changes Oct 17, 2023

View reviewed changes

thofma merged commit 4a830bc into thofma:master Oct 17, 2023
14 of 16 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Complement on multi-sets and sub-set iterators #1241

Complement on multi-sets and sub-set iterators #1241

StevellM commented Oct 10, 2023

thofma commented Oct 10, 2023

StevellM commented Oct 10, 2023

codecov bot commented Oct 10, 2023 •

edited

Loading

fieker Oct 11, 2023

StevellM Oct 11, 2023

fieker Oct 11, 2023

fieker Oct 11, 2023

fieker Oct 11, 2023

fieker Oct 11, 2023

fieker Oct 11, 2023

StevellM Oct 11, 2023

fieker Oct 11, 2023

fieker commented Oct 11, 2023 via email

StevellM commented Oct 11, 2023

fieker commented Oct 11, 2023 via email

fieker commented Oct 11, 2023 via email

StevellM commented Oct 11, 2023

StevellM commented Oct 13, 2023

thofma commented Oct 17, 2023

Complement on multi-sets and sub-set iterators #1241

Complement on multi-sets and sub-set iterators #1241

Conversation

StevellM commented Oct 10, 2023

thofma commented Oct 10, 2023

StevellM commented Oct 10, 2023

codecov bot commented Oct 10, 2023 • edited Loading

Codecov Report

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

fieker commented Oct 11, 2023 via email

StevellM commented Oct 11, 2023

fieker commented Oct 11, 2023 via email

fieker commented Oct 11, 2023 via email

StevellM commented Oct 11, 2023

StevellM commented Oct 13, 2023

thofma commented Oct 17, 2023

codecov bot commented Oct 10, 2023 •

edited

Loading