21
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • $\begingroup$ Yes, please do not move the goal posts; post a new question if you need an extention. $\endgroup$ – Mr.Wizard♦ Aug 13 '13 at 8:39
  • $\begingroup$ Sorry, I will edit the question again. $\endgroup$ – ZKT Aug 13 '13 at 8:40
  • $\begingroup$ Where's your question about that matrix? :) $\endgroup$ – Kuba♦ Aug 14 '13 at 6:18
19
$\begingroup$

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. PackedArrays 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 PackedArrays 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 PackedArrays, 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 PackedArrays. 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
| improve this answer | |
$\endgroup$
  • $\begingroup$ I think it is a good habit to try to optimize code even if it is not measurable for particular case. It can save a lot of time in the future. :) ("bit faster" is an unacceptable statement, you should add some tests :)) $\endgroup$ – Kuba♦ Aug 13 '13 at 8:06
  • $\begingroup$ @Kuba ah yes, I am glad you asked me. Indeed it seems the generation of the list is not faster at all! If you include taking the Total of the list, my solution is only slightly faster. $\endgroup$ – Jacob Akkerboom Aug 13 '13 at 8:19
  • $\begingroup$ I usualy do not post timing because I'm not sure if I'm doing it right :P For what I've tested each is equally fast except of SparseArray which is twice longer than others. (but I might be wrong :)) $\endgroup$ – Kuba♦ Aug 13 '13 at 8:22
  • 2
    $\begingroup$ @JacobAkkerboom @Kuba I think it can be sped up a little bit more by replacing Array[# x &, n] with Range[n]*x. $\endgroup$ – tom Aug 13 '13 at 9:10
  • 3
    $\begingroup$ Range[x, n x, x] will be slightly quicker still $\endgroup$ – Simon Woods Aug 13 '13 at 9:14
18
$\begingroup$

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}
| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot. I didn't know Riffle before. It helped a lot. $\endgroup$ – ZKT Aug 13 '13 at 7:21
  • $\begingroup$ ah, you added 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
  • $\begingroup$ @PinguinDirk I'm sorry :) but do not leave this, I feel like there is something shorter to achieve this. You can add this method, I find it interesting. $\endgroup$ – Kuba♦ Aug 13 '13 at 7:34
  • $\begingroup$ @ Kuba Sorry :-) $\endgroup$ – ZKT Aug 13 '13 at 7:49
  • $\begingroup$ Your answer is very instructive :). Riffling Sequences is a great technique :). $\endgroup$ – Jacob Akkerboom Aug 13 '13 at 8:00
11
$\begingroup$

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}

| improve this answer | |
$\endgroup$
  • $\begingroup$ @image_doctor Thanks a lot for your answer. This is much simpler :-). $\endgroup$ – ZKT Aug 13 '13 at 7:50
  • $\begingroup$ @Nasser Thank you, sometimes I think too much in sets! $\endgroup$ – image_doctor Aug 13 '13 at 7:50
  • $\begingroup$ And the pure function is a bit faster than Table :-) $\endgroup$ – Öskå Aug 13 '13 at 7:52
  • $\begingroup$ @PinguinDirk I've told you :). I was trying to gain speed but I've failed and Table is way more handy :) +1 $\endgroup$ – Kuba♦ Aug 13 '13 at 7:56
  • $\begingroup$ Nice edit :) You may want to replace Mod with Divisible[n,3]. $\endgroup$ – Kuba♦ Aug 13 '13 at 8:19
8
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ I do not know if you have seen chyanog's answer, so I'm putting the comment :) $\endgroup$ – Kuba♦ Aug 13 '13 at 10:53
  • $\begingroup$ @Kuba You're right, I missed it. He just got +1 for creativity, however as written is it fairly slow: 2.761 on my packed test and 7.411 on my unpackable test. $\endgroup$ – Mr.Wizard♦ Aug 13 '13 at 11:19
  • 2
    $\begingroup$ FYI your second line is slightly faster than the first here, even on packable data (version 9) $\endgroup$ – Simon Woods Aug 13 '13 at 11:49
  • $\begingroup$ @Simon Thanks for the info. Out of curiosity did you see 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
  • $\begingroup$ Thinking alike again! I came up with the same ArrayPad solution too :-) $\endgroup$ – Simon Woods Aug 13 '13 at 12:44
3
$\begingroup$ 
(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}*)
| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ this is good but strangely kernel doesn't use packed array to achieve it. PackedArrayQ returns false. $\endgroup$ – Rorschach Aug 31 '13 at 16:07
0
$\begingroup$

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}

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.