2408727188GHR @ 2023-07-07 19:53:46
如题，我本来使用数组模拟trie树，然后超时了，主要是我采用class封装Trie，然后在多组T时直接删了重新构造，猜测是在堆上不断分配大量内存导致超时
于是，我使用指针动态申请内存，然而，确实不超时了，但是1 和6点居然内存超限？？！！
要知道，我是使用动态分配内存！用多少开多少，怎么会比数组模拟还占空间？
修改后
#include <iostream>
#include <array>
#include <memory>
class Trie {
struct Node {
std::array<std::shared_ptr<Node>, 66> nxt;
//int word = 0;
int prefix = 0;
Node() = default;
};
std::shared_ptr<Node> root;
static int get_id(char ch) {
if(ch >= '0' && ch <= '9') {
return ch - '0';
}
if(ch >= 'A' && ch <= 'Z') {
return ch - 'A' + 10;
}
if(ch >= 'a' && ch <= 'z') {
return ch - 'a' + 36;
}
std::cerr << "ERROR!!!!!\n";
return -1;
}
public:
Trie() : root(std::make_shared<Node>()) {
}
void insert(const std::string &s) const {
auto now = root;
for(const auto &ch: s) {
int id = get_id(ch);
if(now->nxt[id] == nullptr) {
now->nxt[id] = std::make_shared<Node>();
}
now = now->nxt[id];
now->prefix++;
}
//now->word++;
}
int find_prefix(const std::string &s) {
auto now = root;
for(const auto &ch: s) {
int id = get_id(ch);
if(now->nxt[id] == nullptr) {
return 0;
}
now = now->nxt[id];
}
return now->prefix;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin >> t;
for(int i = 1; i <= t; i++) {
int n, q;
std::cin >> n >> q;
auto trie = std::make_unique<Trie>();
//Trie* trie = new Trie;
for(int j = 1; j <= n; j++) {
std::string tmp;
std::cin >> tmp;
trie->insert(tmp);
}
for(int j = 1; j <= q; j++) {
std::string tmp;
std::cin >> tmp;
std::cout << trie->find_prefix(tmp) << '\n';
}
//delete trie;
}
return 0;
}
修改前
#include<iostream>
#include<string>
#include<array>
#include<memory>
class Trie {
std::array<std::array<int, 62>, (size_t)2e6> tr;
std::array<int, (size_t)2e6> prefix;
int tot = 0;
int get_id(char ch) {
if(ch >= '0' && ch <= '9') {
return ch - '0';
}
if(ch >= 'A' && ch <= 'Z') {
return ch - 'A' + 10;
}
if(ch >= 'a' && ch <= 'z') {
return ch - 'a' + 36;
}
std::cerr << "ERROR!!!!!\n";
}
public:
void insert(const std::string &str) {
int now = 0;
for(const auto &ch: str) {
int id = get_id(ch);
if(tr[now][id] == 0) {
tr[now][id] = ++tot;
}
now = tr[now][id];
prefix[now]++;
}
}
int find_prefix(const std::string &str) {
int now = 0;
for(const auto &ch: str) {
int id = get_id(ch);
if(tr[now][id] == 0) {
return 0;
}
now = tr[now][id];
}
return prefix[now];
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin >> t;
for(int i = 1; i <= t; i++) {
int n, q;
std::cin >> n >> q;
auto trie = std::make_unique<Trie>();
//Trie* trie = new Trie;
for(int j = 1; j <= n; j++) {
std::string tmp;
std::cin >> tmp;
trie->insert(tmp);
}
for(int j = 1; j <= q; j++) {
std::string tmp;
std::cin >> tmp;
std:: cout << trie->find_prefix(tmp) << '\n';
}
//delete trie;
}
}by 2408727188GHR @ 2023-07-07 19:54:56
目前猜测是共享指针的引用计数器占用内存，正在尝试替换成裸指针
by 2408727188GHR @ 2023-07-07 20:11:38
裸指针AC了，但是消耗内存880MB，远高于数组实现的400MB 真是。。。。为了省空间，反而占用了更多空间。。。。。现在尝试使用哈希表优化数组
裸指针代码
#include <iostream>
#include <array>
#include <functional>
class Trie {
struct Node {
std::array<Node*, 66> nxt{nullptr};
//int word = 0;
int prefix = 0;
Node() = default;
};
Node *root;
static int get_id(char ch) {
if(ch >= '0' && ch <= '9') {
return ch - '0';
}
if(ch >= 'A' && ch <= 'Z') {
return ch - 'A' + 10;
}
if(ch >= 'a' && ch <= 'z') {
return ch - 'a' + 36;
}
std::cerr << "ERROR!!!!!\n";
return -1;
}
public:
Trie() : root(new Node()) {
}
~Trie() {
std::function<void(Node* node)> helper = [&helper](Node* node) {
for(auto p : node->nxt) {
if(p != nullptr) {
helper(p);
}
}
delete node;
};
helper(root);
}
void insert(const std::string &s) const {
auto now = root;
for(const auto &ch: s) {
int id = get_id(ch);
if(now->nxt[id] == nullptr) {
now->nxt[id] = new Node;
}
now = now->nxt[id];
now->prefix++;
}
//now->word++;
}
int find_prefix(const std::string &s) {
auto now = root;
for(const auto &ch: s) {
int id = get_id(ch);
if(now->nxt[id] == nullptr) {
return 0;
}
now = now->nxt[id];
}
return now->prefix;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin >> t;
for(int i = 1; i <= t; i++) {
int n, q;
std::cin >> n >> q;
//auto trie = std::make_unique<Trie>();
Trie* trie = new Trie;
for(int j = 1; j <= n; j++) {
std::string tmp;
std::cin >> tmp;
trie->insert(tmp);
}
for(int j = 1; j <= q; j++) {
std::string tmp;
std::cin >> tmp;
std::cout << trie->find_prefix(tmp) << '\n';
}
delete trie;
}
return 0;
}
by 2408727188GHR @ 2023-07-07 20:36:14
哈希优化后，还是只有裸指针才能通过测试，然鹅，有一次我忘记写析构函数，居然也AC了，300MB
？？？？？？？？？
我真的很好奇洛谷和NOIP到底是怎么判定占用内存的，他真的，我哭死，居然不管内存泄漏？？？？
当我加上析构函数的时候。。。TLE了。。。析构TLE。。。。我谢谢你
代码
// 裸指针+哈希优化 AC 3.02s 353MB
#include <iostream>
#include <array>
#include <memory>
#include <unordered_map>
#include <functional>
class Trie {
struct Node {
std::unordered_map<char, Node*> nxt;
//int word = 0;
int prefix = 0;
Node() = default;
};
Node* root;
static int get_id(char ch) {
if(ch >= '0' && ch <= '9') {
return ch - '0';
}
if(ch >= 'A' && ch <= 'Z') {
return ch - 'A' + 10;
}
if(ch >= 'a' && ch <= 'z') {
return ch - 'a' + 36;
}
std::cerr << "ERROR!!!!!\n";
return -1;
}
public:
Trie() : root(new Node) {
}
void insert(const std::string &s) const {
auto now = root;
for(const auto &ch: s) {
auto it = now->nxt.find(ch);
if(it == now->nxt.end()) {
now->nxt.insert({ch, new Node});
}
now = now->nxt[ch];
now->prefix++;
}
//now->word++;
}
~Trie() {
std::function<void(Node* node)> helper = [&helper](Node* node) {
for(auto [ch, p] : node->nxt) {
helper(p);
}
delete node;
};
helper(root);
}
int find_prefix(const std::string &s) {
auto now = root;
for(const auto &ch: s) {
auto it = now->nxt.find(ch);
if(it == now->nxt.end()) {
return 0;
}
now = now->nxt[ch];
}
return now->prefix;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin >> t;
for(int i = 1; i <= t; i++) {
int n, q;
std::cin >> n >> q;
//auto trie = std::make_unique<Trie>();
Trie* trie = new Trie;
for(int j = 1; j <= n; j++) {
std::string tmp;
std::cin >> tmp;
trie->insert(tmp);
}
for(int j = 1; j <= q; j++) {
std::string tmp;
std::cin >> tmp;
std::cout << trie->find_prefix(tmp) << '\n';
}
delete trie;
}
return 0;
}
by _299817_ @ 2023-07-17 23:15:43
@2408727188GHR 有没有一种可能，记录上显示的空间占用是所有测试点加起来的空间的占用，而不是单个测试点的空间占用
by baoziwu2 @ 2023-07-18 11:40:57
@2408727188GHR 您现在知道为什么智能指针的空间占用如此大吗
蒟蒻使用 std::unique_ptr 实现 Trie 类 空间占用大的不行 (1009MB)
class Trie {
static const int KINDS = 75;
struct node {
std::unique_ptr<node> next[KINDS];
int prefix;
node() = default;
};
std::unique_ptr<node> root;
static int getNum(char x) {
if(isdigit(x)) return x - '0';
if('a' <= x && x <= 'z') return x - 'a' + 10;
if('A' <= x && x <= 'Z') return x - 'A' + 36;
throw std::runtime_error("Invalid character");
}
public:
Trie() : root(std::make_unique<node>()) {}
void insert(const std::string &str) {
auto p = root.get();
for(char const &x : str) {
int c = getnum(x);
if(p -> next[c] == nullptr)
p -> next[c] = std::make_unique<node>();
p = p -> next[c].get();
p -> prefix ++;
}
}
int queryPrefix(const std::string &str) {
auto p = root.get();
for(char const &x : str) {
int c = getnum(x);
if(p -> next[c] == nullptr) return 0;
p = p -> next[c].get();
}
return p -> prefix;
}
};太奇怪了
by 2408727188GHR @ 2023-08-16 22:07:46
@baoziwu2 我也不清楚，但unique_ptr理论上来说应该是零成本抽象，和裸指针应该一样 关键在于我不知道洛谷的内存判断机制是什么，毕竟他居然连内存泄漏都不管。。。
by 2408727188GHR @ 2023-08-16 22:09:24
@299817 哥，有没有一种可能，时间才是求和，内存显示的是最大值
by _299817_ @ 2023-08-16 23:22:09
@2408727188GHR
@299817 哥，有没有一种可能，时间才是求和，内存显示的是最大值
额好像是我的问题