Arrays/Python - Revision history

Admin: /* DynamicArray class */

2019-03-12T15:56:49Z

DynamicArray class

← Older revision		Revision as of 15:56, 12 March 2019
Line 71:		Line 71:
	===DynamicArray class===		===DynamicArray class===

	https://charlesreid1.com~~:3000~~/cs/python/src/master/arrays/DynamicArray.py		https://git.charlesreid1.com/cs/python/src/master/arrays/DynamicArray.py

	Book runs through the implementation of a dynamic array class. Few notes:		Book runs through the implementation of a dynamic array class. Few notes:

2019-03-12T15:56:32Z

← Older revision		Revision as of 15:56, 12 March 2019
Line 1:		Line 1:
	For empirical demonstration of table doubling with Python, see [[Arrays/~~Pthon~~/Sizeof]]		For empirical demonstration of table doubling with Python, see [[Arrays/Python/Sizeof]]

	=Notes=		=Notes=

2019-03-12T15:56:22Z

← Older revision		Revision as of 15:56, 12 March 2019
Line 1:		Line 1:
			For empirical demonstration of table doubling with Python, see [[Arrays/Pthon/Sizeof]]

	=Notes=		=Notes=

2017-05-29T21:41:00Z

Proving Whether Dynamic Shrinkage/Expansion is O(1)

← Older revision		Revision as of 21:41, 29 May 2017
Line 112:		Line 112:

	[[Arrays/Python/DynamicArrayResizing]]		[[Arrays/Python/DynamicArrayResizing]]

			===Searching for duplicates===

2017-05-29T21:04:51Z

Implementing the CaesarCipher with string ops in Python

← Older revision		Revision as of 21:04, 29 May 2017
Line 102:		Line 102:

	R-5.10: [[Arrays/Python/CaesarCipher]]		R-5.10: [[Arrays/Python/CaesarCipher]]

			===Proving Whether Dynamic Shrinkage/Expansion is O(1)===

			Question C-5.19 and C-5.20 both deal with the implementation of a dynamic shrinkage, by which each time an item is popped the capacity of the array is checked.

			Q-5.19: Consider the pop method implemented for the DynamicArray class, in which an array of capacity C is resized to a capacity of n (number of elements) anytime the number of elements goes below C/4. Give a formal proof that any sequence of append/pop operations on an empty, dynamic array takes O(n) time.

			C-5.20: Consider variant of C-5.19, where capacity C is resized to a capcity of n (number of elements) anytime the number of elements goes below C/2. Show that there are sequences of n operations such that the cost of these operations would be Omega(n^2) to execute.

			[[Arrays/Python/DynamicArrayResizing]]

2017-05-29T06:16:13Z

DynamicArray class

← Older revision		Revision as of 06:16, 29 May 2017
Line 68:		Line 68:

	===DynamicArray class===		===DynamicArray class===

			https://charlesreid1.com:3000/cs/python/src/master/arrays/DynamicArray.py

	Book runs through the implementation of a dynamic array class. Few notes:		Book runs through the implementation of a dynamic array class. Few notes:
Line 76:		Line 78:

	Hallmark expansion procedure - implemented with non-public _resize_ method		Hallmark expansion procedure - implemented with non-public _resize_ method

			===Python list class===

			If we look at the sizes of the lists as we append additional elements, we see it is not a pure geometric progression, nor is it an arithmetic progression.

			The append method exhibits amortized constant-time behavior. While the resize operation is expensive, it is done infrequently enough that its cost is amortized over a large number of operations.

			There seems clear evidence the amortized time for each append is independent of n. See [[Arrays/Python/AppendCost]]

	=Questions=		=Questions=

2017-05-29T05:51:01Z

Compact arrays

← Older revision		Revision as of 05:51, 29 May 2017
Line 64:		Line 64:

	See [[Arrays/Python/CompactArrays]]		See [[Arrays/Python/CompactArrays]]

			Lists are referential structures, so the result of getsizeof for a list instance is only including the size of representing the PRIMARY STRUCTURE - that is, it does not count the memory used by the objects in the array.

			===DynamicArray class===

			Book runs through the implementation of a dynamic array class. Few notes:
			* Three private fields: capacity of array, number of elements, and the array itself (which is a low-level ctype object)
			* Implementing private method to manually create a second array with double the capacity, and copy each item in one at a time
			* Implementing <code>__getitem__</code> to allow indexing
			* <code>__len__</code> returns length

			Hallmark expansion procedure - implemented with non-public _resize_ method

	=Questions=		=Questions=

2017-05-29T05:36:21Z

Questions from Goodrich et al Data Structures in Python Chapter 5

← Older revision		Revision as of 05:36, 29 May 2017
Line 68:		Line 68:

	==Questions from Goodrich et al Data Structures in Python Chapter 5==		==Questions from Goodrich et al Data Structures in Python Chapter 5==

			===Getting the size (in bytes) of a list===

	R-5.1, R-5.2, R-5.3: [[Arrays/Python/Sizeof]]		R-5.1, R-5.2, R-5.3: [[Arrays/Python/Sizeof]]

			===Building a custom array data structure===

	R-5.4: [[Arrays/Python/DynamicArray]]		R-5.4: [[Arrays/Python/DynamicArray]]

			===Implementing the CaesarCipher with string ops in Python===

	R-5.10: [[Arrays/Python/CaesarCipher]]		R-5.10: [[Arrays/Python/CaesarCipher]]

2017-05-29T05:34:32Z

Goodrich Python Chapter 5 Questions

← Older revision		Revision as of 05:34, 29 May 2017
Line 65:		Line 65:
	See [[Arrays/Python/CompactArrays]]		See [[Arrays/Python/CompactArrays]]

	=Goodrich Python Chapter 5 ~~Questions~~=		=Questions=

			==Questions from Goodrich et al Data Structures in Python Chapter 5==

	R-5.1, R-5.2, R-5.3: [[Arrays/Python/Sizeof]]		R-5.1, R-5.2, R-5.3: [[Arrays/Python/Sizeof]]

2017-05-29T05:34:10Z

Goodrich Python Chapter 5 Notes

← Older revision		Revision as of 05:34, 29 May 2017
Line 1:		Line 1:
	=Goodrich Python Chapter 5 ~~Notes~~=		=Notes=

			==Notes from Goodrich et al Data Structures in Python Chapter 5==

	Basic usage of lists, strings, and tuples seems straightforward, but there are ''several important subtleties regarding behaviors associated with these classes''		Basic usage of lists, strings, and tuples seems straightforward, but there are ''several important subtleties regarding behaviors associated with these classes''