0

たとえば、[0,1,2, 5,6,7, 9,10,11] のような整数の配列があるとします。理想的な世界では、それらは並べ替えられますが、アルゴリズムが並べ替えられていない状態で機能する場合は、さらに優れています。

このグループにいくつの「フラグメント」があるかを知る必要があります。配列がファイルのバイト配列を構成していると想像してください。このファイルはどの程度断片化されていますか?

上記の例では、3 つのグループ/フラグメントをカウントします。

私の目標は、ディスク上の「ファイル」の総数、次に「フラグメント」の総数を合計してから、断片化を計算することです (1 - (files / fragments)と思います。10 個のファイル、10 個の断片 = 0% の断片化 - ただし、各ファイルが20 個のフラグメントを作る 2 つに分割され、50% のフラグメント化が発生します)。

したがって、私が探しているアルゴリズムでは、int の配列を調べて、連続する数値グループがいくつあるかを計算する必要があります。

何か案は？

4

1 に答える 1

0

私はこのアルゴリズム（ObjectiveC）を思いつきました...

-(NSInteger) numberOfFragments {
    NSInteger fragments = 1;

    NSArray *sortedBytes = [_bytes sortedArrayUsingComparator:^NSComparisonResult(GameFileByte *a, GameFileByte *b) {
        return ([a bytePosition] < [b bytePosition]) ? NSOrderedAscending : ([a bytePosition] > [b bytePosition]) ? NSOrderedDescending : NSOrderedSame;
    }];


    NSInteger lastBytePosition = -1;
    for (GameFileByte *byte in sortedBytes) {
        if (lastBytePosition > 0 && ((byte.bytePosition - lastBytePosition) > 1)) {
            fragments++;
        }
        lastBytePosition = byte.bytePosition;
    }


    return fragments;
}

これは私にとってはうまくいくようです...バイトが正しい順序であることを確認し、それらを循環して、現在のバイトが前のバイトから1以上離れるたびにカウンターを増やします。

于 2014-01-24T00:30:18.920 に答える