Быстрое внедрение BWT в Lua

Question

local function fShallowCopy(tData)
    local tOutput = {}
    for k,v in ipairs(tData) do
        tOutput[k] = v
    end
    return tOutput
end

local function fLexTblSort(tA,tB) --sorter for tables
    for i=1,#tA do 
        if tA[i]~=tB[i] then 
            return tA[i]<tB[i]
        end
    end 
    return false 
end

function fBWT(tData)

    --setup--
    local iSize = #tData
    local tSolution = {}
    local tSolved = {}


    --key table--
    for n=1,iSize do 
        tData[iSize] = fRemove(tData,1)
        tSolution[n] = fShallowCopy(tData)
    end
    table.sort(tSolution,fLexTblSort)


    --encode output--
    for i=1,iSize do
        tSolved[i] = tSolution[i][iSize]
    end


    --finalize--
    for i=1,iSize do
        if fIsEqual(tSolution[i],tData) then
            return i,tSolved
        end
    end
    return false
end

Выше мой текущий код для достижения кодирования BWT в Lua. Проблема в том, что из-за размера таблиц и длины циклов выполнение занимает много времени. Для ввода 1000 символов среднее время кодирования составляет около 1,15 секунды. У кого-нибудь есть предложения по созданию более быстрой функции кодирования BWT?

самые большие замедления, по-видимому, в fLexTblSort и fShallowCopy. Я включил оба выше функции BWT также.

Answer 1

Если я правильно понимаю, ваш алгоритм имеет сложность O(n^2 log n), если сортировка быстрая. Функция компаратора fLexTblSort принимает O(n) сам для каждой пары значений, которые вы сравниваете.

Как я проверил в своей реализации несколько лет назад, я вижу возможности для улучшения. Вы создаете все возможные повороты tData, что также занимает много времени. Я использовал только один блок данных и сохранял только начальные позиции определенных вращений. Вы также используете много петель, которые могут уменьшиться в меньшую.

Моя реализация была в C, но концепция может быть использована и в Lua. Идея в каком-то гибридном псевдокоде между вашим Lua и C.

function fBWT(tData)

  local n = #tData
  local tSolution = {}
  for(i = 0; i < n; i++)
    tSolution[i] = i;

  --table.sort(tSolution, fLexTblSort)
  quicksort(tData, n, tSolution, 0, n)

  for(i = 0; i < n; i++){
    tSolved[i] = tData[(tSolution[i]+n-1)%n];
    if( tSolution[i] == 0 )
        I = i;
  }

  return I, tSolved
end

Вам также понадобится ваша собственная функция сортировки, потому что стандарт не предоставляет достаточной гибкости для этой магии. Хорошая идея - быстрая сортировка (вы можете избежать некоторых аргументов, но я вставил только ту версию C, которую использовал):

void swap(int array[], int left, int right){
    int tmp = array[right]; 
    array[right] = array[left];
    array[left] = tmp;         
}

void quicksort(uint8_t data[], int length, int array[], int left, int right){
    if(left < right){ 
        int boundary = left;
        for(int i = left + 1; i < right; i++){ 
            if( offset_compare(data, length, array, i, left) < 0 ){
                swap(array, i, ++boundary);
            }
        }
        swap(array, left, boundary);
        quicksort(data, length, array, left, boundary);
        quicksort(data, length, array, boundary + 1, right);
    }     
}

Последний шаг - это ваша собственная функция компаратора (похожая на вашу оригинальную, но работающую над поворотами, опять же в C):

/**
 *  compare one string (fixed length) with different rotations.
 */
int offset_compare(uint8_t *data, int length, int *array, int first, int second){
    int res;
    for(int i = 0; i < length; i++){
        res = data[(array[first]+i)%length] - data[(array[second]+i)%length];
        if( res != 0 ){
            return res;
        }
    }
    return 0;
}

Это основная идея, с которой я столкнулся несколько лет назад и которая сработала для меня. Дайте мне знать, если есть что-то непонятное или какая-то ошибка.