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
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Maxima 5.47.0 Manual: Performance considerations for Lists</title>
<meta name="description" content="Maxima 5.47.0 Manual: Performance considerations for Lists">
<meta name="keywords" content="Maxima 5.47.0 Manual: Performance considerations for Lists">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link href="maxima_toc.html#Top" rel="start" title="Top">
<link href="maxima_423.html#Function-and-Variable-Index" rel="index" title="Function and Variable Index">
<link href="maxima_toc.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="maxima_19.html#Lists" rel="up" title="Lists">
<link href="maxima_23.html#Arrays" rel="next" title="Arrays">
<link href="maxima_21.html#Functions-and-Variables-for-Lists" rel="previous" title="Functions and Variables for Lists">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
body {color: black; background: white; margin-left: 8%; margin-right: 13%;
font-family: "FreeSans", sans-serif}
h1 {font-size: 150%; font-family: "FreeSans", sans-serif}
h2 {font-size: 125%; font-family: "FreeSans", sans-serif}
h3 {font-size: 100%; font-family: "FreeSans", sans-serif}
a[href] {color: rgb(0,0,255); text-decoration: none;}
a[href]:hover {background: rgb(220,220,220);}
div.textbox {border: solid; border-width: thin; padding-top: 1em;
padding-bottom: 1em; padding-left: 2em; padding-right: 2em}
div.titlebox {border: none; padding-top: 1em; padding-bottom: 1em;
padding-left: 2em; padding-right: 2em; background: rgb(200,255,255);
font-family: sans-serif}
div.synopsisbox {
border: none; padding-top: 1em; padding-bottom: 1em; padding-left: 2em;
padding-right: 2em; background: rgb(255,220,255);}
pre.example {border: 1px solid rgb(180,180,180); padding-top: 1em;
padding-bottom: 1em; padding-left: 1em; padding-right: 1em;
background-color: rgb(238,238,255)}
div.spacerbox {border: none; padding-top: 2em; padding-bottom: 2em}
div.image {margin: 0; padding: 1em; text-align: center}
div.categorybox {border: 1px solid gray; padding-top: 1em; padding-bottom: 1em;
padding-left: 1em; padding-right: 1em; background: rgb(247,242,220)}
img {max-width:80%; max-height: 80%; display: block; margin-left: auto; margin-right: auto}
-->
</style>
<link rel="icon" href="figures/favicon.ico">
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6>"></script>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
</head>
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Performance-considerations-for-Lists"></a>
<div class="header">
<p>
Previous: <a href="maxima_21.html#Functions-and-Variables-for-Lists" accesskey="p" rel="previous">Functions and Variables for Lists</a>, Up: <a href="maxima_19.html#Lists" accesskey="u" rel="up">Lists</a> [<a href="maxima_toc.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="maxima_423.html#Function-and-Variable-Index" title="Index" rel="index">Index</a>]</p>
</div>
<a name="Performance-considerations-for-Lists-1"></a>
<h4 class="subsection">5.4.3 Performance considerations for Lists</h4>
<p>Lists provide efficient ways of appending and removing elements.
They can be created without knowing their final dimensions.
Lisp provides efficient means of copying and handling lists.
Also nested lists do not need to be strictly rectangular.
These advantages over declared arrays come with the drawback that the amount of time
needed for accessing a random element within a list may be roughly
proportional to the element’s distance from its beginning.
Efficient traversal of lists is still possible, though, by using the list as a
stack or a fifo:
</p>
<div class="example">
<pre class="example">(%i1) l:[Test,1,2,3,4];
(%o1) [Test, 1, 2, 3, 4]
</pre><pre class="example">(%i2) while l # [] do
disp(pop(l));
Test
1
2
3
4
(%o2) done
</pre></div>
<p>Another even faster example would be:
</p><div class="example">
<pre class="example">(%i1) l:[Test,1,2,3,4];
(%o1) [Test, 1, 2, 3, 4]
</pre><pre class="example">(%i2) for i in l do
disp(pop(l));
Test
1
2
3
4
(%o2) done
</pre></div>
<p>Beginning traversal with the last element of a list is possible after
reversing the list using <code>reverse ()</code>.
If the elements of a long list need to be processed in a different
order performance might be increased by converting the list into a
declared array first.
</p>
<p>Note also that the ending condition of <code>for</code> loops
is tested for every iteration which means that the result of a
<code>length</code> should be cached if it is used in the ending
condition:
</p>
<div class="example">
<pre class="example">(%i1) l:makelist(i,i,1,100000)$
</pre><pre class="example">(%i2) lngth:length(l);
(%o2) 100000
</pre><pre class="example">(%i3) x:1;
(%o3) 1
</pre><pre class="example">(%i4) for i:1 thru lngth do
x:x+1$
</pre><pre class="example">(%i5) x;
(%o5) 100001
</pre></div>
<a name="Item_003a-Arrays_002fnode_002fArrays"></a><hr>
<div class="header">
<p>
Previous: <a href="maxima_21.html#Functions-and-Variables-for-Lists" accesskey="p" rel="previous">Functions and Variables for Lists</a>, Up: <a href="maxima_19.html#Lists" accesskey="u" rel="up">Lists</a> [<a href="maxima_toc.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="maxima_423.html#Function-and-Variable-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
