tuple/test/engagement_test.cpp - datasketches-cpp - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */

 #include <iostream>
 #include <iomanip>
 #include <set>
 #include <catch2/catch.hpp>
 #include <tuple_sketch.hpp>
 #include <tuple_union.hpp>
 #include <stdexcept>

 template<typename T>
 class max_value_policy {
 public:
     max_value_policy(const T& initial_value): initial_value(initial_value) {}
     T create() const { return initial_value; }
     void update(T& summary, const T& update) const { summary = std::max(summary, update); }
 private:
     T initial_value;
 };

 using max_float_update_tuple_sketch = datasketches::update_tuple_sketch<float, float, max_value_policy<float>>;

 template<typename T>
 class always_one_policy {
 public:
     always_one_policy(): initial_value(1) {}
     T create() const { return 1; }
     void update(T&, const T&) const {}
 private:
     T initial_value;
 };
 using always_one_tuple_sketch = datasketches::update_tuple_sketch<int, int, always_one_policy<int>>;

 template<typename T>
 class update_sum_value_policy {
 public:
     update_sum_value_policy(): initial_value(0) {}
     T create() const { return initial_value; }
     void update(T& summary, const T& update) const { summary += update; }
 private:
     T initial_value;
 };
 using sum_update_tuple_sketch = datasketches::update_tuple_sketch<int, int, update_sum_value_policy<int>>;

 template<typename Summary>
 struct union_sum_value_policy {
     void operator()(Summary& summary, const Summary& other) const {
         summary += other;
     }
 };

 using sum_union_tuple_sketch = datasketches::tuple_union<int, union_sum_value_policy<int>>;


 class EngagementTest {
 public:
     uint8_t num_std_dev = 2;
     void test_always_one_update() {
         /*
          * Tests that updates into an update_tuple_sketch sketch only keeps a 1 in the column for stored values.
          */
         uint8_t lgK = 8;
         std::vector<datasketches::update_tuple_sketch<int, int, always_one_policy<int>>> sketch_array;

         auto always_one_sketch = always_one_tuple_sketch::builder(always_one_policy<int>()).set_lg_k(lgK).build();

         always_one_sketch.update(1, 1);
         always_one_sketch.update(1, 2);
         always_one_sketch.update(2, 1);
         always_one_sketch.update(3, 3);
         always_one_sketch.update(3, 7);

         int num_retained = 0;
         int sum = 0;
         for (const auto& entry: always_one_sketch) {
             sum += entry.second;
             ++num_retained;
         }
         REQUIRE(num_retained == 3);
         REQUIRE(sum == 3); // we only keep 1 for every stored key.
     }

     void test_sum_update_policy() {
         /*
         * Tests that updates into an sum_update_tuple_sketch sum the stored values on updates.
         */
         uint8_t lgK = 8;
         auto sum_sketch = sum_update_tuple_sketch::builder().set_lg_k(lgK).build();

         sum_sketch.update(1, 1);
         sum_sketch.update(1, 2);
         sum_sketch.update(2, 1);
         sum_sketch.update(3, 3);
         sum_sketch.update(3, 7);
         int num_retained = 0;
         int sum = 0;
         for (const auto& entry: sum_sketch) {
             sum += entry.second;
             ++num_retained;
         }
         REQUIRE(num_retained == 3);
         REQUIRE(sum == 14); // (1+2) + 1 + (3 + 7) = 14
     }

     void test_sum_union_policy(){
         /*
          * Tests that updates into two sketches of sum_update_tuple_sketch flavour, which have been unioned,
          * cause the stored values of two of the same keys to be summed.
          */
         auto sketch1 = sum_update_tuple_sketch::builder().build();
         auto sketch2 = sum_update_tuple_sketch::builder().build();

         sketch1.update(1, 1);
         sketch1.update(2, 1);
         sketch1.update(3, 3);

         sketch2.update(1, 2);
         sketch2.update(2, 1);
         sketch2.update(3, 7);

         auto union_sketch = sum_union_tuple_sketch::builder().build();
         union_sketch.update(sketch1);
         union_sketch.update(sketch2);
         auto union_result = union_sketch.get_result();

         int num_retained = 0;
         int sum = 0;
         for (const auto& entry: union_result) {
             sum += entry.second;
             ++num_retained;
         }
         REQUIRE(num_retained == 3);
         REQUIRE(sum == 15); // 1:(1+2) + 2:(1+1) + 3:(3+7) = 15
     }

     void compute_engagement_histogram() {
         /*
          * Returns the estimated histogram from the synthetic data.
          * On inspection one can verify this agrees with the
          * https://github.com/apache/datasketches-java/blob/master/src/test/java/org/apache/datasketches/tuple/aninteger/EngagementTest.java
          */
         uint8_t lgK = 8;
         const int days = 30;
         int v = 0;
         std::set<int> set_array[days];
         std::vector<datasketches::update_tuple_sketch<int, int, always_one_policy<int>>> sketch_array;


         for (int i = 0; i < days; ++i) {
             auto builder = always_one_tuple_sketch::builder(always_one_policy<int>());
             builder.set_lg_k(lgK);
             auto sketch = builder.build();
             sketch_array.push_back(sketch);
         }
         REQUIRE(sketch_array.size() == days);

         for (int i = 0; i <= days; ++i) {
             int32_t num_ids = get_num_ids(days, i);
             int32_t num_days = get_num_days(days, i);

             int my_v = v++;
             for (int d = 0; d < num_days; ++d) {
                 for (int id = 0; id < num_ids; ++id) {
                     set_array[d].insert(my_v + id);
                     sketch_array[d].update(my_v + id, 1);
                 }
             }
             v += num_ids;
         }
         union_ops(lgK, sketch_array);
     }
 private:
     int32_t get_num_ids(int total_days, int index) {
         /*
          * Generates power law distributed synthetic data
          */
         double d = total_days;
         double i = index;
         return int(round(exp(i * log(d) / d)));
     }

     int32_t get_num_days(int total_days, int index) {
         double d = total_days;
         double i = index;
         return int(round(exp((d-i) * log(d) / d )));
     }

     int32_t round_double_to_int(double x) {
         return int(std::round(x));
     }

     void union_ops(uint8_t lgk, std::vector<datasketches::update_tuple_sketch<int, int, always_one_policy<int>>> sketches) {
         auto num_sketches = sketches.size();
         auto u = sum_union_tuple_sketch::builder().set_lg_k(lgk).build();

         for (auto sk: sketches) {
             u.update(sk);
         }
         auto union_result = u.get_result();
         std::vector<uint64_t> num_days_arr(num_sketches+1);

         for (const auto& entry: union_result) {
             int num_days_visited = entry.second;
             ++num_days_arr[num_days_visited];
         }

         uint64_t sum_visits = 0;
         double theta = union_result.get_theta();
         std::cout <<"\t\tEngagement Histogram.\t\t\t\n";
         std::cout << "Number of Unique Visitors by Number of Days Visited" << std::endl;
         std::cout << "---------------------------------------------------" << std::endl;

         std::cout << std::setw(12) << "Days Visited"
                   << std::setw(12) << "Estimate"
                   << std::setw(12) << "LB"
                   << std::setw(12) << "UB"
                   << std:: endl;

         for (size_t i = 0; i < num_days_arr.size(); ++i) {
             auto visitors_at_days_visited = num_days_arr[i];
             if (visitors_at_days_visited == 0) continue;
             sum_visits += visitors_at_days_visited * i;

             double est_visitors_at_days_visited = visitors_at_days_visited / theta;
             double lower_bound_at_days_visited =  union_result.get_lower_bound(num_std_dev, visitors_at_days_visited);
             double upper_bound_at_days_visited =  union_result.get_upper_bound(num_std_dev, visitors_at_days_visited);

             std::cout << std::setw(12) << i
                       << std::setw(12) << est_visitors_at_days_visited
                       << std::setw(12) << lower_bound_at_days_visited
                       << std::setw(12) << upper_bound_at_days_visited
                       << std:: endl;
         }
         std::cout << std::endl << std::endl;
         std::cout << std::setw(12) << "Totals"
                   << std::setw(12) << "Estimate"
                   << std::setw(12) << "LB"
                   << std::setw(12) << "UB"
                   << std:: endl;
         std::cout << "---------------------------------------------------" << std::endl;

         const double total_visitors = union_result.get_estimate();
         const double lb_visitors = union_result.get_lower_bound(num_std_dev);
         const double ub_visitors = union_result.get_upper_bound(num_std_dev);

         std::cout << std::setw(12) << "Visitors"
                   << std::setw(12) << total_visitors
                   << std::setw(12) << lb_visitors
                   << std::setw(12) << ub_visitors
                   << std:: endl;

         // The total number of visits, however, is a scaled metric and takes advantage of the fact that
         // the retained entries in the sketch is a uniform random sample of all unique visitors, and
         // the  rest of the unique users will likely behave in the same way.
         const double est_visits = sum_visits / theta;
         const double lb_visits = est_visits * lb_visitors / total_visitors;
         const double ub_visits = est_visits * ub_visitors / total_visitors;

         std::cout << std::setw(12) << "Visits"
                   << std::setw(12) << est_visits
                   << std::setw(12) << lb_visits
                   << std::setw(12) << ub_visits
                   << std:: endl;
     }

 };

 namespace datasketches {

   TEST_CASE("engagement", "[engagement]") {
     EngagementTest E;
     E.test_always_one_update();
     E.test_sum_update_policy();
     E.test_sum_union_policy();
     E.compute_engagement_histogram();
   }

 } /* namespace datasketches */
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*/

	#include <iostream>
	#include <iomanip>
	#include <set>
	#include <catch2/catch.hpp>
	#include <tuple_sketch.hpp>
	#include <tuple_union.hpp>
	#include <stdexcept>

	template<typename T>
	class max_value_policy {
	public:
	max_value_policy(const T& initial_value): initial_value(initial_value) {}
	T create() const { return initial_value; }
	void update(T& summary, const T& update) const { summary = std::max(summary, update); }
	private:
	T initial_value;
	};

	using max_float_update_tuple_sketch = datasketches::update_tuple_sketch<float, float, max_value_policy<float>>;

	template<typename T>
	class always_one_policy {
	public:
	always_one_policy(): initial_value(1) {}
	T create() const { return 1; }
	void update(T&, const T&) const {}
	private:
	T initial_value;
	};
	using always_one_tuple_sketch = datasketches::update_tuple_sketch<int, int, always_one_policy<int>>;

	template<typename T>
	class update_sum_value_policy {
	public:
	update_sum_value_policy(): initial_value(0) {}
	T create() const { return initial_value; }
	void update(T& summary, const T& update) const { summary += update; }
	private:
	T initial_value;
	};
	using sum_update_tuple_sketch = datasketches::update_tuple_sketch<int, int, update_sum_value_policy<int>>;

	template<typename Summary>
	struct union_sum_value_policy {
	void operator()(Summary& summary, const Summary& other) const {
	summary += other;
	}
	};

	using sum_union_tuple_sketch = datasketches::tuple_union<int, union_sum_value_policy<int>>;


	class EngagementTest {
	public:
	uint8_t num_std_dev = 2;
	void test_always_one_update() {
	/*
	* Tests that updates into an update_tuple_sketch sketch only keeps a 1 in the column for stored values.
	*/
	uint8_t lgK = 8;
	std::vector<datasketches::update_tuple_sketch<int, int, always_one_policy<int>>> sketch_array;

	auto always_one_sketch = always_one_tuple_sketch::builder(always_one_policy<int>()).set_lg_k(lgK).build();

	always_one_sketch.update(1, 1);
	always_one_sketch.update(1, 2);
	always_one_sketch.update(2, 1);
	always_one_sketch.update(3, 3);
	always_one_sketch.update(3, 7);

	int num_retained = 0;
	int sum = 0;
	for (const auto& entry: always_one_sketch) {
	sum += entry.second;
	++num_retained;
	}
	REQUIRE(num_retained == 3);
	REQUIRE(sum == 3); // we only keep 1 for every stored key.
	}

	void test_sum_update_policy() {
	/*
	* Tests that updates into an sum_update_tuple_sketch sum the stored values on updates.
	*/
	uint8_t lgK = 8;
	auto sum_sketch = sum_update_tuple_sketch::builder().set_lg_k(lgK).build();

	sum_sketch.update(1, 1);
	sum_sketch.update(1, 2);
	sum_sketch.update(2, 1);
	sum_sketch.update(3, 3);
	sum_sketch.update(3, 7);
	int num_retained = 0;
	int sum = 0;
	for (const auto& entry: sum_sketch) {
	sum += entry.second;
	++num_retained;
	}
	REQUIRE(num_retained == 3);
	REQUIRE(sum == 14); // (1+2) + 1 + (3 + 7) = 14
	}

	void test_sum_union_policy(){
	/*
	* Tests that updates into two sketches of sum_update_tuple_sketch flavour, which have been unioned,
	* cause the stored values of two of the same keys to be summed.
	*/
	auto sketch1 = sum_update_tuple_sketch::builder().build();
	auto sketch2 = sum_update_tuple_sketch::builder().build();

	sketch1.update(1, 1);
	sketch1.update(2, 1);
	sketch1.update(3, 3);

	sketch2.update(1, 2);
	sketch2.update(2, 1);
	sketch2.update(3, 7);

	auto union_sketch = sum_union_tuple_sketch::builder().build();
	union_sketch.update(sketch1);
	union_sketch.update(sketch2);
	auto union_result = union_sketch.get_result();

	int num_retained = 0;
	int sum = 0;
	for (const auto& entry: union_result) {
	sum += entry.second;
	++num_retained;
	}
	REQUIRE(num_retained == 3);
	REQUIRE(sum == 15); // 1:(1+2) + 2:(1+1) + 3:(3+7) = 15
	}

	void compute_engagement_histogram() {
	/*
	* Returns the estimated histogram from the synthetic data.
	* On inspection one can verify this agrees with the
	* https://github.com/apache/datasketches-java/blob/master/src/test/java/org/apache/datasketches/tuple/aninteger/EngagementTest.java
	*/
	uint8_t lgK = 8;
	const int days = 30;
	int v = 0;
	std::set<int> set_array[days];
	std::vector<datasketches::update_tuple_sketch<int, int, always_one_policy<int>>> sketch_array;


	for (int i = 0; i < days; ++i) {
	auto builder = always_one_tuple_sketch::builder(always_one_policy<int>());
	builder.set_lg_k(lgK);
	auto sketch = builder.build();
	sketch_array.push_back(sketch);
	}
	REQUIRE(sketch_array.size() == days);

	for (int i = 0; i <= days; ++i) {
	int32_t num_ids = get_num_ids(days, i);
	int32_t num_days = get_num_days(days, i);

	int my_v = v++;
	for (int d = 0; d < num_days; ++d) {
	for (int id = 0; id < num_ids; ++id) {
	set_array[d].insert(my_v + id);
	sketch_array[d].update(my_v + id, 1);
	}
	}
	v += num_ids;
	}
	union_ops(lgK, sketch_array);
	}
	private:
	int32_t get_num_ids(int total_days, int index) {
	/*
	* Generates power law distributed synthetic data
	*/
	double d = total_days;
	double i = index;
	return int(round(exp(i * log(d) / d)));
	}

	int32_t get_num_days(int total_days, int index) {
	double d = total_days;
	double i = index;
	return int(round(exp((d-i) * log(d) / d )));
	}

	int32_t round_double_to_int(double x) {
	return int(std::round(x));
	}

	void union_ops(uint8_t lgk, std::vector<datasketches::update_tuple_sketch<int, int, always_one_policy<int>>> sketches) {
	auto num_sketches = sketches.size();
	auto u = sum_union_tuple_sketch::builder().set_lg_k(lgk).build();

	for (auto sk: sketches) {
	u.update(sk);
	}
	auto union_result = u.get_result();
	std::vector<uint64_t> num_days_arr(num_sketches+1);

	for (const auto& entry: union_result) {
	int num_days_visited = entry.second;
	++num_days_arr[num_days_visited];
	}

	uint64_t sum_visits = 0;
	double theta = union_result.get_theta();
	std::cout <<"\t\tEngagement Histogram.\t\t\t\n";
	std::cout << "Number of Unique Visitors by Number of Days Visited" << std::endl;
	std::cout << "---------------------------------------------------" << std::endl;

	std::cout << std::setw(12) << "Days Visited"
	<< std::setw(12) << "Estimate"
	<< std::setw(12) << "LB"
	<< std::setw(12) << "UB"
	<< std:: endl;

	for (size_t i = 0; i < num_days_arr.size(); ++i) {
	auto visitors_at_days_visited = num_days_arr[i];
	if (visitors_at_days_visited == 0) continue;
	sum_visits += visitors_at_days_visited * i;

	double est_visitors_at_days_visited = visitors_at_days_visited / theta;
	double lower_bound_at_days_visited = union_result.get_lower_bound(num_std_dev, visitors_at_days_visited);
	double upper_bound_at_days_visited = union_result.get_upper_bound(num_std_dev, visitors_at_days_visited);

	std::cout << std::setw(12) << i
	<< std::setw(12) << est_visitors_at_days_visited
	<< std::setw(12) << lower_bound_at_days_visited
	<< std::setw(12) << upper_bound_at_days_visited
	<< std:: endl;
	}
	std::cout << std::endl << std::endl;
	std::cout << std::setw(12) << "Totals"
	<< std::setw(12) << "Estimate"
	<< std::setw(12) << "LB"
	<< std::setw(12) << "UB"
	<< std:: endl;
	std::cout << "---------------------------------------------------" << std::endl;

	const double total_visitors = union_result.get_estimate();
	const double lb_visitors = union_result.get_lower_bound(num_std_dev);
	const double ub_visitors = union_result.get_upper_bound(num_std_dev);

	std::cout << std::setw(12) << "Visitors"
	<< std::setw(12) << total_visitors
	<< std::setw(12) << lb_visitors
	<< std::setw(12) << ub_visitors
	<< std:: endl;

	// The total number of visits, however, is a scaled metric and takes advantage of the fact that
	// the retained entries in the sketch is a uniform random sample of all unique visitors, and
	// the rest of the unique users will likely behave in the same way.
	const double est_visits = sum_visits / theta;
	const double lb_visits = est_visits * lb_visitors / total_visitors;
	const double ub_visits = est_visits * ub_visitors / total_visitors;

	std::cout << std::setw(12) << "Visits"
	<< std::setw(12) << est_visits
	<< std::setw(12) << lb_visits
	<< std::setw(12) << ub_visits
	<< std:: endl;
	}

	};

	namespace datasketches {

	TEST_CASE("engagement", "[engagement]") {
	EngagementTest E;
	E.test_always_one_update();
	E.test_sum_update_policy();
	E.test_sum_union_policy();
	E.compute_engagement_histogram();
	}

	} /* namespace datasketches */