From 58a72af2bb7b1b51c92ab26edea114c33a91c9ff Mon Sep 17 00:00:00 2001 From: "David G. Andersen" Date: Wed, 9 Mar 2016 20:17:09 -0800 Subject: Switching to O(N) duplicate counting using unordered_set. Change: 116831946 --- tensorflow/contrib/linear_optimizer/kernels/sdca_ops.cc | 12 +++++------- 1 file 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 #include #include +#include #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 scratch_storage; - scratch_storage.reserve(example_ids.size()); + std::unordered_set 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( -- cgit v1.2.3