一个常数空间线性时间算法：删除目录中除最近10个文件外的所有文件

<p>假设你有一个包含许多文件的目录，想要删除除最近10个文件外的所有文件。有没有办法告诉<code>Find­First­File</code>按日期顺序枚举文件？</p> <p>没有，无法让<code>Find­First­File</code>按日期顺序枚举文件。<code>Find­First­File</code>枚举的文件按照文件系统驱动想要的顺序产生。例如，FAT通常按照文件在目录列表中出现的顺序枚举，如果文件是顺序添加的，则可能按创建顺序，如果存在重命名或删除操作，则可能是混乱的顺序。</p> <p>既然无法控制文件的枚举顺序，你必须自己进行排序。最简单的解决方案是读取所有条目，按最后修改日期排序，然后删除除最后十个外的所有文件。这需要<var>O</var>(<var>n</var>)的空间和<var>O</var>(<var>n</var> log <var>n</var>)的运行时间。</p> <p>但你可以做得更好。</p> <p>这项任务需要一个优先队列。优先队列是一种支持以下操作的数据结构，其中<var>n</var>是优先队列中的项数。</p> <ul> <li>添加排序: <var>O</var>(log <var>n</var>)</li> <li>查找最大: <var>O</var>(1)</li> <li>移除最大: <var>O</var>(log <var>n</var>)</li> </ul> <p>以上描述是针对最大优先队列的。还有最小优先队列，其最后两个操作是“查找最小”和“移除最小”。两种形式等价，因为你可以使用反序比较来切换。</p> <p>我们可以枚举所有文件，按修改日期逐个添加到最小优先队列中。优先队列保存最新的项。如果优先队列大小超过10，则删除优先队列中“最小”（最早）条目对应的文件，并从优先队列中移除该条目。</p> <p>由于优先队列大小有固定上限，所有操作都在<var>O</var>(1)时间内运行，因为<var>n</var>的值受预定常数限制。（当然，上限越大，<var>O</var>(1)中的常数也越大。）整体算法运行时间为<var>O</var>(<var>n</var>)，其中<var>n</var>是目录中的文件数。</p> <p>以下是解决方案的草图。要获得最小优先堆，我们需要反转<code>dateAscending</code>中的比较方向。</p> <pre>constexpr int files_to_keep = 10; auto dateAscending = [](const WIN32_FIND_DATA&amp; a, const WIN32_FIND_DATA&amp; b) { return CompareFileTime(&amp;a.ftLastWriteTime, &amp;b.ftLastWriteTime) &gt; 0; }; std::priority_queue&lt;WIN32_FIND_DATA, std::vector&lt;WIN32_FIND_DATA&gt;, decltype(dateAscending)&gt; names(dateAscending); WIN32_FIND_DATA wfd; wil::unique_hfind findHandle( FindFirstFileW(L"*.*", &amp;wfd)); if (findHandle.is_valid()) { do { if (wfd.dwFileAttributes &amp; FILE_ATTRIBUTE_DIRECTORY) { // 跳过目录 continue; } names.push(wfd); if (names.size() &gt; files_to_keep) { DeleteFileW(names.top().cFileName); names.pop(); } } while (FindNextFileW(findHandle.get(), &amp;wfd)); } </pre> <p>遗憾的是，<code>std::<wbr />priority_<wbr />queue</code>没有推导<code>Comparator</code>类型的推导指引。我们必须显式指定它，并且由于它位于<code>Container</code>之后，我们必须手动写出容器类型，而不是允许推导。</p> <p>同样遗憾的是，很难在隐藏在<code>priority_<wbr />queue</code>内部的vector上调用<code>reserve()</code>。这意味着<code>names.push()</code>可能抛出异常。至少我们使用了RAII类型（<code>wil::<wbr />unique_<wbr />hfind</code>）来确保查找句柄不会泄漏。</p> <p>如果你可以使用<code>std::<wbr />inplace_<wbr />vector</code>，则可以使用</p> <pre>std::priority_queue&lt;WIN32_FIND_DATA, std::inplace_vector&lt;WIN32_FIND_DATA, files_to_keep + 1&gt;, decltype(dateAscending)&gt; names(dateAscending); </pre> <p>来完全避免内存分配。（这也更清楚地表明算法是常数空间的。）</p> <p>这是所谓<a href="https://en.wikipedia.org/wiki/Online_algorithm">在线算法</a>的一个例子，该算法增量式地完成工作，而不是等待所有输入才开始。</p> <p><b>练习</b>：如果任务是删除最旧的10个文件呢？</p> <p>本文《<a href="https://devblogs.microsoft.com/oldnewthing/20260514-00/?p=112322">一个常数空间线性时间算法：删除目录中除最近10个文件外的所有文件</a>》首发于<a href="https://devblogs.microsoft.com/oldnewthing">The Old New Thing</a>。</p>