Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Tim Holy]

On Sunday, April 10, 2016 09:03:06 AM Fred wrote:
> A huge size difference ! I have to read my array from data file so I
> suppose it is like Y and X is only for simulations ?

There turn out to be many situations in which you can take shortcuts if you 
know the values are sorted in increasing order with no skips in them. For 
example, a[1:5] has better performance than a[[1:5;]], even though they yield 
the same answer. One of julia's strengths is that you can leverage this 
knowledge very effectively. So don't convert to an array unless you have some 
reason that you want/need to.

But yes, any data you read from a data file will likely be an array.

Best,
--Tim

> 
> Le dimanche 10 avril 2016 17:50:02 UTC+2, Tim Holy a écrit :
> > Just FYI:
> > 
> > julia> x = 1:0.1:100
> > 1.0:0.1:1.0e6
> > 
> > julia> y = collect(x);  # this is the same as y = [x;]
> > 
> > julia> sizeof(x)
> > 32
> > 
> > julia> sizeof(y)
> > 7928
> > 
> > --Tim

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Fred]

A huge size difference ! I have to read my array from data file so I 
suppose it is like Y and X is only for simulations ?

Le dimanche 10 avril 2016 17:50:02 UTC+2, Tim Holy a écrit :
>
> Just FYI: 
>
> julia> x = 1:0.1:100 
> 1.0:0.1:1.0e6 
>
> julia> y = collect(x);  # this is the same as y = [x;] 
>
> julia> sizeof(x) 
> 32 
>
> julia> sizeof(y) 
> 7928 
>
> --Tim 
>

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Tim Holy]

Just FYI:

julia> x = 1:0.1:100
1.0:0.1:1.0e6

julia> y = collect(x);  # this is the same as y = [x;]

julia> sizeof(x)
32

julia> sizeof(y)
7928

--Tim

On Sunday, April 10, 2016 07:26:06 AM Fred wrote:
> Maybe my array is too small to see a difference, but if I increase the size
> I will lack of RAM ;)
> 
> julia> x = 1:0.1:100
> 1.0:0.1:1.0e6
> 
> julia> @time searchsorted(x, 8.22)
>   0.045590 seconds (33.21 k allocations: 1.535 MB)
> 74:73
> 
> julia> @time searchsorted(x, 8.22)
>   0.05 seconds (8 allocations: 288 bytes)
> 74:73
> 
> julia> @time searchsorted(x, 8.22)
>   0.05 seconds (8 allocations: 288 bytes)
> 74:73
> 
> julia> @time closest_index(x,8.22)
>   0.103219 seconds (4.37 k allocations: 222.884 KB)
> 73
> 
> julia> @time closest_index(x,8.22)
>   0.095684 seconds (4 allocations: 160 bytes)
> 73
> 
> julia> @time dicotomy(x, 8.22)
>   0.009142 seconds (3.45 k allocations: 173.973 KB)
> (73,74)
> 
> julia> @time dicotomy(x, 8.22)
>   0.05 seconds (5 allocations: 192 bytes)
> (73,74)
> 
> julia> @time dicotomy(x, 8.22)
>   0.04 seconds (5 allocations: 192 bytes)
> (73,74)
> 
> 
> 
> Even better: get rid of the brackets around 1:0.1:10, and you'll be
> 
> > that
> > much more impressed.
> > 
> > --Tim

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Fred]

Maybe my array is too small to see a difference, but if I increase the size 
I will lack of RAM ;)

julia> x = 1:0.1:100
1.0:0.1:1.0e6

julia> @time searchsorted(x, 8.22)
  0.045590 seconds (33.21 k allocations: 1.535 MB)
74:73

julia> @time searchsorted(x, 8.22)
  0.05 seconds (8 allocations: 288 bytes)
74:73

julia> @time searchsorted(x, 8.22)
  0.05 seconds (8 allocations: 288 bytes)
74:73

julia> @time closest_index(x,8.22)
  0.103219 seconds (4.37 k allocations: 222.884 KB)
73

julia> @time closest_index(x,8.22)
  0.095684 seconds (4 allocations: 160 bytes)
73

julia> @time dicotomy(x, 8.22)
  0.009142 seconds (3.45 k allocations: 173.973 KB)
(73,74)

julia> @time dicotomy(x, 8.22)
  0.05 seconds (5 allocations: 192 bytes)
(73,74)

julia> @time dicotomy(x, 8.22)
  0.04 seconds (5 allocations: 192 bytes)
(73,74)



Even better: get rid of the brackets around 1:0.1:10, and you'll be 
> that 
> much more impressed. 
>
> --Tim 
>
>

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Tim Holy]

Even better: get rid of the brackets around 1:0.1:10, and you'll be that 
much more impressed.

--Tim

On Sunday, April 10, 2016 07:16:16 AM Fred wrote:
> Hi,
> 
> I post here my best solution taking advantage that the array is sorted. I
> expected to be a lot much faster than other solutions, but not really.
> I am very impressed by the speed of searchsorted
> 
> 
> x = [1:0.1:100]
> val = 8.22
> 
> function dicotomy(x, val)
>   a = start(eachindex(x))
>   b = length(x)
>   j = length(x)
>   dxbest = abs(x[a]-val)
>   dx = dxbest
> 
>   while true
> dx < dxbest ? dxbest = dx : 1
> j = round(Int,(a+b)/2)
> dx = x[j]-val
> x[j]-val < 0 ? a = j : b = j
> abs(a-b) < 2 && break
>   end
>   return a,b
> end
> 
> @time dicotomy(x, 8.22)
>  0.04 seconds (5 allocations: 192 bytes)
> (73,74)
> 
> 
> @time searchsorted(x, 8.22)
>   0.05 seconds (7 allocations: 240 bytes)
> 
>  @time closest_index(x,8.22)
>   0.027618 seconds (4 allocations: 160 bytes)
> 73

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Fred]

Hi,

I post here my best solution taking advantage that the array is sorted. I 
expected that solution to be a lot much faster than other solutions, but 
not really.
Indeed I am very impressed by the speed of searchsorted
 :

x = [1:0.1:100]
val = 8.22

function dicotomy(x, val)
  a = start(eachindex(x))
  b = length(x)
  j = length(x)
  dxbest = abs(x[a]-val)
  dx = dxbest

  while true
dx < dxbest ? dxbest = dx : 1
j = round(Int,(a+b)/2)
dx = x[j]-val
x[j]-val < 0 ? a = j : b = j
abs(a-b) < 2 && break
  end
  return a,b
end

@time dicotomy(x, 8.22)
 0.04 seconds (5 allocations: 192 bytes)
(73,74)


@time searchsorted(x, 8.22)
  0.05 seconds (7 allocations: 240 bytes)

@time closest_index(x,8.22)
  0.027618 seconds (4 allocations: 160 bytes)
73

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Fred]

Hi,

I post here my best solution taking advantage that the array is sorted. I 
expected to be a lot much faster than other solutions, but not really.
I am very impressed by the speed of searchsorted
 :

x = [1:0.1:100]
val = 8.22

function dicotomy(x, val)
  a = start(eachindex(x))
  b = length(x)
  j = length(x)
  dxbest = abs(x[a]-val)
  dx = dxbest

  while true
dx < dxbest ? dxbest = dx : 1
j = round(Int,(a+b)/2)
dx = x[j]-val
x[j]-val < 0 ? a = j : b = j
abs(a-b) < 2 && break
  end
  return a,b
end

@time dicotomy(x, 8.22)
 0.04 seconds (5 allocations: 192 bytes)
(73,74)


@time searchsorted(x, 8.22)
  0.05 seconds (7 allocations: 240 bytes)

 @time closest_index(x,8.22)
  0.027618 seconds (4 allocations: 160 bytes)
73

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Mauro]

On Sun, 2016-04-10 at 15:24, Fred  wrote:
> That's true ! But why a loop is faster in a function ? :)

Check out:
http://docs.julialang.org/en/release-0.4/manual/performance-tips/#avoid-global-variables

>>
>> I seem to recall that your example loop was not in a function(?)  If so,
>> that makes it lots slower.
>>
>>

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Fred]

That's true ! But why a loop is faster in a function ? :)

>
> I seem to recall that your example loop was not in a function(?)  If so, 
> that makes it lots slower. 
>
>

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Mauro]

> I tested my loop monre than 2 times as it is written in my post and I have
> always the same results. The function Tim Holy posted is much faster, I
> posted the results above :)

I seem to recall that your example loop was not in a function(?)  If so,
that makes it lots slower.

>>  Probably you are doing this wrong; it shouldn't be allocating so much
>> memory.  Is your loop using global variables?  Did you remember to time it
>> twice (since the first time you call it there is compilation overhead.)
>>  Did you try the function Tim Holy posted?
>>

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Fred]

I tested my loop monre than 2 times as it is written in my post and I have 
always the same results. The function Tim Holy posted is much faster, I 
posted the results above :)


>  Probably you are doing this wrong; it shouldn't be allocating so much 
> memory.  Is your loop using global variables?  Did you remember to time it 
> twice (since the first time you call it there is compilation overhead.) 
>  Did you try the function Tim Holy posted?
>

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Steven G. Johnson]

On Sunday, April 10, 2016 at 8:30:48 AM UTC-4, Fred wrote:
>
> my loop solution :
> 0.000419 seconds (547 allocations: 708.797 KB)
> 0.02135 -> 73
>

 Probably you are doing this wrong; it shouldn't be allocating so much 
memory.  Is your loop using global variables?  Did you remember to time it 
twice (since the first time you call it there is compilation overhead.) 
 Did you try the function Tim Holy posted?

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Fred]

 Thank you very much Mauro !  searchsorted is the simplest solution and one 
of the fastest but it gives two indices so another comparison is needed to 
find the closest value :

@time searchsorted(x, 8.22)
  0.04 seconds (7 allocations: 240 bytes)
74:73

abs(x[73] - 8.22) > abs(x[74] - 8.22) ? i = 74 : i = 73 
73

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Fred]

Thank you very much !

I give you the results :

my loop solution :
0.000419 seconds (547 allocations: 708.797 KB)
0.02135 -> 73

 @time closest_index(x,8.22)
  0.03 seconds (4 allocations: 160 bytes)
73

@time for (i,x) in enumerate(array)...
0.000181 seconds (821 allocations: 19.953 KB)
738.20.02135

@time 
reduce((x,y)->x[2](x,abs(y-8.22)),1:length(x),x))
  0.005890 seconds (892 allocations: 24.617 KB)

Of course in my particular situation the array is sorted, so in that case I 
although think about using dichotomy

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Mauro]

If your array is sorted, as your example suggests, there maybe faster
methods, binary search comes to mind (implemented in searchsorted).
Also, if the array is unsorted but you need to look up many values, it
might be worth sorting it first.  Mauro

On Sun, 2016-04-10 at 13:40, Fred  wrote:
> Hi,
>
> I am looking for the most efficient (fastest) way to find the indice of the
> element with the nearest value of a float in an array.
>
> x = [1:0.1:10]
>
> julia> x
> 91-element Array{Float64,1}:
>  1.0
>  1.1
>  1.2
>  1.3
>  1.4
>  ⋮
>  9.4
>  9.5
>  9.6
>  9.7
>  9.8
>  9.9
> 10.0
>
> It is very easy to find the indice of an exact value of x, for example 8.2
>
> julia> find(x .== 8.2)
> 1-element Array{Int64,1}:
> 73
>
> But if I want the indice of the closest value of 8.22
>
> julia> minimum(abs(x-8.22))
> 0.02135
>
> julia> find(x .== minimum(abs(x-8.22)))
> 0-element Array{Int64,1}
>
>
> Of course it is easy to do that with a loop but is it the fastest solution ?
>
> min_i = 0
> min_x = 1.0
>
> for i=[1:length(x)]
>e = abs(collect(x)[i] - 8.22)
>if e < min_x
>  min_x = e
>  min_i = i
>end
> end
>
> println(min_x, " -> ", min_i)
> 0.02135 -> 73
>
>
> Thanks for your comments !

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Erik Schnetter]

Fred

Yes, the fastest way is a loop. (It might be possible to extend e.g.
`minimum` by a "predicate" argument, but that would require a change
to the base library.)

You would write the loop slightly differently, though:
```Julia
mini = 0
minx = 0.0
mindx = typemax(Float64)
for (i,x) in enumerate(array)
dx = abs(x - x0)
if dx < mindx
mini, minx, mindx = i, x, dx
end
end
mini, minx, mindx
```

This will return `imin=0` for empty inputs.

-erik



On Sun, Apr 10, 2016 at 7:40 AM, Fred  wrote:
> Hi,
>
> I am looking for the most efficient (fastest) way to find the indice of the
> element with the nearest value of a float in an array.
>
> x = [1:0.1:10]
>
> julia> x
> 91-element Array{Float64,1}:
>   1.0
>   1.1
>   1.2
>   1.3
>   1.4
>   ⋮
>   9.4
>   9.5
>   9.6
>   9.7
>   9.8
>   9.9
>  10.0
>
> It is very easy to find the indice of an exact value of x, for example 8.2
>
> julia> find(x .== 8.2)
> 1-element Array{Int64,1}:
>  73
>
> But if I want the indice of the closest value of 8.22
>
> julia> minimum(abs(x-8.22))
> 0.02135
>
> julia> find(x .== minimum(abs(x-8.22)))
> 0-element Array{Int64,1}
>
>
> Of course it is easy to do that with a loop but is it the fastest solution ?
>
> min_i = 0
> min_x = 1.0
>
>  for i=[1:length(x)]
>e = abs(collect(x)[i] - 8.22)
>if e < min_x
>min_x = e
>min_i = i
>end
>  end
>
> println(min_x, " -> ", min_i)
> 0.02135 -> 73
>
>
> Thanks for your comments !
>



-- 
Erik Schnetter 
http://www.perimeterinstitute.ca/personal/eschnetter/

Re: [julia-users] Find the indice of the element with the nearest value of a float in an array

[Tim Holy]

indmin(abs(x-val)) is easy and pretty good, but it does create two 
temporaries. Faster would be

function closest_index(x, val)
ibest = start(eachindex(x))
dxbest = abs(x[ibest]-val)
for I in eachindex(x)
dx = abs(x[I]-val)
if dx < dxbest
dxbest = dx
ibest = I
end
end
ibest
end

This should not allocate any memory and is likely the fastest. (It might be 
slightly faster with @inbounds, of course...)

It would be possible to create an indmin(f, x) that applies f to each element 
of x and returns the index of the minimum; this would be efficient in the 
development version of julia but not julia-0.4.

Best,
--Tim

On Sunday, April 10, 2016 04:40:07 AM Fred wrote:
> Hi,
> 
> I am looking for the most efficient (fastest) way to find the indice of the
> element with the nearest value of a float in an array.
> 
> x = [1:0.1:10]
> 
> julia> x
> 91-element Array{Float64,1}:
>   1.0
>   1.1
>   1.2
>   1.3
>   1.4
>   ⋮
>   9.4
>   9.5
>   9.6
>   9.7
>   9.8
>   9.9
>  10.0
> 
> It is very easy to find the indice of an exact value of x, for example 8.2
> 
> julia> find(x .== 8.2)
> 1-element Array{Int64,1}:
>  73
> 
> But if I want the indice of the closest value of 8.22
> 
> julia> minimum(abs(x-8.22))
> 0.02135
> 
> julia> find(x .== minimum(abs(x-8.22)))
> 0-element Array{Int64,1}
> 
> 
> Of course it is easy to do that with a loop but is it the fastest solution ?
> 
> min_i = 0
> min_x = 1.0
> 
>  for i=[1:length(x)]
>e = abs(collect(x)[i] - 8.22)
>if e < min_x
>min_x = e
>min_i = i
>end
>  end
> 
> println(min_x, " -> ", min_i)
> 0.02135 -> 73
> 
> 
> Thanks for your comments !