I need to construct a vector similar to:
v[x_]:={0, 0, x, 0, 0, 2*x, 0, 0, 3*x, ....., 0, 0, n*x};
where n=10^9
. How can I make such a vector wisely?
I need to construct a vector similar to:
v[x_]:={0, 0, x, 0, 0, 2*x, 0, 0, 3*x, ....., 0, 0, n*x};
where n=10^9
. How can I make such a vector wisely?
When n is large and x is known, using a PackedArray may be a good option.
ar3=ConstantArray[0,3n];
ar3[[3;;;;3]]=Range[x, n x, x];
ar3
To see that the result is a PackedArray
, we see that
<< Developer`;
PackedArrayQ[ar]
True
Whereas for Kuba's last array we would have False
(even if x has a value). Note that ConstantArray
also produces a PackedArray
.
Whether this is useful really depends on what you want to do with the List
. PackedArray
s take up less space in memory, which is an advantage, but they probably take up more space than a SparseArray
(in this case). Computations using PackedArray
s can be much faster as well.
Some timings/comparisons
I mainly compare my code with Kuba's MapAt
answer. I also compare with my original answer, found further below.
x = 5;
i = 0;
n = 1000000;
(
ar = ConstantArray[0, 3 n];
Do[
ar[[3 i]] = i x
,
{i, 1, n}
];
ar) // Timing // First
(ar2 = MapAt[(++i; i x) &, ConstantArray[0, 3 n], 3 ;; ;; 3]) //
Timing // First
(ar3 = ConstantArray[0, 3 n];
ar3[[3 ;; ;; 3]] = Range[x, n x, x];
ar3
) // Timing // First
3.125590
3.139499
0.048840
So generating the PackedArray
can be considerably faster, if done right. ar1 and ar3 must be the same as they are Equal
and both PackedArray
s, but I added timings/comparisons using both these anyway.
ByteCount[ar]
ByteCount[ar2]
ByteCount[ar3]
24000144
72000080
24000144
which is in favor of the PackedArray
. Doing calculations may also be faster using a PackedArray, like in the following example
ar // Total // Timing
ar2 // Total // Timing
ar3 //Total //Timing
{0.010633, 2500002500000}
{0.629586, 2500002500000}
{0.012352, 2500002500000}
Original answer
Note: It now turns out this use of Do is not so nice
This is very similar to Kuba's answer with MapAt
. But I think Do
works better with PackedArray
s. The following gives a "list" of the required form.
n = 500;
ar = ConstantArray[0, 3 n];
Do[
ar[[3 i]] = i x
,
{i, 1, n}
];
ar
Total
of the list, my solution is only slightly faster.
$\endgroup$
– Jacob Akkerboom
Aug 13 '13 at 8:19
SparseArray
which is twice longer than others. (but I might be wrong :))
$\endgroup$
– Kuba♦
Aug 13 '13 at 8:22
Array[# x &, n]
with Range[n]*x
.
$\endgroup$
– tom
Aug 13 '13 at 9:10
Range[x, n x, x]
will be slightly quicker still
$\endgroup$
– Simon Woods
Aug 13 '13 at 9:14
There are many ways, for example:
n = 5;
l = SparseArray[i_?(Divisible[#, 3] &) -> i/3 x, {3n}, 0]
SparseArray[<5>,{15}]
List @@ l
{0, 0, x, 0, 0, 2 x, 0, 0, 3 x, 0, 0, 4 x, 0, 0, 5 x}
(*earlier Array[# x &, n], `Range thanks to Simon Woods's, tom's and Mr. Wizard's comment*)
Riffle[Range[x, n x, x],
Hold@Sequence[0, 0]
, {1, -2, 2}] // ReleaseHold
{0, 0, x, 0, 0, 2 x, 0, 0, 3 x, 0, 0, 4 x, 0, 0, 5 x}
i = 0;
MapAt[(++i; i x) &, ConstantArray[0, 3 n], 3 ;; ;; 3]
{0, 0, x, 0, 0, 2 x, 0, 0, 3 x, 0, 0, 4 x, 0, 0, 5 x}
Riffle
before. It helped a lot.
$\endgroup$
– ZKT
Aug 13 '13 at 7:21
SparseArray
... too early in the morning for me, deleted my answer (I did SparseArray[3 Range[n] -> Range[n]] x
), ByteCount
is considerably smaller than in plain vectors
$\endgroup$
– Pinguin Dirk
Aug 13 '13 at 7:31
Sequences
is a great technique :).
$\endgroup$
– Jacob Akkerboom
Aug 13 '13 at 8:00
In Memory:
Table is handy.
v[x_, n_] := Flatten@Table[{0, 0, x i}, {i,n}]
v[x,5]
{0, 0, x, 0, 0, 2 x, 0, 0, 3 x, 0, 0, 4 x, 0, 0, 5 x}
Or
{0, 0, x #} & /@ Range@5 // Flatten
Minimal Memory
Here is an interesting approach if you want to access very large arrays without the memory overhead, create a function to return elements from an endless list.
f[n_Integer] := If[Divisible[n, 3], n/3 x, 0]
And in use:
Obtain the 6th value of the table.
f[6]
2 x
Obtain a range of values:
f /@ Range[1, 10]
{0, 0, x, 0, 0, 2 x, 0, 0, 3 x, 0}
Obtain the values for very distant parts of list:
f /@ Range[10^30, 10^30 + 10]
{0, 0, 333333333333333333333333333334 x, 0, 0, 333333333333333333333333333335 x, 0, 0, 333333333333333333333333333336 x, 0, 0}
Or from a disjoint unordered range of values:
f /@ {1, 45, 27, 10^30, 6, 10^100 + 2}
{0, 15 x, 9 x, 0, 2 x, 333333333333333333333333333333333333333333333333333333333333333333333\ 3333333333333333333333333333334 x}
Listable
It might be slightly more convenient to make the function, f
, Listable
.
SetAttributes[f, Listable]
Allowing constructions of the form:
f@Range[10, 20]
{0, 0, 4 x, 0, 0, 5 x, 0, 0, 6 x, 0, 0}
Table
:-)
$\endgroup$
– Öskå
Aug 13 '13 at 7:52
Table
is way more handy :) +1
$\endgroup$
– Kuba♦
Aug 13 '13 at 7:56
Mod
with Divisible[n,3]
.
$\endgroup$
– Kuba♦
Aug 13 '13 at 8:19
After testing a number of different methods I have found this code to be the fastest on packable data:
Flatten[ArrayPad[{Range[x, x n, x]}, {{2, 0}, 0}]\[Transpose]]
And this fastest on unpackable data:
Module[{rs = ConstantArray[0, 3 n]}, rs[[Range[3, 3 n, 3]]] = Range[x, x n, x]; rs]
SparseArray generation seems to be the fastest with this form but the memory saving is minor and the speed is inferior:
SparseArray[Range[3, 3 n, 3] -> Range[x, x n, x]]
Here are timings, in version 7, for these as well as other methods that did not fare as well:
(timeAvg
may be found in many posts on this site.)
Packable data:
x = 7; (* packable with 0 *)
n = 5000000;
Flatten[ArrayPad[{Range[x, x n, x]}, {{2, 0}, 0}]\[Transpose]] // timeAvg
Module[{rs = ConstantArray[0, 3 n]}, rs[[Range[3, 3 n, 3]]] = Range[x, x n, x]; rs] // timeAvg
Riffle[ConstantArray[0, 2 n], Range[x, x n, x], {3, -1, 3}] // timeAvg
Fold[Riffle[#, 0, {1, -2, #2}] &, Range[x, x n, x], {2, 3}] // timeAvg
Flatten@PadLeft[({Range[x, x n, x]}\[Transpose]), {n, 3}] // timeAvg
Flatten@Drop[ArrayPad[({Range[x, x n, x]}\[Transpose]), {2, 0}], 2] // timeAvg
Flatten@ArrayPad[({Range[x, x n, x]}\[Transpose]), {0, {2, 0}}] // timeAvg
ArrayPad[{x*Range@n}, {{2, 0}, 0}] ~Flatten~ {2, 1} // timeAvg
Flatten[ArrayFlatten[{{0}, {0}, {{Range[x, x n, x]}}}]\[Transpose]] // timeAvg
SparseArray[Range[3, 3 n, 3] -> Range[x, x n, x]] // timeAvg
Riffle[Range[x, x n, x], Unevaluated[0, 0], {1, -2, 2}] // timeAvg
0.02436
0.03496
0.078
0.1496
0.04868
0.0656
0.04804
0.1466
0.312
1.264
0.406
x = Pi; (* unpackable *)
n = 5000000;
(* same test lines as above *)
3.993
1.779
1.903
2.184
3.807
4.025
3.822
3.322
3.776
2.886
2.028
Range[x, n x, x]
in my answer before making your comment or are we thinking alike again?
$\endgroup$
– Mr.Wizard♦
Aug 13 '13 at 11:54
ArrayPad
solution too :-)
$\endgroup$
– Simon Woods
Aug 13 '13 at 12:44
(1 - Unitize[#~Mod~3]) # &@Range[15] x/3
(*{0, 0, x, 0, 0, 2 x, 0, 0, 3 x, 0, 0, 4 x, 0, 0, 5 x}*)
Clip[#~Mod~3, {1, 0}] #/3 &@Range[15] x
(*{0, 0, x, 0, 0, 2 x, 0, 0, 3 x, 0, 0, 4 x, 0, 0, 5 x}*)
There is a function meant to build structures like this -- it's called Upsample
. First you build the nonzero stuff and then upsample. So for instance:
xs = Range[10] x;
Upsample[xs, 3, 3]
{0, 0, x, 0, 0, 2 x, 0, 0, 3 x, 0, 0, 4 x, 0, 0, 5 x, 0, 0, 6 x, 0, 0, 7 x, 0, 0, 8 x, 0, 0, 9 x, 0, 0, 10 x}
The second argument of Upsample
tells how many zeros to insert between each element of the first argument. The third argument tells where to start inserting the zeros. You can also insert something other than zero using an optional fourth parameter.
PackedArrayQ
returns false.
$\endgroup$
– Rorschach
Aug 31 '13 at 16:07
Just one more way,but is not packed array,
Table[{0, 0, i x} /. List -> Sequence, {i, 1, 4}]
{0, 0, x, 0, 0, 2 x, 0, 0, 3 x, 0, 0, 4 x}