英文:
Why std::array<int, 10> is faster than std::vector<int>(10) in this scenario?
问题
I am given N, where N belongs to [3; 1000000] different numbers X, where X belongs to [0; 18446744073709551616).
How many numbers can be formed by rearranging the digits of a different number in the input ?
Example:
6
25 21 10242 42210 52 24021
Answer:
5
Explanation:
There are 5 different numbers namely {25, 52} and {10242, 42210, 24021}
25 -> 52 and 52 -> 25
10242 -> 42210 and 42210 -> 10242
10242 -> 24021 and 24021 -> 10242
42210 -> 24021 and 24021 -> 42210
lhs -> rhs means that rhs can be formed from the digits of lhs
I solved the task successfully. Here is my solution:
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <iterator>
namespace Const {
std::string::size_type constexpr sz_max{ 20 };
}
int main() {
// 0
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
// 1
int n;
std::cin >> n;
int i;
std::string x;
x.reserve(Const::sz_max);
std::vector<std::array<int, 10>> lut(n);
for (i = 0; i != n; ++i) {
std::cin >> x;
for (auto const& ch : x) {
++lut[i][ch - '0'];
}
}
// 2
std::sort(lut.begin(), lut.end());
// 3
auto prev{ lut.cbegin() };
decltype(prev) curr;
auto cnt{ 1 }, ans{ 0 };
for (curr = std::next(prev); curr != lut.cend(); ++curr) {
if (*curr == *prev) {
++cnt;
}
else {
if (cnt != 1) {
ans += cnt;
}
prev = curr;
cnt = 1;
}
}
if (cnt != 1) {
ans += cnt;
}
prev = curr;
cnt = 1;
// 4
std::cout << ans << '\n';
return 0;
}
The execution time of this version is 550-600 ms.
If I change the definition of lut in // 1 from
std::vector<std::array<int, 10>> lut(n);
to
std::vector<std::vector<int>> lut(n, std::vector<int>(10));
the execution time increases drastically to 1050-1150 ms.
In both cases heap allocations have to take place but why the first ones are faster than the second ones ?
英文:
The task (from a Bulgarian judge, click on "Език" to change it to English):
I am given N, where N belongs to [3; 1000000] different numbers X, where X belongs to [0; 18446744073709551616).
How many numbers can be formed by rearranging the digits of a different number in the input ?
Example:
6
25 21 10242 42210 52 24021
Answer:
5
Explanation:
There are 5 different numbers namely {25, 52} and {10242, 42210, 24021}
25 -> 52 and 52 -> 25
10242 -> 42210 and 42210 -> 10242
10242 -> 24021 and 24021 -> 10242
42210 -> 24021 and 24021 -> 42210
lhs -> rhs means that rhs can be formed from the digits of lhs
I solved the task successfully. Here is my solution:
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <iterator>
namespace Const {
std::string::size_type constexpr sz_max{ 20 };
}
int main() {
// 0
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
// 1
int n;
std::cin >> n;
int i;
std::string x;
x.reserve(Const::sz_max);
std::vector<std::array<int, 10>> lut(n);
for (i = 0; i != n; ++i) {
std::cin >> x;
for (auto const& ch : x) {
++lut[i][ch - '0'];
}
}
// 2
std::sort(lut.begin(), lut.end());
// 3
auto prev{ lut.cbegin() };
decltype(prev) curr;
auto cnt{ 1 }, ans{ 0 };
for (curr = std::next(prev); curr != lut.cend(); ++curr) {
if (*curr == *prev) {
++cnt;
}
else {
if (cnt != 1) {
ans += cnt;
}
prev = curr;
cnt = 1;
}
}
if (cnt != 1) {
ans += cnt;
}
prev = curr;
cnt = 1;
// 4
std::cout << ans << '\n';
return 0;
}
The execution time of this version is 550-600 ms.
If I change the definition of lut in // 1 from
std::vector<std::array<int, 10>> lut(n);
to
std::vector<std::vector<int>> lut(n, std::vector<int>(10));
the execution time increases drastically to 1050-1150 ms.
In both cases heap allocations have to take place but why the first ones are faster than the second ones ?
答案1
得分: 2
std::array 不像 std::vector 那样为其元素进行单独的堆分配，即
sizeof(std::array<int,16>) == sizeof(int) * 16
所有的元素都直接存储在对象中。因此，vector<array<int,10>> 中的所有数据都存储在相同的连续分配中。
英文:
std::array doesn't make a separate heap allocation for its elements like std::vector does, i.e.,
sizeof(std::array<int,16>) == sizeof(int) * 16
All of the elements are stored directly in the object. Because of this, all the data in a vector<array<int,10>> is stored in the same contiguous allocation.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论