这是几只 log 啊,我打了个三只 log 的暴力空间只用了不到 40MB。
by E1_de5truct0r @ 2023-05-19 20:12:44
首先,大量的 `new` 很慢。
其次,指针占八字节,结构体还要补齐,空间不小。
by H_Kaguya @ 2023-05-19 20:13:43
@[E1_de5truct0r](/user/195198) 单
by lzyqwq @ 2023-05-19 20:14:26
@[H_Kaguya](/user/663405) /jy
by lzyqwq @ 2023-05-19 20:14:35
@[蒟蒻·廖子阳](/user/539211) 单 log 跑这么慢?LCT 意义下的单 log 重现江湖(?)/jk
by E1_de5truct0r @ 2023-05-19 20:16:45
我觉得还是主席树用数组写跑的快。
by E1_de5truct0r @ 2023-05-19 20:17:35
@[E1_de5truct0r](/user/195198) 学到了/bx
by lzyqwq @ 2023-05-19 20:18:33
@[蒟蒻·廖子阳](/user/539211) 我不太清楚指针是否有比较好的实现,至少我写过的跑的不快,至少没我自己数组写法快((
by E1_de5truct0r @ 2023-05-19 20:21:43
@[蒟蒻·廖子阳](/user/539211) new 的效率低,可以开内存池代替。
指针也是有解决办法的。建议之后用 int 类型存下标,当指针用。这样还可以避免判断某些边界条件,很方便。
by robinyqc @ 2023-05-19 20:52:54
指针类型的内存池写法举例:
```cpp
struct node {
int data,cnt;
node() {}
node(int data,int cnt):data(data),cnt(cnt) {}
};
node node_pool[MAXSIZE];
node* node_pool_pointer=node_pool;
node* tmp_node_pointer;
//分配一个空的 node
node* NewNode() {
return node_pool_pointer++;
}
//分配一个指定的 node
node* NewNode(int data,int cnt) {
tmp_node_pointer=node_pool_pointer;
(*node_pool_pointer)=node(data,cnt);
node_pool_pointer++;
return tmp_node_pointer;
}
//分配长度为 size 的连续的 node 类型的空间
node* NodeArrayAllocate(int size) {
tmp_node_pointer=node_pool_pointer;
node_pool_pointer+=size;
return tmp_node_pointer;
}
```
by robinyqc @ 2023-05-19 21:02:45