Algorithmic Analysis of Data Structures - Revision history

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

2019-10-09T03:13:53Z

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

← Older revision		Revision as of 03:13, 9 October 2019
Line 25:		Line 25:
	Investigation of linked list scaling behavior (isee [[Linked Lists/Java/Timing]]) shows O(1) time per add or add/remove operation, both for a long sequence of add operations and a 75/25 mix of add/remove operations. Output from a timing script is shown here:		Investigation of linked list scaling behavior (isee [[Linked Lists/Java/Timing]]) shows O(1) time per add or add/remove operation, both for a long sequence of add operations and a 75/25 mix of add/remove operations. Output from a timing script is shown here:

	Timing script link: https://charlesreid1.com~~:3000~~/cs/java/src/master/lists/linked-lists/Timing.java		Timing script link: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/Timing.java

	Generic templated linked list being tested against the Java Collections API. TLinkedList class link: See https://charlesreid1.com~~:3000~~/cs/java/src/master/lists/linked-lists/TLinkedList.java		Generic templated linked list being tested against the Java Collections API. TLinkedList class link: See https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/TLinkedList.java

	'''Output:'''		'''Output:'''

Admin: /* Linked Lists */

2017-06-05T04:30:00Z

Linked Lists

← Older revision		Revision as of 04:30, 5 June 2017
Line 28:		Line 28:

	Generic templated linked list being tested against the Java Collections API. TLinkedList class link: See https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/TLinkedList.java		Generic templated linked list being tested against the Java Collections API. TLinkedList class link: See https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/TLinkedList.java

			'''Output:'''

			<pre>
			N, Add Amortized Walltime Per 1k Builtin (us), Add Amortized Walltime Per 1k SLL (us), Add Amortized Walltime Per 1k DLL (us)
			1024, 30.273, 16.602, 30.273,
			2048, 26.367, 16.602, 26.367,
			4096, 31.250, 10.254, 31.250,
			8192, 14.771, 13.916, 14.771,
			16384, 17.700, 17.639, 17.700,
			32768, 15.594, 6.989, 15.594,
			65536, 15.274, 7.874, 15.274,
			131072, 14.778, 8.125, 14.778,
			262144, 15.751, 8.671, 15.751,

			N, Add Remove Amortized Walltime Per 1k Builtin (us), Add Remove Amortized Walltime Per 1k SLL (us), Add Remove Amortized Walltime Per 1k DLL (us)
			1000, 43.000, 29.000 27.000
			4000, 29.000, 19.250 18.500
			16000, 21.313, 18.500 18.813
			64000, 21.672, 18.969 18.859
			256000, 21.738, 18.906 19.586
			</pre>

			The first column shows the size of the input, the number of elements being added or removed from the list. (N is an operations count.) This time, normalized per 1000 operations, is shown for three cases:
			* Second column - time in microseconds per 1000 operations for Java Collections LinkedList
			* Third column - time in microseconds per 1000 operations for TLinkedList, singly-linked generic linked list
			* Fourth column - time in microseconds per 1000 operations for DLinkedList, doubly-linked generic linked list

			You can see that the amortized runtime, as the input size scales from thousands to millions, remains constant for all three types, except at small sizes where algorithm performance is harder to compare.

	==Flags==		==Flags==

Admin: /* Memory usage */

2017-06-05T04:20:01Z

Memory usage

← Older revision		Revision as of 04:20, 5 June 2017
Line 21:		Line 21:
	No way to measure memory usage of objects in-memory, we are left on our own to performing memory profiling.		No way to measure memory usage of objects in-memory, we are left on our own to performing memory profiling.

			===Linked Lists===

			Investigation of linked list scaling behavior (isee [[Linked Lists/Java/Timing]]) shows O(1) time per add or add/remove operation, both for a long sequence of add operations and a 75/25 mix of add/remove operations. Output from a timing script is shown here:

			Timing script link: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/Timing.java

			Generic templated linked list being tested against the Java Collections API. TLinkedList class link: See https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/TLinkedList.java

	==Flags==		==Flags==

Admin: /* Big O complexity analysis */

2017-06-05T02:25:42Z

Big O complexity analysis

← Older revision		Revision as of 02:25, 5 June 2017
Line 12:		Line 12:

	Testing different operation times versus N, to plot on graphs and verify our code is correct.		Testing different operation times versus N, to plot on graphs and verify our code is correct.

			Where do we start? Let's start with creating and removing items from a list.

			Adda lotsa items, time the amortized cost of expanding..

	===Memory usage===		===Memory usage===

Admin: /* Big O complexity analysis */

2017-06-05T01:06:03Z

Big O complexity analysis

← Older revision		Revision as of 01:06, 5 June 2017
Line 9:		Line 9:
	To perform a big O complexity analysis, we utilize random but seeded inputs that statistically sample the input space in a representative way. This ensures we aren't getting stuck measuring the runtime of a worst-case or best-case, and thus getting a skewed view of the algorithm.		To perform a big O complexity analysis, we utilize random but seeded inputs that statistically sample the input space in a representative way. This ensures we aren't getting stuck measuring the runtime of a worst-case or best-case, and thus getting a skewed view of the algorithm.

	~~Corner cases and other~~ kinds of timing tests, like adding and removing at a high, balanced rate and having a near-empty queue with high throughput.		Different kinds of timing tests, like adding and removing at a high, balanced rate and having a near-empty queue with high throughput.

			Testing different operation times versus N, to plot on graphs and verify our code is correct.

	===Memory usage===		===Memory usage===

Admin at 00:49, 5 June 2017

2017-06-05T00:49:48Z

← Older revision		Revision as of 00:49, 5 June 2017
Line 1:		Line 1:
	=Algorithmic analysis=		==Algorithmic analysis==

	While each data container is implemented differently, due to different tradeoffs between storage space and algorithmic complexity, it is useful to define a set of core tests for algorithmic analysis of data structures.		While each data container is implemented differently, due to different tradeoffs between storage space and algorithmic complexity, it is useful to define a set of core tests for algorithmic analysis of data structures.
Line 5:		Line 5:
	We begin with lists, which are arguably the simplest.		We begin with lists, which are arguably the simplest.

	==Big O complexity analysis==		===Big O complexity analysis===

	To perform a big O complexity analysis, we utilize random but seeded inputs that statistically sample the input space in a representative way. This ensures we aren't getting stuck measuring the runtime of a worst-case or best-case, and thus getting a skewed view of the algorithm.		To perform a big O complexity analysis, we utilize random but seeded inputs that statistically sample the input space in a representative way. This ensures we aren't getting stuck measuring the runtime of a worst-case or best-case, and thus getting a skewed view of the algorithm.
Line 11:		Line 11:
	Corner cases and other kinds of timing tests, like adding and removing at a high, balanced rate and having a near-empty queue with high throughput.		Corner cases and other kinds of timing tests, like adding and removing at a high, balanced rate and having a near-empty queue with high throughput.

	==Memory usage==		===Memory usage===

	No way to measure memory usage of objects in-memory, left on our own performing memory profiling.		No way to measure memory usage of objects in-memory, we are left on our own to performing memory profiling.



			==Flags==

			{{DataStructuresFlag}}

			[[Category:Algorithm analysis]]
			[[Category:Lists]]
			[[Category:Linked Lists]]
			[[Category:Queues]]

Admin: Created page with "=Algorithmic analysis= While each data container is implemented differently, due to different tradeoffs between storage space and algorithmic complexity, it is useful to defi..."

2017-06-05T00:48:09Z

Created page with "=Algorithmic analysis= While each data container is implemented differently, due to different tradeoffs between storage space and algorithmic complexity, it is useful to defi..."

New page

=Algorithmic analysis=

While each data container is implemented differently, due to different tradeoffs between storage space and algorithmic complexity, it is useful to define a set of core tests for algorithmic analysis of data structures.

We begin with lists, which are arguably the simplest.

==Big O complexity analysis==

To perform a big O complexity analysis, we utilize random but seeded inputs that statistically sample the input space in a representative way. This ensures we aren't getting stuck measuring the runtime of a worst-case or best-case, and thus getting a skewed view of the algorithm.

Corner cases and other kinds of timing tests, like adding and removing at a high, balanced rate and having a near-empty queue with high throughput.

==Memory usage==

No way to measure memory usage of objects in-memory, left on our own performing memory profiling.