设计内存有限的记忆系统的简单方法是什么? [英] What's a simple way to design a memoization system with limited memory?
问题描述
我正在编写一个手动计算记忆系统(嗯，在Matlab中).简单的部分很容易:
I am writing a manual computation memoization system (ugh, in Matlab). The straightforward parts are easy:
- 一种在执行计算之后将数据放入备忘录系统的方法.
- 一种从备忘录中查询和获取数据的方法.
- 一种查询系统中所有键"的方法.
这些部分并没有太大的疑问.问题是我的计算机内存有限，因此有时"put"操作必须将某些对象转储出内存.我担心高速缓存未命中"，因此我希望使用一些相对简单的系统来删除那些不经常使用和/或重新计算成本不高的已记忆对象.我如何设计该系统?我可以想象的部分包括:
These parts are not so much in doubt. The problem is that my computer has a finite amount of memory, so sometime the 'put' operation will have to dump some objects out of memory. I am worried about 'cache misses', so I would like some relatively simple system for dropping the memoized objects which are not used frequently and/or are not costly to recompute. How do I design that system? The parts I can imagine it having:
- 一种告诉"put"操作(相对而言)的计算成本的方法.
- 一种可选的方式，可以提示"put"操作多久进行一次计算(前进).
- 获取"操作将要注意查询给定对象的频率.
- 一种告诉整个系统要使用的最大内存量的方法(好吧，这很简单).
当您达到内存限制时，它的真正实质是在"put"操作中，并且它必须根据它们的内存占用量，昂贵性和有用性来剔除某些对象.我该怎么办?
The real guts of it would be in the 'put' operation when you hit the memory limit and it has to cull some objects, based on their memory footprint, their costliness, and their usefulness. How do I do that?
对不起，如果太含糊或不合时宜.
Sorry if this is too vague, or off-topic.
推荐答案
I'd do it by creating a subclass to DYNAMICPROPS that uses a cell array to store the data internally. This way, you can dynamically add more data to the object.
这是基本的设计思路:
数据存储在单元格数组中.每个属性都有自己的行，第一列是属性名称(为方便起见)，第二列是用于计算数据的函数句柄，第三列是数据，第四列是生成数据所花费的时间，第五列是一个长度为100的数组，存储与最近100次访问该属性的时间相对应的时间戳，第六列包含可变大小.
The data is stored in a cell array. Each property gets its own row, with the first column being the property name (for convenience), the second column a function handle to calculate the data, the third column the data, the fourth column the time it took to generate the data, the fifth column an array of, say, length 100 storing the timestamps corresponding to when the property was accessed the last 100 times, and the sixth column contains the variable size.
有一个通用的get方法，将与该属性对应的行号作为输入(请参见下文). get方法首先检查第3列是否为空.如果否，则返回该值并存储时间戳.如果是，它将使用 TIC/TOC 语句来衡量计算的成本(存储在col4中，时间戳存储在col5中).然后，它检查是否有足够的空间来存储结果.如果是，它将存储数据，否则将检查大小以及访问数据的次数与重新生成需要花费多长时间的乘积，以决定要剔除什么内容.
There is a generic get method that takes as input the row number corresponding to the property (see below). The get method first checks whether column 3 is empty. If no, it returns the value and stores the timestamp. If yes, it performs the computation using the handle from column 1 inside a TIC/TOC statement to measure how expensive the computation is (which is stored in col4, and the timestamp is stored in col5). Then it checks whether there is enough space for storing the result. If yes, it stores the data, otherwise it checks size, as well as the product of how many times data were accessed with how long it would take to regenerate, to decide what to cull.
此外，还有一个"add"属性，该属性将一行添加到单元格数组，创建一个动态函数(使用addprops)，其名称与函数句柄相同，并将get方法设置为myGetMethod(myPropertyIndex).如果需要将参数传递给该函数，则可以使用set方法创建一个附加属性myDynamicPropertyName_parameters，该方法将在参数更改值时删除以前计算的数据.
In addition, there is an 'add' property, that adds a row to the cell array, creates a dynamic property (using addprops) of the same name as the function handle, and sets the get-method to myGetMethod(myPropertyIndex). If you need to pass parameters to the function, you can create an additional property myDynamicPropertyName_parameters with a set method that will remove previously calculated data whenever the parameters change value.
最后，您可以添加一些从属属性，这些属性可以告诉您有多少个属性(单元格数组中的行数)，如何调用它们(单元格数组的第一列)等.
Finally, you can add a few dependent properties, that can tell how many properties there are (# of rows in the cell array), how they're called (first col of the cell array), etc.
这篇关于设计内存有限的记忆系统的简单方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
