diff options
| author |  David G. Andersen <dga@google.com> | 2016-03-09 20:17:09 -0800 |
|---|---|---|
| committer |  TensorFlower Gardener <gardener@tensorflow.org> | 2016-03-09 22:02:19 -0800 |
| commit | 58a72af2bb7b1b51c92ab26edea114c33a91c9ff (patch) | |
| tree | b1c96d78a2c5a1330f734413d3bd7994786d8f18 | |
| parent | 7706eca44476e8217b61b05d8de70d1ef3e99a5c (diff) | |
Switching to O(N) duplicate counting using unordered_set.
Change: 116831946
| -rw-r--r-- | tensorflow/contrib/linear_optimizer/kernels/sdca_ops.cc | 12 |
1 files changed, 5 insertions, 7 deletions
diff --git a/tensorflow/contrib/linear_optimizer/kernels/sdca_ops.cc b/tensorflow/contrib/linear_optimizer/kernels/sdca_ops.cc index 37c372cc00..dd085ee7e0 100644 --- a/tensorflow/contrib/linear_optimizer/kernels/sdca_ops.cc +++ b/tensorflow/contrib/linear_optimizer/kernels/sdca_ops.cc @@ -23,6 +23,7 @@ limitations under the License. #include <functional> #include <limits> #include <string> +#include <unordered_set> #include "third_party/eigen3/unsupported/Eigen/CXX11/Tensor" #include "tensorflow/contrib/linear_optimizer/kernels/hinge-loss.h" @@ -575,15 +576,12 @@ class SdcaSolver : public OpKernel { example_ids.size(), num_examples))); const int64 num_duplicate_example_ids = [&] { // TODO(katsiapis): Benchmark and/or optimize. - std::vector<StringPiece> scratch_storage; - scratch_storage.reserve(example_ids.size()); + std::unordered_set<StringPiece, StringPiece::Hasher> unique_ids( + example_ids.size()); for (size_t i = 0; i < example_ids.size(); ++i) { - scratch_storage.emplace_back(example_ids(i)); + unique_ids.emplace(example_ids(i)); } - std::sort(scratch_storage.begin(), scratch_storage.end()); - return std::distance( - std::unique(scratch_storage.begin(), scratch_storage.end()), - scratch_storage.end()); + return example_ids.size() - unique_ids.size(); }(); OP_REQUIRES(context, num_duplicate_example_ids == 0, errors::InvalidArgument(strings::Printf( |