Dot Product - FB Prepare

http://www.cnblogs.com/EdwardLiu/p/6399867.html

Conduct Dot Product of two large Vectors

1. two pointers

2. hashmap

3. 如果没有额外空间，如果一个很大，一个很小，适合scan小的，并且在大的里面做binary search

 5     public int dotPro(int[][] v1, int[][] v2) {
 6         int[][] shortV;
 7         int[][] longV;
 8         if (v1.length < v2.length) {
 9             shortV = v1;
10             longV = v2;
11         }
12         else {
13             shortV = v2;
14             longV = v1;
15         }
16         
17         int res = 0;
18         for (int i=0; i<shortV.length; i++) {
19             int shortIndex = shortV[i][0];
20             int shortValue = shortV[i][1];
21             int longSeq = binarySearch(longV, shortIndex);
22             if (longSeq >= 0) {
23                 res += shortValue * longV[longSeq][1];
24             }
25         }
26         return res;
27     }
28     
29     public int binarySearch(int[][] arr, int target) {
30         int l=0, r=arr.length-1;
31         while (l <= r) {
32             int m = (l+r)/2;
33             if (arr[m][0] == target) return m;
34             else if (arr[m][0] < target) l = m + 1;
35             else r = m - 1;
36         }
37         return -1;
38     }

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Vector%20Dot/VectorDot.java

    public int[] dotHash(int[] a, int[] b) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < a.length; i ++)
            if (a[i] > 0)
                map.put(i, a[i]);
        int[] c = new int[a.length];
        for (int i = 0; i < b.length; i ++)
            if (b[i] > 0 && map.containsKey(i))
                c[i] = b[i] * map.get(i);
        return c;
    }

    private class Vector {
        int index, value;
        public Vector(int index, int value){
            this.index = index;
            this.value = value;
        }
    }

    private int binarySearch(List<Vector> a, int target) {
        int l = 0, r = a.size();
        while (l < r - 1) {
            int mid = l + (r - l) / 2;
            if (a.get(mid).index == target)
                return a.get(mid).value;
            else if (a.get(mid).index < target)
                l = mid + 1;
            else r = mid;
        }
        if (l >= a.size() || a.get(l).index != target) return 0;
        return a.get(l).value;
    }

    public int[] dotList(int[] va, int[] vb) {
        List<Vector> a = new ArrayList<>();
        for (int i = 0; i < va.length; i ++)
            if (va[i] > 0)
                a.add(new Vector(i, va[i]));
        List<Vector> b = new ArrayList<>();
        for (int i = 0; i < vb.length; i ++)
            if (vb[i] > 0)
                b.add(new Vector(i, vb[i]));
        int[] c = new int[va.length];
        /*
        int i = 0, j = 0;
        while (i < a.size() && j < b.size()) {
            while (i < a.size() && a.get(i).index < b.get(j).index) i ++;
            if (i == a.size()) break;
            while (j < b.size() && a.get(i).index > b.get(j).index) j ++;
            if (j == b.size()) break;
            c[a.get(i).index] = a.get(i ++).value * b.get(j ++).value;
        }
        */

        for (int i = 0; i < b.size(); i ++) {
            int tmp = binarySearch(a, b.get(i).index);
            if (tmp != 0) {
                tmp *= b.get(i).value;
                c[b.get(i).index] = tmp;
            }
        }

        return c;
    }

1. VectorDot

HashMap (code)

2. VectorDot

TwoPointer (code)

3. VectorDot

BinarySearch (code)

稀疏向量量点积

1. 优化: hash -> array ->BS -> 两根指针

第⼀一个部分:如何处理理和表达这些原始数据。

第⼆二部分是完成运算。

Follow-up: ⽐比较细节的优化，点积代码中怎么减少不不必要的条件判断。假

设ia是 向量量A的iterator，ib是向量量B的iterator，while (ia < lenA && ib <

lenB)，如果循环内部只增加了了ib，那么(ia < lenA) 这个条件判断就是不不必

要的。while循环内部，再加循环确保ia ib都增加过。

2. ⼀一道点乘题，题⽬目⼤大概是这样的 <1,1,2,2, 3, 3, 3> * <4, 4, 4, 4, 5, 5,

7>问怎么优化存储。