2

ここにあるものは、たとえば10行バイトx10列バイト=100要素のデータに対しては正常に機能します。しかし今、私は256行バイトx256列バイト=65536要素でそれを試しました、そしてそれは適切な辞書式順序で行をソートするのに約30分かかります。とにかく、この機能を最適化して、完了するまでに最大5秒かかる可能性があります。

他の並べ替えアルゴリズムを使用する必要があることはわかっていますが、どうすればよいかわかりません。

Function SortArrayOfArraysLexicoGraphically(ByRef data() As Byte) As Byte()
Dim lexicoGraphicalIndexes() As Byte

Dim dataSize As Long
dataSize = UBound(data) + 1
Dim squareRootMinusOne As Integer
Dim squareRoot As Integer
squareRoot = Sqr(dataSize)
squareRootMinusOne = squareRoot - 1

ReDim lexicoGraphicalIndexes(squareRootMinusOne)

Dim columnStart As Long
Dim row As Long
Dim column As Long
Dim rowSwapped As Boolean

For columnStart = 0 To UBound(lexicoGraphicalIndexes)
    lexicoGraphicalIndexes(columnStart) = columnStart
Next columnStart

'start column from the last element from the row and go backwards to first element in that row.
For columnStart = squareRootMinusOne To 0 Step -1
    Do
        rowSwapped = False
        Do
             If data((row * squareRoot) + columnStart) > data(((row + 1) * squareRoot) + columnStart) Then

                'Swaps a full row byte by byte.
                For column = 0 To squareRootMinusOne
                    Call SwapBytes(data, (row * squareRoot) + column, ((row + 1) * squareRoot) + column)
                Next column
                Call SwapBytes(lexicoGraphicalIndexes, row, row + 1)
                rowSwapped = True
            End If
            row = row + 1
        Loop Until row > squareRootMinusOne - 1
        row = 0
    Loop Until rowSwapped = False
Next columnStart

'returns a byte array of sorted indexes.
SortArrayOfArraysLexicoGraphically = lexicoGraphicalIndexes
End Function

Public Sub SwapBytes(data() As Byte, firstIndex As Long, secondIndex As Long)
    Dim tmpFirstByte As Byte
    tmpFirstByte = data(firstIndex)
    data(firstIndex) = data(secondIndex)
    data(secondIndex) = tmpFirstByte
End Sub
4

1 に答える 1

4

これの遅いステップは、ループ内のバイトごとのコピーです。RtlMoveMemory API呼び出し（多くの場合、CopyMemoryと呼ばれます）を利用します。これにより、ブロックメモリのコピーが実行されます。これははるかに高速です。また、行スワップの一時バッファーとして機能するモジュールレベルの配列を宣言します。以下の2つの手順をマージして、自己完結型にすることができます。

Private Declare Sub CopyMemory Lib "Kernel32.dll" Alias "RtlMoveMemory" (ByVal pDest As Long, ByVal pSrc As Long, ByVal nCount As Long)

Private m_bytTemp() As Byte


Function SortArrayOfArraysLexicoGraphically2(ByRef data() As Byte) As Byte()

    Dim lexicoGraphicalIndexes() As Byte
    Dim dataSize As Long
    Dim squareRootMinusOne As Integer
    Dim squareRoot As Integer
    Dim columnStart As Long
    Dim row As Long
    Dim column As Long
    Dim rowSwapped As Boolean

    dataSize = UBound(data) + 1
    squareRoot = Sqr(dataSize)
    ReDim m_bytTemp(1 To squareRoot)
    squareRootMinusOne = squareRoot - 1
    ReDim lexicoGraphicalIndexes(squareRootMinusOne)

    For columnStart = 0 To UBound(lexicoGraphicalIndexes)
        lexicoGraphicalIndexes(columnStart) = columnStart
    Next columnStart

    'start column from the last element from the row and go backwards to first element in that row.
    For columnStart = squareRootMinusOne To 0 Step -1
        Do
            rowSwapped = False
            Do
                If data((row * squareRoot) + columnStart) > data(((row + 1) * squareRoot) + columnStart) Then
                    'Swaps a full row in a few copies.
                    SwapMultipleBytes data, (row * squareRoot), ((row + 1) * squareRoot), squareRoot
                    Call SwapBytes(lexicoGraphicalIndexes, row, row + 1)
                    rowSwapped = True
                End If
                row = row + 1
            Loop Until row > squareRootMinusOne - 1
            row = 0
        Loop Until rowSwapped = False
    Next columnStart

    'returns a byte array of sorted indexes.
    SortArrayOfArraysLexicoGraphically2 = lexicoGraphicalIndexes
End Function

Public Sub SwapMultipleBytes(ByRef data() As Byte, ByVal firstIndex As Long, ByVal secondIndex As Long, ByVal nCount As Long)

    CopyMemory VarPtr(m_bytTemp(1)), VarPtr(data(firstIndex)), nCount
    CopyMemory VarPtr(data(firstIndex)), VarPtr(data(secondIndex)), nCount
    CopyMemory VarPtr(data(secondIndex)), VarPtr(m_bytTemp(1)), nCount

End Sub
于 2012-08-29T10:17:54.070 に答える