我正在开发一种玩具语言,下面是我想要做的。
x = [1 2 3 4 5]这定义了一个向量,
y = rest(x)现在y包含了除first之外的x的所有元素。在原生方面,x是一个向量,当用户调用rest时,它将生成除第一个元素之外的自身的完整副本。这是一个问题,我只有2kb的内存,做一个完整的拷贝是昂贵的。使用链表可以解决这个特定的问题,但在这种情况下,链表本身就是一个内存占用问题。那么,对于共享元素的这些类型的操作(first rest是最频繁的操作),是否存在一种内存高效的结构?
这是一种函数式语言,所以一旦定义了x,它就不会改变,而且也没有可用的boost或std c++库,我将实现所有的东西。
发布于 2011-04-30 02:25:16
您可以将[1, 2, 3, 4, 5]存储在某个内存中,并使x指向该内存,即
template <typename T>
struct slice { T* begin; T* end; };
....
int backing_store[] = {1, 2, 3, 4, 5};
// ^-- the expression [1 2 3 4 5] create this
....
slice<int> x (backing_store, backing_store + 5);
// ^-- the assignment x = [1 2 3 4 5] does this然后,您可以将rest实现为
template <typename T>
slice<T> rest(slice<T> p) {
return slice<T>(p.begin + 1, p.end);
}您可以使用一些引用计数方案或GC (对于您的内存来说可能太大)来确保当没有‘backing_store’再使用它时,它会被释放。
发布于 2011-04-30 02:24:15
由于您的内存非常有限,我能想到的最好的解决方案是使用指向第一个元素的指针。很难想象还有比这更节省空间的解决方案。
https://stackoverflow.com/questions/5835761
复制相似问题