流算法

流算法（streaming algorithm），理学-计算机科学技术-计算机科学理论-算法-流算法，在计算机科学中，流算法指在流式计算模型下、以数据流的形式处理大规模数据并从中获得有价值信息的算法。流式计算模型把输入元素序列理解成一个连续的数据流，并严格限制流算法扫描这个数据流的次数（通常仅允许扫描一次）；另一方面，流式计算模型还会把流算法可用的存储空间限制在远远小于输入数据规模的量级。理想情况是仅为输入规模的对数量级，即对于长度为n的输入仅使用的存储空间。为了保证流算法的效率，在其所用存储空间超过对数量级时还需要限制流算法处理每个输入元素所花费时间。流算法最大的优势在于其效率：只需要扫描输入数据流一次的算法可以省掉存储输入数据的空间，同时也可以限制算法的运行时间；即便需要多次扫描输入数据流，顺序扫描外存储器（比如硬盘）的效率也远高于随机访问。另一方面，由于空间、时间和对输入遍历次数的限制，在绝大多数情况下，流算法都无法充分利用输入数据流的所有信息以求出精确的计算结果。通常，流算法会以损失一部分信息为代价来减少所需要的存储的中间计算结果的规模，从而高效地求出一个近似结果。