-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathbook-test.html
More file actions
3841 lines (3751 loc) · 419 KB
/
Copy pathbook-test.html
File metadata and controls
3841 lines (3751 loc) · 419 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.12: http://docutils.sourceforge.net/" />
<title>Urban Analytics and Planning</title>
<link rel="stylesheet" href="book.css" type="text/css" />
<link rel="stylesheet" href="math.css" type="text/css" />
</head>
<body>
<div class="document" id="urban-analytics-and-planning">
<h1 class="title">Urban Analytics and Planning</h1>
<h2 class="subtitle" id="copyright-c-2017-paul-waddell-waddell-berkeley-edu">Copyright (c) 2017 - Paul Waddell <<a class="reference external" href="mailto:waddell%40berkeley.edu">waddell<span>@</span>berkeley<span>.</span>edu</a>></h2>
<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<!-- Title: From Python to Numpy -->
<!-- Author: Nicolas P. Rougier -->
<!-- Date: January 2017 -->
<!-- License: Creative Commons Share-Alike Non-Commercial International 4.0 -->
<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<div class="title-logos container">
<img alt="data/cc.large.png" src="data/cc.large.png" style="width: 40px;" />
<img alt="data/by.large.png" src="data/by.large.png" style="width: 40px;" />
<img alt="data/sa.large.png" src="data/sa.large.png" style="width: 40px;" />
<img alt="data/nc.large.png" src="data/nc.large.png" style="width: 40px;" />
<div class="line-block">
<div class="line"><br /></div>
<div class="line">Latest version - January 2017</div>
<div class="line">DOI: <a class="reference external" href="http://doi.org/10.5281/zenodo.225783">10.5281/zenodo.225783</a></div>
</div>
</div>
<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<div class="title-logos container">
<img alt="data/cover.png" src="data/cover.png" style="width: 100%;" />
</div>
<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<p>There are so many great books available about cities, how they work, and how to plan them, so why write another?
This book aims to
bridge a gap between books aimed at communicating the ideas and models of neoclassical urban economics, which tend
to rely heavily on the assumptions of neoclassical economics at the expense of more nuanced consideration of equity
concerns and political economy aspects of cities and the metropolitan regions they inhabit, and to be relatively
uninformed by the emergence of massive amounts of emerging data about cities, and to gloss over the details of
urban form, design, and structure in favor of more stylized, mathematically tractable theoretical representations. The
aims of this book are to balance ideas from urban economics with consideration of equity and the structuring of
markets for real estate, labor, infrastructure and public services by cities, counties, metropolitan planning
organizations, state and federal agencies. We also seek to broaden the discussion by taking a
more modern approach to engaging theory with data. The proliferation of publicly available data and the rapid
advancement of analytical and computational methods to analyze data about cities and metropolitan areas has not, in
my assessment, been adequately integrated into an accessible, scholarly introduction to cities and metropolitan
areas. We think there is much to be gained from a balancing of theory with data, and from beginning with less strong
assumptions than those that have guided much of the development of urban economics, and instead approaching cities with a
combination of prior expectations rooted in theory, curiosity, and an open mind to be influenced by data that
is rapidly emerging about almost every dimension of urban life.</p>
<!-- **Website:** http://www.labri.fr/perso/nrougier/from-python-to-numpy -->
<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<div class="contents main-content topic" id="table-of-contents">
<p class="topic-title first"><strong>Table of Contents</strong></p>
<ul class="simple">
<li><a class="reference internal" href="#preface" id="id60">Preface</a><ul>
<li><a class="reference internal" href="#about-the-author" id="id61">About the author</a></li>
<li><a class="reference internal" href="#about-this-book" id="id62">About this book</a></li>
<li><a class="reference internal" href="#license" id="id63">License</a></li>
</ul>
</li>
<li><a class="reference internal" href="#introduction" id="id64">Introduction</a><ul>
<li><a class="reference internal" href="#simple-example" id="id65">Simple example</a></li>
<li><a class="reference internal" href="#readability-vs-speed" id="id66">Readability vs speed</a></li>
</ul>
</li>
<li><a class="reference internal" href="#anatomy-of-an-array" id="id67">Anatomy of an array</a><ul>
<li><a class="reference internal" href="#id3" id="id68">Introduction</a></li>
<li><a class="reference internal" href="#memory-layout" id="id69">Memory layout</a></li>
<li><a class="reference internal" href="#views-and-copies" id="id70">Views and copies</a></li>
<li><a class="reference internal" href="#conclusion" id="id71">Conclusion</a></li>
</ul>
</li>
<li><a class="reference internal" href="#code-vectorization" id="id72">Code vectorization</a><ul>
<li><a class="reference internal" href="#id5" id="id73">Introduction</a></li>
<li><a class="reference internal" href="#uniform-vectorization" id="id74">Uniform vectorization</a></li>
<li><a class="reference internal" href="#temporal-vectorization" id="id75">Temporal vectorization</a></li>
<li><a class="reference internal" href="#spatial-vectorization" id="id76">Spatial vectorization</a></li>
<li><a class="reference internal" href="#id17" id="id77">Conclusion</a></li>
</ul>
</li>
<li><a class="reference internal" href="#problem-vectorization" id="id78">Problem vectorization</a><ul>
<li><a class="reference internal" href="#id19" id="id79">Introduction</a></li>
<li><a class="reference internal" href="#path-finding" id="id80">Path finding</a></li>
<li><a class="reference internal" href="#fluid-dynamics" id="id81">Fluid Dynamics</a></li>
<li><a class="reference internal" href="#blue-noise-sampling" id="id82">Blue noise sampling</a></li>
<li><a class="reference internal" href="#id27" id="id83">Conclusion</a></li>
</ul>
</li>
<li><a class="reference internal" href="#custom-vectorization" id="id84">Custom vectorization</a><ul>
<li><a class="reference internal" href="#id29" id="id85">Introduction</a></li>
<li><a class="reference internal" href="#typed-list" id="id86">Typed list</a></li>
<li><a class="reference internal" href="#memory-aware-array" id="id87">Memory aware array</a></li>
<li><a class="reference internal" href="#id36" id="id88">Conclusion</a></li>
</ul>
</li>
<li><a class="reference internal" href="#beyond-numpy" id="id89">Beyond Numpy</a><ul>
<li><a class="reference internal" href="#back-to-python" id="id90">Back to Python</a></li>
<li><a class="reference internal" href="#numpy-co" id="id91">Numpy & co</a></li>
<li><a class="reference internal" href="#scipy-co" id="id92">Scipy & co</a></li>
<li><a class="reference internal" href="#id52" id="id93">Conclusion</a></li>
</ul>
</li>
<li><a class="reference internal" href="#id53" id="id94">Conclusion</a></li>
<li><a class="reference internal" href="#quick-references" id="id95">Quick References</a><ul>
<li><a class="reference internal" href="#id56" id="id96">Data type</a></li>
<li><a class="reference internal" href="#id57" id="id97">Creation</a></li>
<li><a class="reference internal" href="#id58" id="id98">Indexing</a></li>
<li><a class="reference internal" href="#reshaping" id="id99">Reshaping</a></li>
<li><a class="reference internal" href="#broadcasting" id="id100">Broadcasting</a></li>
</ul>
</li>
<li><a class="reference internal" href="#bibliography" id="id101">Bibliography</a><ul>
<li><a class="reference internal" href="#tutorials" id="id102">Tutorials</a></li>
<li><a class="reference internal" href="#articles" id="id103">Articles</a></li>
<li><a class="reference internal" href="#books" id="id104">Books</a></li>
</ul>
</li>
</ul>
</div>
<div class="line-block">
<div class="line"><br /></div>
<div class="line"><br /></div>
</div>
<p><strong>Disclaimer:</strong> All external pictures should have associated credits. If there
are missing credits, please tell me, I will correct it. Similarly, all excerpts
should be sourced (wikipedia mostly). If not, this is an error and I will
correct it as soon as you tell me.</p>
<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<div class="section" id="preface">
<h1><a class="toc-backref" href="#table-of-contents">Preface</a></h1>
<div class="contents local topic" id="contents">
<p class="topic-title first"><strong>Contents</strong></p>
<ul class="simple">
<li><a class="reference internal" href="#about-the-author" id="id105">About the author</a></li>
<li><a class="reference internal" href="#about-this-book" id="id106">About this book</a><ul>
<li><a class="reference internal" href="#prerequisites" id="id107">Prerequisites</a></li>
<li><a class="reference internal" href="#conventions" id="id108">Conventions</a></li>
<li><a class="reference internal" href="#how-to-contribute" id="id109">How to contribute</a></li>
<li><a class="reference internal" href="#publishing" id="id110">Publishing</a></li>
</ul>
</li>
<li><a class="reference internal" href="#license" id="id111">License</a></li>
</ul>
</div>
<div class="section" id="about-the-author">
<h2><a class="toc-backref" href="#contents">About the author</a></h2>
<p><code>Paul Waddell</code> is a professor of city and regional planning at the University
of California, Berkeley. His research and teaching focus on planning and modeling
cities, with particular emphasis on the interactive impacts of of land use regulations and
investment in transportation and other infrastructure.</p>
</div>
<div class="section" id="about-this-book">
<h2><a class="toc-backref" href="#contents">About this book</a></h2>
<p>This book has been written in <a class="reference external" href="http://docutils.sourceforge.net/rst.html">restructured text</a> format and generated using the
<code>rst2html.py</code> command line available from the <a class="reference external" href="http://docutils.sourceforge.net/">docutils</a> python package.</p>
<p>If you want to rebuild the html output, from the top directory, type:</p>
<pre class="code literal-block">
$ rst2html.py --link-stylesheet --cloak-email-addresses \
--toc-top-backlinks --stylesheet=book.css \
--stylesheet-dirs=. book.rst book.html
</pre>
<p>The sources are available from <a class="reference external" href="https://github.com/rougier/from-python-to-numpy">https://github.com/rougier/from-python-to-numpy</a>.</p>
<div class="section" id="prerequisites">
<h3><a class="toc-backref" href="#contents">Prerequisites</a></h3>
<p>This is not a Python beginner guide and you should have an intermediate level in
Python and ideally a beginner level in numpy. If this is not the case, have
a look at the <a class="reference internal" href="#bibliography">bibliography</a> for a curated list of resources.</p>
</div>
<div class="section" id="conventions">
<h3><a class="toc-backref" href="#contents">Conventions</a></h3>
<p>We will use usual naming conventions. If not stated explicitly, each script
should import numpy, scipy and matplotlib as:</p>
<pre class="code python literal-block">
<span class="keyword namespace">import</span> <span class="name namespace">numpy</span> <span class="keyword namespace">as</span> <span class="name namespace">np</span>
<span class="keyword namespace">import</span> <span class="name namespace">scipy</span> <span class="keyword namespace">as</span> <span class="name namespace">sp</span>
<span class="keyword namespace">import</span> <span class="name namespace">matplotlib.pyplot</span> <span class="keyword namespace">as</span> <span class="name namespace">plt</span>
</pre>
<p>We'll use up-to-date versions (at the date of writing, i.e. January, 2017) of the
different packages:</p>
<table border="1" class="docutils">
<colgroup>
<col width="55%" />
<col width="45%" />
</colgroup>
<thead valign="bottom">
<tr><th class="head">Packages</th>
<th class="head">Version</th>
</tr>
</thead>
<tbody valign="top">
<tr><td>Python</td>
<td>3.5.2</td>
</tr>
<tr><td>Numpy</td>
<td>1.11.2</td>
</tr>
<tr><td>Scipy</td>
<td>0.18.1</td>
</tr>
<tr><td>Matplotlib</td>
<td>1.5.3</td>
</tr>
</tbody>
</table>
</div>
<div class="section" id="how-to-contribute">
<h3><a class="toc-backref" href="#contents">How to contribute</a></h3>
<p>If you want to contribute to this book, you can:</p>
<ul class="simple">
<li>Review chapters (please contact me)</li>
<li>Report issues (<a class="reference external" href="https://github.com/rougier/from-python-to-numpy/issues">https://github.com/rougier/from-python-to-numpy/issues</a>)</li>
<li>Suggest improvements (<a class="reference external" href="https://github.com/rougier/from-python-to-numpy/pulls">https://github.com/rougier/from-python-to-numpy/pulls</a>)</li>
<li>Correct English (<a class="reference external" href="https://github.com/rougier/from-python-to-numpy/issues">https://github.com/rougier/from-python-to-numpy/issues</a>)</li>
<li>Design a better and more responsive html template for the book.</li>
<li>Star the project (<a class="reference external" href="https://github.com/rougier/from-python-to-numpy">https://github.com/rougier/from-python-to-numpy</a>)</li>
</ul>
</div>
<div class="section" id="publishing">
<h3><a class="toc-backref" href="#contents">Publishing</a></h3>
<p>If you're an editor interested in publishing this book, you can <a class="reference external" href="mailto:Nicolas.Rougier%40inria.fr">contact me</a> if you agree to have this version and all
subsequent versions open access (i.e. online at <a class="reference external" href="http://www.labri.fr/perso/nrougier/from-python-to-numpy">this address</a>), you know how to
deal with <a class="reference external" href="http://docutils.sourceforge.net/rst.html">restructured text</a> (Word
is not an option), you provide a real added-value as well as supporting
services, and more importantly, you have a truly amazing latex book template
(and be warned that I'm a bit picky about typography & design: <a class="reference external" href="https://www.edwardtufte.com/tufte/">Edward Tufte</a> is my hero). Still here?</p>
</div>
</div>
<div class="section" id="license">
<h2><a class="toc-backref" href="#contents">License</a></h2>
<p><strong>Book</strong></p>
<p>This work is licensed under a <a class="reference external" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">Creative Commons Attribution-Non Commercial-Share
Alike 4.0 International License</a>. You are free to:</p>
<ul class="simple">
<li><strong>Share</strong> — copy and redistribute the material in any medium or format</li>
<li><strong>Adapt</strong> — remix, transform, and build upon the material</li>
</ul>
<p>The licensor cannot revoke these freedoms as long as you follow the license terms.</p>
<p><strong>Code</strong></p>
<p>The code is licensed under the <a class="reference external" href="LICENSE-code.txt">OSI-approved BSD 2-Clause License</a>.</p>
<!-- - - - Links - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
<!-- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -->
</div>
</div>
<div class="section" id="introduction">
<h1><a class="toc-backref" href="#table-of-contents">Introduction</a></h1>
<div class="contents local topic" id="id1">
<p class="topic-title first"><strong>Contents</strong></p>
<ul class="simple">
<li><a class="reference internal" href="#simple-example" id="id112">Simple example</a></li>
<li><a class="reference internal" href="#readability-vs-speed" id="id113">Readability vs speed</a></li>
</ul>
</div>
<div class="section" id="simple-example">
<h2><a class="toc-backref" href="#id1">Simple example</a></h2>
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">You can execute any code below from the <a class="reference external" href="code">code</a> folder using the
regular python shell or from inside an IPython session or Jupyter notebook. In
such a case, you might want to use the magic command <code>%timeit</code> instead of the
<a class="reference external" href="code/tools.py">custom one</a> I wrote.</p>
</div>
<p>Numpy is all about vectorization. If you are familiar with Python, this is the
main difficulty you'll face because you'll need to change your way of thinking
and your new friends (among others) are named "vectors", "arrays", "views" or
"ufuncs".</p>
<p>Let's take a very simple example, random walk. One possible object oriented
approach would be to define a <code>RandomWalker</code> class and write a walk
method that would return the current position after each (random) step. It's nice,
it's readable, but it is slow:</p>
<p><strong>Object oriented approach</strong></p>
<pre class="code python literal-block">
<span class="keyword">class</span> <span class="name class">RandomWalker</span><span class="punctuation">:</span>
<span class="keyword">def</span> <span class="name function">__init__</span><span class="punctuation">(</span><span class="name builtin pseudo">self</span><span class="punctuation">):</span>
<span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">position</span> <span class="operator">=</span> <span class="literal number integer">0</span>
<span class="keyword">def</span> <span class="name function">walk</span><span class="punctuation">(</span><span class="name builtin pseudo">self</span><span class="punctuation">,</span> <span class="name">n</span><span class="punctuation">):</span>
<span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">position</span> <span class="operator">=</span> <span class="literal number integer">0</span>
<span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="name">n</span><span class="punctuation">):</span>
<span class="keyword">yield</span> <span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">position</span>
<span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">position</span> <span class="operator">+=</span> <span class="literal number integer">2</span><span class="operator">*</span><span class="name">random</span><span class="operator">.</span><span class="name">randint</span><span class="punctuation">(</span><span class="literal number integer">0</span><span class="punctuation">,</span> <span class="literal number integer">1</span><span class="punctuation">)</span> <span class="operator">-</span> <span class="literal number integer">1</span>
<span class="name">walker</span> <span class="operator">=</span> <span class="name">RandomWalker</span><span class="punctuation">()</span>
<span class="name">walk</span> <span class="operator">=</span> <span class="punctuation">[</span><span class="name">position</span> <span class="keyword">for</span> <span class="name">position</span> <span class="operator word">in</span> <span class="name">walker</span><span class="operator">.</span><span class="name">walk</span><span class="punctuation">(</span><span class="literal number integer">1000</span><span class="punctuation">)]</span>
</pre>
<p>Benchmarking gives us:</p>
<pre class="code pycon literal-block">
<span class="keyword namespace"></span><span class="generic prompt">>>> </span><span class="keyword namespace">from</span> <span class="name namespace">tools</span> <span class="keyword namespace">import</span> <span class="name">timeit</span>
<span class="generic prompt">>>> </span><span class="name">walker</span> <span class="operator">=</span> <span class="name">RandomWalker</span><span class="punctuation">()</span>
<span class="generic prompt">>>> </span><span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"[position for position in walker.walk(n=10000)]"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="generic output">10 loops, best of 3: 15.7 msec per loop</span>
</pre>
<p><strong>Functional approach</strong></p>
<p>For such a simple problem, we can probably save the class definition and
concentrate only on the walk method that computes successive positions after
each random step.</p>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">random_walk</span><span class="punctuation">(</span><span class="name">n</span><span class="punctuation">):</span>
<span class="name">position</span> <span class="operator">=</span> <span class="literal number integer">0</span>
<span class="name">walk</span> <span class="operator">=</span> <span class="punctuation">[</span><span class="name">position</span><span class="punctuation">]</span>
<span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="name">n</span><span class="punctuation">):</span>
<span class="name">position</span> <span class="operator">+=</span> <span class="literal number integer">2</span><span class="operator">*</span><span class="name">random</span><span class="operator">.</span><span class="name">randint</span><span class="punctuation">(</span><span class="literal number integer">0</span><span class="punctuation">,</span> <span class="literal number integer">1</span><span class="punctuation">)</span><span class="operator">-</span><span class="literal number integer">1</span>
<span class="name">walk</span><span class="operator">.</span><span class="name">append</span><span class="punctuation">(</span><span class="name">position</span><span class="punctuation">)</span>
<span class="keyword">return</span> <span class="name">walk</span>
<span class="name">walk</span> <span class="operator">=</span> <span class="name">random_walk</span><span class="punctuation">(</span><span class="literal number integer">1000</span><span class="punctuation">)</span>
</pre>
<p>This new method saves some CPU cycles but not that much because this function
is pretty much the same as in the object-oriented approach and the few cycles
we saved probably come from the inner Python object-oriented machinery.</p>
<pre class="code pycon literal-block">
<span class="keyword namespace"></span><span class="generic prompt">>>> </span><span class="keyword namespace">from</span> <span class="name namespace">tools</span> <span class="keyword namespace">import</span> <span class="name">timeit</span>
<span class="generic prompt">>>> </span><span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"random_walk(n=10000)"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="generic output">10 loops, best of 3: 15.6 msec per loop</span>
</pre>
<p><strong>Vectorized approach</strong></p>
<p>But we can do better using the <a class="reference external" href="https://docs.python.org/3.6/library/itertools.html">itertools</a> Python module that
offers a set of functions creating iterators for efficient looping. If we
observe that a random walk is an accumulation of steps, we can rewrite the
function as follows:</p>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">random_walk_faster</span><span class="punctuation">(</span><span class="name">n</span><span class="operator">=</span><span class="literal number integer">1000</span><span class="punctuation">):</span>
<span class="keyword namespace">from</span> <span class="name namespace">itertools</span> <span class="keyword namespace">import</span> <span class="name">accumulate</span>
<span class="name">steps</span> <span class="operator">=</span> <span class="name">random</span><span class="operator">.</span><span class="name">sample</span><span class="punctuation">([</span><span class="literal number integer">1</span><span class="punctuation">,</span> <span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">]</span><span class="operator">*</span><span class="name">n</span><span class="punctuation">,</span> <span class="name">n</span><span class="punctuation">)</span>
<span class="keyword">return</span> <span class="name builtin">list</span><span class="punctuation">(</span><span class="name">accumulate</span><span class="punctuation">(</span><span class="name">steps</span><span class="punctuation">))</span>
<span class="name">walk</span> <span class="operator">=</span> <span class="name">random_walk_faster</span><span class="punctuation">(</span><span class="literal number integer">1000</span><span class="punctuation">)</span>
</pre>
<p>In fact, we've just <em>vectorized</em> our function. Instead of looping for picking
sequential steps and add them to the current position, we first generated all the
steps at once and used the <a class="reference external" href="https://docs.python.org/3.6/library/itertools.html#itertools.accumulate">accumulate</a>
function to compute all the positions. We got rid of the loop and this makes
things faster:</p>
<pre class="code pycon literal-block">
<span class="keyword namespace"></span><span class="generic prompt">>>> </span><span class="keyword namespace">from</span> <span class="name namespace">tools</span> <span class="keyword namespace">import</span> <span class="name">timeit</span>
<span class="generic prompt">>>> </span><span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"random_walk_faster(n=10000)"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="generic output">10 loops, best of 3: 8.21 msec per loop</span>
</pre>
<p>We gained 50% of computation-time compared to the previous version, not so
bad. But the advantage of this new version is that it makes numpy vectorization
super simple. We just have to translate itertools call into numpy ones.</p>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">random_walk_fastest</span><span class="punctuation">(</span><span class="name">n</span><span class="operator">=</span><span class="literal number integer">1000</span><span class="punctuation">):</span>
<span class="name">steps</span> <span class="operator">=</span> <span class="literal number integer">2</span><span class="operator">*</span><span class="name">np</span><span class="operator">.</span><span class="name">random</span><span class="operator">.</span><span class="name">randint</span><span class="punctuation">(</span><span class="literal number integer">0</span><span class="punctuation">,</span> <span class="literal number integer">2</span><span class="punctuation">,</span> <span class="name">size</span><span class="operator">=</span><span class="name">n</span><span class="punctuation">)</span> <span class="operator">-</span> <span class="literal number integer">1</span>
<span class="keyword">return</span> <span class="name">np</span><span class="operator">.</span><span class="name">cumsum</span><span class="punctuation">(</span><span class="name">steps</span><span class="punctuation">)</span>
<span class="name">walk</span> <span class="operator">=</span> <span class="name">random_walk_fastest</span><span class="punctuation">(</span><span class="literal number integer">1000</span><span class="punctuation">)</span>
</pre>
<p>Not too difficult, but we gained a factor 500x using numpy:</p>
<pre class="code pycon literal-block">
<span class="keyword namespace"></span><span class="generic prompt">>>> </span><span class="keyword namespace">from</span> <span class="name namespace">tools</span> <span class="keyword namespace">import</span> <span class="name">timeit</span>
<span class="generic prompt">>>> </span><span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"random_walk_fastest(n=10000)"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="generic output">1000 loops, best of 3: 14 usec per loop</span>
</pre>
<p>This book is about vectorization, be it at the code or problem level. We'll
see this difference is important before looking at custom vectorization.</p>
</div>
<div class="section" id="readability-vs-speed">
<h2><a class="toc-backref" href="#id1">Readability vs speed</a></h2>
<p>Before heading to the next chapter, I would like to warn you about a potential
problem you may encounter once you'll have become familiar with numpy. It is a
very powerful library and you can make wonders with it but, most of the time,
this comes at the price of readability. If you don't comment your code at the
time of writing, you won't be able to tell what a function is doing after a few
weeks (or possibly days). For example, can you tell what the two functions
below are doing? Probably you can tell for the first one, but unlikely for the
second (or your name is <a class="reference external" href="http://stackoverflow.com/questions/7100242/python-numpy-first-occurrence-of-subarray">Jaime Fernández del Río</a>
and you don't need to read this book).</p>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">function_1</span><span class="punctuation">(</span><span class="name">seq</span><span class="punctuation">,</span> <span class="name">sub</span><span class="punctuation">):</span>
<span class="keyword">return</span> <span class="punctuation">[</span><span class="name">i</span> <span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="name builtin">len</span><span class="punctuation">(</span><span class="name">seq</span><span class="punctuation">)</span> <span class="operator">-</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">sub</span><span class="punctuation">))</span> <span class="keyword">if</span> <span class="name">seq</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">:</span><span class="name">i</span><span class="operator">+</span><span class="name builtin">len</span><span class="punctuation">(</span><span class="name">sub</span><span class="punctuation">)]</span> <span class="operator">==</span> <span class="name">sub</span><span class="punctuation">]</span>
<span class="keyword">def</span> <span class="name function">function_2</span><span class="punctuation">(</span><span class="name">seq</span><span class="punctuation">,</span> <span class="name">sub</span><span class="punctuation">):</span>
<span class="name">target</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">dot</span><span class="punctuation">(</span><span class="name">sub</span><span class="punctuation">,</span> <span class="name">sub</span><span class="punctuation">)</span>
<span class="name">candidates</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">where</span><span class="punctuation">(</span><span class="name">np</span><span class="operator">.</span><span class="name">correlate</span><span class="punctuation">(</span><span class="name">seq</span><span class="punctuation">,</span> <span class="name">sub</span><span class="punctuation">,</span> <span class="name">mode</span><span class="operator">=</span><span class="literal string single">'valid'</span><span class="punctuation">)</span> <span class="operator">==</span> <span class="name">target</span><span class="punctuation">)[</span><span class="literal number integer">0</span><span class="punctuation">]</span>
<span class="name">check</span> <span class="operator">=</span> <span class="name">candidates</span><span class="punctuation">[:,</span> <span class="name">np</span><span class="operator">.</span><span class="name">newaxis</span><span class="punctuation">]</span> <span class="operator">+</span> <span class="name">np</span><span class="operator">.</span><span class="name">arange</span><span class="punctuation">(</span><span class="name builtin">len</span><span class="punctuation">(</span><span class="name">sub</span><span class="punctuation">))</span>
<span class="name">mask</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">all</span><span class="punctuation">((</span><span class="name">np</span><span class="operator">.</span><span class="name">take</span><span class="punctuation">(</span><span class="name">seq</span><span class="punctuation">,</span> <span class="name">check</span><span class="punctuation">)</span> <span class="operator">==</span> <span class="name">sub</span><span class="punctuation">),</span> <span class="name">axis</span><span class="operator">=-</span><span class="literal number integer">1</span><span class="punctuation">)</span>
<span class="keyword">return</span> <span class="name">candidates</span><span class="punctuation">[</span><span class="name">mask</span><span class="punctuation">]</span>
</pre>
<p>As you may have guessed, the second function is the
vectorized-optimized-faster-numpy version of the first function. It is 10 times
faster than the pure Python version, but it is hardly readable.</p>
</div>
</div>
<div class="section" id="anatomy-of-an-array">
<h1><a class="toc-backref" href="#table-of-contents">Anatomy of an array</a></h1>
<div class="contents local topic" id="id2">
<p class="topic-title first"><strong>Contents</strong></p>
<ul class="simple">
<li><a class="reference internal" href="#id3" id="id114">Introduction</a></li>
<li><a class="reference internal" href="#memory-layout" id="id115">Memory layout</a></li>
<li><a class="reference internal" href="#views-and-copies" id="id116">Views and copies</a><ul>
<li><a class="reference internal" href="#direct-and-indirect-access" id="id117">Direct and indirect access</a></li>
<li><a class="reference internal" href="#temporary-copy" id="id118">Temporary copy</a></li>
</ul>
</li>
<li><a class="reference internal" href="#conclusion" id="id119">Conclusion</a></li>
</ul>
</div>
<div class="section" id="id3">
<h2><a class="toc-backref" href="#id2">Introduction</a></h2>
<p>As explained in the <a class="reference internal" href="#preface">Preface</a>, you should have a basic experience with numpy to
read this book. If this is not the case, you'd better start with a beginner
tutorial before coming back here. Consequently I'll only give here a quick
reminder on the basic anatomy of numpy arrays, especially regarding the memory
layout, view, copy and the data type. They are critical notions to
understand if you want your computation to benefit from numpy philosophy.</p>
<p>Let's consider a simple example where we want to clear all the values from an
array whose dtype is <code>np.float32</code>. How does one write it to maximize speed? The
below syntax is rather obvious (at least for those familiar with numpy) but the
above question asks to find the fastest operation.</p>
<pre class="code python literal-block">
<span class="operator">>>></span> <span class="name">Z</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">ones</span><span class="punctuation">(</span><span class="literal number integer">4</span><span class="operator">*</span><span class="literal number integer">1000000</span><span class="punctuation">,</span> <span class="name">np</span><span class="operator">.</span><span class="name">float32</span><span class="punctuation">)</span>
<span class="operator">>>></span> <span class="name">Z</span><span class="punctuation">[</span><span class="operator">...</span><span class="punctuation">]</span> <span class="operator">=</span> <span class="literal number integer">0</span>
</pre>
<p>If you look more closely at both the dtype and the size of the array, you can
observe that this array can be casted (i.e. viewed) into many other
"compatible" data types. By compatible, I mean that <code>Z.size * Z.itemsize</code> can
be divided by the new dtype itemsize.</p>
<pre class="code python literal-block">
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"Z.view(np.float16)[...] = 0"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">100</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number float">2.72</span> <span class="name">msec</span> <span class="name">per</span> <span class="name">loop</span>
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"Z.view(np.int16)[...] = 0"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">100</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number float">2.77</span> <span class="name">msec</span> <span class="name">per</span> <span class="name">loop</span>
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"Z.view(np.int32)[...] = 0"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">100</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number float">1.29</span> <span class="name">msec</span> <span class="name">per</span> <span class="name">loop</span>
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"Z.view(np.float32)[...] = 0"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">100</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number float">1.33</span> <span class="name">msec</span> <span class="name">per</span> <span class="name">loop</span>
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"Z.view(np.int64)[...] = 0"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">100</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number integer">874</span> <span class="name">usec</span> <span class="name">per</span> <span class="name">loop</span>
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"Z.view(np.float64)[...] = 0"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">100</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number integer">865</span> <span class="name">usec</span> <span class="name">per</span> <span class="name">loop</span>
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"Z.view(np.complex128)[...] = 0"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">100</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number integer">841</span> <span class="name">usec</span> <span class="name">per</span> <span class="name">loop</span>
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"Z.view(np.int8)[...] = 0"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">100</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number integer">630</span> <span class="name">usec</span> <span class="name">per</span> <span class="name">loop</span>
</pre>
<p>Interestingly enough, the obvious way of clearing all the values is not the
fastest. By casting the array into a larger data type such as <code>np.float64</code>, we
gained a 25% speed factor. But, by viewing the array as a byte array
(<code>np.int8</code>), we gained a 50% factor. The reason for such speedup are to be
found in the internal numpy machinery and the compiler optimization. This
simple example illustrates the philosophy of numpy as we'll see in the next
section below.</p>
</div>
<div class="section" id="memory-layout">
<h2><a class="toc-backref" href="#id2">Memory layout</a></h2>
<p>The <a class="reference external" href="https://docs.scipy.org/doc/numpy/reference/arrays.ndarray.html">numpy documentation</a> defines the
ndarray class very clearly:</p>
<blockquote>
<em>An instance of class ndarray consists of a contiguous one-dimensional segment
of computer memory (owned by the array, or by some other object), combined
with an indexing scheme that maps N integers into the location of an item in
the block.</em></blockquote>
<p>Said differently, an array is mostly a contiguous block of memory whose parts
can be accessed using an indexing scheme. Such indexing scheme is in turn
defined by a <a class="reference external" href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.shape.html#numpy.ndarray.shape">shape</a>
and a <a class="reference external" href="https://docs.scipy.org/doc/numpy/reference/arrays.dtypes.html">data type</a> and this is
precisely what is needed when you define a new array:</p>
<pre class="code python literal-block">
<span class="name">Z</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">arange</span><span class="punctuation">(</span><span class="literal number integer">9</span><span class="punctuation">)</span><span class="operator">.</span><span class="name">reshape</span><span class="punctuation">(</span><span class="literal number integer">3</span><span class="punctuation">,</span><span class="literal number integer">3</span><span class="punctuation">)</span><span class="operator">.</span><span class="name">astype</span><span class="punctuation">(</span><span class="name">np</span><span class="operator">.</span><span class="name">int16</span><span class="punctuation">)</span>
</pre>
<p>Here, we know that Z itemsize is 2 bytes (<code>int16</code>), the shape is (3,3) and
the number of dimensions is 2 (<code>len(Z.shape)</code>).</p>
<pre class="code pycon literal-block">
<span class="keyword"></span><span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z</span><span class="operator">.</span><span class="name">itemize</span><span class="punctuation">)</span>
<span class="generic output">2
</span><span class="keyword"></span><span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z</span><span class="operator">.</span><span class="name">shape</span><span class="punctuation">)</span>
<span class="generic output">(3, 3)
</span><span class="keyword"></span><span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z</span><span class="operator">.</span><span class="name">ndim</span><span class="punctuation">)</span>
<span class="generic output">2</span>
</pre>
<p>Furthermore and because Z is not a view, we can deduce the
<a class="reference external" href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.strides.html#numpy.ndarray.strides">strides</a> of the array that define the number of bytes to step in each dimension when traversing the array.</p>
<pre class="code pycon literal-block">
<span class="name"></span><span class="generic prompt">>>> </span><span class="name">strides</span> <span class="operator">=</span> <span class="name">Z</span><span class="operator">.</span><span class="name">shape</span><span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">]</span><span class="operator">*</span><span class="name">Z</span><span class="operator">.</span><span class="name">itemize</span><span class="punctuation">,</span> <span class="name">Z</span><span class="operator">.</span><span class="name">itemize</span>
<span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">strides</span><span class="punctuation">)</span>
<span class="generic output">(6, 2)
</span><span class="keyword"></span><span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z</span><span class="operator">.</span><span class="name">strides</span><span class="punctuation">)</span>
<span class="generic output">(6, 2)</span>
</pre>
<p>With all these information, we know how to access a specific item (designed by
an index tuple) and more precisely, how to compute the start and end offsets:</p>
<pre class="code python literal-block">
<span class="name">offset_start</span> <span class="operator">=</span> <span class="literal number integer">0</span>
<span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="name">ndim</span><span class="punctuation">):</span>
<span class="name">offset_start</span> <span class="operator">+=</span> <span class="name">strides</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">]</span><span class="operator">*</span><span class="name">index</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">]</span>
<span class="name">offset_end</span> <span class="operator">=</span> <span class="name">offset_start</span> <span class="operator">+</span> <span class="name">Z</span><span class="operator">.</span><span class="name">itemsize</span>
</pre>
<p>Let's see if this is correct using the <a class="reference external" href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.tobytes.html">tobytes</a>
conversion method:</p>
<pre class="code python literal-block">
<span class="operator">>>></span> <span class="name">Z</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">arange</span><span class="punctuation">(</span><span class="literal number integer">9</span><span class="punctuation">)</span><span class="operator">.</span><span class="name">reshape</span><span class="punctuation">(</span><span class="literal number integer">3</span><span class="punctuation">,</span><span class="literal number integer">3</span><span class="punctuation">)</span><span class="operator">.</span><span class="name">astype</span><span class="punctuation">(</span><span class="name">np</span><span class="operator">.</span><span class="name">int16</span><span class="punctuation">)</span>
<span class="operator">>>></span> <span class="name">index</span> <span class="operator">=</span> <span class="literal number integer">1</span><span class="punctuation">,</span><span class="literal number integer">1</span>
<span class="operator">>>></span> <span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z</span><span class="punctuation">[</span><span class="name">index</span><span class="punctuation">]</span><span class="operator">.</span><span class="name">tobytes</span><span class="punctuation">())</span>
<span class="name">b</span><span class="literal string single">'</span><span class="literal string escape">\x04\x00</span><span class="literal string single">'</span>
<span class="operator">>>></span> <span class="name">offset</span> <span class="operator">=</span> <span class="literal number integer">0</span>
<span class="operator">>>></span> <span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="name">Z</span><span class="operator">.</span><span class="name">ndim</span><span class="punctuation">):</span>
<span class="operator">...</span> <span class="name">offset</span> <span class="operator">+</span> <span class="operator">=</span> <span class="name">Z</span><span class="operator">.</span><span class="name">strides</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">]</span><span class="operator">*</span><span class="name">index</span><span class="punctuation">[</span><span class="name">i</span><span class="punctuation">]</span>
<span class="operator">>>></span> <span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z</span><span class="operator">.</span><span class="name">tobytes</span><span class="punctuation">()[</span><span class="name">offset_start</span><span class="punctuation">:</span><span class="name">offset_end</span><span class="punctuation">]</span>
<span class="name">b</span><span class="literal string single">'</span><span class="literal string escape">\x04\x00</span><span class="literal string single">'</span>
</pre>
<p>This array can be actually considered from different perspectives (i.e. layouts):</p>
<p><strong>Item layout</strong></p>
<pre class="code output literal-block">
shape[1]
(=3)
┌───────────┐
┌ ┌───┬───┬───┐ ┐
│ │ 0 │ 1 │ 2 │ │
│ ├───┼───┼───┤ │
shape[0] │ │ 3 │ 4 │ 5 │ │ len(Z)
(=3) │ ├───┼───┼───┤ │ (=3)
│ │ 6 │ 7 │ 8 │ │
└ └───┴───┴───┘ ┘
</pre>
<p><strong>Flattened item layout</strong></p>
<pre class="code output literal-block">
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
└───────────────────────────────────┘
Z.size
(=9)
</pre>
<p><strong>Memory layout (C order, big endian)</strong></p>
<pre class="code output literal-block">
strides[1]
(=2)
┌─────────────────────┐
┌ ┌──────────┬──────────┐ ┐
│ p+00: │ 00000000 │ 00000000 │ │
│ ├──────────┼──────────┤ │
│ p+02: │ 00000000 │ 00000001 │ │ strides[0]
│ ├──────────┼──────────┤ │ (=2x3)
│ p+04 │ 00000000 │ 00000010 │ │
│ ├──────────┼──────────┤ ┘
│ p+06 │ 00000000 │ 00000011 │
│ ├──────────┼──────────┤
Z.nbytes │ p+08: │ 00000000 │ 00000100 │
(=3x3x2) │ ├──────────┼──────────┤
│ p+10: │ 00000000 │ 00000101 │
│ ├──────────┼──────────┤
│ p+12: │ 00000000 │ 00000110 │
│ ├──────────┼──────────┤
│ p+14: │ 00000000 │ 00000111 │
│ ├──────────┼──────────┤
│ p+16: │ 00000000 │ 00001000 │
└ └──────────┴──────────┘
└─────────────────────┘
Z.itemsize
Z.dtype.itemsize
(=2)
</pre>
<p>If we now take a slice of <code>Z</code>, the result is a view of the base array <code>Z</code>:</p>
<pre class="code python literal-block">
<span class="name">V</span> <span class="operator">=</span> <span class="name">Z</span><span class="punctuation">[::</span><span class="literal number integer">2</span><span class="punctuation">,::</span><span class="literal number integer">2</span><span class="punctuation">]</span>
</pre>
<p>Such view is specified using a shape, a dtype <strong>and</strong> strides because strides
cannot be deduced anymore from the dtype and shape only:</p>
<p><strong>Item layout</strong></p>
<pre class="code output literal-block">
shape[1]
(=2)
┌───────────┐
┌ ┌───┬╌╌╌┬───┐ ┐
│ │ 0 │ │ 2 │ │ ┌───┬───┐
│ ├───┼╌╌╌┼───┤ │ │ 0 │ 2 │
shape[0] │ ╎ ╎ ╎ ╎ │ len(Z) → ├───┼───┤
(=2) │ ├───┼╌╌╌┼───┤ │ (=2) │ 6 │ 8 │
│ │ 6 │ │ 8 │ │ └───┴───┘
└ └───┴╌╌╌┴───┘ ┘
</pre>
<p><strong>Flattened item layout</strong></p>
<pre class="code output literal-block">
┌───┬╌╌╌┬───┬╌╌╌┬╌╌╌┬╌╌╌┬───┬╌╌╌┬───┐ ┌───┬───┬───┬───┐
│ 0 │ │ 2 │ ╎ ╎ │ 6 │ │ 8 │ → │ 0 │ 2 │ 6 │ 8 │
└───┴╌╌╌┴───┴╌╌╌┴╌╌╌┴╌╌╌┴───┴╌╌╌┴───┘ └───┴───┴───┴───┘
└─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘
└───┬───┘ └───┬───┘
└───────────┬───────────┘
Z.size
(=4)
</pre>
<p><strong>Memory layout (C order, big endian)</strong></p>
<pre class="code output literal-block">
┌ ┌──────────┬──────────┐ ┐ ┐
┌─┤ p+00: │ 00000000 │ 00000000 │ │ │
│ └ ├──────────┼──────────┤ │ strides[1] │
┌─┤ p+02: │ │ │ │ (=4) │
│ │ ┌ ├──────────┼──────────┤ ┘ │
│ └─┤ p+04 │ 00000000 │ 00000010 │ │
│ └ ├──────────┼──────────┤ │ strides[0]
│ p+06: │ │ │ │ (=12)
│ ├──────────┼──────────┤ │
Z.nbytes ─┤ p+08: │ │ │ │
(=8) │ ├──────────┼──────────┤ │
│ p+10: │ │ │ │
│ ┌ ├──────────┼──────────┤ ┘
│ ┌─┤ p+12: │ 00000000 │ 00000110 │
│ │ └ ├──────────┼──────────┤
└─┤ p+14: │ │ │
│ ┌ ├──────────┼──────────┤
└─┤ p+16: │ 00000000 │ 00001000 │
└ └──────────┴──────────┘
└─────────────────────┘
Z.itemsize
Z.dtype.itemsize
(=2)
</pre>
</div>
<div class="section" id="views-and-copies">
<h2><a class="toc-backref" href="#id2">Views and copies</a></h2>
<p>Views and copies are important concepts for the optimization of your numerical
computations. Even if we've already manipulated them in the previous section,
the whole story is a bit more complex.</p>
<div class="section" id="direct-and-indirect-access">
<h3><a class="toc-backref" href="#id2">Direct and indirect access</a></h3>
<p>First, we have to distinguish between <a class="reference external" href="https://docs.scipy.org/doc/numpy/user/basics.indexing.html#">indexing</a> and <a class="reference external" href="https://docs.scipy.org/doc/numpy/reference/arrays.indexing.html#advanced-indexing">fancy
indexing</a>. The first will always return a view while the second will return a
copy. This difference is important because in the first case, modifying the view
modifies the base array while this is not true in the second case:</p>
<pre class="code pycon literal-block">
<span class="name"></span><span class="generic prompt">>>> </span><span class="name">Z</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">zeros</span><span class="punctuation">(</span><span class="literal number integer">9</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">Z_view</span> <span class="operator">=</span> <span class="name">Z</span><span class="punctuation">[:</span><span class="literal number integer">3</span><span class="punctuation">]</span>
<span class="generic prompt">>>> </span><span class="name">Z_view</span><span class="punctuation">[</span><span class="operator">...</span><span class="punctuation">]</span> <span class="operator">=</span> <span class="literal number integer">1</span>
<span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z</span><span class="punctuation">)</span>
<span class="generic output">[ 1. 1. 1. 0. 0. 0. 0. 0. 0.]
</span><span class="name"></span><span class="generic prompt">>>> </span><span class="name">Z</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">zeros</span><span class="punctuation">(</span><span class="literal number integer">9</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">Z_copy</span> <span class="operator">=</span> <span class="name">Z</span><span class="punctuation">[[</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="literal number integer">2</span><span class="punctuation">]]</span>
<span class="generic prompt">>>> </span><span class="name">Z_copy</span><span class="punctuation">[</span><span class="operator">...</span><span class="punctuation">]</span> <span class="operator">=</span> <span class="literal number integer">1</span>
<span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z</span><span class="punctuation">)</span>
<span class="generic output">[ 0. 0. 0. 0. 0. 0. 0. 0. 0.]</span>
</pre>
<p>Thus, if you need fancy indexing, it's better to keep a copy of you fancy index
(especially if it was complex to compute it) and to work with it:</p>
<pre class="code pycon literal-block">
<span class="name"></span><span class="generic prompt">>>> </span><span class="name">Z</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">zeros</span><span class="punctuation">(</span><span class="literal number integer">9</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">index</span> <span class="operator">=</span> <span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="literal number integer">2</span><span class="punctuation">]</span>
<span class="generic prompt">>>> </span><span class="name">Z</span><span class="punctuation">[</span><span class="name">index</span><span class="punctuation">]</span> <span class="operator">=</span> <span class="literal number integer">1</span>
<span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z</span><span class="punctuation">)</span>
<span class="generic output">[ 1. 1. 1. 0. 0. 0. 0. 0. 0.]</span>
</pre>
<p>If you are unsure if the result of you indexing is a view or a copy, you can
check what is the <code>base</code> of your result. If it is <code>None</code>, then you result is a
copy:</p>
<pre class="code pycon literal-block">
<span class="name"></span><span class="generic prompt">>>> </span><span class="name">Z</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">random</span><span class="operator">.</span><span class="name">uniform</span><span class="punctuation">(</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">1</span><span class="punctuation">,(</span><span class="literal number integer">5</span><span class="punctuation">,,</span><span class="literal number integer">5</span><span class="punctuation">))</span>
<span class="generic prompt">>>> </span><span class="name">Z1</span> <span class="operator">=</span> <span class="name">Z</span><span class="punctuation">[:</span><span class="literal number integer">3</span><span class="punctuation">,:]</span>
<span class="generic prompt">>>> </span><span class="name">Z2</span> <span class="operator">=</span> <span class="name">Z</span><span class="punctuation">[[</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="literal number integer">2</span><span class="punctuation">],</span> <span class="punctuation">:]</span>
<span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">np</span><span class="operator">.</span><span class="name">allclose</span><span class="punctuation">(</span><span class="name">Z1</span><span class="punctuation">,</span><span class="name">Z2</span><span class="punctuation">))</span>
<span class="generic output">True
</span><span class="keyword"></span><span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z1</span><span class="operator">.</span><span class="name">base</span> <span class="operator word">is</span> <span class="name">Z</span><span class="punctuation">)</span>
<span class="generic output">True
</span><span class="keyword"></span><span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z2</span><span class="operator">.</span><span class="name">base</span> <span class="operator word">is</span> <span class="name">Z</span><span class="punctuation">)</span>
<span class="generic output">False
</span><span class="keyword"></span><span class="generic prompt">>>> </span><span class="keyword">print</span><span class="punctuation">(</span><span class="name">Z2</span><span class="operator">.</span><span class="name">base</span> <span class="operator word">is</span> <span class="name builtin pseudo">None</span><span class="punctuation">)</span>
<span class="generic output">True</span>
</pre>
<p>Note that some numpy functions return a view when possible (e.g. <a class="reference external" href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.ravel.html">ravel</a>)
while some others always return a copy (e.g. <a class="reference external" href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.flatten.html#numpy.ndarray.flatten">flatten</a>):</p>
<pre class="code pycon literal-block">
<span class="name"></span><span class="generic prompt">>>> </span><span class="name">Z</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">zeros</span><span class="punctuation">((</span><span class="literal number integer">5</span><span class="punctuation">,</span><span class="literal number integer">5</span><span class="punctuation">))</span>
<span class="generic prompt">>>> </span><span class="name">Z</span><span class="operator">.</span><span class="name">ravel</span><span class="punctuation">()</span><span class="operator">.</span><span class="name">base</span> <span class="operator word">is</span> <span class="name">Z</span>
<span class="generic output">True
</span><span class="name"></span><span class="generic prompt">>>> </span><span class="name">Z</span><span class="punctuation">[::</span><span class="literal number integer">2</span><span class="punctuation">,::</span><span class="literal number integer">2</span><span class="punctuation">]</span><span class="operator">.</span><span class="name">ravel</span><span class="punctuation">()</span><span class="operator">.</span><span class="name">base</span> <span class="operator word">is</span> <span class="name">Z</span>
<span class="generic output">False
</span><span class="name"></span><span class="generic prompt">>>> </span><span class="name">Z</span><span class="operator">.</span><span class="name">flatten</span><span class="punctuation">()</span><span class="operator">.</span><span class="name">base</span> <span class="operator word">is</span> <span class="name">Z</span>
<span class="generic output">False</span>
</pre>
</div>
<div class="section" id="temporary-copy">
<h3><a class="toc-backref" href="#id2">Temporary copy</a></h3>
<p>Copies can be made explicitly like in the previous section, but the most
general case is the implicit creation of intermediate copies. This is the case
when you are doing some arithmetic with arrays:</p>
<pre class="code pycon literal-block">
<span class="name"></span><span class="generic prompt">>>> </span><span class="name">X</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">ones</span><span class="punctuation">(</span><span class="literal number integer">10</span><span class="punctuation">,</span> <span class="name">dtype</span><span class="operator">=</span><span class="name">np</span><span class="operator">.</span><span class="name">int</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">Y</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">ones</span><span class="punctuation">(</span><span class="literal number integer">10</span><span class="punctuation">,</span> <span class="name">dtype</span><span class="operator">=</span><span class="name">np</span><span class="operator">.</span><span class="name">int</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">A</span> <span class="operator">=</span> <span class="literal number integer">2</span><span class="operator">*</span><span class="name">X</span> <span class="operator">+</span> <span class="literal number integer">2</span><span class="operator">*</span><span class="name">Y</span>
</pre>
<p>In the example above, three intermediate arrays have been created. One for
holding the result of <code>2*X</code>, one for holding the result of <code>2*Y</code> and the last
one for holding the result of <code>2*X+2*Y</code>. In this specific case, the arrays are
small enough and this does not really make a difference. However, if your
arrays are big, then you have be careful with such expression and wonder if you
can do it differently. For example, if only the final result matters and you
don't need <code>X</code> nor <code>Y</code> afterwards, an alternate solution would be:</p>
<pre class="code pycon literal-block">
<span class="name"></span><span class="generic prompt">>>> </span><span class="name">X</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">ones</span><span class="punctuation">(</span><span class="literal number integer">10</span><span class="punctuation">,</span> <span class="name">dtype</span><span class="operator">=</span><span class="name">np</span><span class="operator">.</span><span class="name">int</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">Y</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">ones</span><span class="punctuation">(</span><span class="literal number integer">10</span><span class="punctuation">,</span> <span class="name">dtype</span><span class="operator">=</span><span class="name">np</span><span class="operator">.</span><span class="name">int</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">np</span><span class="operator">.</span><span class="name">multiply</span><span class="punctuation">(</span><span class="name">X</span><span class="punctuation">,</span> <span class="literal number integer">2</span><span class="punctuation">,</span> <span class="name">out</span><span class="operator">=</span><span class="name">X</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">np</span><span class="operator">.</span><span class="name">multiply</span><span class="punctuation">(</span><span class="name">Y</span><span class="punctuation">,</span> <span class="literal number integer">2</span><span class="punctuation">,</span> <span class="name">out</span><span class="operator">=</span><span class="name">Y</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">np</span><span class="operator">.</span><span class="name">add</span><span class="punctuation">(</span><span class="name">X</span><span class="punctuation">,</span> <span class="name">Y</span><span class="punctuation">,</span> <span class="name">out</span><span class="operator">=</span><span class="name">X</span><span class="punctuation">)</span>
</pre>
<p>Using this alternate solution, no temporary array has been created. Problem is
that there are many other cases where such copies needs to be created and this
impact the performance like demonstrated on the example below:</p>
<pre class="code pycon literal-block">
<span class="name"></span><span class="generic prompt">>>> </span><span class="name">X</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">ones</span><span class="punctuation">(</span><span class="literal number integer">1000000000</span><span class="punctuation">,</span> <span class="name">dtype</span><span class="operator">=</span><span class="name">np</span><span class="operator">.</span><span class="name">int</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">Y</span> <span class="operator">=</span> <span class="name">np</span><span class="operator">.</span><span class="name">ones</span><span class="punctuation">(</span><span class="literal number integer">1000000000</span><span class="punctuation">,</span> <span class="name">dtype</span><span class="operator">=</span><span class="name">np</span><span class="operator">.</span><span class="name">int</span><span class="punctuation">)</span>
<span class="generic prompt">>>> </span><span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"X = X + 2.0*Y"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="generic output">100 loops, best of 3: 3.61 ms per loop
</span><span class="name"></span><span class="generic prompt">>>> </span><span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"X = X + 2*Y"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="generic output">100 loops, best of 3: 3.47 ms per loop
</span><span class="name"></span><span class="generic prompt">>>> </span><span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"X += 2*Y"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="generic output">100 loops, best of 3: 2.79 ms per loop
</span><span class="name"></span><span class="generic prompt">>>> </span><span class="name">np</span><span class="operator">.</span><span class="name">add</span><span class="punctuation">(</span><span class="name">X</span><span class="punctuation">,</span> <span class="name">Y</span><span class="punctuation">,</span> <span class="name">out</span><span class="operator">=</span><span class="name">X</span><span class="punctuation">),</span> <span class="name">np</span><span class="operator">.</span><span class="name">add</span><span class="punctuation">(</span><span class="name">X</span><span class="punctuation">,</span> <span class="name">Y</span><span class="punctuation">,</span> <span class="name">out</span><span class="operator">=</span><span class="name">X</span><span class="punctuation">),</span>
<span class="generic output">1000 loops, best of 3: 1.57 ms per loop</span>
</pre>
</div>
</div>
<div class="section" id="conclusion">
<h2><a class="toc-backref" href="#id2">Conclusion</a></h2>
<p>As a conclusion, we'll make an exercise. Given two vectors <code>Z1</code> and <code>Z2</code>. We
would like to know if <code>Z2</code> is a view of <code>Z1</code> and if yes, what is this view ?</p>
<pre class="code literal-block">
>>> Z1 = np.arange(10)
>>> Z2 = Z1[1:-1:2]
</pre>
<pre class="code output literal-block">
╌╌╌┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬╌╌
Z1 │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
╌╌╌┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴╌╌
╌╌╌╌╌╌╌┬───┬╌╌╌┬───┬╌╌╌┬───┬╌╌╌┬───┬╌╌╌╌╌╌╌╌╌╌
Z2 │ 1 │ │ 3 │ │ 5 │ │ 7 │
╌╌╌╌╌╌╌┴───┴╌╌╌┴───┴╌╌╌┴───┴╌╌╌┴───┴╌╌╌╌╌╌╌╌╌╌
</pre>
<p>First, we need to check if <code>Z1</code> is the base of <code>Z2</code></p>
<pre class="code literal-block">
>>> print(Z2.base is Z1)
True
</pre>
<p>At this point, we know <code>Z2</code> is a view of <code>Z1</code>, meaning <code>Z2</code> can be expressed as
<code>Z1[start:stop:step]</code>. The difficulty is to find <code>start</code>, <code>stop</code> and
<code>step</code>. For the <code>step</code>, we can use the <code>strides</code> property of any array that
gives the number of bytes to go from one element to the other in each
dimension. In our case, and because both arrays are one-dimensional, we can
directly compare the first stride only:</p>
<pre class="code literal-block">
>>> step = Z2.strides[0] // Z1.strides[0]
>>> print(step)
2
</pre>
<p>Next difficulty is to find the <code>start</code> and the <code>stop</code> indices. To do this, we
can take advantage of the <code>byte_bounds</code> method that returns a pointer to the
end-points of an array.</p>
<pre class="code output literal-block">
byte_bounds(Z1)[0] byte_bounds(Z1)[-1]
↓ ↓
╌╌╌┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬╌╌
Z1 │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │
╌╌╌┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴╌╌
byte_bounds(Z2)[0] byte_bounds(Z2)[-1]
↓ ↓
╌╌╌╌╌╌╌┬───┬╌╌╌┬───┬╌╌╌┬───┬╌╌╌┬───┬╌╌╌╌╌╌╌╌╌╌
Z2 │ 1 │ │ 3 │ │ 5 │ │ 7 │
╌╌╌╌╌╌╌┴───┴╌╌╌┴───┴╌╌╌┴───┴╌╌╌┴───┴╌╌╌╌╌╌╌╌╌╌
</pre>
<pre class="code literal-block">
>>> offset_start = np.byte_bounds(Z2)[0] - np.byte_bounds(Z1)[0]
>>> print(offset_start) # bytes
8
>>> offset_stop = np.byte_bounds(Z2)[-1] - np.byte_bounds(Z1)[-1]
>>> print(offset_stop) # bytes
-16
</pre>
<p>Converting these offsets into indices is straightforward using the <code>itemsize</code>
and taking into account that the <code>offset_stop</code> is negative (end-bound of <code>Z2</code>
is logically smaller than end-bound of <code>Z1</code> array). We thus need to add the
items size of Z1 to get the right end index.</p>
<pre class="code literal-block">
>>> start = offset_start // Z1.itemsize
>>> stop = Z1.size + offset_stop // Z1.itemsize
>>> print(start, stop, step)
1, 8, 2
</pre>
<p>Last we test our results:</p>
<pre class="code literal-block">
>>> print(np.allclose(Z1[start:stop:step], Z2))
True
</pre>
<p>As an exercise, you can improve this first and very simple implementation by
taking into account:</p>
<ul class="simple">
<li>Negative steps</li>
<li>Multi-dimensional arrays</li>
</ul>
<p><a class="reference external" href="code/find_index.py">Solution</a> to the exercise.</p>
</div>
</div>
<div class="section" id="code-vectorization">
<h1><a class="toc-backref" href="#table-of-contents">Code vectorization</a></h1>
<div class="contents local topic" id="id4">
<p class="topic-title first"><strong>Contents</strong></p>
<ul class="simple">
<li><a class="reference internal" href="#id5" id="id120">Introduction</a></li>
<li><a class="reference internal" href="#uniform-vectorization" id="id121">Uniform vectorization</a><ul>
<li><a class="reference internal" href="#the-game-of-life" id="id122">The Game of Life</a></li>
<li><a class="reference internal" href="#python-implementation" id="id123">Python implementation</a></li>
<li><a class="reference internal" href="#numpy-implementation" id="id124">Numpy implementation</a></li>
<li><a class="reference internal" href="#exercise" id="id125">Exercise</a></li>
<li><a class="reference internal" href="#sources" id="id126">Sources</a></li>
<li><a class="reference internal" href="#references" id="id127">References</a></li>
</ul>
</li>
<li><a class="reference internal" href="#temporal-vectorization" id="id128">Temporal vectorization</a><ul>
<li><a class="reference internal" href="#id6" id="id129">Python implementation</a></li>
<li><a class="reference internal" href="#id7" id="id130">Numpy implementation</a></li>
<li><a class="reference internal" href="#faster-numpy-implementation" id="id131">Faster numpy implementation</a></li>
<li><a class="reference internal" href="#visualization" id="id132">Visualization</a></li>
<li><a class="reference internal" href="#id8" id="id133">Exercise</a></li>
<li><a class="reference internal" href="#id9" id="id134">Sources</a></li>
<li><a class="reference internal" href="#id10" id="id135">References</a></li>
</ul>
</li>
<li><a class="reference internal" href="#spatial-vectorization" id="id136">Spatial vectorization</a><ul>
<li><a class="reference internal" href="#boids" id="id137">Boids</a></li>
<li><a class="reference internal" href="#id12" id="id138">Python implementation</a></li>
<li><a class="reference internal" href="#id13" id="id139">Numpy implementation</a></li>
<li><a class="reference internal" href="#id14" id="id140">Exercise</a></li>
<li><a class="reference internal" href="#id15" id="id141">Sources</a></li>
<li><a class="reference internal" href="#id16" id="id142">References</a></li>
</ul>
</li>
<li><a class="reference internal" href="#id17" id="id143">Conclusion</a></li>
</ul>
</div>
<div class="section" id="id5">
<h2><a class="toc-backref" href="#id4">Introduction</a></h2>
<p>Code vectorization means that the problem you're trying to solve is inherently
vectorizable and only requires a few numpy tricks to make it faster. Of course
it does not mean it is easy nor straightforward, but at least it does not
necessitate to totally rethink your problem (as it will be the case in the
<a class="reference internal" href="#problem-vectorization">Problem vectorization</a> chapter). Still, it may require some experience to see
where code can be vectorized. Let's illustrate this through the most simple
example where we want to sum up two lists of integers. One simple way using
pure Python is:</p>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">add_python</span><span class="punctuation">(</span><span class="name">Z1</span><span class="punctuation">,</span><span class="name">Z2</span><span class="punctuation">):</span>
<span class="keyword">return</span> <span class="punctuation">[</span><span class="name">z1</span><span class="operator">+</span><span class="name">z2</span> <span class="keyword">for</span> <span class="punctuation">(</span><span class="name">z1</span><span class="punctuation">,</span><span class="name">z2</span><span class="punctuation">)</span> <span class="operator word">in</span> <span class="name builtin">zip</span><span class="punctuation">(</span><span class="name">Z1</span><span class="punctuation">,</span><span class="name">Z2</span><span class="punctuation">)]</span>
</pre>
<p>This first naive solution can be vectorized very easily using numpy:</p>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">add_numpy</span><span class="punctuation">(</span><span class="name">Z1</span><span class="punctuation">,</span><span class="name">Z2</span><span class="punctuation">):</span>
<span class="keyword">return</span> <span class="name">np</span><span class="operator">.</span><span class="name">add</span><span class="punctuation">(</span><span class="name">Z1</span><span class="punctuation">,</span><span class="name">Z2</span><span class="punctuation">)</span>
</pre>
<p>Without any surprise, benchmarking the two approaches shows the second method
is the fastest with one order of magnitude.</p>
<pre class="code python literal-block">
<span class="operator">>>></span> <span class="name">Z1</span> <span class="operator">=</span> <span class="name">random</span><span class="operator">.</span><span class="name">sample</span><span class="punctuation">(</span><span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">1000</span><span class="punctuation">),</span> <span class="literal number integer">100</span><span class="punctuation">)</span>
<span class="operator">>>></span> <span class="name">Z2</span> <span class="operator">=</span> <span class="name">random</span><span class="operator">.</span><span class="name">sample</span><span class="punctuation">(</span><span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">1000</span><span class="punctuation">),</span> <span class="literal number integer">100</span><span class="punctuation">)</span>
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"add_python(Z1, Z2)"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">1000</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number integer">68</span> <span class="name">usec</span> <span class="name">per</span> <span class="name">loop</span>
<span class="operator">>>></span> <span class="name">timeit</span><span class="punctuation">(</span><span class="literal string double">"add_numpy(Z1, Z2)"</span><span class="punctuation">,</span> <span class="name builtin">globals</span><span class="punctuation">())</span>
<span class="literal number integer">10000</span> <span class="name">loops</span><span class="punctuation">,</span> <span class="name">best</span> <span class="name">of</span> <span class="literal number integer">3</span><span class="punctuation">:</span> <span class="literal number float">1.14</span> <span class="name">usec</span> <span class="name">per</span> <span class="name">loop</span>
</pre>
<p>Not only is the second approach faster, but it also naturally adapts to the
shape of <code>Z1</code> and <code>Z2</code>. This is the reason why we did not write <code>Z1 + Z2</code>
because it would not work if <code>Z1</code> and <code>Z2</code> were both lists. In the first Python
method, the inner <code>+</code> is interpreted differently depending on the nature of the
two objects such that if we consider two nested lists, we get the following
outputs:</p>
<pre class="code pycon literal-block">
<span class="name"></span><span class="generic prompt">>>> </span><span class="name">Z1</span> <span class="operator">=</span> <span class="punctuation">[[</span><span class="literal number integer">1</span><span class="punctuation">,</span> <span class="literal number integer">2</span><span class="punctuation">],</span> <span class="punctuation">[</span><span class="literal number integer">3</span><span class="punctuation">,</span> <span class="literal number integer">4</span><span class="punctuation">]]</span>
<span class="generic prompt">>>> </span><span class="name">Z2</span> <span class="operator">=</span> <span class="punctuation">[[</span><span class="literal number integer">5</span><span class="punctuation">,</span> <span class="literal number integer">6</span><span class="punctuation">],</span> <span class="punctuation">[</span><span class="literal number integer">7</span><span class="punctuation">,</span> <span class="literal number integer">8</span><span class="punctuation">]]</span>
<span class="generic prompt">>>> </span><span class="name">Z1</span> <span class="operator">+</span> <span class="name">Z2</span>
<span class="generic output">[[1, 2], [3, 4], [5, 6], [7, 8]]
</span><span class="name"></span><span class="generic prompt">>>> </span><span class="name">add_python</span><span class="punctuation">(</span><span class="name">Z1</span><span class="punctuation">,</span> <span class="name">Z2</span><span class="punctuation">)</span>
<span class="generic output">[[1, 2, 5, 6], [3, 4, 7, 8]]
</span><span class="name"></span><span class="generic prompt">>>> </span><span class="name">add_numpy</span><span class="punctuation">(</span><span class="name">Z1</span><span class="punctuation">,</span> <span class="name">Z2</span><span class="punctuation">)</span>
<span class="generic output">[[ 6 8]
[10 12]]</span>
</pre>
<p>The first method concatenates the two lists together, the second method
concatenates the internal lists together and the last one computes what is
(numerically) expected. As an exercise, you can rewrite the Python version
such that it accepts nested lists of any depth.</p>
</div>
<div class="section" id="uniform-vectorization">
<h2><a class="toc-backref" href="#id4">Uniform vectorization</a></h2>
<p>Uniform vectorization is the simplest form of vectorization where all the
elements share the same computation at every time step with no specific
processing for any element. One stereotypical case is the Game of Life that has
been invented by John Conway (see below) and is one of the earliest examples of
cellular automata. Those cellular automata can be conveniently regarded as
an array of cells that are connected together with the notion of neighbours and
their vectorization is straightforward. Let me first define the game and we'll
see how to vectorize it.</p>
<div class="legend admonition">
<p class="first admonition-title"><strong>Figure 4.1</strong></p>
<p class="last">Conus textile snail exhibits a cellular automaton pattern on its shell.
Image by <a class="reference external" href="https://commons.wikimedia.org/wiki/File:Textile_cone.JPG">Richard Ling</a>, 2005.</p>
</div>
<img alt="data/Textile-Cone-cropped.jpg" class="bordered" src="data/Textile-Cone-cropped.jpg" style="width: 100%;" />
<div class="section" id="the-game-of-life">
<h3><a class="toc-backref" href="#id4">The Game of Life</a></h3>
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">Excerpt from the Wikipedia entry on the
<a class="reference external" href="https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life">Game of Life</a></p>
</div>
<p>The Game of Life is a cellular automaton devised by the British mathematician
John Horton Conway in 1970. It is the best-known example of a cellular
automaton. The "game" is actually a zero-player game, meaning that its
evolution is determined by its initial state, needing no input from human
players. One interacts with the Game of Life by creating an initial
configuration and observing how it evolves.</p>
<p>The universe of the Game of Life is an infinite two-dimensional orthogonal grid
of square cells, each of which is in one of two possible states, live or
dead. Every cell interacts with its eight neighbours, which are the cells that
are directly horizontally, vertically, or diagonally adjacent. At each step in
time, the following transitions occur:</p>
<ol class="arabic simple">
<li>Any live cell with fewer than two live neighbours dies, as if by needs
caused by underpopulation.</li>
<li>Any live cell with more than three live neighbours dies, as if by
overcrowding.</li>
<li>Any live cell with two or three live neighbours lives, unchanged, to the
next generation.</li>
<li>Any dead cell with exactly three live neighbours becomes a live cell.</li>
</ol>
<p>The initial pattern constitutes the 'seed' of the system. The first generation
is created by applying the above rules simultaneously to every cell in the seed
– births and deaths happen simultaneously, and the discrete moment at which
this happens is sometimes called a tick. (In other words, each generation is a
pure function of the one before.) The rules continue to be applied repeatedly
to create further generations.</p>
</div>
<div class="section" id="python-implementation">
<h3><a class="toc-backref" href="#id4">Python implementation</a></h3>
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">We could have used the more efficient python <a class="reference external" href="http://docs.python.org/3/library/array.html">array interface</a> but it is more convenient to
use the familiar list object.</p>
</div>
<p>In pure Python, we can code the Game of Life using a list of lists representing
the board where cells are supposed to evolve. Such a board will be equipped with
border of 0 that allows to accelerate things a bit by avoiding to have specific
tests for borders when counting the number of neighbours.</p>
<pre class="code python literal-block">
<span class="name">Z</span> <span class="operator">=</span> <span class="punctuation">[[</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">],</span>
<span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">],</span>
<span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">],</span>
<span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">],</span>
<span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">],</span>
<span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">,</span><span class="literal number integer">0</span><span class="punctuation">]]</span>
</pre>
<p>Taking the border into account, counting neighbours then is straightforward:</p>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">compute_neighbours</span><span class="punctuation">(</span><span class="name">Z</span><span class="punctuation">):</span>
<span class="name">shape</span> <span class="operator">=</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">Z</span><span class="punctuation">),</span> <span class="name builtin">len</span><span class="punctuation">(</span><span class="name">Z</span><span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">])</span>
<span class="name">N</span> <span class="operator">=</span> <span class="punctuation">[[</span><span class="literal number integer">0</span><span class="punctuation">,]</span><span class="operator">*</span><span class="punctuation">(</span><span class="name">shape</span><span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">])</span> <span class="keyword">for</span> <span class="name">i</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="name">shape</span><span class="punctuation">[</span><span class="literal number integer">1</span><span class="punctuation">])]</span>
<span class="keyword">for</span> <span class="name">x</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="name">shape</span><span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">]</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">):</span>
<span class="keyword">for</span> <span class="name">y</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="name">shape</span><span class="punctuation">[</span><span class="literal number integer">1</span><span class="punctuation">]</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">):</span>
<span class="name">N</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> <span class="operator">=</span> <span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">][</span><span class="name">y</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">]</span><span class="operator">+</span><span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">]</span><span class="operator">+</span><span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="operator">+</span><span class="literal number integer">1</span><span class="punctuation">][</span><span class="name">y</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">]</span> \
<span class="operator">+</span> <span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> <span class="operator">+</span><span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="operator">+</span><span class="literal number integer">1</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> \
<span class="operator">+</span> <span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">][</span><span class="name">y</span><span class="operator">+</span><span class="literal number integer">1</span><span class="punctuation">]</span><span class="operator">+</span><span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="operator">+</span><span class="literal number integer">1</span><span class="punctuation">]</span><span class="operator">+</span><span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="operator">+</span><span class="literal number integer">1</span><span class="punctuation">][</span><span class="name">y</span><span class="operator">+</span><span class="literal number integer">1</span><span class="punctuation">]</span>
<span class="keyword">return</span> <span class="name">N</span>
</pre>
<p>To iterate one step in time, we then simply count the number of neighbours for
each internal cell and we update the whole board according to the four
aforementioned rules:</p>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">iterate</span><span class="punctuation">(</span><span class="name">Z</span><span class="punctuation">):</span>
<span class="name">N</span> <span class="operator">=</span> <span class="name">compute_neighbours</span><span class="punctuation">(</span><span class="name">Z</span><span class="punctuation">)</span>
<span class="keyword">for</span> <span class="name">x</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="name">shape</span><span class="punctuation">[</span><span class="literal number integer">0</span><span class="punctuation">]</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">):</span>
<span class="keyword">for</span> <span class="name">y</span> <span class="operator word">in</span> <span class="name builtin">range</span><span class="punctuation">(</span><span class="literal number integer">1</span><span class="punctuation">,</span><span class="name">shape</span><span class="punctuation">[</span><span class="literal number integer">1</span><span class="punctuation">]</span><span class="operator">-</span><span class="literal number integer">1</span><span class="punctuation">):</span>
<span class="keyword">if</span> <span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> <span class="operator">==</span> <span class="literal number integer">1</span> <span class="operator word">and</span> <span class="punctuation">(</span><span class="name">N</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> <span class="operator"><</span> <span class="literal number integer">2</span> <span class="operator word">or</span> <span class="name">N</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> <span class="operator">></span> <span class="literal number integer">3</span><span class="punctuation">):</span>
<span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> <span class="operator">=</span> <span class="literal number integer">0</span>
<span class="keyword">elif</span> <span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> <span class="operator">==</span> <span class="literal number integer">0</span> <span class="operator word">and</span> <span class="name">N</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> <span class="operator">==</span> <span class="literal number integer">3</span><span class="punctuation">:</span>
<span class="name">Z</span><span class="punctuation">[</span><span class="name">x</span><span class="punctuation">][</span><span class="name">y</span><span class="punctuation">]</span> <span class="operator">=</span> <span class="literal number integer">1</span>
<span class="keyword">return</span> <span class="name">Z</span>
</pre>
<p>The figure below shows four iterations on a 4x4 area where the initial state is a
<a class="reference external" href="https://en.wikipedia.org/wiki/Glider_(Conway%27s_Life)">glider</a>, a structure
discovered by Richard K. Guy in 1970.</p>
<div class="legend admonition">
<p class="first admonition-title"><strong>Figure 4.2</strong></p>
<p class="last">The glider pattern is known to replicate itself one step diagonally in 4
iterations.</p>
</div>
<img alt="data/glider.png" src="data/glider.png" style="width: 100%;" />
</div>
<div class="section" id="numpy-implementation">
<h3><a class="toc-backref" href="#id4">Numpy implementation</a></h3>
<p>Starting from the Python version, the vectorization of the Game of Life