2

たとえば、ファイルに多数のデータ エントリが保存されていて、それぞれサイズが異なり、ファイルが 100MB のように大きくなる 1000 個のエントリがある場合、ファイルの途中にある次のサイズのエントリを削除したい場合50KB、最後のバイトをすべて移動していっぱいにせずに、ファイル内の空の 50KB のバイトを削除するにはどうすればよいですか?

ファイル管理に次のような winapi 関数を使用しています。

CreateFile、WriteFile、ReadFileおよびSetFilePointerEx

4

3 に答える 3

7

If you really want to do that, set a flag in your entry. When you want to remove an entry from your file, simply invalidate that flag(logical removal) w/o deleting it physically. The next time you add an entry, just go through the file, look for the first invalidated entry, and overwrite it. If all are validated, append it to the end. This takes O(1) time to remove an entry and O(n) to add a new entry, assuming that reading/writing a single entry from/to disk is the basic operation.

You can even optimize it further. At the beginning of the file, store a bit map(1 for invalidated). E.g., 0001000... represents that the 4th entry in your file is invalidated. When you add an entry, search for the first 1 in the bit map and use Random file I/O (in contrast with sequential file I/O) to redirect the file pointer to that entry-to-overwrite directly. Adding in this way only takes O(1) time.

Oh, I notice your comment. If you want to do it efficiently with entry removed physically, a simple way is to swap the entry-to-remove with the very last one in your file and remove the last one, assuming your entries are not sorted. The time is also good, which is O(1) for both adding and removing.

Edit: Just as Joe mentioned, this requires that all of your entries have the same size. You can implement one with variable length of entries, but that'll be more complicated than the one in discussion here.

于 2011-08-22T13:42:12.803 に答える
1

未使用の領域にフラグを立て続け、しばらくして内部の断片化が特定の比率を超えたときに、ファイルを圧縮するルーチンを実行できます。このスキームを使用すると、削除は高速になりますが、定期的な再編成が必要です。別のファイル処理スキームがある場合は、ファイルをいくつかのチャンクに分割してから、空きチャンクを追跡し、削除時にチャンクを未使用としてマークして追跡し、後で挿入の場合は再利用できます. このスキームは、ファイル内のレコードのタイプ、固定長レコードまたは可変長レコードによって異なります。

于 2011-08-22T13:57:03.237 に答える
1

A = ファイルの先頭、B = 削除するブロックの先頭、C = 削除するブロックの末尾とする

CreateFileフラグ付きFILE_FLAG_RANDOM_ACCESS

SetFilePointerExC の位置に移動し、バッファに EOF まで読み込みます (ファイル サイズを考えると、これは大きなバッファになる可能性があります。ファイル IO 操作では、移動などの単純な操作を行うために、レコード サイズの仮想メモリを割り当てる必要があるため、巨大なレコードには注意してください。 ）。

バッファをファイルの位置 B にコピーします

位置 B + sizeof(block C) にあるはずです。SetEndOfFileその位置でファイルを切り捨ててから閉じます。

これは、 memmove関数を使用すると簡単に実行できることに注意してください。ただし、これには、ファイル全体をメモリにマップし、移動して、書き戻す必要があります。これは小さなファイルには最適ですが、50 ～ 100 MB を超えるファイルの場合は、連続した仮想アドレス空間を十分に確保するように注意してください。

于 2011-08-22T13:49:32.197 に答える