4

「スライディング ウィンドウ」を使用してファイルをスキャンするアルゴリズムを C++ で作成しています。つまり、バイト 0 から n までをスキャンし、何かを実行してから、バイト 1 から n+1 までをスキャンし、何かを実行し、というように最後まで実行します。が達成された。

私の最初のアルゴリズムは、最初の n バイトを読み取り、何かを実行し、1 バイトをダンプし、新しいバイトを読み取り、繰り返すというものでした。一度に 1 バイトずつ HDD から "ReadFile" を実行するのは非効率的だったため、これは非常に遅くなりました。(約100kB/s)

私の 2 番目のアルゴリズムでは、ファイルのチャンク (おそらく n*1000 バイト。大きすぎない場合はファイル全体を意味します) をバッファーに読み取り、バッファーから個々のバイトを読み取ります。現在、約 10MB/秒 (まともな SSD + Core i5、1.6GHz ラップトップ) を取得しています。

私の質問: さらに高速なモデルの提案はありますか?

edit :私の大きなバッファ (ウィンドウ サイズに比べて) は次のように実装されています:
- 5kB のローリング ウィンドウの場合、バッファは 5MB に初期化されます -
ファイルの最初の 5MB をバッファに読み込みます
- ウィンドウ ポインタは先頭から始まりますバッファの
- シフトすると、ウィンドウ ポインタがインクリメントされます
- ウィンドウ ポインタが 5MB バッファの終わり (たとえば 4.99MB) に近づくと、残りの 0.01MB をバッファの先頭にコピーし、ウィンドウ ポインタを開始し、追加の 4.99MB をバッファーに読み込みます。- 繰り返す

編集 2 - 実際の実装 (削除)

皆様、多くの洞察に満ちた回答をありがとうございました。「ベストアンサー」を選ぶのは難しかったです。それらはすべて素晴らしく、私のコーディングを助けてくれました。

4

3 に答える 3

3

私は自分のアプリの 1 つでスライディング ウィンドウを使用しています (実際には、スライディング ウィンドウの複数のレイヤーが互いに重なり合っていますが、それはこの説明の範囲外です)。CreateFileMapping()ウィンドウはとを介してメモリ マップされたファイル ビューを使用し、MapViewOfFile()その上に抽象化レイヤーを配置します。必要なバイト範囲を抽象化レイヤーに要求すると、それに応じてファイル マッピングとファイル ビューが調整され、それらのバイトがメモリ内にあることが保証されます。新しいバイト範囲が要求されるたびに、必要な場合にのみファイル ビューが調整されます。

ファイル ビューは、によって報告されたシステム粒度の偶数倍であるページ境界に配置され、サイズが設定されGetSystemInfo()ます。スキャンが特定のバイト範囲の終わりに達したからといって、ページ境界の終わりにまだ達しているとは限らないため、次のスキャンでファイル ビューをまったく変更する必要がない場合があります。次のバイトは既にメモリ内にあります。範囲の最初に要求されたバイトがマップされたページの右側の境界を超える場合、ファイル ビューの左端が要求されたページの左側の境界に調整され、左側のページはマップされません。範囲内で最後に要求されたバイトがマップされた一番右のページの右側の境界を超える場合、新しいページがマップされ、ファイル ビューに追加されます。

コーディングに入ると、実際に実装するよりも複雑に思えます。

ファイル内にビューを作成する

固定サイズのブロックでバイトをスキャンしているように聞こえるので、このアプローチは非常に高速で非常に効率的です。この手法に基づいて、マルチGIGBYTEファイルを最初から最後までかなり迅速に順次スキャンできます。通常、最も遅いマシンでも 1 分以内です。ファイルがシステムの粒度よりも小さい場合、またはほんの数メガバイトであっても、経過時間はほとんどわかりません (スキャン自体が遅い場合を除きます)。

更新:これは私が使用するものの単純化されたバリエーションです:

class FileView
{
private:
    DWORD m_AllocGran;
    DWORD m_PageSize;

    HANDLE m_File;
    unsigned __int64 m_FileSize;

    HANDLE m_Map;
    unsigned __int64 m_MapSize;

    LPBYTE m_View;
    unsigned __int64 m_ViewOffset;
    DWORD m_ViewSize;

    void CloseMap()
    {
        CloseView();

        if (m_Map != NULL)
        {
            CloseHandle(m_Map);
            m_Map = NULL;
        }
        m_MapSize = 0;
    }

    void CloseView()
    {
        if (m_View != NULL)
        {
            UnmapViewOfFile(m_View);
            m_View = NULL;
        }
        m_ViewOffset = 0;
        m_ViewSize = 0;
    }

    bool EnsureMap(unsigned __int64 Size)
    {
        // do not exceed EOF or else the file on disk will grow!
        Size = min(Size, m_FileSize);

        if ((m_Map == NULL) ||
            (m_MapSize != Size))
        {
            // a new map is needed...

            CloseMap();

            ULARGE_INTEGER ul;
            ul.QuadPart = Size;

            m_Map = CreateFileMapping(m_File, NULL, PAGE_READONLY, ul.HighPart, ul.LowPart, NULL);
            if (m_Map == NULL)
                return false;

            m_MapSize = Size;
        }

        return true;
    }

    bool EnsureView(unsigned __int64 Offset, DWORD Size)
    {
        if ((m_View == NULL) ||
            (Offset < m_ViewOffset) ||
            ((Offset + Size) > (m_ViewOffset + m_ViewSize)))
        {
            // the requested range is not already in view...

            // round down the offset to the nearest allocation boundary
            unsigned __int64 ulNewOffset = ((Offset / m_AllocGran) * m_AllocGran);

            // round up the size to the next page boundary
            DWORD dwNewSize = ((((Offset - ulNewOffset) + Size) + (m_PageSize-1)) & ~(m_PageSize-1));

            // if the new view will exceed EOF, truncate it
            unsigned __int64 ulOffsetInFile = (ulNewOffset + dwNewSize);
            if (ulOffsetInFile > m_FileSize)
                dwNewViewSize -= (ulOffsetInFile - m_FileSize);

            if ((m_View == NULL) ||
                (m_ViewOffset != ulNewOffset) ||
                (m_ViewSize != ulNewSize))
            {
                // a new view is needed...

                CloseView();

                // make sure the memory map is large enough to contain the entire view
                if (!EnsureMap(ulNewOffset + dwNewSize))
                    return false;

                ULARGE_INTEGER ul;
                ul.QuadPart = ulNewOffset;

                m_View = (LPBYTE) MapViewOfFile(m_Map, FILE_MAP_READ, ul.HighPart, ul.LowPart, dwNewSize);
                if (m_View == NULL)
                    return false;

                m_ViewOffset = ulNewOffset;
                m_ViewSize = dwNewSize;
            }
        }

        return true;
    }

public:
    FileView() :
        m_AllocGran(0),
        m_PageSize(0),
        m_File(INVALID_HANDLE_VALUE),
        m_FileSize(0),
        m_Map(NULL),
        m_MapSize(0),
        m_View(NULL),
        m_ViewOffset(0),
        m_ViewSize(0)
    {
        // map views need to be positioned on even multiples
        // of the system allocation granularity.  let's size
        // them on even multiples of the system page size...

        SYSTEM_INFO si = {0};
        if (GetSystemInfo(&si))
        {
            m_AllocGran = si.dwAllocationGranularity;
            m_PageSize = si.dwPageSize;
        }
    }

    ~FileView()
    {
        CloseFile();
    }

    bool OpenFile(LPTSTR FileName)
    {
        CloseFile();

        if ((m_AllocGran == 0) || (m_PageSize == 0))
            return false;

        HANDLE hFile = CreateFile(FileName, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, 0, NULL);
        if (hFile == INVALID_HANDLE_VALUE)
            return false;

        ULARGE_INTEGER ul;
        ul.LowPart = GetFileSize(hFile, &ul.HighPart);
        if ((ul.LowPart == INVALID_FILE_SIZE) && (GetLastError() != 0))
        {
            CloseHandle(hFile);
            return false;
        }

        m_File = hFile;
        m_FileSize = ul.QuadPart;

        return true;
    }

    void CloseFile()
    {
        CloseMap();

        if (m_File != INVALID_HANDLE_VALUE)
        {
            CloseHandle(m_File);
            m_File = INVALID_HANDLE_VALUE;
        }
        m_FileSize = 0;
    }

    bool AccessBytes(unsigned __int64 Offset, DWORD Size, LPBYTE *Bytes, DWORD *Available)
    {
        if (Bytes) *Bytes = NULL;
        if (Available) *Available = 0;

        if ((m_FileSize != 0) && (offset < m_FileSize))
        {
            // make sure the requested range is in view
            if (!EnsureView(Offset, Size))
                return false;

            // near EOF, the available bytes may be less than requested

            DWORD dwOffsetInView = (Offset - m_ViewOffset);

            if (Bytes) *Bytes = &m_View[dwOffsetInView];
            if (Available) *Available = min(m_ViewSize - dwOffsetInView, Size);
        }

        return true;
    }
};

.

FileView fv;
if (fv.OpenFile(TEXT("C:\\path\\file.ext")))
{
    LPBYTE data;
    DWORD len;

    unsigned __int64 offset = 0, filesize = fv.FileSize();

    while (offset < filesize)
    {
        if (!fv.AccessBytes(offset, some size here, &data, &len))
            break; // error

        if (len == 0)
            break; // unexpected EOF

        // use data up to len bytes as needed...

        offset += len;
    }

    fv.CloseFile();
}

このコードは、任意のデータ サイズでファイル内の任意の場所にランダム ジャンプできるように設計されています。バイトを順番に読み取るため、ロジックの一部は必要に応じて単純化できます。

于 2012-10-27T03:22:57.453 に答える
2

新しいアルゴリズムは、I/O の非効率性の 0.1% しか負担しません...心配する必要はありません。

スループットをさらに向上させるには、「何かをする」ステップを詳しく調べる必要があります。オーバーラップ ウィンドウからの結果の一部を再利用できるかどうかを確認します。キャッシュの動作を確認します。同じ計算に対してより良いアルゴリズムがあるかどうかを確認してください。

于 2012-10-27T02:51:31.877 に答える
1

基本的な I/O テクニックがダウンしました。今できる最も簡単な改善は、適切なバッファ サイズを選択することです。いくつかの実験では、約 16k に達するまで、バッファ サイズに応じて読み取りパフォーマンスが急速に向上し、その後パフォーマンスが横ばいになり始めることがわかります。

次のタスクは、おそらくコードのプロファイリングを行い、コードがどこで時間を費やしているかを確認することです。パフォーマンスを扱うときは、推測ではなく測定することが常に最善です。使用している OS について言及していないため、プロファイラーの推奨事項は作成しません。

バッファとワークスペース間のデータのコピー/移動の量を減らすこともできます。一般に、コピーは少ない方が良いです。データを新しい場所に移動するのではなく、その場で処理できれば、それは成功です。(あなたの編集から、あなたはすでにこれを行っていることがわかります。

最後に、数ギガバイトのアーカイブされた情報を処理している場合は、データを圧縮しておくことを検討する必要があります。多くの人は、圧縮されたデータを読み取ってから解凍する方が、解凍されたデータを読み取るよりも高速であることに驚かれることでしょう。この目的で私のお気に入りのアルゴリズムはLZOです。これは、他のアルゴリズムほど圧縮はしませんが、非常に高速に解凍します。この種のセットアップは、次の場合にのみエンジニアリング作業を行う価値があります。

  • あなたの仕事は I/O バウンドです。
  • 多くの G のデータを読み取っています。
  • プログラムを頻繁に実行しているので、実行を高速化するために多くの時間を節約できます。
于 2012-10-27T02:56:26.860 に答える