9fcf66e16d
xla::IsPermutation() does two things: it checks a permutation is actually a permutation, and checks it has a particular size. There's no need to do the latter in xla::IsPermutation because it can be done just as easily by checking .size(), and a number of callers don't need the size check. In addition, change the implementation to be O(n) time; there's no need to call std::is_permutation() which guarantees nothing better than O(n^2) behavior. PiperOrigin-RevId: 356643750 Change-Id: Ib177287556b5c22266185fa813798a4ad5392054
65 lines
2.0 KiB
C++
65 lines
2.0 KiB
C++
/* Copyright 2017 The TensorFlow Authors. All Rights Reserved.
|
|
|
|
Licensed 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 "tensorflow/compiler/xla/permutation_util.h"
|
|
|
|
#include "absl/algorithm/container.h"
|
|
#include "absl/container/inlined_vector.h"
|
|
|
|
namespace xla {
|
|
|
|
bool IsPermutation(absl::Span<const int64> permutation) {
|
|
absl::InlinedVector<bool, 8> seen(permutation.size(), false);
|
|
for (int64 p : permutation) {
|
|
if (p < 0 || p >= permutation.size() || seen[p]) {
|
|
return false;
|
|
}
|
|
seen[p] = true;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
std::vector<int64> InversePermutation(
|
|
absl::Span<const int64> input_permutation) {
|
|
DCHECK(IsPermutation(input_permutation));
|
|
std::vector<int64> output_permutation(input_permutation.size(), -1);
|
|
for (size_t i = 0; i < input_permutation.size(); ++i) {
|
|
output_permutation.at(input_permutation.at(i)) = i;
|
|
}
|
|
return output_permutation;
|
|
}
|
|
|
|
std::vector<int64> ComposePermutations(absl::Span<const int64> p1,
|
|
absl::Span<const int64> p2) {
|
|
CHECK_EQ(p1.size(), p2.size());
|
|
std::vector<int64> output;
|
|
output.reserve(p1.size());
|
|
for (size_t i = 0; i < p1.size(); ++i) {
|
|
output.push_back(p1.at(p2.at(i)));
|
|
}
|
|
return output;
|
|
}
|
|
|
|
bool IsIdentityPermutation(absl::Span<const int64> permutation) {
|
|
for (int64 i = 0; i < permutation.size(); ++i) {
|
|
if (permutation[i] != i) {
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
} // namespace xla
|