Log in / Register
Home arrow Computer Science arrow Data Structures and Algorithms with Python
< Prev   CONTENTS   Next >

2.3.2 A Plot XML Sample

1 <?xml version="1.0" encoding="UTF-8" standalone="no" ?>

2 <Plot title="Average List Element Access Time">

3 <Axes>

4 <XAxis min="1000" max="200000">List Size</XAxis>

5 <YAxis min="20.244" max="60">Microseconds</YAxis>

6 </Axes>

7 <Sequence title="Average Access Time vs List Size" color="red">

8 <DataPoint x="1000" y="33.069"/>

9 <DataPoint x="2000" y="27.842"/>

10 <DataPoint x="3000" y="23.908"/>

11 <DataPoint x="4000" y="26.349"/>

12 <DataPoint x="5000" y="23.212"/>

13 <DataPoint x="6000" y="23.765"/>

14 <DataPoint x="7000" y="21.251"/>

15 <DataPoint x="8000" y="21.321"/>

16 <DataPoint x="9000" y="23.197"/>

17 <DataPoint x="10000" y="21.527"/>

18 <DataPoint x="11000" y="35.799"/>

19 <DataPoint x="12000" y="22.173"/>

20 ...

21 <DataPoint x="197000" y="26.245"/>

22 <DataPoint x="198000" y="30.013"/>

23 <DataPoint x="199000" y="25.888"/>

24 <DataPoint x="200000" y="23.578"/>

25 </Sequence>

26 <Sequence title="Access Time Distribution" color="blue">

27 <DataPoint x="219" y="41.0"/>

28 <DataPoint x="2839" y="38.0"/> 29 <DataPoint x="5902" y="38.0"/> 30 <DataPoint x="8531" y="58.0"/>

31 <DataPoint x="11491" y="38.0"/>

32 <DataPoint x="15415" y="38.0"/>

33 <DataPoint x="17645" y="31.0"/>

34 <DataPoint x="18658" y="38.0"/>

35 <DataPoint x="20266" y="40.0"/>

36 <DataPoint x="21854" y="31.0"/>

37 ...

38 <DataPoint x="197159" y="37.0"/>

39 <DataPoint x="199601" y="40.0"/>

40 </Sequence>

41 </Plot>

Since we'll be taking a look at quite a bit of experimental data in this text, we have written a Tkinter program that will read an XML file with the format given in Sect. 2.3.2 and plot the sequences to the screen. The program is given in Chap. 20.4.

If we use the program to plot the data gathered by the list access experiment, we see a graph like the one in Fig. 2.2. This graph provides the experimental data to back up the two statements we made earlier about lists in Python. The red line shows the average element access time of 1,000 element accesses on a list of the given size. The average access time (computed from a sample of 1,000 random list accesses) is no longer on a list of 10,000 than it is on a list of 160,000. While the exact values are not printed in the graph, the exact values are not important. What we would be interested in seeing is any trend toward longer or shorter average access times. Clearly the only trend is that the size of the list does not affect the average access time. There are some ups and downs in the experimental data, but this is caused by the system being

Fig. 2.2 Access Times in a Python List

a multi-tasking system. Another factor is likely the caching of memory locations. A cache is a way of speeding up access to memory in some situations and it is likely that the really low access times benefited from the existence of a cache for the RAM of the computer. The experimental data backs up the claim that the size of a list does not affect the average access time in the list.

The blue line in the plot is the result of doing 100 list retrieval and store operations on one list of 200,000 elements. The reason the blue line is higher than the red line is likely the result of doing both a retrieval from and a store operation into the element of the list. In addition, the further apart the values in memory, the less likely a cache will help reduce the access time. Whatever the reason for the blue line being higher the important thing to notice is that accessing the element at index 0 takes no more time than accessing any other element of the sequence. All locations within the list are treated equally. This backs up the claim that the average access time at any location within a list is the same, regardless of its location within the list.

Found a mistake? Please highlight the word and press Shift + Enter  
< Prev   CONTENTS   Next >
Business & Finance
Computer Science
Language & Literature
Political science