Arrays/Python/DynamicArray - Revision history

Admin: /* The class */

2017-05-29T20:59:12Z

The class

← Older revision		Revision as of 20:59, 29 May 2017
Line 10:		Line 10:


	<~~source lang="python"~~>		<pre>
	"""		"""
	Goodrich et al		Goodrich et al
Line 108:		Line 108:
	a.pop()		a.pop()
	print("Done.\n")		print("Done.\n")
	</~~source~~>		</pre>

	===Expected output===		===Expected output===

Admin: /* The class */

2017-05-29T20:27:40Z

The class

← Older revision		Revision as of 20:27, 29 May 2017
Line 10:		Line 10:


	<~~pre~~>		<source lang="python">
	"""		"""
	Goodrich et al		Goodrich et al
Line 108:		Line 108:
	a.pop()		a.pop()
	print("Done.\n")		print("Done.\n")
	</~~pre~~>		</source>

	===Expected output===		===Expected output===

Admin at 20:27, 29 May 2017

2017-05-29T20:27:20Z

← Older revision		Revision as of 20:27, 29 May 2017
Line 1:		Line 1:
	The DynamicArray class in Python demonstrates the use of a low-level ctype array to keep track of objects.		The DynamicArray class in Python demonstrates the use of a low-level ctype array to keep track of objects.

			Features:
			* Implements an array-based structure that works like a Python list, has many of the same features and O() operational costs
			* Handles negative indices like mylist[-1]
			* "Dynamic shrinkage" that works like a Python list - as more elements are removed, the array is automatically resized to be smaller
			* See pop() method implementation

	===The class===		===The class===
Line 10:		Line 16:
	Chapter 5: Array-Based Sequences		Chapter 5: Array-Based Sequences

	Question R-4		Question R-5.4

	Expand on the DynamicArray class to support negative indexing		Expand on the DynamicArray class to support negative indexing
	with the __getitem__ method.		with the __getitem__ method.

			Question C-5.16

			Implement a pop() method for DynamicArray.
			It should remove the last item in the array.
			It should shrink the capacity in half
			if the number of elements drops below N/4.
	"""		"""
	import ctypes		import ctypes
Line 42:		Line 55:
	self._A[self._n] = obj		self._A[self._n] = obj
	self._n += 1		self._n += 1

			def pop(self):
			"""Pop obj from end of array"""
			self._A[self._n] = None
			self._n -= 1
			if(self._capacity//4 > self._n):
			self._resize(self._capacity//2)

	def _resize(self,c):		def _resize(self,c):
	""" Resize to capacity c (private)"""		""" Resize to capacity c (private)"""
	print("Resizing array: {0:3d}".format(self._n))		print("Resizing array: {0:4d} elements, {1:5d} capacity".format(self._n,c))
	B = self._make_array(c) # bigger array		B = self._make_array(c) # bigger array
	for k in range(self._n):		for k in range(self._n):
Line 55:		Line 75:
	"""Make the internal array (private)"""		"""Make the internal array (private)"""
	return (n*ctypes.py_object)()		return (n*ctypes.py_object)()
	~~</pre>~~


	~~This should also utilize the following test, which can be tacked onto the end of the file.~~		if __name__=="__main__":

	=~~==The test===~~		import random, sys
			a = DynamicArray()

	~~<pre>~~

	~~if __name__==~~"~~__main__~~":		print("Appending 1,000 elements to array...")
	~~import random, sys~~
	~~a = DynamicArray(~~)
	for j in range(1000):		for j in range(1000):
	a.append(random.randint(0,9))		a.append(random.randint(0,9))
			print("Done.\n")


			print("Accessing array at individual positive/negative indices...")
	for ix in [0, 10, 35, -10, -999, 999, -1000]:		for ix in [0, 10, 35, -10, -999, 999, -1000]:
	print("Index {0:4d}\tDynamicArray value: {1:2d}".format(ix,a[ix]))		print("Index {0:4d}\tDynamicArray value: {1:2d}".format(ix,a[ix]))
			print("Done.\n")


			print("Accessing array at invalid index...")
	try:		try:
	ix = 1000		ix = 1000
Line 78:		Line 101:
	except IndexError:		except IndexError:
	print("Correctly throws IndexError for index {0}.".format(ix))		print("Correctly throws IndexError for index {0}.".format(ix))
			print("Done.\n")


			print("Popping 995 elements from array...")
			for j in range(995):
			a.pop()
			print("Done.\n")
	</pre>		</pre>

Line 84:		Line 114:
	<pre>		<pre>
	$ python DynamicArray.py		$ python DynamicArray.py
	Resizing array: 1		Appending 1,000 elements to array...
	Resizing array: 2		Resizing array: 1 elements, 2 capacity
	Resizing array: 4		Resizing array: 2 elements, 4 capacity
	Resizing array: 8		Resizing array: 4 elements, 8 capacity
	Resizing array: 16		Resizing array: 8 elements, 16 capacity
	Resizing array: 32		Resizing array: 16 elements, 32 capacity
	Resizing array: 64		Resizing array: 32 elements, 64 capacity
	Resizing array: 128		Resizing array: 64 elements, 128 capacity
	Resizing array: 256		Resizing array: 128 elements, 256 capacity
	Resizing array: 512		Resizing array: 256 elements, 512 capacity
	Index 0 DynamicArray value: 3		Resizing array: 512 elements, 1024 capacity
	Index 10 DynamicArray value: 6		Done.
	Index 35 DynamicArray value: 1
			Accessing array at individual positive/negative indices...
			Index 0 DynamicArray value: 5
			Index 10 DynamicArray value: 9
			Index 35 DynamicArray value: 4
	Index -10 DynamicArray value: 2		Index -10 DynamicArray value: 2
	Index -999 DynamicArray value: 8		Index -999 DynamicArray value: 1
	Index 999 DynamicArray value: 3		Index 999 DynamicArray value: 7
	Index -1000 DynamicArray value: 3		Index -1000 DynamicArray value: 5
			Done.

			Accessing array at invalid index...
	Correctly throws IndexError for index 1000.		Correctly throws IndexError for index 1000.
			Done.

			Popping 995 elements from array...
			Resizing array: 255 elements, 512 capacity
			Resizing array: 127 elements, 256 capacity
			Resizing array: 63 elements, 128 capacity
			Resizing array: 31 elements, 64 capacity
			Resizing array: 15 elements, 32 capacity
			Resizing array: 7 elements, 16 capacity
			Done.
	</pre>		</pre>

Admin at 06:54, 29 May 2017

2017-05-29T06:54:39Z

← Older revision		Revision as of 06:54, 29 May 2017
Line 103:		Line 103:
	Correctly throws IndexError for index 1000.		Correctly throws IndexError for index 1000.
	</pre>		</pre>



			{{PythonArraysFlag}}

Admin: /* The test */

2017-05-29T04:20:02Z

The test

@@ Line 78: / Line 78: @@
      except IndexError:
          print("Correctly throws IndexError for index {0}.".format(ix))
 </pre>

Admin at 04:19, 29 May 2017

2017-05-29T04:19:38Z

← Older revision		Revision as of 04:19, 29 May 2017
Line 1:		Line 1:
	The DynamicArray class in Python demonstrates the use of a low-level ctype array to keep track of objects.		The DynamicArray class in Python demonstrates the use of a low-level ctype array to keep track of objects.

			===The class===


	<pre>		<pre>
Line 52:		Line 55:
	"""Make the internal array (private)"""		"""Make the internal array (private)"""
	return (n*ctypes.py_object)()		return (n*ctypes.py_object)()
			</pre>


			This should also utilize the following test, which can be tacked onto the end of the file.

			===The test===

			<pre>

	if __name__=="__main__":		if __name__=="__main__":

Admin: Created page with "The DynamicArray class in Python demonstrates the use of a low-level ctype array to keep track of objects.

 """ Goodrich et al Data Structures in Python Chapter 5: Array..."

2017-05-29T04:19:01Z

Created page with "The DynamicArray class in Python demonstrates the use of a low-level ctype array to keep track of objects. <pre> """ Goodrich et al Data Structures in Python Chapter 5: Array..."

New page

The DynamicArray class in Python demonstrates the use of a low-level ctype array to keep track of objects.

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

Question R-4

Expand on the DynamicArray class to support negative indexing
with the __getitem__ method.
"""
import ctypes

class DynamicArray:
"""
A dynamic array class that works like a list.
"""
def __init__(self):
self._n = 0 # number of elements
self._capacity = 1 # default array capacity
self._A = self._make_array(self._capacity) # low-level guts

def __getitem__(self,k):
if(0<=k<self._n):
return self._A[k]
elif(-self._n<=k<0):
return self._A[self._n+k]
else:
raise IndexError("Invalid index: Requested index {0} exceeds number of elements {1}".format(k,self._n))

def append(self,obj):
"""Add obj to end of array"""
if(self._n==self._capacity):
# We are out of space, so resize.
# Resize will update capacity for us.
self._resize(2*self._capacity)
self._A[self._n] = obj
self._n += 1

def _resize(self,c):
""" Resize to capacity c (private)"""
print("Resizing array: {0:3d}".format(self._n))
B = self._make_array(c) # bigger array
for k in range(self._n):
B[k] = self._A[k] # copy existing elements only
self._A = B # forget the old array
self._capacity = c # update capacity

def _make_array(self,n):
"""Make the internal array (private)"""
return (n*ctypes.py_object)()

if __name__=="__main__":
import random, sys
a = DynamicArray()
for j in range(1000):
a.append(random.randint(0,9))

for ix in [0, 10, 35, -10, -999, 999, -1000]:
print("Index {0:4d}\tDynamicArray value: {1:2d}".format(ix,a[ix]))

try:
ix = 1000
print("Index {0:4d}\tDynamicArray value: {1:2d}".format(ix,a[ix]))
except IndexError:
print("Correctly throws IndexError for index {0}.".format(ix))
</pre>