Multivariate amortized resource analysis

doi:10.1145/2362389.2362393

Multivariate amortized resource analysis

2012-11-05

0

OA

AI

DOI：10.1145/2362389.2362393

原文链接

查看原文

摘要

En 中文

我们研究了自动分析多参数过程最坏情况资源使用的问题。基于摊销或大小类型的现有自动分析方法将此类过程的资源使用量或结果大小限制为参数大小的若干一元函数之和。在本文中，我们将此方法推广到任意多元多项式函数，从而允许形如 mn 的界限，而此前需要过度估计为 m2 + n2。我们的框架甚至涵盖了形如 ∑ i,j≤ n m i m j 的界限，其中 m i 是长度为 n 的列表中各项的大小。这使我们首次能够推导出适用于矩阵（表示为列表的列表）操作的有用资源界限，并显著改进其他超线性列表操作（如最长公共子序列和从列表的列表中删除重复项）的界限。此外，资源界限现在对组合操作封闭，从而提高了当某些或所有组件表现出超线性资源或大小行为时组合程序的分析精度。该分析基于一种新颖的多元摊销资源分析方法。我们将其以一个包含列表和树的简单一阶函数式语言的类型系统的形式呈现，证明了其正确性，并描述了基于线性规划的自动类型推断。我们已在大量来自函数式编程中列表和树的示例上实验验证了自动分析方法。将获得的界限与实际资源消耗进行了比较。所有界限在渐近意义上都是紧致的，且常数接近甚至等于最优值。

Multivariate amortized resource analysis

摘要

AI总结

期刊

机构

引用论文