CODEWITHSUNDEEP
julia
21rw
21rw

Reputation: 1126

Convert an integer vector to an integer

What is the most efficient way to convert a vector like this

[1, 0, 2, 4]

to the corresponding integer 1024?

(Assuming that the array will always be a valid integer)

Upvotes: 1

Views: 548

Answers (3)

rafak
rafak

Reputation: 5551

There was a trick recently posted on Julia's issue tracker recently:

julia> evalpoly(10, [4, 2, 0, 1])
1024

julia> @evalpoly(10, 4, 2, 0, 1)
1024

This is pretty fast, but this requires the list of coefficients in the reverse order, the same as what the digits function gives:

julia> digits(1024)
4-element Vector{Int64}:
 4
 2
 0
 1

Upvotes: 2

Nathan Boyer
Nathan Boyer

Reputation: 1474

Probably slow, but here's a one-liner: parse(Int,join(string.([1, 0, 2, 4]))).

Upvotes: 0

cbk
cbk

Reputation: 4370

In general, what you want to do is multiply each number in the array by the desired "place" (i.e., the base raised to a power incrementing in unit steps from zero at the last/rightmost place). The fastest way to do this in Julia for vectors of arbitrary length should be a simple loop along the lines of

function arraytoint10(A)
    n = 0
    l = length(A)
    for i = 1:l
        n += A[i]*10^(l-i)
    end
    return n
end

julia> A = [1, 0, 2, 4];

julia> arraytoint10(A)
1024

This is quite fast

julia> using BenchmarkTools

julia> @benchmark arraytoint10($A)
BechmarkTools.Trial: 10000 samples with 998 evaluations.
 Range (min … max):  15.114 ns … 108.888 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     17.394 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   18.469 ns ±   4.297 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

   ▃█ █▅▂█ ▂▇     ▂▆     ▁ ▆        ▁  ▁                     ▂ ▂
  ▄██████████▇▇▆▄▄██▄█▅▅▄█▆█▃▆▅▄▄▆▆██▇██▆▄▆▆▅▅▅▄▆▄▄▄▄▄▄▄▄▅▄▅▅█ █
  15.1 ns       Histogram: log(frequency) by time      33.8 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

and could be easily generalized to other bases by substituting the desired base in place of the 10 in A[i]*10^(l-i).

Edit: in response to the excellent suggestion by @vincent-yu in the comment below

function arraytoint10_iterative(A)
    n = 0
    l = length(A)
    for i = 1:l
        n = 10n + A[i]
    end
    return n
end

julia> @benchmark arraytoint10_iterative($A)
BechmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  3.670 ns … 21.758 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     3.787 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   4.226 ns ±  1.320 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █▅ ▇▃▄▄▂  ▁                                                ▂
  ██▆█████▅██▄▄█▅▃▃▁▆▆▆█▇▆▇▄▅▄▁▃▁▁▁▁▁▁▁▁▁▁▁▄▁▁▁▁▁▁▁▁▁▄▄▄▅▆▆▃ █
  3.67 ns      Histogram: log(frequency) by time     13.7 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

That shifts us all the way down to O(n) complexity and gives us about another 4x speedup (and even more for larger arrays)!

Upvotes: 3

Related Questions