Heap based algorithm (Avg. O(nlogn)) beats Hash based algorithm (Avg. O(n)) from 2^5 to 2^23


  • 0
    Z

    Hello world! I am sharing this very fast, heap based algorithm. I will explain the notion behind my alg. first. Then, I will show some benchmark result between my algorithm and hash based algorithms with length ranging from 2^5 to 2^23.

    First things first, the idea:

    1. We know that if a+b=target, then a<target/2 and b>target/2, or a,b=target/2
      Therefore, if we first partition our sequence into 3 parts (A<target/2;B=target/2;C>target/2), we can simplify our search. If part B contains two numbers, they are the answers. Otherwise, we will need to proceed to check part A and C. (complexity O(n))
    2. Let the largest number of part A plus the smallest number of part C. If the sum is target, lucky! You get the result. Otherwise, the sum can be either smaller than the target or bigger than the target. If the sum is smaller, for example, the smallest number from C can be discarded, because other numbers from A, that is smaller than the largest number from A, will only produce a even smaller sum, when added to our smallest number from C. Since each comparison eliminates a number from A or C, we have O(n) for comparison.
    3. Notice that we do not need to have the numbers sorted. if we make use of max and min heap for A and C respectively, we can try to find our two numbers while sorting our sequence. We need O(n) for building heaps, and O(nlogn) to have our sequence partially sorted.
      Quite to my surprise, this alg. runs at most twice as fast as hash based alg. (see below)
      The code is below for inspection. Have fun.

    About hash based O(n) solution: (see topic 3294 for code)

    I did the benchmark because several other posts have pointed out that the hash based algorithm is slow, and there are also arguments that hash based alg. is not O(n). To settle the debates, I ran a few benchmarks on my local machine. The test sequences were generated randomly, put into a unordered_set and checked to eliminate adding numbers that sum up to target. Then I can control where the answer to put inside the sequence.
    Anyway, with these long sequences, I got the following the result (averages of 100 to 3 repeats, unit: us):

    N     hash alg.    heap alg.
    32        29          12
    64	  61	      25
    128	 117          56
    256      235         121
    512      462         261
    1024     925         548
    2048    1932         1185
    4096    3951         2462
    8192    8042         5229
    16384  16372        11019
    32768  33816        23462
    65536  80363        49982
    131072 176597      105490
    262144  367625     224972
    524288  755913     490834
    1048576 1483167   1089676
    2097152 3038274   2418336
    4194304 6295344   5311888
    8388608 13271319 11692934
    

    You may copy the data into spreadsheet and plot them out. Even better, calculate the slopes like in calculus 101, plot the change in slope out too. O(n) solution should have a constant slope.

    Heap based alg. is O(nlogn), no doubt. Hash based alg. is more or less O(n) if we ignore a bump in the slope at N=~2^16, where the slope increased from 1 to 1.5 and stabilizes there afterward. Whatever the bump is, hash based alg. is O(n), in theory and mostly in practice, but hashing and conflict resolution are probably so computationally expensive, that hash based alg is slower than heap based alg even for reasonable large datasets. The slope of heap based alg. does increase, but it starts from ~0.4 to ~1.4, the slope never surpass the slope of hash based alg (~1, and then ~1.5) within my test range. Yes, eventually, heap based alg should fall behind, but not on my machine (2^24 ints overflow my 4GB RAM).

    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target){
            vector<int> vecResult(2);
            int size=numbers.size();
            int* tmpArr=new int[size];
            int left=0,right=size-1,swapSpace;
            int endL,startR,endR=size-1;
            
            //copy numbers vector into tmpArr
            for (int i=0;i<size;i++){
                tmpArr[i]=numbers[i];
            }
            
            //partitions tmpArr into A'<=half and C>half
            while (left<=right){
                if (tmpArr[left]*2<=target){
                    left++;
                }
                else if (tmpArr[right]*2>target){
                    right--;
                }
                else {
                    swapSpace=tmpArr[left];
                    tmpArr[left]=tmpArr[right];
                    tmpArr[right]=swapSpace;
                    left++;
                    right--;
                }
            }
            startR=left;
    
            //partitions tmpArr part A' from above into A<half and B=half
            left=0;
            while (left<=right){
                if (tmpArr[left]*2<target){
                    left++;
                }
                else if (tmpArr[right]*2==target){
                    right--;
                }
                else {
                    swapSpace=tmpArr[left];
                    tmpArr[left]=tmpArr[right];
                    tmpArr[right]=swapSpace;
                    left++;
                    right--;
                }
            }
            endL=right;
            //now, the tmpArr is partitioned into 3 parts:
            //A, B, C, where for all x in A, x<half
            //               for all x in B, x==half
            //               for all x in C, x>half
            
            if (startR-endL-1==2){
            //when two number==half is found
            //find such two numbers in the original vec
                int pos=0;
                for (int i=0;pos<2 && i<size;i++){
                    if ( numbers[i]*2==target ){
                        vecResult[pos]=i;
                        pos++;
                    }
                }
                return vecResult;
            }
            else {
            //when two number==half is NOT found
            //build max heap on the first part of vector that contains numbers smaller than half
            //build min heap on the thrid part of vector that contains numbers largerer than half
                make_heap(tmpArr,tmpArr+endL+1); //max heap
                make_heap(tmpArr+startR,tmpArr+endR+1,greater<int>()); //min heap
    
                while (endL>=0 && endR-startR>=0){
                    if (tmpArr[0]+tmpArr[startR]>target){
                    //the biggest number (say a) in part A plus the smallest number in C is larger than target
                    //we have: for any x in C, a+x>target
                    //remove a from A
                        pop_heap(tmpArr,tmpArr+endL+1);
                        endL--;
                    }
                    else if (tmpArr[0]+tmpArr[startR]<target){
                    //the biggest number in part A plus the smallest number (say c) in C is smaller than target
                    //we have: for any x in A, x+c<target
                    //remove c from C
                        pop_heap(tmpArr+startR,tmpArr+endR+1,greater<int>());
                        endR--;
                    }
                    else {
                        //found tmpArr[0]+tmpArr[startR]==target
                        for (int i=0,pos=0; pos<=1 && i<size;i++){
                            if ( numbers[i]==tmpArr[0] || numbers[i]==tmpArr[startR]){
                                vecResult[pos]=i;
                                pos++;
                            }
                        }
                        break;
                    }
                }
                return vecResult;
            }
            delete [] tmpArr;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.