# Improve removing members of one array from another

**URL:** <https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922>\
**Category:** Performance\
**Tags:** question\
**Created:** [February 14, 2025, 8:54pm UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922 "2025-02-14T20:54:26Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![jzakiya](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jzakiya/32/6416_2.png) [@jzakiya](https://discourse.julialang.org/u/jzakiya)\
**Post date:** [February 14, 2025, 8:54pm UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/1 "2025-02-14T20:54:26Z")

</div>

The following Julua code is much slower than Ruby and Python because of the slow way it removes the members of one array from another.

```julia
function prime_pairs_lohi(n)
  if (n&1 == 1 || n < 4) return println("Input not even n > 2") end
  if (n <= 6) println([n, 1]); println([div(n,2),div(n,2)]); println([div(n,2),div(n,2)]); return end

  # generate the low-half-residues (lhr) r < n/2
  ndiv2, rhi = div(n,2), n-2 # lhr:hhr midpoint, max residue limit
  lhr = [] # array for low half residues
  for r in 3:2:ndiv2; if (gcd(r, n) == 1) append!(lhr, r) end end

  # store all powers and cross-products of the lhr members < n-2
  lhr_mults = [] # lhr multiples, not part of a pcp
  i = 2; ln = length(lhr)
  while (i < ln)
    r = lhr[i-1] # make 1st lhr reference multiplier
    rmax = div(rhi, r) # ri can't multiply r with values > this
    if (r < rmax) append!(lhr_mults, r*r) end # for r^2 multiples
    if (lhr[i] > rmax) break end # exit if product of consecutive r’s > n-2
    j = i # index to next larger residue in lhr
    while (j < ln) # for each residue in reduced list
      if (lhr[j] > rmax) break end # exit for r if cross-product with ri > n-2
      append!(lhr_mults, r * lhr[j]) # store value if < n-2
      j += 1 # next lhr value to multiply
    end
    i += 1
  end

  # convert lhr_mults vals > n/2 to their lhr complements n-r,
  # store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals
  lhr_del = []
  for r in lhr_mults # convert all lhr multiples to lhr values
    r_del = (r > ndiv2) ? n - r : r # convert r > n/2 to lhr mc if necessary
    append!(lhr_del, r_del) # store in lhr_del
  end

  lhr = setdiff(lhr,lhr_del) # remove lhr_del multiples from lhr
  println([n, length(lhr)]) # show n and pcp prime pairs count
  println([first(lhr),n-first(lhr)]) # show first pcp prime pair of n
  println([last(lhr), n-last(lhr)]) # show last pcp prime pair of n
end

num = readline() # get n value string from terminal
n = parse(Int64, num) # convert to Int64 integer value
@time begin prime_pairs_lohi(n) end # execute code and show its timing

```

In Ruby|Crystal its: `lhr -= lhr_del`

In Pyrhon its: `lhr = [r for r in lhr if r not in lhr_del]`

In Julia this is mag orders slower: `lhr = setdiff(lhr,lhr_del)`

Is there a way to do this faster, and in general, to optimize all the code.

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [February 14, 2025, 9:32pm UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/2 "2025-02-14T21:32:14Z")

</div>

Are you sure it’s that specific line? Did you profile the code?

If you just compared the times you got from this script then these likely are heavily dominated by compilation time. Please switch to `@btime` from BenchmarkTools.jl for proper timing.  
It’d also be great, if you could post some example times.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 14, 2025, 9:38pm UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/3 "2025-02-14T21:38:43Z")

</div>

I think you can already gain significant speed by ensuring that

- your vectors are not `Vector{Any}` but instead `Vector{Int}`
- you replace `append!` with `push!` (which is the correct way to add a single element in Julia)
- you pre-allocate the correct size (or a mild overestimate) for your vectors

Here’s a new version that runs at least 5 times faster, if my benchmarks are correct:

```julia
function prime_pairs_lohi_fast(n::T) where {T<:Integer}
    if (n & 1 == 1 || n < 4)
        return println("Input not even n > 2")
    end
    if (n <= 6)
        println([n, 1])
        println([div(n, 2), div(n, 2)])
        println([div(n, 2), div(n, 2)])
        return nothing
    end

    # generate the low-half-residues (lhr) r < n/2
    ndiv2, rhi = div(n, 2), n - 2 # lhr:hhr midpoint, max residue limit
    lhr = T[] # array for low half residues
    sizehint!(lhr, ndiv2 ÷ 2)
    for r in 3:2:ndiv2
        if (gcd(r, n) == 1)
            push!(lhr, r)
        end
    end

    # store all powers and cross-products of the lhr members < n-2
    lhr_mults = T[] # lhr multiples, not part of a pcp
    sizehint!(lhr_mults, length(lhr)^2)
    i = 2
    ln = length(lhr)
    while (i < ln)
        r = lhr[i - 1] # make 1st lhr reference multiplier
        rmax = div(rhi, r) # ri can't multiply r with values > this
        if (r < rmax)
            push!(lhr_mults, r * r)
        end # for r^2 multiples
        if (lhr[i] > rmax)
            break
        end # exit if product of consecutive r’s > n-2
        j = i # index to next larger residue in lhr
        while (j < ln) # for each residue in reduced list
            if (lhr[j] > rmax)
                break
            end # exit for r if cross-product with ri > n-2
            push!(lhr_mults, r * lhr[j]) # store value if < n-2
            j += 1 # next lhr value to multiply
        end
        i += 1
    end

    # convert lhr_mults vals > n/2 to their lhr complements n-r,
    # store them, those < n/2, in lhr_del; it now holds non-pcp lhr vals
    lhr_del = T[]
    sizehint!(lhr_del, length(lhr_mults))
    for r in lhr_mults # convert all lhr multiples to lhr values
        r_del = (r > ndiv2) ? n - r : r # convert r > n/2 to lhr mc if necessary
        push!(lhr_del, r_del) # store in lhr_del
    end

    lhr = setdiff(lhr, lhr_del) # remove lhr_del multiples from lhr
    println([n, length(lhr)]) # show n and pcp prime pairs count
    println([first(lhr), n - first(lhr)]) # show first pcp prime pair of n
    println([last(lhr), n - last(lhr)]) # show last pcp prime pair of n
    return nothing
end

```

Note the creation of vectors with `T[]` instead of `[]` (which would be your Pythonic reflex), and the use of `sizehint!`

Benchmark results (with printing commented out):

```julia
julia> using BenchmarkTools

julia> @btime prime_pairs_lohi(1_000_000);
  114.282 ms (6624625 allocations: 147.57 MiB)

julia> @btime prime_pairs_lohi_fast(1_000_000);
  18.351 ms (27 allocations: 298.03 GiB)

```

It seems my size estimates are excessive, probably because the `break` condition is hit fairly often. So you may want to use a better heuristic (I don’t understand what the code does so I picked numbers that looked about right). Even if it’s not an overestimate, that won’t impact the correctness of your code.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [February 14, 2025, 10:58pm UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/4 "2025-02-14T22:58:21Z")

</div>

> [@gdalle](#):
>
> the use of `sizehint!`

I know you intended to reduce resizing allocations, but it’s resulting in a massive increase in allocated memory. `sizehint!(lhr_mults, length(lhr)^2)` in particular crashes on my system with `OutOfMemoryError`. FWIW, the original function culminates in `length.((lhr, lhr_mults, lhr_del)) = (199999, 893066, 893066)`, so the estimate can be improved.

> [@jzakiya](#):
>
> ```julia-auto
> println([n, length(lhr)]) # show n and pcp prime pairs count
> println([first(lhr),n-first(lhr)]) # show first pcp prime pair of n
> println([last(lhr), n-last(lhr)]) # show last pcp prime pair of n
> end
> 
> num = readline() # get n value string from terminal
> 
> ```

Are you heavily using `println` and `readline` because you’re working from the command line? There are better ways of doing IO.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [February 15, 2025, 12:15am UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/5 "2025-02-15T00:15:01Z")

</div>

> [@jzakiya](#):
>
> the slow way it removes the members of one array from another

> [@jzakiya](#):
>
> ```julia
> lhr = setdiff(lhr,lhr_del)  
> 
> ```

I didn’t read the entirety of your code, but I suppose you’d rather want `setdiff!(lhr, lhr_del)`, where `setdiff!` is like `setdiff` but mutates the first argument instead of returning a result.

NB: the `setdiff` doc string points to `setdiff!` under “see also”. I try to read all relevant doc strings.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [February 15, 2025, 12:17am UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/6 "2025-02-15T00:17:52Z")

</div>

> [@jzakiya](#):
>
> ```julia
> lhr_del = []
> for r in lhr_mults # convert all lhr multiples to lhr values
> r_del = (r > ndiv2) ? n - r : r # convert r > n/2 to lhr mc if necessary
> append!(lhr_del, r_del) # store in lhr_del
> end
> 
> lhr = setdiff(lhr,lhr_del)   
> 
> ```

It might be more efficient to avoid constructing `lhr_del` at all and just delete elements one-by-one? Not sure.

---

<div class="post-metadata">

**Author:** ![jzakiya](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jzakiya/32/6416_2.png) [@jzakiya](https://discourse.julialang.org/u/jzakiya)\
**Post date:** [February 15, 2025, 3:05am UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/7 "2025-02-15T03:05:57Z")

</div>

I took the code suggestions and played with them, and this is the fastest version I’ve been able to create so far.

1. I got rid of creating the `lhr_mutls` array.
2. Using `setdiff` is way faster than `setdiff!`.

To make the code operationally the same as Ruby|Python, need to take inputs with uderscores: `123_456` and take inputs directly off the cli.  
`$ julia prime_pairs_lohi 123_456`

Does Julia have something like `n.Args[0]` to take inputs direclty from cli?

This implementation is now faster than Ruby|Crystal|Python for most inputs I tested, and faster than D for some (smaller) values. I’ll do more timing tests when I get time and post some results.

```julia
function prime_pairs_lohi(n::T) where {T<:Integer}
  if (n & 1 == 1 || n < 4); return println("Input not even n > 2") end
  if (n <= 6); println([n, 1]); println([div(n, 2), div(n, 2)]);
     println([div(n, 2), div(n, 2)]); return
  end

  # generate the low-half-residues (lhr) r < n/2
  ndiv2, rhi = div(n, 2), n - 2 # lhr:hhr midpoint, max residue limit
  lhr = T[] # array for low half residues
  sizehint!(lhr, ndiv2 ÷ 2)
  for r in 3:2:ndiv2; if (gcd(r, n) == 1) push!(lhr, r) end end

  # store all powers and cross-products of the lhr members < n-2
  lhr_del = T[] # lhr multiples, not part of a pcp
  sizehint!(lhr_del, length(lhr))
  i = 2; ln = length(lhr)
  while (i < ln) # iterate thru lhr to find prime multiples
    r = lhr[i - 1] # make current lhr reference multiplier
    rmax = div(rhi, r) # ri can't multiply r with values > this
    if (r < rmax)
       r2 = r*r; if (r2 > ndiv2) r2 = n - r2 end
       push!(lhr_del, r2) end # for r^2 multiples
    if (lhr[i] > rmax) break end # exit if product of consecutive r’s > n-2
    j = i # index to next larger residue in lhr
    while (j < ln) # for each residue in reduced list
      if (lhr[j] > rmax) break end # exit for r if cross-product with ri > n-2
      r3 = r * lhr[j]; if (r3 > ndiv2) r3 = n - r3 end
      push!(lhr_del, r3) # store value if < n-2
      j += 1 # next lhr value to multiply
    end
    i += 1
  end

  # remove from lhr its lhr_mults, convert vals > n/2 to lhr complements first
  lhr = setdiff(lhr, lhr_del) # remove lhr_del multiples from lhr

  println([n, length(lhr)]) # show n and pcp prime pairs count
  println([first(lhr), n-first(lhr)]) # show first pcp prime pair of n
  println([last(lhr), n-last(lhr)]) # show last pcp prime pair of n
  return
end

num = readline() # get n value string from terminal
n = parse(Int64, num) # convert to Int64 integer value
@time begin prime_pairs_lohi(n) end # execute code and show its timing

```

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/224680_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 15, 2025, 9:39am UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/8 "2025-02-15T09:39:53Z")

</div>

> [@Benny](#):
>
> I know you intended to reduce resizing allocations, but it’s resulting in a massive increase in allocated memory. `sizehint!(lhr_mults, length(lhr)^2)` in particular crashes on my system with `OutOfMemoryError`. FWIW, the original function culminates in `length.((lhr, lhr_mults, lhr_del)) = (199999, 893066, 893066)`, so the estimate can be improved.

Yeah the estimate can definitely be improved, that’s what I meant by

> [@gdalle](#):
>
> It seems my size estimates are excessive, probably because the `break` condition is hit fairly often. So you may want to use a better heuristic (I don’t understand what the code does so I picked numbers that looked about right). Even if it’s not an overestimate, that won’t impact the correctness of your code.

I suspect there are some number-theoretic arguments that would provide decent approximations [coughs in n \log n]. But of course, getting rid of that big array is even better.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [February 15, 2025, 9:46am UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/9 "2025-02-15T09:46:01Z")

</div>

> [@jzakiya](#):
>
> Does Julia have something like `n.Args[0]` to take inputs direclty from cli?

Right at the top of the [Command-line Interface docs](https://docs.julialang.org/en/v1/manual/command-line-interface/):

> When running a script using `julia`, you can pass additional arguments to your script:
> 
> ```julia
> $ julia script.jl arg1 arg2...
> 
> ```
> 
> These additional command-line arguments are passed in the global constant `ARGS`.

Just process `ARGS` into your inputs and pass them into your function calls, or process `ARGS` in your function, whichever works.

However, starting up a Julia process, reevaluating your whole script, and recompiling your main function only to execute it once is eating up time. The internal `@time begin prime_pairs_lohi(n) end` would measure the compilation and execution of the main function, but it’s missing everything beforehand.

If you plan to work from the command line _practically_, it’s better to use a language that compiles ahead of time to an executable AND doesn’t load much of a runtime. There’s nothing wrong with doing impractical work like reimplementing a program in half a dozen languages to see how fast it can compile and run, but it’s not _optimal._

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [February 15, 2025, 11:32am UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/10 "2025-02-15T11:32:12Z")

</div>

> [@jzakiya](#):
>
> ```julia
> @time begin prime_pairs_lohi(n) end # execute code and show its timing
> 
> ```

I don’t think you’re aware that this timing is including the compilation time?

---

<div class="post-metadata">

**Author:** ![jzakiya](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jzakiya/32/6416_2.png) [@jzakiya](https://discourse.julialang.org/u/jzakiya)\
**Post date:** [March 10, 2025, 9:35pm UTC](https://discourse.julialang.org/t/improve-removing-members-of-one-array-from-another/125922/11 "2025-03-10T21:35:51Z")

</div>

FYI  
I just released the final version of the paper this code is related too. In the paper I now use optimized Crystal code (full source provided).

> **[Proof of Goldbach's Conjecture and Bertrand's Postulate Using Prime Generator...](https://www.academia.edu/127404211/Proof_of_Goldbachs_Conjecture_and_Bertrands_Postulate_Using_Prime_Generator_Theory_PGT_)**
>
> Goldbach's Conjecture states every even integer n \> 2 can be written as the sum of 2 primes, while Bertrand's Postulate states for each n ≥ 2 there is at least one prime p such that n \< p \< 2n. I show both are essentially statements