Guest User

Untitled

a guest
Oct 15th, 2019
112
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "raq.h"
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <cmath>
  5.  
  6. // Create the RAQ object; perform precomputation
  7. RAQ::RAQ(std::vector<float> data){
  8. m_dataCopy = data;
  9. m_dataSize = int(data.size());
  10.  
  11. raqComp();
  12. }
  13.  
  14. // Query the RAQ for interval [i, j]
  15. float RAQ::query(int i, int j) const{
  16. if(0 <= i and i <= j and j <= m_dataSize-1){
  17. return m_avgValues[i][j];
  18. }
  19. else{
  20. throw std::domain_error("RAQ::query() i or j value is out of bounds");
  21. }
  22. }
  23.  
  24. // Dump the RAQ data structure to stdout
  25. void RAQ::dump() const{
  26. for (int i = 0; i < m_avgValues.size(); i++){
  27. for (int j = i; j < m_avgValues[i].size(); j++){
  28. std::cout << " " << std::left << std::setw(7) << m_avgValues[i][j];
  29. }
  30. std::cout << std::endl;
  31. }
  32. std::cout << std::right;
  33. }
  34.  
  35. void RAQ::raqComp(){
  36.  
  37. for(int i = 0; i < m_dataSize; i++){
  38. std::vector<float> temp {};
  39.  
  40. if(i != 0){
  41. for (int j = 0; j < i; j++){
  42. temp.push_back(0);
  43. }
  44. }
  45.  
  46. temp.push_back(m_dataCopy[i]);
  47.  
  48. temp = update(i, i, m_dataCopy[i], temp);
  49.  
  50. m_avgValues.push_back(temp);
  51. }
  52. }
  53.  
  54. std::vector<float> RAQ::update(float i, float j, float prevAvg, std::vector<float> temp){
  55.  
  56. float avg;
  57.  
  58. //base case if j = size-1
  59. if(j == m_dataSize - 1){
  60.  
  61. return temp;
  62.  
  63. }
  64. else{
  65.  
  66. avg = ( ( (j - i + 1) * prevAvg ) + m_dataCopy[j+1] ) / (j-i+2);
  67.  
  68. temp.push_back(avg);
  69.  
  70. return update(i, j+1, avg, temp);
  71. }
  72.  
  73. }
  74.  
  75. //Beginning of BlockRAQ Code
  76.  
  77. // Create the BlockRAQ object; perform precomputation
  78. BlockRAQ::BlockRAQ(std::vector<float> data){
  79. //initialize member variables
  80. m_dataCopy = data;
  81. m_blockSize = calcBlockSize();
  82. m_dataSize = int(data.size());
  83. m_numBlocks = ceil(m_dataSize / m_blockSize);
  84.  
  85. //make the precomputations
  86. blockComp();
  87. }
  88.  
  89. // Query the BlockRAQ for interval [i, j]
  90. float BlockRAQ::query(int i, int j) const{
  91.  
  92. if(0 <= i and i <= j and j <= m_dataSize-1){
  93.  
  94. float sum = 0;
  95. float range = j - i + 1;
  96. int size = m_blockSize;
  97. //low is the lower bound
  98. int low = i;
  99.  
  100. //for values before any full blocks
  101. while (low <= j and low % size != 0){
  102. sum += m_dataCopy[low];
  103. low++;
  104. }
  105. //for values that make up entire blocks
  106. while(low +size <= j+1 and low % size == 0){
  107. sum += m_blockAverages[(low/size)] * 3;
  108. low += size;
  109. }
  110. //for values remaining after a block
  111. while (low <= j){
  112. sum += m_dataCopy[low];
  113. low++;
  114. }
  115.  
  116. return (sum/range);
  117.  
  118. }
  119. else{
  120. throw std::domain_error("BlockRAQ::query() i or j value is out of bounds");
  121. }
  122. }
  123.  
  124. // Dump the BlockRAQ data structure to stdout
  125. void BlockRAQ::dump() const{
  126. std::cout << "Num blocks: " << m_numBlocks<< std::endl;
  127. std::cout << "Block size: " << m_blockSize << std::endl;
  128. std::cout << "Block averages: " << std::endl;
  129. for(int i = 0; i < int(m_blockAverages.size()); i++){
  130. std::cout << m_blockAverages[i] << " ";
  131. }
  132. std::cout << std::endl;
  133.  
  134. }
  135.  
  136. void BlockRAQ::blockComp(){
  137. int tempSum = 0;
  138. float avg = 0;
  139. float counter = 0;
  140.  
  141. for (int i = 0; i < m_dataSize; i++){
  142. //summing the values for each block subgroup
  143. if (counter < m_blockSize){
  144. tempSum += m_dataCopy[i];
  145. counter++;
  146. }
  147. //if the block is the max size we add the average to the vector
  148. else{
  149. m_blockSums.push_back(tempSum);
  150. avg = tempSum / counter;
  151. m_blockAverages.push_back(avg);
  152. //if we're not at the end of the data vector we start the new sum
  153. tempSum = 0;
  154. tempSum += m_dataCopy[i];
  155. counter = 1;
  156. }
  157.  
  158. }
  159.  
  160. //This is a catch for a smaller final block
  161. //if the last block isn't completed than the tempSum value
  162. //will remain and we can add the smaller block to the averages
  163. if(tempSum != 0){
  164. m_blockSums.push_back(tempSum);
  165. avg = tempSum / counter;
  166. m_blockAverages.push_back(avg);
  167. }
  168.  
  169. }
  170.  
  171. int BlockRAQ::calcBlockSize(){
  172. int size = int(m_dataCopy.size());
  173. int bSize = (int) sqrt((float) size);
  174. return bSize;
  175.  
  176. }
RAW Paste Data