SHARE
TWEET

Untitled

bbescos Feb 24th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. // {1, 4, 5}   <--- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0} N n
  6. // {6, -2, 0}  <--- {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1} N m
  7.  
  8. // SparseVector
  9. struct SparseVector {
  10.     vector<pair<int,int>> vals; // first:= index , second:= value
  11. };
  12.  
  13. // Run-time complexity O(N)
  14. // Memory complexity O(1)
  15.  
  16. int DotProduct(const vector<int>& v1, const vector<int>& v2) {
  17.     int ans = 0;
  18.     for (int i = 0; i < v1.size(); ++i) {
  19.         if (v1[i] != 0 && v2[i] != 0)
  20.             ans += v1[i]*v2[i];
  21.     }
  22.     return ans;
  23. }
  24.  
  25. // (1, 5, 4, 3)  (4, 3, 7 ,8)
  26.  
  27. // ans = 3*3 + 4*4 + 8*8
  28.  
  29. // (1, 3, 4, 8)
  30. //  ^
  31. // (3, 4, 7 ,8)
  32. //  ^
  33. // (
  34.  
  35. // Run-time complexity O(m*n)
  36. // Memory complexity O(1)
  37.  
  38. int SparseDotProduct(const SparseVector& v1, const SparseVector& v2) {
  39.     int ans = 0;
  40.     for (int i = 0; i < v1.vals.size(); ++i) {
  41.         for (int j = 0; j < v2.vals.size(); ++j) {
  42.             if (v1.vals[i].first == v2.vals[i].first)
  43.                 ans += v1.vals[i].second * v2.vals[i].second;
  44.         }
  45.     }
  46.     return ans;
  47. }
  48.  
  49. // (1, 3, 4, 5)  (3, 4, 7 ,8)
  50.  
  51. // (1, 3, 4, 5)
  52. //  ^
  53. // (3, 4, 7 ,8)
  54. //  ^
  55. // ans = 3*3 + 4*4
  56.  
  57. // Run-time complexity O(m + n)
  58. // Memory complexity O(1)
  59.  
  60. int SparseDotProduct(const SparseVector& v1, const SparseVector& v2) {
  61.     int ans = 0;
  62.     int i1 = 0;
  63.     int i2 = 0;
  64.     while (i1 < v1.vals.size() && i2 < v2.vals.size()) {
  65.         if (v1.vals[i1].first == v2.vals[i2].first)
  66.             ans += v1.vals[i1++].second * v2.vals[i2++].second;
  67.         else {
  68.             if (v1.vals[i1].first < v2.vals[i2].first)
  69.                 ++i1;
  70.             else
  71.                 ++i2;
  72.         }
  73.     }
  74.     return ans;
  75. }
  76.  
  77. // SparseVector
  78. struct SparseVector {
  79.     unordered_map<int, int> vals; // first:= index , second:= value
  80. };
  81.  
  82. // O(min(n, m))
  83. int SparseDotProduct(const SparseVector& v1, const SparseVector& v2) {
  84.  
  85.     if (v1.vals.size() > v2.vals.size())
  86.         return SparseDotProduct(v2, v1);
  87.    
  88.     int ans = 0;
  89.     for (auto it = v1.vals.begin(); it != v1.vals.end(); ++it) {
  90.         if (v2.vals.count(it->first) == 1)
  91.             ans += it->second * v2.vals[it->first];
  92.     }
  93.    
  94.     return ans;
  95. }
  96.  
  97.  
  98. // [x]
  99. // [ ]
  100. // [y]
  101. // [ ]
  102.  
  103. // hash_function(input)  ->  index e [0, table_size)
  104. //     return input % table_size;
  105.  
  106. // unordered_map<int, int> hash;
  107. // hash[5] = 10;
  108. // hash_function(5) -> 5, hash.internal_table[5] = 10;
  109.  
  110. // hash[70000] = 8;
  111. // hash_function(70000) -> 8, hash.internal_table[8] = 8;
  112.  
  113. // hash[5443] = 3;
  114. // hash_function(5443) -> 5 // collision! -> 6; hash.internal_table[6] = 3
  115.  
  116. int main(){
  117.  
  118. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top