Arrays/Python/AppendCost - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:16:42Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:16, 9 October 2019
Line 20:		Line 20:
	==The script==		==The script==

	Repo on git.charlesreid1.com: https://charlesreid1.com~~:3000~~/cs/python/src/master/arrays/amortized-append-cost.py		Repo on git.charlesreid1.com: https://git.charlesreid1.com/cs/python/src/master/arrays/amortized-append-cost.py

	Source:		Source:

Admin: /* The script */

2017-05-29T06:37:46Z

The script

← Older revision		Revision as of 06:37, 29 May 2017
Line 18:		Line 18:
	</pre>		</pre>

	===The script===		==The script==

	~~====~~git.charlesreid1.com ~~repo====~~		Repo on git.charlesreid1.com: https://charlesreid1.com:3000/cs/python/src/master/arrays/amortized-append-cost.py

	~~https~~:~~//charlesreid1.com:3000/cs/python/src/master/arrays/amortized-append-cost.py~~		Source:

	~~====source====~~

	<pre>		<pre>

Admin at 06:37, 29 May 2017

2017-05-29T06:37:22Z

@@ Line 19: / Line 19: @@
 ===The script===
 <pre>
@@ Line 52: / Line 58: @@
 </pre>

Admin: Created page with "==Ammortized Cost of Appending is O(1)== The following script shows that the amortized cost of expanding when appending to a list is O(1) when amortized over the operations w..."

2017-05-29T06:35:49Z

Created page with "==Ammortized Cost of Appending is O(1)== The following script shows that the amortized cost of expanding when appending to a list is O(1) when amortized over the operations w..."

New page

==Ammortized Cost of Appending is O(1)==

The following script shows that the amortized cost of expanding when appending to a list is O(1) when amortized over the operations where the resizing operation is not performed.

The script prints the amount of time per operation for appending None objects to a list. These show the amortized cost of resizing an array dynamically is independent of the array size, and is therefore O(1).

==The output==

<pre>
$ python amortized-append-cost.py
n: 10 microsec: 0.501
n: 100 microsec: 0.131
n: 1000 microsec: 0.150
n: 10000 microsec: 0.107
n: 100000 microsec: 0.106
n: 1000000 microsec: 0.124
n: 10000000 microsec: 0.110
</pre>

===The script===

<pre>
"""
Goodrich et al
Data Structures in Python
Chapter 5: Array-Based Sequences

Demonstrate the amortized cost of resizing when append happens.

Much to learn: https://docs.python.org/3/library/string.html#formatstrings
"""

from time import time, clock

def compute_average(n):
data = []
start = time()
startc = clock()
for k in range(n):
data.append(None)
end = time()
endc = clock()
return (end-start)/n
#return ((end-start)/n, (endc-startc)/n)

if __name__=="__main__":
values = [int(10**j) for j in range(1,8)]
for n in values:
INV_MICROSEC = 10**6
t = compute_average(n)*INV_MICROSEC
print("n: {0:10d}\tmicrosec: {1:.3f}".format(n,t))

</pre>