Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

intersect could be more efficient for mixtures of UnitRange and Vector #41759

Closed
IanButterworth opened this issue Aug 2, 2021 · 2 comments · Fixed by #41769
Closed

intersect could be more efficient for mixtures of UnitRange and Vector #41759

IanButterworth opened this issue Aug 2, 2021 · 2 comments · Fixed by #41769

Comments

@IanButterworth
Copy link
Member

It seems like it should be possible to do this without collecting the full range

julia> intersect(1:typemax(Int), [1,3])
julia(30683,0x116666e00) malloc: can't allocate region
:*** mach_vm_map(size=4611686018427392000, flags: 100) failed (error code=3)
julia(30683,0x116666e00) malloc: *** set a breakpoint in malloc_error_break to debug
ERROR: OutOfMemoryError()
Stacktrace:
  [1] _growend!
    @ ./array.jl:982 [inlined]
  [2] resize!
    @ ./array.jl:1207 [inlined]
  [3] rehash!(h::Dict{Int64, Nothing}, newsz::Int64)
    @ Base ./dict.jl:184
  [4] sizehint!
    @ ./dict.jl:244 [inlined]
  [5] sizehint!
    @ ./set.jl:76 [inlined]
  [6] union!(s::Set{Int64}, itr::UnitRange{Int64})
    @ Base ./abstractset.jl:95
  [7] Set
    @ ./set.jl:10 [inlined]
  [8] _Set
    @ ./set.jl:25 [inlined]
  [9] Set
    @ ./set.jl:23 [inlined]
 [10] _shrink(shrinker!::Function, itr::UnitRange{Int64}, itrs::Tuple{Vector{Int64}})
    @ Base ./array.jl:2609
 [11] intersect(itr::UnitRange{Int64}, itrs::Vector{Int64})
    @ Base ./array.jl:2613
 [12] top-level scope
    @ REPL[10]:1
@barucden
Copy link
Contributor

barucden commented Aug 3, 2021

Would this be viable

function intersect(r::AbstractRange, vec::AbstractVector)
    common = Iterators.filter(x -> x  r, vec)
    seen = Set{eltype(vec)}(common)
    return vectorfilter(_shrink_filter!(seen), common)
end

?

@IanButterworth
Copy link
Member Author

IanButterworth commented Aug 3, 2021

Nice. Looks good to me!

It's more efficient than the vec vec version

julia> @btime intersect(1:typemax(Int), [1,3])
  302.226 ns (8 allocations: 688 bytes)
2-element Vector{Int64}:
 1
 3

julia> @btime Base.intersect([1,2,3,4,5], [1,3])
  654.689 ns (15 allocations: 1.11 KiB)
2-element Vector{Int64}:
 1
 3

julia> @btime Base.intersect(1:typemax(Int), 1:2:3)
  0.044 ns (0 allocations: 0 bytes)
1:2:3

I'd also define

intersect(vec::AbstractVector, r::AbstractRange) = intersect(r, vec)

Could you PR this? I'd like to use this in another Base PR. Thanks!

barucden added a commit to barucden/julia that referenced this issue Aug 3, 2021
barucden added a commit to barucden/julia that referenced this issue Aug 3, 2021
barucden added a commit to barucden/julia that referenced this issue Aug 4, 2021
barucden added a commit to barucden/julia that referenced this issue Aug 18, 2021
barucden added a commit to barucden/julia that referenced this issue Aug 27, 2021
Also adds:
 - `intersect(::AbstractRange, ::AbstractRange)`
 - `intersect(::AbstractRange, ::AbstractRange)`

Closes JuliaLang#41759

Co-authored-by: Ian Butterworth <[email protected]>
Co-authored-by: Jeff Bezanson <[email protected]>
barucden added a commit to barucden/julia that referenced this issue Aug 27, 2021
Also adds:
 - `intersect(::AbstractRange, ::AbstractRange)`
 - `intersect(::AbstractRange, ::AbstractRange)`

Closes JuliaLang#41759

Co-authored-by: Ian Butterworth <[email protected]>
Co-authored-by: Jeff Bezanson <[email protected]>
barucden added a commit to barucden/julia that referenced this issue Aug 28, 2021
Also adds:
 - `intersect(::AbstractRange, ::AbstractRange)`
 - `intersect(::AbstractRange, ::AbstractRange)`

Closes JuliaLang#41759

Co-authored-by: Ian Butterworth <[email protected]>
Co-authored-by: Jeff Bezanson <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants