# Compare permutaion of two numbers efficiently?

**URL:** <https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195>\
**Category:** Performance\
**Created:** [August 3, 2020, 2:53pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195 "2020-08-03T14:53:10Z")\
**Posts on this page:** 13\
**Page:** 2

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [August 3, 2020, 5:38pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/22 "2020-08-03T17:38:59Z")

</div>

There’s something else going on as well, something shouldn’t be cached here, I think:

```julia
julia> @benchmark map(a -> isPerm2(a...), zip($x,$y))
BenchmarkTools.Trial:
  memory estimate: 1.06 KiB
  allocs estimate: 1
  --------------
  minimum time: 51.200 μs (0.00% GC)
  median time: 51.400 μs (0.00% GC)
  mean time: 53.868 μs (0.00% GC)
  maximum time: 153.700 μs (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 1

julia> @benchmark map(a -> isPerm2(a...), zip(g,h)) setup=(g = rand(94852219876975:9485229765865123,1000); h = rand(94852219876975:9485229765865123,1000))
BenchmarkTools.Trial:
  memory estimate: 1.06 KiB
  allocs estimate: 1
  --------------
  minimum time: 51.400 μs (0.00% GC)
  median time: 51.800 μs (0.00% GC)
  mean time: 53.125 μs (0.27% GC)
  maximum time: 1.550 ms (93.81% GC)
  --------------
  samples: 10000
  evals/sample: 1

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 3, 2020, 5:48pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/23 "2020-08-03T17:48:09Z")

</div>

> [@Sukera](#):
>
> ```julia
> function isPerm2(a,b)
> test = zeros(MVector{10,UInt})
> while a > 0 && b > 0
> a, a_ind = divrem(a, 10)
> b, b_ind = divrem(b, 10)
> test[a_ind + 1] += one(eltype(test))
> test[b_ind + 1] -= one(eltype(test))
> end
> a != 0 || b != 0 && return false
> !any(!=(0), test)
> end
> 
> ```

Why are you using `UInt` as eltype in the `test` vector?

---

<div class="post-metadata">

**Author:** ![bernhard](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bernhard/32/2619_2.png) [@bernhard](https://discourse.julialang.org/u/bernhard)\
**Post date:** [August 3, 2020, 5:50pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/24 "2020-08-03T17:50:08Z")

</div>

That is an elegant solution.  
It seems to be a [count sort](https://en.wikipedia.org/wiki/Counting_sort) in disguise.  
It should be possible to add an additional entry for the sign, if you care about negative numbers.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [August 3, 2020, 6:14pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/25 "2020-08-03T18:14:42Z")

</div>

There’s no special reason, other than me writing it that way. Both `UInt` and `Int` are equally fast. Conceptually, having a negative number of a “wrong” digit could indicate which of the two input numbers has more of that digit, but since `test` isn’t returned either way, it didn’t matter to me.

One thing I did deliberately was `one(eltype(test))`, to make sure whatever we add is of the same type as the place we add it onto.

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [August 3, 2020, 6:18pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/26 "2020-08-03T18:18:44Z")

</div>

This is the fastest I got so far, pretty impressive! Thank you all for the useful discussions.

```julia
function isPerm2(a,b)
   test = @MVector fill(0, 10)
   while a > 0 && b > 0
       a, a_ind = divrem(a, 10)
       b, b_ind = divrem(b, 10)
       test[a_ind + 1] += 1
       test[b_ind + 1] -= 1
   end
   a == 0 && b == 0 && all(iszero, test)
end

@benchmark isPerm2.($x,$y)
BenchmarkTools.Trial:
  memory estimate: 4.42 KiB
  allocs estimate: 3
  --------------
  minimum time: 25.399 μs (0.00% GC)
  median time: 25.701 μs (0.00% GC)
  mean time: 27.687 μs (0.00% GC)
  maximum time: 195.100 μs (0.00% GC)
  --------------
  samples: 10000
  evals/sample: 1

```

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [August 3, 2020, 6:23pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/27 "2020-08-03T18:23:23Z")

</div>

Comparing with your initial post, that’s a 12x speedup in both the minimum and mean time and a 5.5x speedup in the maximum time - that’s pretty neat 😃

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 3, 2020, 6:27pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/28 "2020-08-03T18:27:21Z")

</div>

You didn’t use `@inbounds`. On my computer it makes a difference, but apparently not on yours?

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [August 3, 2020, 6:28pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/29 "2020-08-03T18:28:58Z")

</div>

Oh, you’re right! Maybe it’s the version?

```julia
julia> versioninfo()
Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 4

```

---

<div class="post-metadata">

**Author:** ![bernhard](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bernhard/32/2619_2.png) [@bernhard](https://discourse.julialang.org/u/bernhard)\
**Post date:** [August 3, 2020, 6:29pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/30 "2020-08-03T18:29:00Z")

</div>

depending on the size of your vectors and the size of the numbers it may be worth preallocating test

this does not reflect the updates above though

```julia

function isperm3(test,a,b)
    fill!(test,0)
    while a > 0 && b > 0
        a, a_ind = divrem(a, 10)
        b, b_ind = divrem(b, 10)
        test[a_ind + 1] += 1
        test[b_ind + 1] -= 1
    end
    a != 0 || b != 0 && return false
    !any(!=(0), test)
end

function isperm3(a::Vector,b::Vector)
    sz=length(a)
    res = falses(sz)
    test = fill(0, 10)
    @inbounds for i=1:sz
        res[i] = _isperm(test,a[i],b[i]) 
    end
    return res
end

@btime isPerm2.($x,$y); # 103 micro seconds
@btime isperm3($x,$y) #70 micro seconds

```

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [August 3, 2020, 6:50pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/31 "2020-08-03T18:50:05Z")

</div>

Yes, of course, I prefer the `--check-bounds=no` flag since I tend to forget annotating my code `@inbounds` and it helps reduce code clutter.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 3, 2020, 6:53pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/32 "2020-08-03T18:53:35Z")

</div>

Does that completely disable bounds checks in all cases? That sounds pretty risky. I thought `@inbounds` was for cases where you are absolutely positive that you are guaranteed to not go out of bounds.

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [August 3, 2020, 7:34pm UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/33 "2020-08-03T19:34:22Z")

</div>

I usually run two different instances of the REPL during development. One with almost all optimizations turned off and a nother with full optimizations. These are called from a .bat file. In 99% of the time, I notice no need for bounds-checking. This way, I free my mind from the burden of annotating code and focus on the algorithm. I also don’t use `@simd` as I add `--inline=yes` in the production version. Not only this, I also used to turn on `fast-math` in final versions without problems other than known issues like `sinpi`, `cospi`. I was sad when they lately decided to disable the `--math-mode=fast` flag, why then there is an `/Ofast` in C and Fortran? Sometimes one wants to squeeze that last drop of performance out of their code.

---

<div class="post-metadata">

**Author:** ![bernhard](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bernhard/32/2619_2.png) [@bernhard](https://discourse.julialang.org/u/bernhard)\
**Post date:** [August 4, 2020, 9:12am UTC](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195/34 "2020-08-04T09:12:20Z")

</div>

It may be worth terminating early if the number of digits do not match (no need to perform any divisions). For the median time this is a bit faster on my machine.  
Of course, depending on your input / use case, this may not be meaningful

```julia

function isPerm2b(a,b)
    ndigits(a) == ndigits(b) || return false
    test = @MVector fill(0, 10)
    while a > 0 && b > 0
        a, a_ind = divrem(a, 10)
        b, b_ind = divrem(b, 10)
        test[a_ind + 1] += 1
        test[b_ind + 1] -= 1
    end
    a == 0 && b == 0 && all(iszero, test)
end

```

[Previous page](https://discourse.julialang.org/t/compare-permutaion-of-two-numbers-efficiently/44195.md?page=1)
