# What's the fastest way to generate \`\[1,2,....,n\]\`?

**URL:** <https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564>\
**Category:** Performance\
**Created:** [December 6, 2017, 12:02pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564 "2017-12-06T12:02:46Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [December 6, 2017, 12:02pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/1 "2017-12-06T12:02:46Z")

</div>

For an algorithm I need to generate `x = [1,2,...,n]` for a large `n` and I can’t do `x = 1:n` as I need to reassign the values in `x` so I can do something like `x[10] = x[2]`.

Currently I am doing `x=collect(1:n)` and I tested `x =[1:n...]` and they are both similar in speed. But am wondering if those are the fastest way already?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [December 6, 2017, 12:04pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/2 "2017-12-06T12:04:06Z")

</div>

Perhaps `Array(1:10)`? The speed should be the same though.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [December 6, 2017, 12:19pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/4 "2017-12-06T12:19:29Z")

</div>

For `collect` and `Array` in `v0.6.1`, it is almost the same:

```julia
using BenchmarkTools
f1(n) = Array(1:n)
f2(n) = collect(1:n)
n = 1_000_000

julia> @benchmark f1($n)
BenchmarkTools.Trial: 
  memory estimate: 7.63 MiB
  allocs estimate: 3
  --------------
  minimum time: 514.845 μs (0.00% GC)
  median time: 1.730 ms (0.00% GC)
  mean time: 1.729 ms (28.30% GC)
  maximum time: 5.186 ms (64.53% GC)
  --------------
  samples: 2878
  evals/sample: 1

julia> @benchmark f2($n)
BenchmarkTools.Trial: 
  memory estimate: 7.63 MiB
  allocs estimate: 3
  --------------
  minimum time: 407.858 μs (0.00% GC)
  median time: 579.133 μs (0.00% GC)
  mean time: 808.760 μs (27.26% GC)
  maximum time: 7.762 ms (57.44% GC)
  --------------
  samples: 6156
  evals/sample: 1

```

Preallocating and reusing `x` will save you a bit.

---

<div class="post-metadata">

**Author:** ![harven](https://avatars.discourse-cdn.com/v4/letter/h/3da27b/32.png) [@harven](https://discourse.julialang.org/u/harven)\
**Post date:** [December 6, 2017, 12:45pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/5 "2017-12-06T12:45:43Z")

</div>

```
  [1:10;]

```

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [December 6, 2017, 12:49pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/6 "2017-12-06T12:49:31Z")

</div>

Why would that be faster? You are generating 5 random numbers that you then throw away and then fill the array with what you actually want.

---

<div class="post-metadata">

**Author:** ![yakir12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yakir12/32/297_2.png) [@yakir12](https://discourse.julialang.org/u/yakir12)\
**Post date:** [December 6, 2017, 12:56pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/7 "2017-12-06T12:56:02Z")

</div>

OK, reread it 5 times now. I misunderstood. Removing comment as to keep this clean.

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [December 6, 2017, 2:15pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/8 "2017-12-06T14:15:33Z")

</div>

Will [lazy.jl](https://github.com/MikeInnes/Lazy.jl) suit this purpose?

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [December 6, 2017, 7:50pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/9 "2017-12-06T19:50:02Z")

</div>

Because [your question on SO](https://stackoverflow.com/questions/47491713/julia-best-way-to-sample-from-successively-shrinking-range) I think you probably want to have array with 2 billion elements. And that you like some concrete problem to solve.

I am just curious. If you cannot use something like `array(n) = n` instead of `array = [1:2^31...]` then you probably need to change these values.

But are you planning shrinking this array with `deleteat!` or something similar?

Maybe you could set array by init values: `array = zeros(2^31)` (which has to be quick) and use something like `getvalue(index) = array[index] == 0 ? index : array[index]` if you don’t need to look at values too often.

Don’t you want describe your problem in gist or blog (or here if it is not too long) to help us understand what to optimize?

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [December 6, 2017, 8:04pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/10 "2017-12-06T20:04:34Z")

</div>

It’s actually something different to SO post now. Basically I am trying to  
create an algorithm to sort a vector and produce its sortperm at the same  
time. To start the algo I need an index vector from 1:n which I then  
permute.

Anyway I think collect(v) is pretty fast but just wanted to make sure

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [December 6, 2017, 9:32pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/11 "2017-12-06T21:32:17Z")

</div>

@benchmark zeros(Int64, $n) # I am surprised - this is really not faster?

---

<div class="post-metadata">

**Author:** ![ZacLN](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zacln/32/2748_2.png) [@ZacLN](https://discourse.julialang.org/u/ZacLN)\
**Post date:** [December 6, 2017, 9:57pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/12 "2017-12-06T21:57:01Z")

</div>

Maybe use a dict storing all all elements where xi !=I ?

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [December 6, 2017, 11:27pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/13 "2017-12-06T23:27:59Z")

</div>

> [@Liso](#):
>
> @benchmark zeros(Int64, $n)

```julia
using BenchmarkTools
function genn(n)
    x = zeros(Int,n)
    x .= 1:n
    x
end
@benchmark genn(100_000_000)

function genn1(n)
    collect(1:n)
end
@benchmark genn1(100_000_000)

```

got roughly the same results

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [December 7, 2017, 12:30am UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/14 "2017-12-07T00:30:06Z")

</div>

If you can use `Int32`, it might be faster.

---

<div class="post-metadata">

**Author:** ![Ralph\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ralph_smith/32/10344_2.png) [@Ralph\_Smith](https://discourse.julialang.org/u/Ralph_Smith)\
**Post date:** [December 7, 2017, 4:34am UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/15 "2017-12-07T04:34:19Z")

</div>

Indeed.

```julia
using Base.Threads
function fcollect(N,T=Int)
    nt = nthreads()
    n,r = divrem(N,nt)
    a = Vector{T}(N)
    @threads for i=1:nt
        ioff = (i-1)*n
        nn = ifelse(i == nt, n+r, n)
        @inbounds for j=1:nn
            a[ioff+j] = ioff+j
        end
    end
    a
end

```

This is twice as fast for `T=Int32` as for `T=Int64`, and both are substantially faster than `collect(1:N)` with several threads. But it’s still a factor of 2 under the memory bandwidth limit (on my system, at least) so the field is still open.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [December 7, 2017, 4:44am UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/16 "2017-12-07T04:44:23Z")

</div>

Wow! This is amazing

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [December 8, 2017, 3:00pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/17 "2017-12-08T15:00:53Z")

</div>

In the future, it would be nice to do this threading automatically at least in simple cases. Should be doable once threading is more solid and turned on by default.

---

<div class="post-metadata">

**Author:** ![mkborregaard](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkborregaard/32/556_2.png) [@mkborregaard](https://discourse.julialang.org/u/mkborregaard)\
**Post date:** [December 8, 2017, 6:51pm UTC](https://discourse.julialang.org/t/whats-the-fastest-way-to-generate-1-2-n/7564/18 "2017-12-08T18:51:52Z")

</div>

It’d be great if collect(1:n) ends up as the fastest implementation of this.