SHARE
TWEET

Untitled

bbescos Feb 24th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Compiled with: g++ -Wall -std=c++14 -pthread
  2.  
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. // {1, 4, 5}   <--- {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0} N n
  10. // {6, -2, 0}  <--- {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1} N m
  11.  
  12. // SparseVector
  13. struct SparseVector {
  14.     vector<pair<int,int>> vals; // first:= index , second:= value
  15. };
  16.  
  17. // O(N)
  18. int DotProduct(const vector<int>& v1, const vector<int>& v2) {
  19.  
  20.     int ans = 0;
  21.    
  22.     for (int i = 0; i < v1.size(); ++i) {
  23.         if (v1[i] != 0 && v2[i] != 0)
  24.             ans += v1[i]*v2[i];
  25.     }
  26.     return ans;
  27. }
  28.  
  29. // O(n*m)  {4, 3, 7, 8}
  30. // O(1)    {1, 5, 4, 3}
  31. // (1, 5, 4, 3)  (4, 3, 7 ,8)
  32.  
  33. // ans = 3*3 + 4*4 + 8*8
  34.  
  35. // (1, 3, 4, 8)
  36. //  ^
  37. // (3, 4, 7 ,8)
  38. //  ^
  39. // (
  40.  
  41. // O(m + n)
  42.  
  43. int SparseDotProduct(const SparseVector& v1, const SparseVector& v2) {
  44.  
  45.     int ans = 0;
  46.    
  47.     for (int i = 0; i < v1.vals.size(); ++i) {
  48.         for (int j = 0; j < v2.vals.size(); ++j) {
  49.             if (v1.vals[i].first == v2.vals[i].first)
  50.                 ans += v1.vals[i].second * v2.vals[i].second;
  51.         }
  52.     }
  53.     return ans;
  54. }
  55.  
  56. // O(m + n)
  57. int IntersectionSparseDotProduct(const SparseVector& v1, const SparseVector& v2) {
  58.  
  59.     int ans = 0;
  60.    
  61.     int i1 = 0;
  62.     int i2 = 0;
  63.    
  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.    
  75.     return ans;
  76. }
  77.  
  78. // SparseVector
  79. struct SparseVector2 {
  80.     unordered_map<int, int> vals; // first:= index , second:= value
  81. };
  82.  
  83. // O(min(n, m))
  84. int HashSparseDotProduct(const SparseVector2& v1, const SparseVector2& v2) {
  85.  
  86.     if (v1.vals.size() > v2.vals.size())
  87.         return HashSparseDotProduct(v2, v1);
  88.    
  89.     int ans = 0;
  90.    
  91.     // for (auto& pair: v1.vals)
  92.     for (auto it = v1.vals.begin(); it != v1.vals.end(); ++it) {
  93.         if (v2.vals.count(it->first) == 1)
  94.             ans += it->second * v2.vals[it->first];
  95.     }
  96.    
  97.     return ans;
  98. }
  99.  
  100.  
  101. // [x]
  102. // [ ]
  103. // [y]
  104. // [ ]
  105.  
  106.  
  107. //
  108. // hash_function(input)  ->  index e [0, table_size)
  109. //     return input % table_size;
  110.  
  111.  
  112. // unordered_map<int, int> hash;
  113. // hash[5] = 10;
  114. // hash_function(5) -> 5, hash.internal_table[5] = 10;
  115.  
  116.  
  117. // hash[70000] = 8;
  118. // hash_function(70000) -> 8, hash.internal_table[8] = 8;
  119.  
  120.  
  121. // hash[5443] = 3
  122. // hash_function(5443) -> 5 // collision! -> 6; hash.internal_table[6] = 3
  123. //
  124.  
  125.  
  126.  
  127. int main(){
  128.  
  129. }
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