차단 된 파일에서 레코드를 압축하기위한 좋은 알고리즘은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/130227

문제

고정 크기 블록이 많은 큰 파일이 있다고 가정합니다. 이 블록 각각에는 몇 가지 가변 크기의 레코드가 포함되어 있습니다. 각 레코드는 단일 블록 내에 완전히 맞아야하며 정의에 따른 해당 레코드는 전체 블록보다 크지 않습니다. 시간이 지남에 따라 레코드 가이 "데이터베이스"에서 나오고 이동함에 따라 레코드가 추가 및 삭제됩니다.

어느 시점에서, 특히 많은 레코드가 데이터베이스에 추가되고 몇 가지가 제거 된 후에는 많은 블록이 부분적으로 만 채워질 수 있습니다.

부분적으로 채워진 블록을 더 잘 채우면서 파일 끝에 불필요한 블록을 압축하기 위해이 데이터베이스의 레코드를 셔플하기위한 좋은 알고리즘은 무엇입니까?

알고리즘의 요구 사항 :

  • 압축은 파일을 시작 크기에서 최대 몇 블록 이상으로 일시적으로 확장하지 않고 원본 파일 대신에 발생해야합니다.
  • 알고리즘은 이미 주로 가득 찬 블록을 불필요하게 방해해서는 안됩니다.
  • 전체 블록은 한 번에/파일에서 읽거나 작성해야하며, 쓰기 작동이 비교적 비싸다고 가정해야합니다.
  • 레코드가 한 블록에서 다른 블록으로 이동하면 시작 위치에서 제거되기 전에 새 위치에 추가되어야합니다. 따라서 작업이 중단되면 "실패한"압축의 결과로 레코드가 손실되지 않습니다. (이러한 기록의 임시 복제는 복구시 감지 될 수 있다고 가정합니다).
  • 이 작업에 사용할 수있는 메모리는 전체 파일 크기의 매우 작은 비율 인 여러 블록의 순서에만있을 수 있습니다.
  • 레코드는 평균 크기가 100 바이트 일 수있는 10 바이트에서 1k 바이트의 순서라고 가정합니다. 고정 크기의 블록은 4K 또는 8K 순서에 있으며 파일은 1000 대의 블록 순서입니다.
도움이 되었습니까?

해결책

이것은 변형처럼 들립니다 빈 포장 문제, 그러나 당신이 이미 개선하고자하는 열등한 할당이있는 곳. 따라서 빈 포장 문제에 성공한 접근 방식의 변형을 살펴 보는 것이 좋습니다.

우선, 당신은 아마도 당신이 "충분히 가득 채우는 것"(블록이 만지고 싶지 않은 블록이 가득 차서)을 정의하여 문제를 매개 변수화하고 싶을 것입니다. 너무 빈 공간이 너무 많아서 더 많은 레코드가 추가되어야합니다). 그런 다음 모든 블록을 충분히 가득 차거나 너무 비어 있거나 부분적으로 가득 찬 것으로 분류 할 수 있습니다 (충분히 가득 차거나 너무 비어 있지 않은 것). 그런 다음 부분적으로 전체 블록의 수를 최소화하면서 가능한 한 충분한 블록을 생성하여 너무 빈 블록을 제거하는 방법으로 문제를 재정의합니다.

또한 더 중요한 것을 해결하고 싶을 것입니다. 레코드를 가능한 가장 적은 블록으로 가져 오거나 적절하게 포장하지만 최소한의 블록을 읽고 작성했습니다.

저의 접근 방식은 모든 블록을 초기 통과하여 위에서 정의 된 세 가지 클래스 중 하나로 분류하는 것입니다. 각 블록마다 사용 가능한 여유 공간을 추적하고 너무 빈 블록의 경우 모든 레코드와 해당 크기의 목록을 원할 것입니다. 그런 다음 너무 비어있는 블록의 가장 큰 레코드부터 시작하여 부분적으로 전체 블록으로 이동하십시오. 읽기와 쓰기를 최소화하려면 현재 메모리에있는 블록으로 옮기십시오. 낭비 된 공간을 최소화하려면 여전히 레코드를 유지하는 빈 공간이 가장 적은 블록을 찾아 필요한 경우 블록을 읽으십시오. 블록이 레코드를 보유하지 않으면 새 블록을 만듭니다. 메모리의 블록이 "충분한 충분한"임계 값에 도달하면 기록하십시오. 부분적으로 채워진 블록의 모든 레코드가 배치 될 때까지 반복하십시오.

나는 몇 가지 세부 정보 이상을 건너 뛰었지만 이것은 당신에게 몇 가지 아이디어를 줄 것입니다. 빈 포장 문제는 다음과 같습니다 NP-HARD, 즉, 실제 응용 프로그램의 경우 가장 중요한 것을 결정하고 합리적인 시간에 대략 최상의 솔루션을 제공 할 수있는 접근 방식을 선택할 수 있습니다.

다른 팁

이 레코드에 주문하지 않으면 마지막 블록에서 추출한 레코드로 전면에서 블록을 채우는 것입니다. 이것은 데이터의 움직임을 최소화하고 상당히 간단하며 데이터를 단단히 포장하는 괜찮은 작업을 수행해야합니다.

예 :

// records should be sorted by size in memory (probably in a balanced BST)
records = read last N blocks on disk;

foreach (block in blocks) // read from disk into memory
{
    if (block.hasBeenReadFrom())
    {
        // we read from this into records already
        // all remaining records are already in memory

        writeAllToNewBlocks(records);

        // this will leave some empty blocks on the disk that can either
        // be eliminated programmatically or left alone and filled during
        // normal operation

        foreach (record in records)
        {
            record.eraseFromOriginalLocation();
        }

        break;
    }

    while(!block.full())
    {
        moveRecords = new Array; // list of records we've moved

        size = block.availableSpace();
        record = records.extractBestFit(size);
        if (record == null)
        {
            break;
        }

        moveRecords.add(record);
        block.add(record);

        if (records.gettingLow())
        {
            records.readMoreFromDisk();
        }
    }

    if(moveRecords.size() > 0)
    {
        block.writeBackToDisk();
        foreach (record in moveRecords)
        {
            record.eraseFromOriginalLocation();
        }
    }
}

업데이트 : 블록 전용 메모리 규칙을 유지하는 것을 무시했습니다. 이 문제를 해결하기 위해 의사 코드를 업데이트했습니다. 또한 내 루프 조건에서 결함을 수정했습니다.

온라인 (한 번의 패스에서 탈퇴)을 수정 한 바운드 공간 (메모리 요구 사항) 빈 포장 알고리즘을 수정하면 여기서는 작동 할 수 있습니다.

보다 "빈 포장 근사 알고리즘 : 조합 분석" Coffman et al.

고정 크기 블록 내의 레코드에는 약간 더 많은 작업이 필요할 수 있지만 활용할 수있는 알고리즘이 있습니다.

제한된 시간에 힙 분할

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top