2f:T4da,Below are options to control:
- - -The number of items in the array: this is useful to get a sense of how well an algorithm scales from small list sizes to large ones.
- - -The speed at which the visuals updates their values: useful if you want to slow down to process exact actions an algorithm does
- - -The height of the array visual: in case your screen doesn't fit the current visual
- - -The range of values in the array: can be used to control how often combinations will occur or to plug in a real dataset you are curious about
- - -The variation in array ordering: can have each algorithm randomly generate an array of values each time it runs or can have each algorithm share the same array and array order. If all algorithm share the same order, can also control whether or not an algorithm is already pre-sorted or if it is pre-sorted to see if either of those interactions are particularly beneficial or detrimental to a certain algorithm.
- - -What labels exist on the graph: can have the original index position of a value be shown to better track any swapping that occurs in an algorithm. Can also show values on top of any column to numerically evaluate the validity of combinations.30:Td1a,In order to save on this excessive computation, an algorithm must have some way of determining certain combination of values will not result in the goal without ever actually comparing these values. The most obvious way of doing this would be to simply sort the values in the array before doing any searching for two-sum values. This is immensely useful as a sorted array allows us to use a method called "two-pointers" to find all combinations resulting in the goal value in a number of searches approximately equivalent to either the length of the list itself or the number of combinations resulting in the goal, whichever of these two values is larger. In most cases, this will simply reuslt in some multiple of the number of searches equivalent to the number of items in the list unless most values in the list tend to combine to reach the goal value. To describe the two-pointer method, this process essentially involves searching and comparing values on the two ends of the array: starting from the start of the list moving forwards while also starting from the end of the list moving backwards. For each individual comparison, the algorithm checks if the value is less than the goal, greater than the goal, or the same. If it is less than the goal, we know that the combination must be larger so we can move the pointer on the small (left) end forwards to get a bigger number as all numbers to the right of the current number on the left are larger values and can potentially result in the larger value needed for the goal. If it is more than the goal, we know that the combination must be smaller so we can move the pointer on the large (right) end backwards to get a smaller number as all numbers to the left of the current number on the right are smaller values than this number and potentially result in the smaller combination needed for the goal. If the value is the goal value, we will continue moving the pointers through repeating values until we find all combinations of these two values resulting in the goal. This method works because we know all values to the left of the left pointer will only include values that are smaller than the left pointer value at any point and all values to the right of the right pointer will only include values that are larger than the right pointer at any point so we can necessarily exclude these values as being finished once we have moved past them. More specifically, the numbers on the left of the left pointer cannot combine with the remaining numbers in the middle to make a large enough value needed for the goal and the numbers on the right of the right pointer cannot combine with the remaining numbers in the middle to make a small enough value needed for the goal. The efficiency of such a method can be seen when iterating through larger array sizes like 150 where the sorting process may take awhile, but after sorting, this method will find all combinations that result in the goal staggeringly quickly. However, one must be careful to make sure they also use an efficient algorithm to sort the array. Using an inefficient algorithm for the array such as a simple selection sort, may result in having the sorting process provides no benefit over the basic two-sum approach would. This can be seen below where the sorting process takes just as long as the simple two-sum approach would.31:Ta68,sort_and_narrow = { var input, goal, matches, finished, og_idx, actions, hash, start; [input, goal, matches, finished, og_idx, actions, hash] = setup(2) yield* pauser(two_display(input, { goal: goal, immediate: true })); start = new Date() let d1 = new Date() for (let i = 0; i < input.length; i++) { let min = i; for (let j = i + 1; j < input.length; j++) { actions.push(false) if (input[j] < input[min]) { min = j; } yield two_display(input, {goal: goal, left: i, right: j, extra: min, og_idx: og_idx }); } if (min !== i) { swap(i, min, input, og_idx) actions.push(false) yield two_display(input, {goal: goal, left: i, right: min, og_idx: og_idx }); } actions.push(false) } let i = 0; let j = input.length-1 yield two_display(input, {goal: goal, left:i, right:j, og_idx: og_idx }); while (i < j) { if (input[i] + input[j] > goal) { finished.push(j) actions.push(false) j = j - 1 yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); } else if (input[i] + input[j] < goal) { finished.push(i) actions.push(false) i = i + 1 yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); } else { let left_val = input[i] let right_val = input[j] while (input[i] == left_val) { let count = 0; while (input[j-count] == right_val && j-count > i) { var match = {left:i, right:j-count} matches.push(match) actions.push(true) yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); count = count + 1 } finished.push(i) actions.push(false) i = i + 1 yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); } right_val = input[j] while (input[j] == right_val) { finished.push(j) actions.push(false) j = j - 1 yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); } } } actions.push(false) finished.push(i) yield two_display(input, {goal: goal, matches:matches, finished: finished, og_idx: og_idx}); output_data("naive_sort", 2, actions, matches, start) }32:Ta66,sort_and_narrow_2 = { var input, goal, matches, finished, og_idx, actions, hash, start; [input, goal, matches, finished, og_idx, actions, hash] = setup(2) yield* pauser(two_display(input, { goal: goal, immediate: true })); start = new Date() for (let j = 1; j < input.length; j++) { let i = j - 1 yield two_display(input, {goal: goal, left: i, right: j, matches: matches }); while(i >= 0 && input[i] > input[i + 1]) { swap(i,i+1, input, og_idx) actions.push(false) yield two_display(input, {goal: goal, left: i, right: i + 1, matches: matches}); i = i - 1 } actions.push(false) } let i = 0; let j = input.length-1 yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); while (i < j) { if (input[i] + input[j] > goal) { finished.push(j) actions.push(false) j = j - 1 yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); } else if (input[i] + input[j] < goal) { finished.push(i) actions.push(false) i = i + 1 yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); } else { let left_val = input[i] let right_val = input[j] while (input[i] == left_val) { let count = 0; while (input[j-count] == right_val && j-count > i) { var match = {left:i, right:j-count} matches.push(match) actions.push(true) yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); count = count + 1 } finished.push(i) actions.push(false) i = i + 1 yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); } right_val = input[j] while (input[j] == right_val) { finished.push(j) actions.push(false) j = j - 1 yield two_display(input, {goal: goal, matches:matches, left:i, right:j, finished: finished, og_idx: og_idx }); } actions.push(false) } } actions.push(false) finished.push(i) yield two_display(input, {goal: goal, matches:matches, finished: finished, og_idx: og_idx}); output_data("better_sort", 2, actions, matches, start) }33:T590,This approach involves iterating through all values in a list one by one and putting each value in a dictionary associating any given value with all the index positions it can appear at; then it simply goes through all values in the array a second time and checks if the value needed to sum to the goal is in the "hash" (dictionary) and if it is, it simply adds the combination of these two values once for every index associated with the value in the hash. Since the process of putting information in the hash and the process of accessing information from the hash is, on balance, instantaneous due to the way this type of information is stored, both times we go through each value in the dictionary we will only need to really do about one action resulting in a number of operations equivalent to the length of the list times some constant (which can be approximated as two). This is easily visualized by using a very large array size where other algorithms are unable to make any results within a reasonable amount of time while this algorithm provides a solution within seconds. However, it should be noted that this probably isn't the best algorithm when we know that the array will be very small or when we want to avoid using extra space on the computer as the computer will always allocate space for each value and index in the array which would be an unnecessary cost for many basic usages of the two-sum algorithm.34:T5b7,hash_and_match = { var input, goal, matches, finished, og_idx, actions, hash, start; [input, goal, matches, finished, og_idx, actions, hash] = setup(2) yield* pauser(two_display(input, { goal: goal, immediate: true })); start = new Date() for (let i = 0; i < input.length; i++) { if (hash.get(input[i]) != undefined) hash.set(input[i], hash.get(input[i])+1) else hash.set(input[i], 1) yield two_display(input, { goal: goal, immediate: true, left: i, finished: finished, matches: matches, hash: hash }); actions.push(false); } let i = 0 let doubles = 1 for (let i = 0; i < input.length; i++) { yield two_display(input, {goal: goal, matches:matches, left:i, finished: finished, hash: hash, }); let desired = goal - input[i] let desired_matches = hash.get(desired) if (desired_matches && desired >= input[i]) { let j if (desired == input[i]) { j = doubles doubles += 1 } else j = 0 while (j < desired_matches) { var match = {left:i, hash_val:desired} matches.push(match) actions.push(true) j += 1 // yield two_display(input, {goal: goal, matches:matches, left:i, finished: finished, hash: hash}); } } finished.push(i) actions.push(false); } yield two_display(input, {goal: goal, matches:matches, finished: finished, hash: hash }); output_data("hash_match", 2, actions, matches, start) }35:T738,Below is an overall analysis of how these algorithms compare over time and by approximate number of actions. Neither of these are perfect methods as the time amount is largely dependent on system speed as well as what other processes are running at the same time (which is unpredictable), while the number of actions is hard to directly define (what is an action?) and can only be subjectively estimated. Still, these tools are really useful as a gauge of the overall O-value for time complexity as when we start to evaluate larger array sizes, the differences between these estimations tends to better reflect the true differences. Furthermore, several steps were done to ensure accuracy. For time, all algorithms were run one-by-one and all other active and controllable processes were closed. For actions, I tried to make a clear barometer for what can be considered an action only typically considering something an action if it involves an iteration or swap although this might not have been perfect. Furthermore, consistent settings were set for these experiments as follows: speed: 0, height: 800, range: [0:40], goal: 45, list_type: same random These graphs show a clear picture of how these algorithms compare. Both the naive approaches take an amount of time and an amount of actions proportional to the square of the length of the array to a very similar extent, which results in absurd run time of over 10 minutes for an array of length 200. Meanwhile, the hashing approach is linear in time and actions not even taking up half a minute for an array of 200 length. The better sorting approach lays somewhere in between with a less predictable line largely a testament to how the chosen sorting algorithm may vary based on the ordering of the given array and also a testament to how this algorithm should actually run in O(nlogn) time.36:T19b6,// function show_bars(dataset, {finished, left, right, immediate} = {} ) { function two_display(dataset, {goal, left, right, matches = [], finished = [], hash = [], og_idx = [], extra, immediate}) { let height = height_slider let buffer_1 = 0 let buffer_2 = 8 let buffer_h1 = 30 let arr_width = width*(dataset.length)/(dataset.length+2+matches.length) - buffer_1 - buffer_2 // let arr_height = height / 2 let xScale = d3.scaleBand() .domain(d3.range(dataset.length)) // .rangeRound([width-arr_width, width]) .range([0, arr_width]) // .padding(.05); .padding(.25/Math.sqrt(dataset.length)); let yScale = d3.scaleLinear() .domain([0, Math.max(d3.max(dataset), goal/2)]) .range([0, height/2-buffer_h1]); let svg = d3.select(DOM.svg(width, height)); svg.append("rect") .attr("width", "100%") .attr("height", "100%") .attr("fill", "#dbefff"); // array bars svg.selectAll("bars") .data(dataset) .enter().append("rect") .attr("x", (d, i) => xScale(i)) .attr("width", xScale.bandwidth()) .attr("y", d => height - yScale(d)) .attr("height", d => yScale(d)) .attr("fill", (d, i) => { // if (finished && finished.includes(i)) {return '#233b3b'} // else if (i == left || i == right || i == extra) {return 'lime'} // else {return 'steelblue'} // ;}) .attr("stroke", "black") .attr("stroke-width", "1"); // hash bars svg.selectAll("hash") .data(hash.keys()) .enter().append("rect") .attr("x", (d, i) => xScale(i)) .attr("width", xScale.bandwidth()) .attr("y", d => 0) .attr("height", d => yScale(d)) .attr("fill", (d, i) => { // if (goal - d == dataset[left]) {return 'lime'} // else {return 'wheat'} // ;}) .attr("stroke", "black") .attr("stroke-width", "1"); // matches svg.selectAll("matches_l") .data(matches) .enter().append("rect") .attr("x", (d, i) => arr_width + buffer_2 + i*xScale.bandwidth()) .attr("width", xScale.bandwidth()) .attr("y", d => { if (d.length > 1 || !("hash_val" in d)) {return height - yScale(dataset[d.left]);} else {return height - yScale(d.hash_val)} }) .attr("height", d => { if (d.length > 1 || !("hash_val" in d)) {return yScale(dataset[d.left]);} else {return yScale(d.hash_val);} }) .attr("fill", '#710000') .attr("stroke", "black") .attr("stroke-width", "3"); svg.selectAll("matches_r") .data(matches) .enter().append("rect") .attr("x", (d, i) => arr_width + buffer_2 + i*xScale.bandwidth()) .attr("width", xScale.bandwidth()) .attr("y", d => { // if ("right" in d) { return height - yScale(dataset[d.left]) - yScale(dataset[d.right])} // else if ("hash_val" in d) { return height - yScale(dataset[d.left]) - yScale(d.hash_val)} // }) // .attr("height", d => { // if ("right" in d) { return yScale(dataset[d.right])} else if ("hash_val" in d) { return yScale(d.hash_val)} }) // .attr("fill", 'black') .attr("stroke", "white") .attr("stroke-width", 4.2 - dataset.length/100 - matches.length/200); // .attr("stroke-width", (d) => { // if (dataset.length < 100) {return '4'} // // else if (dataset.length < 200) {return '3'} // else if (dataset.length < 300) {return '2'} // else if (dataset.length < 400) {return '2'} // else {return '0'} // }); // current combo svg.append("rect") // .attr("x", arr_width + buffer_2 + (1+matches.length) * xScale.bandwidth() + buffer_1) .attr("x", arr_width + buffer_2 + matches.length * xScale.bandwidth() + buffer_1) .attr("width", xScale.bandwidth()) .attr("y", height - yScale(dataset[left])) .attr("height", yScale(dataset[left])) // .attr("fill", '#8f5825') .attr("fill", '#FF7F50') .attr("stroke", "black") .attr("stroke-width", "3"); svg.append("rect") // .attr("x", arr_width + buffer_2 + (1+matches.length) * xScale.bandwidth() + buffer_1) .attr("x", arr_width + buffer_2 + matches.length * xScale.bandwidth() + buffer_1) .attr("width", xScale.bandwidth()) // .attr("y", height - yScale(dataset[left]) - yScale(dataset[right])) .attr("y", d => { if (right) {return height - yScale(dataset[left]) - yScale(dataset[right])} else {return height - yScale(dataset[left]) - yScale(goal-dataset[left])} }) // // .attr("height", yScale(dataset[right])) .attr("height", d => { // if (right) { return yScale(dataset[right])} else if (matches.length > 0) { return yScale(goal - dataset[left])} }) // .attr("fill", 'grey') .attr("stroke", "black") .attr("stroke-width", "3"); // goal svg.append("rect") // .attr("x", arr_width + buffer_2 + matches.length * xScale.bandwidth()) .attr("x", arr_width + buffer_2 + (1+matches.length) * xScale.bandwidth()) .attr("width", xScale.bandwidth()) .attr("y", height - yScale(goal)) .attr("height", yScale(goal)) // .attr("fill", 'wheat') .attr("fill", '#2a0254') .attr("stroke", "black") .attr("stroke-width", "3"); if (labels.includes("Values") && dataset.length + matches.length < 125) { svg.selectAll("bar_val_labels") .data(dataset) .enter().append("text") .attr("fill", "red") .attr("x", (d, i) => xScale(i) + xScale.bandwidth()/2) .attr("y", d => Math.min(height - 10 - .4*xScale.bandwidth(), height - yScale(d))) .attr("dy", -6 - 130/size) .text(d => d) .style("font-size", (d, i) => .75*xScale.bandwidth() + "px") .attr("text-anchor", "middle") .attr("dominant-baseline", "middle"); } if (labels.includes("Original_Index") && dataset.length + matches.length < 125) { svg.selectAll("bar_idx_labels") .data(dataset) .enter().append("text") .attr("fill", "white") .attr("x", (d, i) => xScale(i) + xScale.bandwidth()/2) .attr("y", height-1) .attr("dy", -6 - 130/size) .text((d,i) => { if (og_idx.length > 0) {return og_idx[i]} else {return i} }) .style("font-size", (d, i) => .75*xScale.bandwidth() + "px") .attr("text-anchor", "middle") .attr("dominant-baseline", "middle"); } return immediate ? svg.node() : Promises.delay(speed, svg.node()); }37:Ta02,sort_and_narrow_3 = { var input, goal, matches, finished, og_idx, actions, hash, start; [input, goal, matches, finished, og_idx, actions, hash] = setup(3); start = new Date() yield* pauser(three_display(input, { goal: goal, immediate: true })); for (let j = 1; j < input.length; j++) { let i = j - 1 yield three_display(input, {goal: goal, left: i, right: j, matches: matches }); while(i >= 0 && input[i] > input[i + 1]) { let temp = input[i] input[i] = input[i+1] input[i+1] = temp yield three_display(input, {goal: goal, left: i, right: i + 1, matches: matches }); i = i - 1 } } let end = input.length-1 let k for (k = 0; k < input.length-2; k++) { let sub_goal = goal - input[k] let i = k+1; yield three_display(input, {goal: goal, matches:matches, left:k, middle:i, right:end, finished: finished }); while (end > i && input[k] + input[i] + input[end] > goal) { finished.push(end) end = end - 1 yield three_display(input, {goal: goal, matches:matches, left:k, middle:i, right:end, finished: finished }); } let j = end while (i < j) { if (input[i] + input[j] > sub_goal) { j = j - 1 yield three_display(input, {goal: goal, matches:matches, left:k, middle:i, right:j, finished: finished }); } else if (input[i] + input[j] < sub_goal) { i = i + 1 yield three_display(input, {goal: goal, matches:matches, left:k, middle:i, right:j, finished: finished }); } else { let left_val = input[i] let right_val = input[j] while (input[i] == left_val) { let count = 0; while (input[j-count] == right_val && j-count > i) { var match = {left:k, middle:i, right:j-count} matches.push(match) yield three_display(input, {goal: goal, matches:matches, left:k, middle:i, right:j, finished: finished }); count = count + 1 } i = i + 1 yield three_display(input, {goal: goal, matches:matches, left:k, middle:i, right:j, finished: finished }); } right_val = input[j] while (input[j] == right_val) { j = j - 1 yield three_display(input, {goal: goal, matches:matches, left:k, middle:i, right:j, finished: finished, hash: hash }); } } } finished.push(k) } finished.push(k-1) finished.push(k) finished.push(k+1) // finished.push() yield three_display(input, {goal: goal, matches:matches, finished: finished, hash: hash}); }38:T1c05,// function show_bars(dataset, {finished, left, right, immediate} = {} ) { function three_display(dataset, {goal, left, middle, right, extra, active_val = [], active_hash = [], matches = [], finished = [], hash = [], og_idx =[], immediate}) { // let width = 1152 let height = height_slider let buffer_1 = 0 let buffer_2 = 8 let buffer_h1 = 30 let arr_width = width*(dataset.length)/(dataset.length+2+matches.length) - buffer_1 - buffer_2 let xScale = d3.scaleBand() .domain(d3.range(dataset.length)) .range([0, arr_width]) .padding(.25/Math.sqrt(dataset.length)); let yScale = d3.scaleLinear() .domain([0, Math.max(d3.max(dataset), goal/2)]) .range([0, height/2-buffer_h1]); let svg = d3.select(DOM.svg(width, height)); // background svg.append("rect") .attr("width", "100%") .attr("height", "100%") .attr("fill", "#dbefff"); // array bars svg.selectAll("bars") .data(dataset) .enter().append("rect") .attr("x", (d, i) => xScale(i)) .attr("width", xScale.bandwidth()) .attr("y", d => height - yScale(d)) .attr("height", d => yScale(d)) .attr("fill", (d, i) => { // if (finished && finished.includes(i)) {return '#233b3b'} // else if (i == left || i == right || i == middle || i == extra || i in active_val) {return 'lime'} // else {return 'steelblue'} // ;}) .attr("stroke", "black") .attr("stroke-width", "1"); // hash bars svg.selectAll("hash") .data(hash.keys()) .enter().append("rect") .attr("x", (d, i) => xScale(i)) .attr("width", xScale.bandwidth()) .attr("y", d => 0) .attr("height", d => yScale(d)) .attr("fill", (d, i) => { // if (d in active_hash) {return 'lime'} // // goal - d == dataset[left]) else {return 'wheat'} // ;}) .attr("stroke", "black") .attr("stroke-width", "1"); // matches svg.selectAll("matches_l") .data(matches) .enter().append("rect") .attr("x", (d, i) => arr_width + buffer_2 + i*xScale.bandwidth()) .attr("width", xScale.bandwidth()) .attr("y", d => height - yScale(dataset[d.left])) .attr("height", d => yScale(dataset[d.left])) .attr("fill", '#710000') .attr("stroke", "black") .attr("stroke-width", "3"); svg.selectAll("matches_m") .data(matches) .enter().append("rect") .attr("x", (d, i) => arr_width + buffer_2 + i*xScale.bandwidth()) .attr("width", xScale.bandwidth()) .attr("y", d => height - yScale(dataset[d.left]) - yScale(dataset[d.middle])) .attr("height", d => yScale(dataset[d.middle])) .attr("fill", 'orange'); // .attr("stroke", "black") // .attr("stroke-width", "3"); svg.selectAll("matches_r") .data(matches) .enter().append("rect") .attr("x", (d, i) => arr_width + buffer_2 + i*xScale.bandwidth()) .attr("width", xScale.bandwidth()) .attr("y", d => { // if ("right" in d) { return height - yScale(dataset[d.left]) - yScale(dataset[d.middle]) - yScale(dataset[d.right])} // else if ("hash_val" in d) { return height - yScale(dataset[d.left]) - yScale(d.hash_val)} // }) // .attr("height", d => { // if ("right" in d) { return yScale(dataset[d.right])} else if ("hash_val" in d) { return yScale(d.hash_val)} }) // .attr("fill", 'black') .attr("stroke", "white") .attr("stroke-width", 4.2 - dataset.length/100 - matches.length/200); // .attr("stroke-width", (d) => { // if (dataset.length < 100) {return '4'} // // else if (dataset.length < 200) {return '3'} // else if (dataset.length < 300) {return '2'} // else if (dataset.length < 400) {return '2'} // else {return '0'} // }); // current combo svg.append("rect") // .attr("x", arr_width + buffer_2 + (1+matches.length) * xScale.bandwidth() + buffer_1) .attr("x", arr_width + buffer_2 + matches.length * xScale.bandwidth() + buffer_1) .attr("width", xScale.bandwidth()) .attr("y", height - yScale(dataset[left])) .attr("height", yScale(dataset[left])) .attr("fill", '#8f5825') .attr("stroke", "black") .attr("stroke-width", "3"); svg.append("rect") // .attr("x", arr_width + buffer_2 + (1+matches.length) * xScale.bandwidth() + buffer_1) .attr("x", arr_width + buffer_2 + matches.length * xScale.bandwidth() + buffer_1) .attr("width", xScale.bandwidth()) .attr("y", height - yScale(dataset[left]) - yScale(dataset[middle])) .attr("height", yScale(dataset[middle])) .attr("fill", '#FF7F50') .attr("stroke", "black") .attr("stroke-width", "3"); svg.append("rect") .attr("x", arr_width + buffer_2 + matches.length * xScale.bandwidth() + buffer_1) .attr("width", xScale.bandwidth()) .attr("y", d => { if (right && middle) {return height - yScale(dataset[left]) - yScale(dataset[middle]) - yScale(dataset[right])} else if (right) {return height - yScale(dataset[left]) - yScale(dataset[right])} else {return height - yScale(dataset[left]) - yScale(goal-dataset[left])} }) // .attr("height", d => { // if (right) { return yScale(dataset[right])} else if (matches.length > 0) { return yScale(goal - dataset[left])} }) // .attr("fill", 'grey') .attr("stroke", "black") .attr("stroke-width", "3"); svg.append("rect") // .attr("x", arr_width + buffer_2 + matches.length * xScale.bandwidth()) .attr("x", arr_width + buffer_2 + (1+matches.length) * xScale.bandwidth()) .attr("width", xScale.bandwidth()) .attr("y", height - yScale(goal)) .attr("height", yScale(goal)) // .attr("fill", 'wheat') .attr("fill", '#2a0254') .attr("stroke", "black") .attr("stroke-width", "3"); if (labels.includes("Values") && dataset.length + matches.length < 125) { svg.selectAll("bar_val_labels") .data(dataset) .enter().append("text") .attr("fill", "red") .attr("x", (d, i) => xScale(i) + xScale.bandwidth()/2) .attr("y", d => Math.min(height - 10 - .4*xScale.bandwidth(), height - yScale(d))) .attr("dy", -6 - 130/size) .text(d => d) .style("font-size", (d, i) => .75*xScale.bandwidth() + "px") .attr("text-anchor", "middle") .attr("dominant-baseline", "middle"); } if (labels.includes("Original_Indeces") && dataset.length + matches.length < 125) { svg.selectAll("bar_idx_labels") .data(dataset) .enter().append("text") .attr("fill", "white") .attr("x", (d, i) => xScale(i) + xScale.bandwidth()/2) .attr("y", height-1) .attr("dy", -6 - 130/size) .text((d,i) => { if (og_idx.length > 0) {return og_idx[i]} else {return i} }) .style("font-size", (d, i) => .75*xScale.bandwidth() + "px") .attr("text-anchor", "middle") .attr("dominant-baseline", "middle"); } return immediate ? svg.node() : Promises.delay(speed, svg.node()); }39:Tb03,// function show_bars(dataset, {finished, left, right, immediate} = {} ) { function backup_show_bars_combo_matches(dataset, {goal, finished, left, right, immediate}) { // let goal_width = 50 let buffer_1 = 0 // let combo_width = 50 let buffer_2 = 0 // let arr_width = 1100 // let width = goal_width + buffer_1 + combo_width + buffer_2 + arr_width let width = 1000 let height = 1000 let arr_width = width*(dataset.length)/(dataset.length+2) - buffer_1 - buffer_2 let xScale = d3.scaleBand() .domain(d3.range(dataset.length)) .rangeRound([width-arr_width, width]) // .align(1) // .padding(0.05); let combo_width = xScale.bandwidth() let goal_width = xScale.bandwidth() // let arr_width = width let svg = d3.select(DOM.svg(width, height)); // ***Compensate for margins later // let margin = { bottom: 20, top: 10, left: 10, right: 10 }; let yScale = d3.scaleLinear() .domain([0, Math.max(d3.max(dataset), goal/2)]) .range([0, height/2]); // .nice() linear? svg.selectAll("bars") .data(dataset) .enter().append("rect") .attr("x", (d, i) => xScale(i)) .attr("width", xScale.bandwidth()) .attr("y", d => height - yScale(d)) .attr("height", d => yScale(d)) .attr("fill", (d, i) => { // if (finished && finished.includes(i)) {return 'darkslategrey'} // // if (finished == i) {return 'darkslategrey'} // else if (i == left || i == right) {return 'lime'} // else {return 'steelblue'} // ;}) .attr("stroke", "black") .attr("stroke-width", "1") svg.append("rect") // .attr("x", goal_width + buffer_1 + combo_width/2 - xScale.bandwidth()/2) .attr("x", combo_width/2 - xScale.bandwidth()/2) .attr("width", xScale.bandwidth()) .attr("y", height - yScale(dataset[left])) .attr("height", yScale(dataset[left])) .attr("fill", 'grey') .attr("stroke", "black") .attr("stroke-width", "3"); svg.append("rect") // .attr("/x", goal_width + buffer_1 + combo_width/2 - xScale.bandwidth()/2) .attr("x", combo_width/2 - xScale.bandwidth()/2) .attr("width", xScale.bandwidth()) .attr("y", d => height - yScale(dataset[left]) - yScale(dataset[right])) .attr("height", yScale(dataset[right])) .attr("fill", 'grey') .attr("stroke", "black") .attr("stroke-width", "3"); svg.append("rect") // .attr("x", goal_width/2 - xScale.bandwidth()/2) .attr("x", combo_width + buffer_1 + goal_width/2 - xScale.bandwidth()/2) .attr("width", xScale.bandwidth()) .attr("y", height - yScale(goal)) .attr("height", yScale(goal)) .attr("fill", 'wheat') .attr("stroke", "black") .attr("stroke-width", "3"); return immediate ? svg.node() : Promises.delay(speed, svg.node()); }3a:[{"id":"22ee697be7a2075006fec4c46ac18b4f313de051ea9f97c07d32986ca6d5dd82d0a8324b825ddb2eb87b19bb390e6a1c5a9ddee014aaf1835a0a05ea944bf9e0","href":"https://static.observableusercontent.com/files/22ee697be7a2075006fec4c46ac18b4f313de051ea9f97c07d32986ca6d5dd82d0a8324b825ddb2eb87b19bb390e6a1c5a9ddee014aaf1835a0a05ea944bf9e0","name":"time_chart(1).svg","type":"image/svg+xml","lastModified":1682135014599.216,"size":7411},{"id":"0d6f7d19ecc6d518d8f35165a0f1435eb9a4adf0b7367a2e91afcecbbfe68063b977fa848effc859ddcd1b996d61a2476a4da1420e032b1be3c9c8cda507a544","href":"https://static.observableusercontent.com/files/0d6f7d19ecc6d518d8f35165a0f1435eb9a4adf0b7367a2e91afcecbbfe68063b977fa848effc859ddcd1b996d61a2476a4da1420e032b1be3c9c8cda507a544","name":"actions_chart(1).svg","type":"image/svg+xml","lastModified":1682135083743.441,"size":6335}] 2d:{"title":"Visualizing Finding Sums in an Array","cells":[{"id":0,"value":"

Visualizing Finding Sums in an Array

","pinned":false,"hidden":false,"mode":"md"},{"id":1637,"value":"The two-sum problem is characterized as searching for all combination of two values in an array that add up to a specific goal value. Such a problem is immensely useful playing a foundational role in several basic array search operations like combination finding and as a sub-process in larger n-sum problems. However, novice coders often use certain solutions to this problem that work, in theory, but in practice are far too slow to be used on a larger scale. This notebook hopes to create a simple visualization that highlights the exact nature of the three fundamental approaches to this problem and the speed and space complexities associated with these approaches. ","pinned":false,"hidden":false,"mode":"md"},{"id":1676,"value":"$2f","pinned":false,"hidden":false,"mode":"md"},{"id":393,"value":"viewof size = slider({\n min: 2,\n max: 450,\n step: 1,\n title: \"Items\",\n value: 30\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":379,"value":"// add speed control here\nviewof speed = slider({\n min: 0,\n max: 1000,\n step: 5,\n title: \"Action Delay\",\n value: 20\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":859,"value":"viewof height_slider = slider({\n min: 100,\n max: 2000,\n step: 10,\n title: \"Height\",\n // value: 800\n value: 800\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":507,"value":"viewof value_range = interval([0, 200], {\n step: 1,\n value: [0, 40],\n label: 'Value Range',\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1169,"value":"viewof list_type = Inputs.select([\"unique\", \"same random\", \"sorted\", \"reverse sorted\"], {value: \"unique\", label: \"Generate unique arrays & goals?\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":992,"value":"viewof labels = Inputs.checkbox([\"Values\", \"Original_Index\"], {label: \"Labels\", value: [\"Values\", \"Original_Index\"]})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1180,"value":"default_array = Array.from({length: size}, () => Math.floor(Math.random() * (value_range[1]-value_range[0]+1)) + value_range[0]) ","pinned":false,"hidden":false,"mode":"ojs"},{"id":1249,"value":"sorted = [...default_array].sort((x,y)=>(x-y))","pinned":false,"hidden":false,"mode":"ojs"},{"id":1256,"value":"reversed = [...sorted].reverse()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1034,"value":"

Two-Sums

","pinned":false,"hidden":false,"mode":"md"},{"id":514,"value":"viewof two_goal_range = interval([2*value_range[0], 2*value_range[1]], {\n step: 1,\n value: [(value_range[1]+value_range[0]), 1.75*(value_range[1]+value_range[0])],\n label: 'Two Goal Range',\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1304,"value":"default_two_goal = Math.floor(Math.random() * (two_goal_range[1]-two_goal_range[0])) + two_goal_range[0]","pinned":false,"hidden":false,"mode":"ojs"},{"id":224,"value":"## Naive Two-Val","pinned":false,"hidden":false,"mode":"md"},{"id":297,"value":"At the most basic level, one can find all combinations summing up to a goal value by simply iterating through each combination of values. More specifically, we go through each value one by one and check its combination with all later values one by one. While this solution does work, it falters as we search through bigger list sizes as it requires us to do a number of searches approximately equivalent to the size of the list squared in both the worst and best case scenario. For example, if the list has 150 items in it, this algorithm will always search through 22,500 combination of values. However, it's not useless in all scenarios having utility when we know that we only want to sort a few values, such as 3 or 4, due to the lack of any extraneous processing and the lack of any extra space used.","pinned":false,"hidden":false,"mode":"md"},{"id":570,"value":"naive_two_val_flip = {\n var input, goal, matches, finished, og_idx, actions, hash, start;\n [input, goal, matches, finished, og_idx, actions, hash] = setup(2)\n yield* pauser(two_display(input, { goal: goal, immediate: true }));\n start = new Date()\n \n for (let i = 0; i < input.length; i++) {\n for (let j = i+1; j < input.length; j++) {\n if (input[i] + input[j] == goal) {\n var match = {left:i, right:j}\n matches.push(match)\n actions.push(true)\n }\n yield two_display(input, { goal: goal, finished: finished, left: i, right: j, matches: matches});\n actions.push(false);\n }\n finished.push(i)\n actions.push(false) \n }\n\n yield two_display(input, {goal: goal, finished: finished, matches: matches});\n output_data(\"naive_direct\", 2, actions, matches, start)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":599,"value":"## Naive Sort & Narrow","pinned":false,"hidden":false,"mode":"md"},{"id":1652,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":607,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":696,"value":"## Better sort & narrow","pinned":false,"hidden":false,"mode":"md"},{"id":1701,"value":"Below, it is shown just how efficient the sorting approach can be when using a better sorting algorithm. This uses the insertion sort method which is not necessarily the best algorithm but is ideal for visualizing a more streamlined sorting process that can, in most cases, save a lot of time. In the case of finding two-sums in an array that is likely sorted ascending or close to that, this is likely the best approach as it doesn't need to do much and can finish processing in about the same amount of operations as the length of the list. However, in the rare situation where the array is sorted in reverse relative to the algorithm's sorting method, this is just as bad as insertion sort as it will need to move all values to the left of the array one by one.","pinned":false,"hidden":false,"mode":"md"},{"id":669,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":657,"value":"## Hash and Match","pinned":false,"hidden":false,"mode":"md"},{"id":1706,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":655,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":1150,"value":"

Two Sum Analyses

","pinned":false,"hidden":false,"mode":"md"},{"id":1156,"value":"$35","pinned":false,"hidden":false,"mode":"md"},{"id":1752,"value":"actions_chart1 = FileAttachment(\"actions_chart(1).svg\").image()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1750,"value":"time_chart11 = FileAttachment(\"time_chart(1).svg\").image()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1754,"value":"Press play on the two cells below to create your own chart using the data from the runs of each algorithm that you've finished so far !","pinned":false,"hidden":false,"mode":"md"},{"id":1540,"value":"time_chart = LineChart(metadata, {\n x: d => d.size,\n y: d => d.time/1000,\n z: d => d.algo,\n xType: d3.scaleLinear,\n yLabel: \"Time (s)\",\n title: d => d.algo,\n width,\n height: 800,\n strokeWidth: 3.5,\n color: z => get_line_color(z),\n voronoi: false // if true, show Voronoi overlay\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1579,"value":"actions_chart = LineChart(metadata, {\n x: d => d.size,\n y: d => d.actions.length,\n z: d => d.algo,\n xType: d3.scaleLinear,\n yLabel: \"Approximate Number of Actions \",\n title: d => d.algo,\n width,\n height: 800,\n color: z => get_line_color(z),\n strokeWidth: 3.5,\n voronoi: false // if true, show Voronoi overlay\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1538,"value":"## Visualization Algorithm","pinned":false,"hidden":false,"mode":"md"},{"id":1767,"value":"The following algorithm was used to visualize the two-sum approach:","pinned":false,"hidden":false,"mode":"md"},{"id":705,"value":"$36","pinned":true,"hidden":false,"mode":"ojs"},{"id":1052,"value":"

Three-Sum

","pinned":false,"hidden":false,"mode":"md"},{"id":1772,"value":"Lastly, it should be recognized that the same approaches to two-sum can scale to larger sum approaches by merely combining different aspects of the various approaches described above. Below is an example of this for the three-sum approach where we first sort using the better insertion sort algorithm described above before combining this with what is essentially just a ccombination of the naive approach described above where at each combination of two values we also do the two-pointer method going downward. This solves this problem in an amount of time equivalent to n^2 without any extra space requirements of a hashing algorithm. With a more lengthy investigation, it'd be useful to explore the algorithm for three-sum and four-sum involving creating the hash of each summation and comparing it to each value for three-sum and each other combination in the hash for four_sum.","pinned":false,"hidden":false,"mode":"md"},{"id":1101,"value":"viewof three_goal_range = interval([3*value_range[0], 3*value_range[1]], {\n step: 1,\n value: [1.5*(value_range[1]+value_range[0]), 2.25*(value_range[1]+value_range[0])],\n label: 'Three Goal Range',\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1316,"value":"default_three_goal = Math.floor(Math.random() * (three_goal_range[1]-three_goal_range[0])) + three_goal_range[0]","pinned":false,"hidden":false,"mode":"ojs"},{"id":1074,"value":"$37","pinned":true,"hidden":false,"mode":"ojs"},{"id":1068,"value":"$38","pinned":true,"hidden":false,"mode":"ojs"},{"id":368,"value":"$39","pinned":false,"hidden":false,"mode":"ojs"},{"id":1328,"value":"## Functions","pinned":false,"hidden":false,"mode":"md"},{"id":1379,"value":"metadata = []","pinned":false,"hidden":false,"mode":"ojs"},{"id":1371,"value":"function output_data(algo, num_sum, actions, matches, start) {\n let end = new Date()\n let time = end - start\n var result = {\"algo\": algo, \"num_sum\": num_sum, \"size\": size, \"list_type\": list_type, \"actions\": actions, \"matches\": matches, \"time\": time, \"speed\": speed, }\n metadata.push(result)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1297,"value":"function setup(num_sum) {\n var input, goal, matches, finished, og_idx, actions, hash, date1\n [input, goal] = get_input(num_sum)\n\n matches = []\n finished = []\n actions = []\n hash = new Map()\n og_idx = [...Array(input.length).keys()]\n date1 = new Date()\n return [input, goal, matches, finished, og_idx, actions, hash, date1]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1294,"value":"function get_input(num_sum) {\n var input;\n var goal;\n if (list_type == \"unique\") {\n input = Array.from({length: size}, () => \n Math.floor(Math.random() * (value_range[1]-value_range[0]+1)) + value_range[0]);\n if (num_sum == 2)\n goal = Math.floor(Math.random() * (two_goal_range[1]-two_goal_range[0])) + two_goal_range[0]\n else if (num_sum == 3)\n goal = Math.floor(Math.random() * (three_goal_range[1]-three_goal_range[0])) + three_goal_range[0]\n }\n else if (list_type == \"sorted\") {\n input = [...sorted]\n if (num_sum == 2)\n goal = default_two_goal\n else if (num_sum == 3)\n goal = default_three_goal\n } else if (list_type == \"reverse sorted\") {\n input = [...reversed]\n if (num_sum == 2)\n goal = default_two_goal\n else if (num_sum == 3)\n goal = default_three_goal\n } else {\n input = [...default_array];\n if (num_sum == 2)\n goal = default_two_goal\n else if (num_sum == 3)\n goal = default_three_goal\n }\n return [input, goal]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1289,"value":"function swap(a, b, input, og_idx) {\n let temp = input[a]\n input[a] = input[b]\n input[b] = temp\n let i = og_idx[a]\n og_idx[a] = og_idx[b]\n og_idx[b] = i\n return input, og_idx\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1556,"value":"function get_line_color(z) {\n let d3_cat_colors = [\"#e41a1c\",\"#377eb8\",\"#4daf4a\",\"#984ea3\",\"#ff7f00\",\"#ffff33\",\"#a65628\",\"#f781bf\",\"#999999\"]\n if (z == \"hash_match\") {return d3_cat_colors[0]}\n else if (z == \"better_sort\") {return d3_cat_colors[1]}\n else if (z == \"naive_sort\") {return d3_cat_colors[2]}\n else {return d3_cat_colors[6]}\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":119,"value":"import {pauser} from \"@tmcw/pauser\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":384,"value":"import {slider} from \"@jashkenas/inputs\";","pinned":false,"hidden":false,"mode":"ojs"},{"id":509,"value":"import {interval} from '@mootari/range-slider@1786'","pinned":false,"hidden":false,"mode":"ojs"},{"id":1542,"value":"import {LineChart} from \"@d3/multi-line-chart\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":17,"value":"// d3 = require(\"d3@5\")\nd3 = require('d3')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W3a","stdlib":"1","titling":"auto"}