You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@quickstep.apache.org by hbdeshmukh <gi...@git.apache.org> on 2017/10/06 04:16:28 UTC
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
GitHub user hbdeshmukh opened a pull request:
https://github.com/apache/incubator-quickstep/pull/309
Add ProbabilityStore class
- Used to store probabilities of objects.
- Probabilities are of two kinds: Individual and cumulative.
- All the individual probabilities within the store add up to one.
- Support for finding the object with given cumulative probability.
This PR is in continuation with the set of PRs for QUICKSTEP-107.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/hbdeshmukh/incubator-quickstep probability-store
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/incubator-quickstep/pull/309.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #309
----
commit eca1c37ed146fdf4601a1d4c4536086c184a14f0
Author: Harshad Deshmukh <hb...@apache.org>
Date: 2017-09-29T20:38:42Z
Add ProbabilityStore class
- Used to store probabilities of objects.
- Probabilities are of two kinds: Individual and cumulative.
- All the individual probabilities within the store add up to one.
- Support for finding the object with given cumulative probability.
----
---
[GitHub] incubator-quickstep issue #309: Added ProbabilityStore class
Posted by hbdeshmukh <gi...@git.apache.org>.
Github user hbdeshmukh commented on the issue:
https://github.com/apache/incubator-quickstep/pull/309
Thanks for the comments. I have addressed all of them. The precision with floats is good enough for our use case.
---
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on a diff in the pull request:
https://github.com/apache/incubator-quickstep/pull/309#discussion_r143528439
--- Diff: query_execution/tests/ProbabilityStore_unittest.cpp ---
@@ -0,0 +1,106 @@
+/**
+ * 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 <cstddef>
+#include <vector>
+
+#include "gtest/gtest.h"
+
+#include "query_execution/ProbabilityStore.hpp"
--- End diff --
Per header order, move it to the top.
---
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on a diff in the pull request:
https://github.com/apache/incubator-quickstep/pull/309#discussion_r143525719
--- Diff: query_execution/ProbabilityStore.hpp ---
@@ -0,0 +1,274 @@
+/**
+ * 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.
+ **/
+
+#ifndef QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+#define QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <random>
+#include <unordered_map>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/**
+ * @brief A class that stores the probabilities of objects. We use an integer field
+ * called "key" to identify each object.
+ * A probability is expressed as a fraction. All the objects share a common denominator.
+ **/
+class ProbabilityStore {
+ public:
+ /**
+ * @brief Constructor.
+ **/
+ ProbabilityStore()
+ : common_denominator_(1.0) {}
+
+ /**
+ * @brief Get the number of objects in the store.
+ **/
+ inline const std::size_t getNumObjects() const {
+ DCHECK_EQ(individual_probabilities_.size(), cumulative_probabilities_.size());
+ return individual_probabilities_.size();
+ }
+
+ /**
+ * @brief Get the common denominator.
+ */
+ inline const std::size_t getDenominator() const {
+ return common_denominator_;
+ }
+
+ /**
+ * @brief Check if an object with a given key is present.
+ * @param key The key of the given object.
+ * @return True if the object is present, false otherwise.
+ */
+ inline bool hasObject(const std::size_t key) const {
+ return (individual_probabilities_.find(key) != individual_probabilities_.end());
+ }
+
+ /**
+ * @brief Add individual (not cumulative) probability for a given object with
+ * updated denominator.
+ *
+ * @note This function leaves the cumulative probabilities in a consistent
+ * state. An alternative lazy implementation should be written if cost
+ * of calculating cumulative probabilities is high.
+ *
+ * @param key The key of the given object.
+ * @param numerator The numerator for the given object.
+ * @param new_denominator The updated denominator for the store.
+ **/
+ void addOrUpdateObjectNewDenominator(const std::size_t key,
+ const float numerator,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ DCHECK_LE(numerator, new_denominator);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectHelper(key, numerator);
+ }
+
+ /**
+ * @brief Add or update multiple objects with a new denominator.
+ * @param keys The keys to be added/updated.
+ * @param numerators The numerators to be added/updated.
+ * @param new_denominator The new denominator.
+ */
+ void addOrUpdateObjectsNewDenominator(
+ const std::vector<std::size_t> &keys,
+ const std::vector<float> &numerators,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectsHelper(keys, numerators);
+ }
+
+ /**
+ * @brief Remove an object from the store.
+ *
+ * @note This function decrements the denominator with the value of the numerator being removed.
+ *
+ * @param key The key of the object to be removed.
+ **/
+ void removeObject(const std::size_t key) {
+ auto individual_it = individual_probabilities_.find(key);
+ DCHECK(individual_it != individual_probabilities_.end());
+ const float new_denominator = common_denominator_ - individual_it->second;
+ individual_probabilities_.erase(individual_it);
+ common_denominator_ = new_denominator;
+ updateCumulativeProbabilities();
+ }
+
+ /**
+ * @brief Get the individual probability (not cumulative) for an object.
+ *
+ * @param key The key of the object.
+ **/
+ const float getIndividualProbability(const std::size_t key) const {
+ const auto it = individual_probabilities_.find(key);
+ DCHECK(it != individual_probabilities_.end());
+ return it->second / common_denominator_;
+ }
+
+ /**
+ * @brief Update the cumulative probabilities.
+ *
+ * @note This function should be called upon if there are any updates,
+ * additions or deletions to the individual probabilities.
+ * @note An efficient implementation should be written if there are large
+ * number of objects.
+ **/
+ void updateCumulativeProbabilities() {
+ cumulative_probabilities_.clear();
+ float cumulative_probability = 0;
+ for (const auto p : individual_probabilities_) {
+ cumulative_probability += p.second / common_denominator_;
+ cumulative_probabilities_.emplace_back(p.first,
+ cumulative_probability);
+ }
+ if (!cumulative_probabilities_.empty()) {
+ // Adjust the last cumulative probability manually to 1, so that
+ // floating addition related rounding issues are ignored.
+ cumulative_probabilities_.back().updateProbability(1);
+ }
+ }
+
+ /**
+ * @brief Return a randomly chosen key.
+ *
+ * TODO(harshad) - If it is expensive to create the random device
+ * on every invocation of this function, make it a class variable.
+ * In which case, we won't be able to mark the function as const.
+ *
+ * @note The random number is uniformly chosen.
+ **/
+ inline const std::size_t pickRandomKey() const {
+ std::uniform_real_distribution<float> dist(0.0, 1.0);
+ std::random_device rd;
+ const float chosen_probability = dist(rd);
+ return getKeyForProbability(chosen_probability);
+ }
+
+ private:
+ class ProbabilityInfo {
--- End diff --
It seems a `struct` to me.
---
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on a diff in the pull request:
https://github.com/apache/incubator-quickstep/pull/309#discussion_r143524550
--- Diff: query_execution/ProbabilityStore.hpp ---
@@ -0,0 +1,274 @@
+/**
+ * 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.
+ **/
+
+#ifndef QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+#define QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <random>
+#include <unordered_map>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/**
+ * @brief A class that stores the probabilities of objects. We use an integer field
+ * called "key" to identify each object.
+ * A probability is expressed as a fraction. All the objects share a common denominator.
+ **/
+class ProbabilityStore {
+ public:
+ /**
+ * @brief Constructor.
+ **/
+ ProbabilityStore()
+ : common_denominator_(1.0) {}
+
+ /**
+ * @brief Get the number of objects in the store.
+ **/
+ inline const std::size_t getNumObjects() const {
+ DCHECK_EQ(individual_probabilities_.size(), cumulative_probabilities_.size());
+ return individual_probabilities_.size();
+ }
+
+ /**
+ * @brief Get the common denominator.
+ */
+ inline const std::size_t getDenominator() const {
+ return common_denominator_;
+ }
+
+ /**
+ * @brief Check if an object with a given key is present.
+ * @param key The key of the given object.
+ * @return True if the object is present, false otherwise.
+ */
+ inline bool hasObject(const std::size_t key) const {
+ return (individual_probabilities_.find(key) != individual_probabilities_.end());
+ }
+
+ /**
+ * @brief Add individual (not cumulative) probability for a given object with
+ * updated denominator.
+ *
+ * @note This function leaves the cumulative probabilities in a consistent
+ * state. An alternative lazy implementation should be written if cost
+ * of calculating cumulative probabilities is high.
+ *
+ * @param key The key of the given object.
+ * @param numerator The numerator for the given object.
+ * @param new_denominator The updated denominator for the store.
+ **/
+ void addOrUpdateObjectNewDenominator(const std::size_t key,
+ const float numerator,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ DCHECK_LE(numerator, new_denominator);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectHelper(key, numerator);
+ }
+
+ /**
+ * @brief Add or update multiple objects with a new denominator.
+ * @param keys The keys to be added/updated.
+ * @param numerators The numerators to be added/updated.
+ * @param new_denominator The new denominator.
+ */
+ void addOrUpdateObjectsNewDenominator(
+ const std::vector<std::size_t> &keys,
+ const std::vector<float> &numerators,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectsHelper(keys, numerators);
+ }
+
+ /**
+ * @brief Remove an object from the store.
+ *
+ * @note This function decrements the denominator with the value of the numerator being removed.
+ *
+ * @param key The key of the object to be removed.
+ **/
+ void removeObject(const std::size_t key) {
+ auto individual_it = individual_probabilities_.find(key);
+ DCHECK(individual_it != individual_probabilities_.end());
+ const float new_denominator = common_denominator_ - individual_it->second;
+ individual_probabilities_.erase(individual_it);
+ common_denominator_ = new_denominator;
+ updateCumulativeProbabilities();
+ }
+
+ /**
+ * @brief Get the individual probability (not cumulative) for an object.
+ *
+ * @param key The key of the object.
+ **/
+ const float getIndividualProbability(const std::size_t key) const {
+ const auto it = individual_probabilities_.find(key);
+ DCHECK(it != individual_probabilities_.end());
+ return it->second / common_denominator_;
+ }
+
+ /**
+ * @brief Update the cumulative probabilities.
+ *
+ * @note This function should be called upon if there are any updates,
+ * additions or deletions to the individual probabilities.
+ * @note An efficient implementation should be written if there are large
+ * number of objects.
+ **/
+ void updateCumulativeProbabilities() {
+ cumulative_probabilities_.clear();
+ float cumulative_probability = 0;
+ for (const auto p : individual_probabilities_) {
+ cumulative_probability += p.second / common_denominator_;
+ cumulative_probabilities_.emplace_back(p.first,
+ cumulative_probability);
+ }
+ if (!cumulative_probabilities_.empty()) {
+ // Adjust the last cumulative probability manually to 1, so that
+ // floating addition related rounding issues are ignored.
+ cumulative_probabilities_.back().updateProbability(1);
+ }
+ }
+
+ /**
+ * @brief Return a randomly chosen key.
+ *
+ * TODO(harshad) - If it is expensive to create the random device
+ * on every invocation of this function, make it a class variable.
+ * In which case, we won't be able to mark the function as const.
+ *
+ * @note The random number is uniformly chosen.
+ **/
+ inline const std::size_t pickRandomKey() const {
+ std::uniform_real_distribution<float> dist(0.0, 1.0);
+ std::random_device rd;
+ const float chosen_probability = dist(rd);
--- End diff --
Two things: first, this implementation seems not to be uniformly random, as you create the pseudo generator each call. So the returned value should be the same all the time.
On the other hand, `const` property is not an issue by marking the generator `mutable`. See https://github.com/apache/incubator-quickstep/blob/master/catalog/PartitionSchemeHeader.hpp#L243.
---
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on a diff in the pull request:
https://github.com/apache/incubator-quickstep/pull/309#discussion_r143527518
--- Diff: query_execution/ProbabilityStore.hpp ---
@@ -0,0 +1,274 @@
+/**
+ * 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.
+ **/
+
+#ifndef QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+#define QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <random>
+#include <unordered_map>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/**
+ * @brief A class that stores the probabilities of objects. We use an integer field
+ * called "key" to identify each object.
+ * A probability is expressed as a fraction. All the objects share a common denominator.
+ **/
+class ProbabilityStore {
+ public:
+ /**
+ * @brief Constructor.
+ **/
+ ProbabilityStore()
+ : common_denominator_(1.0) {}
+
+ /**
+ * @brief Get the number of objects in the store.
+ **/
+ inline const std::size_t getNumObjects() const {
+ DCHECK_EQ(individual_probabilities_.size(), cumulative_probabilities_.size());
+ return individual_probabilities_.size();
+ }
+
+ /**
+ * @brief Get the common denominator.
+ */
+ inline const std::size_t getDenominator() const {
+ return common_denominator_;
+ }
+
+ /**
+ * @brief Check if an object with a given key is present.
+ * @param key The key of the given object.
+ * @return True if the object is present, false otherwise.
+ */
+ inline bool hasObject(const std::size_t key) const {
+ return (individual_probabilities_.find(key) != individual_probabilities_.end());
+ }
+
+ /**
+ * @brief Add individual (not cumulative) probability for a given object with
+ * updated denominator.
+ *
+ * @note This function leaves the cumulative probabilities in a consistent
+ * state. An alternative lazy implementation should be written if cost
+ * of calculating cumulative probabilities is high.
+ *
+ * @param key The key of the given object.
+ * @param numerator The numerator for the given object.
+ * @param new_denominator The updated denominator for the store.
+ **/
+ void addOrUpdateObjectNewDenominator(const std::size_t key,
+ const float numerator,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ DCHECK_LE(numerator, new_denominator);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectHelper(key, numerator);
+ }
+
+ /**
+ * @brief Add or update multiple objects with a new denominator.
+ * @param keys The keys to be added/updated.
+ * @param numerators The numerators to be added/updated.
+ * @param new_denominator The new denominator.
+ */
+ void addOrUpdateObjectsNewDenominator(
+ const std::vector<std::size_t> &keys,
+ const std::vector<float> &numerators,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectsHelper(keys, numerators);
+ }
+
+ /**
+ * @brief Remove an object from the store.
+ *
+ * @note This function decrements the denominator with the value of the numerator being removed.
+ *
+ * @param key The key of the object to be removed.
+ **/
+ void removeObject(const std::size_t key) {
+ auto individual_it = individual_probabilities_.find(key);
+ DCHECK(individual_it != individual_probabilities_.end());
+ const float new_denominator = common_denominator_ - individual_it->second;
+ individual_probabilities_.erase(individual_it);
+ common_denominator_ = new_denominator;
+ updateCumulativeProbabilities();
+ }
+
+ /**
+ * @brief Get the individual probability (not cumulative) for an object.
+ *
+ * @param key The key of the object.
+ **/
+ const float getIndividualProbability(const std::size_t key) const {
+ const auto it = individual_probabilities_.find(key);
+ DCHECK(it != individual_probabilities_.end());
+ return it->second / common_denominator_;
+ }
+
+ /**
+ * @brief Update the cumulative probabilities.
+ *
+ * @note This function should be called upon if there are any updates,
+ * additions or deletions to the individual probabilities.
+ * @note An efficient implementation should be written if there are large
+ * number of objects.
+ **/
+ void updateCumulativeProbabilities() {
+ cumulative_probabilities_.clear();
+ float cumulative_probability = 0;
+ for (const auto p : individual_probabilities_) {
+ cumulative_probability += p.second / common_denominator_;
+ cumulative_probabilities_.emplace_back(p.first,
+ cumulative_probability);
+ }
+ if (!cumulative_probabilities_.empty()) {
+ // Adjust the last cumulative probability manually to 1, so that
+ // floating addition related rounding issues are ignored.
+ cumulative_probabilities_.back().updateProbability(1);
+ }
+ }
+
+ /**
+ * @brief Return a randomly chosen key.
+ *
+ * TODO(harshad) - If it is expensive to create the random device
+ * on every invocation of this function, make it a class variable.
+ * In which case, we won't be able to mark the function as const.
+ *
+ * @note The random number is uniformly chosen.
+ **/
+ inline const std::size_t pickRandomKey() const {
+ std::uniform_real_distribution<float> dist(0.0, 1.0);
+ std::random_device rd;
+ const float chosen_probability = dist(rd);
+ return getKeyForProbability(chosen_probability);
+ }
+
+ private:
+ class ProbabilityInfo {
+ public:
+ ProbabilityInfo(const std::size_t key, const float probability)
+ : key_(key), probability_(probability) {
+ // As GLOG doesn't provide DEBUG only checks for less than equal
+ // comparison for floats, we can't ensure that probability is less than
+ // 1.0.
+ }
+
+ ProbabilityInfo(const ProbabilityInfo &other) = default;
+
+ ProbabilityInfo& operator=(const ProbabilityInfo &other) = default;
+
+ void updateProbability(const float new_probability) {
+ probability_ = new_probability;
+ }
+
+ std::size_t key_;
+ float probability_;
+ };
+
+ /**
+ * @brief Get a key for a given cumulative probability.
+ *
+ * @param key_cumulative_probability The input cumulative probability.
+ *
+ * @return The object that has a cumulative probability that is greater than
+ * or equal to the input cumulative probability.
+ **/
+ inline const std::size_t getKeyForProbability(
--- End diff --
Remove `const`.
---
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on a diff in the pull request:
https://github.com/apache/incubator-quickstep/pull/309#discussion_r143522609
--- Diff: query_execution/ProbabilityStore.hpp ---
@@ -0,0 +1,274 @@
+/**
+ * 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.
+ **/
+
+#ifndef QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+#define QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <random>
+#include <unordered_map>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/**
+ * @brief A class that stores the probabilities of objects. We use an integer field
+ * called "key" to identify each object.
+ * A probability is expressed as a fraction. All the objects share a common denominator.
+ **/
+class ProbabilityStore {
+ public:
+ /**
+ * @brief Constructor.
+ **/
+ ProbabilityStore()
+ : common_denominator_(1.0) {}
+
+ /**
+ * @brief Get the number of objects in the store.
+ **/
+ inline const std::size_t getNumObjects() const {
+ DCHECK_EQ(individual_probabilities_.size(), cumulative_probabilities_.size());
+ return individual_probabilities_.size();
+ }
+
+ /**
+ * @brief Get the common denominator.
+ */
+ inline const std::size_t getDenominator() const {
+ return common_denominator_;
+ }
+
+ /**
+ * @brief Check if an object with a given key is present.
+ * @param key The key of the given object.
+ * @return True if the object is present, false otherwise.
+ */
+ inline bool hasObject(const std::size_t key) const {
+ return (individual_probabilities_.find(key) != individual_probabilities_.end());
+ }
+
+ /**
+ * @brief Add individual (not cumulative) probability for a given object with
+ * updated denominator.
+ *
+ * @note This function leaves the cumulative probabilities in a consistent
+ * state. An alternative lazy implementation should be written if cost
+ * of calculating cumulative probabilities is high.
+ *
+ * @param key The key of the given object.
+ * @param numerator The numerator for the given object.
+ * @param new_denominator The updated denominator for the store.
+ **/
+ void addOrUpdateObjectNewDenominator(const std::size_t key,
+ const float numerator,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ DCHECK_LE(numerator, new_denominator);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectHelper(key, numerator);
+ }
+
+ /**
+ * @brief Add or update multiple objects with a new denominator.
+ * @param keys The keys to be added/updated.
+ * @param numerators The numerators to be added/updated.
+ * @param new_denominator The new denominator.
+ */
+ void addOrUpdateObjectsNewDenominator(
+ const std::vector<std::size_t> &keys,
+ const std::vector<float> &numerators,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectsHelper(keys, numerators);
+ }
+
+ /**
+ * @brief Remove an object from the store.
+ *
+ * @note This function decrements the denominator with the value of the numerator being removed.
+ *
+ * @param key The key of the object to be removed.
+ **/
+ void removeObject(const std::size_t key) {
+ auto individual_it = individual_probabilities_.find(key);
+ DCHECK(individual_it != individual_probabilities_.end());
+ const float new_denominator = common_denominator_ - individual_it->second;
+ individual_probabilities_.erase(individual_it);
+ common_denominator_ = new_denominator;
+ updateCumulativeProbabilities();
+ }
+
+ /**
+ * @brief Get the individual probability (not cumulative) for an object.
+ *
+ * @param key The key of the object.
+ **/
+ const float getIndividualProbability(const std::size_t key) const {
+ const auto it = individual_probabilities_.find(key);
+ DCHECK(it != individual_probabilities_.end());
+ return it->second / common_denominator_;
--- End diff --
Do we need to check `common_denominator_` is non-zero?
---
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on a diff in the pull request:
https://github.com/apache/incubator-quickstep/pull/309#discussion_r143522055
--- Diff: query_execution/ProbabilityStore.hpp ---
@@ -0,0 +1,274 @@
+/**
+ * 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.
+ **/
+
+#ifndef QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+#define QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <random>
+#include <unordered_map>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/**
+ * @brief A class that stores the probabilities of objects. We use an integer field
+ * called "key" to identify each object.
+ * A probability is expressed as a fraction. All the objects share a common denominator.
+ **/
+class ProbabilityStore {
+ public:
+ /**
+ * @brief Constructor.
+ **/
+ ProbabilityStore()
+ : common_denominator_(1.0) {}
+
+ /**
+ * @brief Get the number of objects in the store.
+ **/
+ inline const std::size_t getNumObjects() const {
+ DCHECK_EQ(individual_probabilities_.size(), cumulative_probabilities_.size());
+ return individual_probabilities_.size();
+ }
+
+ /**
+ * @brief Get the common denominator.
+ */
+ inline const std::size_t getDenominator() const {
--- End diff --
Remove `const` in the return type.
---
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on a diff in the pull request:
https://github.com/apache/incubator-quickstep/pull/309#discussion_r143527465
--- Diff: query_execution/ProbabilityStore.hpp ---
@@ -0,0 +1,274 @@
+/**
+ * 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.
+ **/
+
+#ifndef QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+#define QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <random>
+#include <unordered_map>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/**
+ * @brief A class that stores the probabilities of objects. We use an integer field
+ * called "key" to identify each object.
+ * A probability is expressed as a fraction. All the objects share a common denominator.
+ **/
+class ProbabilityStore {
+ public:
+ /**
+ * @brief Constructor.
+ **/
+ ProbabilityStore()
+ : common_denominator_(1.0) {}
+
+ /**
+ * @brief Get the number of objects in the store.
+ **/
+ inline const std::size_t getNumObjects() const {
+ DCHECK_EQ(individual_probabilities_.size(), cumulative_probabilities_.size());
+ return individual_probabilities_.size();
+ }
+
+ /**
+ * @brief Get the common denominator.
+ */
+ inline const std::size_t getDenominator() const {
+ return common_denominator_;
+ }
+
+ /**
+ * @brief Check if an object with a given key is present.
+ * @param key The key of the given object.
+ * @return True if the object is present, false otherwise.
+ */
+ inline bool hasObject(const std::size_t key) const {
+ return (individual_probabilities_.find(key) != individual_probabilities_.end());
+ }
+
+ /**
+ * @brief Add individual (not cumulative) probability for a given object with
+ * updated denominator.
+ *
+ * @note This function leaves the cumulative probabilities in a consistent
+ * state. An alternative lazy implementation should be written if cost
+ * of calculating cumulative probabilities is high.
+ *
+ * @param key The key of the given object.
+ * @param numerator The numerator for the given object.
+ * @param new_denominator The updated denominator for the store.
+ **/
+ void addOrUpdateObjectNewDenominator(const std::size_t key,
+ const float numerator,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ DCHECK_LE(numerator, new_denominator);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectHelper(key, numerator);
+ }
+
+ /**
+ * @brief Add or update multiple objects with a new denominator.
+ * @param keys The keys to be added/updated.
+ * @param numerators The numerators to be added/updated.
+ * @param new_denominator The new denominator.
+ */
+ void addOrUpdateObjectsNewDenominator(
+ const std::vector<std::size_t> &keys,
+ const std::vector<float> &numerators,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectsHelper(keys, numerators);
+ }
+
+ /**
+ * @brief Remove an object from the store.
+ *
+ * @note This function decrements the denominator with the value of the numerator being removed.
+ *
+ * @param key The key of the object to be removed.
+ **/
+ void removeObject(const std::size_t key) {
+ auto individual_it = individual_probabilities_.find(key);
+ DCHECK(individual_it != individual_probabilities_.end());
+ const float new_denominator = common_denominator_ - individual_it->second;
+ individual_probabilities_.erase(individual_it);
+ common_denominator_ = new_denominator;
+ updateCumulativeProbabilities();
+ }
+
+ /**
+ * @brief Get the individual probability (not cumulative) for an object.
+ *
+ * @param key The key of the object.
+ **/
+ const float getIndividualProbability(const std::size_t key) const {
+ const auto it = individual_probabilities_.find(key);
+ DCHECK(it != individual_probabilities_.end());
+ return it->second / common_denominator_;
+ }
+
+ /**
+ * @brief Update the cumulative probabilities.
+ *
+ * @note This function should be called upon if there are any updates,
+ * additions or deletions to the individual probabilities.
+ * @note An efficient implementation should be written if there are large
+ * number of objects.
+ **/
+ void updateCumulativeProbabilities() {
+ cumulative_probabilities_.clear();
+ float cumulative_probability = 0;
+ for (const auto p : individual_probabilities_) {
+ cumulative_probability += p.second / common_denominator_;
+ cumulative_probabilities_.emplace_back(p.first,
+ cumulative_probability);
+ }
+ if (!cumulative_probabilities_.empty()) {
+ // Adjust the last cumulative probability manually to 1, so that
+ // floating addition related rounding issues are ignored.
+ cumulative_probabilities_.back().updateProbability(1);
+ }
+ }
+
+ /**
+ * @brief Return a randomly chosen key.
+ *
+ * TODO(harshad) - If it is expensive to create the random device
+ * on every invocation of this function, make it a class variable.
+ * In which case, we won't be able to mark the function as const.
+ *
+ * @note The random number is uniformly chosen.
+ **/
+ inline const std::size_t pickRandomKey() const {
+ std::uniform_real_distribution<float> dist(0.0, 1.0);
+ std::random_device rd;
+ const float chosen_probability = dist(rd);
+ return getKeyForProbability(chosen_probability);
+ }
+
+ private:
+ class ProbabilityInfo {
+ public:
+ ProbabilityInfo(const std::size_t key, const float probability)
+ : key_(key), probability_(probability) {
+ // As GLOG doesn't provide DEBUG only checks for less than equal
+ // comparison for floats, we can't ensure that probability is less than
+ // 1.0.
+ }
+
+ ProbabilityInfo(const ProbabilityInfo &other) = default;
+
+ ProbabilityInfo& operator=(const ProbabilityInfo &other) = default;
+
+ void updateProbability(const float new_probability) {
+ probability_ = new_probability;
+ }
+
+ std::size_t key_;
--- End diff --
Does `key_` changes? If no, we could mark `const`.
---
[GitHub] incubator-quickstep issue #309: Added ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on the issue:
https://github.com/apache/incubator-quickstep/pull/309
LGTM. Merging.
---
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on a diff in the pull request:
https://github.com/apache/incubator-quickstep/pull/309#discussion_r143522173
--- Diff: query_execution/ProbabilityStore.hpp ---
@@ -0,0 +1,274 @@
+/**
+ * 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.
+ **/
+
+#ifndef QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+#define QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <random>
+#include <unordered_map>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/**
+ * @brief A class that stores the probabilities of objects. We use an integer field
+ * called "key" to identify each object.
+ * A probability is expressed as a fraction. All the objects share a common denominator.
+ **/
+class ProbabilityStore {
+ public:
+ /**
+ * @brief Constructor.
+ **/
+ ProbabilityStore()
+ : common_denominator_(1.0) {}
+
+ /**
+ * @brief Get the number of objects in the store.
+ **/
+ inline const std::size_t getNumObjects() const {
+ DCHECK_EQ(individual_probabilities_.size(), cumulative_probabilities_.size());
--- End diff --
Does it follow the rule that the left side is the checked variable, and the right is the expected one?
---
[GitHub] incubator-quickstep pull request #309: Added ProbabilityStore class
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/incubator-quickstep/pull/309
---
[GitHub] incubator-quickstep pull request #309: Add ProbabilityStore class
Posted by zuyu <gi...@git.apache.org>.
Github user zuyu commented on a diff in the pull request:
https://github.com/apache/incubator-quickstep/pull/309#discussion_r143527323
--- Diff: query_execution/ProbabilityStore.hpp ---
@@ -0,0 +1,274 @@
+/**
+ * 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.
+ **/
+
+#ifndef QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+#define QUICKSTEP_QUERY_EXECUTION_PROBABILITY_STORE_HPP_
+
+#include <algorithm>
+#include <cstddef>
+#include <random>
+#include <unordered_map>
+#include <vector>
+
+#include "utility/Macros.hpp"
+
+#include "glog/logging.h"
+
+namespace quickstep {
+
+/**
+ * @brief A class that stores the probabilities of objects. We use an integer field
+ * called "key" to identify each object.
+ * A probability is expressed as a fraction. All the objects share a common denominator.
+ **/
+class ProbabilityStore {
+ public:
+ /**
+ * @brief Constructor.
+ **/
+ ProbabilityStore()
+ : common_denominator_(1.0) {}
+
+ /**
+ * @brief Get the number of objects in the store.
+ **/
+ inline const std::size_t getNumObjects() const {
+ DCHECK_EQ(individual_probabilities_.size(), cumulative_probabilities_.size());
+ return individual_probabilities_.size();
+ }
+
+ /**
+ * @brief Get the common denominator.
+ */
+ inline const std::size_t getDenominator() const {
+ return common_denominator_;
+ }
+
+ /**
+ * @brief Check if an object with a given key is present.
+ * @param key The key of the given object.
+ * @return True if the object is present, false otherwise.
+ */
+ inline bool hasObject(const std::size_t key) const {
+ return (individual_probabilities_.find(key) != individual_probabilities_.end());
+ }
+
+ /**
+ * @brief Add individual (not cumulative) probability for a given object with
+ * updated denominator.
+ *
+ * @note This function leaves the cumulative probabilities in a consistent
+ * state. An alternative lazy implementation should be written if cost
+ * of calculating cumulative probabilities is high.
+ *
+ * @param key The key of the given object.
+ * @param numerator The numerator for the given object.
+ * @param new_denominator The updated denominator for the store.
+ **/
+ void addOrUpdateObjectNewDenominator(const std::size_t key,
+ const float numerator,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ DCHECK_LE(numerator, new_denominator);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectHelper(key, numerator);
+ }
+
+ /**
+ * @brief Add or update multiple objects with a new denominator.
+ * @param keys The keys to be added/updated.
+ * @param numerators The numerators to be added/updated.
+ * @param new_denominator The new denominator.
+ */
+ void addOrUpdateObjectsNewDenominator(
+ const std::vector<std::size_t> &keys,
+ const std::vector<float> &numerators,
+ const float new_denominator) {
+ CHECK_GT(new_denominator, 0u);
+ common_denominator_ = new_denominator;
+ addOrUpdateObjectsHelper(keys, numerators);
+ }
+
+ /**
+ * @brief Remove an object from the store.
+ *
+ * @note This function decrements the denominator with the value of the numerator being removed.
+ *
+ * @param key The key of the object to be removed.
+ **/
+ void removeObject(const std::size_t key) {
+ auto individual_it = individual_probabilities_.find(key);
+ DCHECK(individual_it != individual_probabilities_.end());
+ const float new_denominator = common_denominator_ - individual_it->second;
+ individual_probabilities_.erase(individual_it);
+ common_denominator_ = new_denominator;
+ updateCumulativeProbabilities();
+ }
+
+ /**
+ * @brief Get the individual probability (not cumulative) for an object.
+ *
+ * @param key The key of the object.
+ **/
+ const float getIndividualProbability(const std::size_t key) const {
+ const auto it = individual_probabilities_.find(key);
+ DCHECK(it != individual_probabilities_.end());
+ return it->second / common_denominator_;
+ }
+
+ /**
+ * @brief Update the cumulative probabilities.
+ *
+ * @note This function should be called upon if there are any updates,
+ * additions or deletions to the individual probabilities.
+ * @note An efficient implementation should be written if there are large
+ * number of objects.
+ **/
+ void updateCumulativeProbabilities() {
+ cumulative_probabilities_.clear();
+ float cumulative_probability = 0;
+ for (const auto p : individual_probabilities_) {
+ cumulative_probability += p.second / common_denominator_;
+ cumulative_probabilities_.emplace_back(p.first,
+ cumulative_probability);
+ }
+ if (!cumulative_probabilities_.empty()) {
+ // Adjust the last cumulative probability manually to 1, so that
+ // floating addition related rounding issues are ignored.
+ cumulative_probabilities_.back().updateProbability(1);
+ }
+ }
+
+ /**
+ * @brief Return a randomly chosen key.
+ *
+ * TODO(harshad) - If it is expensive to create the random device
+ * on every invocation of this function, make it a class variable.
+ * In which case, we won't be able to mark the function as const.
+ *
+ * @note The random number is uniformly chosen.
+ **/
+ inline const std::size_t pickRandomKey() const {
+ std::uniform_real_distribution<float> dist(0.0, 1.0);
+ std::random_device rd;
+ const float chosen_probability = dist(rd);
+ return getKeyForProbability(chosen_probability);
+ }
+
+ private:
+ class ProbabilityInfo {
+ public:
+ ProbabilityInfo(const std::size_t key, const float probability)
+ : key_(key), probability_(probability) {
+ // As GLOG doesn't provide DEBUG only checks for less than equal
+ // comparison for floats, we can't ensure that probability is less than
+ // 1.0.
--- End diff --
But we could use `QUICKSTEP_DEBUG` to wrap our own checks.
On the other hand, does `DCHECK(probability_ < 1.0)` work?
---