Teacher Huang Shen’s title is really too good, can’t find better title to describe today’s learning content. Haha~

Divide and Conquer Thinking in Merge Sort

Problem: Sort a pile of messy unordered numbers according to rules from small to large or large to small

Ordered Case

Try merging ordered arrays {1, 2, 5, 8} and {3, 4, 6} process.

Unordered Case

Try to continuously simplify problem, i.e., continuously simplify sequence, until only 1 number remains. 1 number itself is ordered,

Simplify sequence of length n to sequence of length n-1 each time, until length 1. However, such processing has no parallelism, need n-1 merge operations, but efficiency will be very low.

Introduce Divide and Conquer Thinking

Divide and Conquer, we usually abbreviate as divide and conquer. Its thinking is, decompose a complex problem into two or even multiple subproblems of same or similar scale, then further subdivide these subproblems, until final subproblems become very simple, easily solvable, then this complex problem is solved.

An array’s sorting

Two arrays sorted then merged

Most important thinking is how to decompose problem

Different stages of merge sort

Use Recursive Method to Implement Above Thinking

      // Recursively split array
      function merge_sort(to_sort) {
        // Invalid data, directly return []
        if (!to_sort) return [];
        
        // If decomposed to only one number, return that number
        if (to_sort.length == 1) return to_sort;
        
        // Decompose array into left and right halves
        let mid = to_sort.length / 2;

        // splice in js will modify original array content,
        // After taking first half, second half directly take original array variable reference
        let left = [].concat(to_sort.splice(0,mid))
        let right = [].concat(to_sort)

        // Nested calls, sort both halves separately
        left = merge_sort(left);
        right = merge_sort(right);
        
        // Merge sorted halves
        let merged = merge(left, right);
        
        return merged;
      }


// Array merge sort
function merge(a, b) {
    if (!a) a = [];
    if (!b) b = [];
    
    // Will push results to this array later
    let merged_one = []
    
    // a,b array indices
    let ai = 0;
    let bi = 0;
    
    // Alternately take smaller values from two arrays, put into merged array
    while (ai < a.length && bi < b.length) {
     if (a[ai] <= b[bi]) {
        merged_one.push(a[ai])
      ai ++;
     } else {
        merged_one.push(b[bi])
      bi ++;
     }
    }
    
    // Put remaining numbers from some array into merged array
    if (ai < a.length) {
     for (let i = ai; i < a.length; i++) {
      merged_one.push(a[i])
     }
    } else {
     for (let i = bi; i < b.length; i++) {
      merged_one.push(b[i])
     }
    }
    
    return merged_one;
   }


let arr = [2,5,3,1,4,6,7,8,9]

console.log('Sort result',merge_sort(arr))
// Sort result [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

Divide and Conquer Thinking in Distributed Systems

When array to sort is very large (like reaching 1024GB), we can’t stuff all this data into one ordinary machine’s memory. What to do? One method, we can decompose this super large dataset into multiple smaller datasets (like 16GB or smaller), then distribute to multiple machines, let them process in parallel.

MapReduce Architecture

Three Steps Use Divide and Conquer Thinking

Data Segmentation and Mapping Segmentation

Refers to segmenting data source, and sending segments to Mapper. Mapping refers to Mapper according to application needs, storing content according to key-value matching into hash structure.

Reduction

Reduction refers to receiving a set of key-value pairs, if pairs have same key content, merge their values. This is similar to local recursive call then return result process

Merge

To improve shuffle stage efficiency, can choose to reduce key-value pairs sent to reduction stage. Specific method is add merge process between data mapping and shuffle, perform one local reduction on each Mapper node first. Then only send merged results to shuffle and reduction stages. This is similar to local recursive call then return result process

Afterword

Recursion, decompose complex problems into simple problems,

Then preset all failure situations you can think of (emergency plan), handle them.

A recursive algorithm comes out.

Article Link: