文件中数据段的重新排序

本文关键字：排序 新排序 数据 文件 | 更新日期: 2023-09-27 18:17:27

我正试图找到一种算法，也许是C, c++， c#， Java或任何语言的例子，以帮助解决我一直面临的重新排序问题。

目标是获取文件中的一系列范围，并以新的模式重新组织，基本上是在不破坏数据完整性的情况下移动数据块。我更希望找到一个可以就地执行它，并使用单个缓冲区进行交换，或者直接从一个地方移动到另一个地方。重新组织过程可以将范围分解成几个部分，只要这些范围在完成时具有相同的长度和数据完整性。

例如，给定一组值:

  Length    SrcStart     Src End   Dst Start     Dst End
    9178      274054      283231           0        9177
  274051           0      274050        9178      283228
  582929      283229      866157      283229      866157
  399208      874397     1273604      866158     1265365
    8239    14675709    14683947     1265366     1273604
  986980     1273605     2260584     1273605     2260584
  602862     2811144     3414005     2260585     2863446
  138712     4092072     4230783     2863447     3002158
  116210     3414007     3530216     3002159     3118368
  550559     2260585     2811143     3118369     3668927
  561856     3530217     4092072     3668928     4230783
24319165     4230784    28549948     4230784    28549948
  578539    30246149    30824687    28549949    29128487
  491856    28549949    29041804    29128488    29620343
  593580    29639113    30232692    29620344    30213923
  597308    29041805    29639112    30213924    30811231
   13456    30232693    30246148    30811232    30824687
  633513    31407949    32041461    30824688    31458200
  583261    30824688    31407948    31458201    32041461
40117358    32041462    72158819    32041462    72158819

SrcStart -> SrcEnd范围内的所有内容都需要移动到DstStart -> DstEnd范围。请注意，在许多情况下，从源到目标的转移将导致目标的内容被改变，由于所需的原始数据已被破坏，因此您无法再从该位置复制这些内容。

目标是将每个数据段从SrcStart移动到带有第一列Length的DstStart。每行对应的"结束"只是开始加上长度减去1(所以它是实际的偏移量)。

我已经做了相当多的研究，并研究了交换值，并分解了与其他值交叉的区域以及容器内交换的容器，但它们似乎不足。因此，这让我回到了我的第一个陈述，我希望也许有一个算法或一些我可以学习的资源来帮助解决这个问题，而社区的共享知识似乎是可行的。

谢谢!

文件中数据段的重新排序

您可以使用磁盘碎片整理程序使用的方法。

  • 先将需要覆盖的数据复制到空闲区域
  • 将引用该数据的所有索引都指向新位置，以便将来使用该副本。
  • 如果系统有这样的概念，你可能需要注意是否有任何块变为"未使用"。

然而，如果索引是以字节为单位的，则意味着整个文件只有80mb。如此小的文件可以非常快地复制(不到两秒)。这个文件总共有多大?

你问的问题就好像它是一个不透明的二进制文件，出于某种原因你想要交换块。这似乎不太可能是真的。文件肯定有自己的结构吧?你不能利用它来帮助你记账吗?

  • 文件是否有"已使用"answers"未使用"区域的概念?
  • 文件是否有块头的内部结构?
  • 文件是否有任何相关索引或任何需要保持同步的内容?(如果没有，你从哪里得到要移动的方块列表?)
  • 移动的块可以相互重叠吗?请注意，如果它们可以，操作顺序将变得重要。

也就是说，@Peter Lawrey推荐的方法是好的。如果覆盖一个块，首先将它复制到文件中的另一个位置，更新任何重叠的索引。

总而言之，在我看来，你试图把一个难题分成两步来解决，一步简单，另一步……更加困难。最初的问题是什么?

(强制性建议:在Windows上事务性IO api可能会使用)。

我认为下面的算法可以处理它，最多两倍最大的缓存大小的内存缓存数据。除了数据缓存之外，你还需要一个簿记FIFO和原始列表。它是这样的:

  1. 如果FIFO和移动表都为空，则结束。
  2. 如果FIFO为空，将移动表的顶部项移到FIFO，同时将项数据读入数据缓存。
  3. 检查在移动表中FIFO的第一个表项的目的区域是否有任何块重叠。
  4. 如果存在块，则将块的数据读入缓存，将该条目移到FIFO，转到3。
  5. 如果没有block，将FIFO表项的数据从cache写到destination，删除第一个FIFO表项，转1。

这个想法是找到被占用的块，缓存它们以打开空间，并尽快摆脱缓存中的数据。您可能需要添加一些完整性检查，以查看源地址和目标地址是否相同。您可能还需要做额外的检查，看看原始表是否有意义(两个块移动到相同的位置，等等)。

编辑:我可能在陈述最大块乘以2的最大值时过于乐观了。我认为它可以超越这一点。我认为乘以3是一个简单(但不严格)的上界。

由于源表中有相当大的块，您可以将它们分开以减少缓存使用。比方说，您希望最多使用1gb的缓存:在运行算法之前，将所有大于1/3gb的块拆分为长度为1/3gb的多个条目。或者，您可以使算法在子块大小中工作(而不是将整个块读取到缓存中，您只读取相关部分，并在源表中保留修改的条目)，但我认为这将更难以管理/实现。

相关文章：