Быстрая реализация 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 

Вам также потребуется собственную функцию сортировки, потому что стандарт не обеспечивает достаточной гибкости для этой магии. Quicksort это хорошая идея (вы могли бы избежать некоторых из аргументов, но я вставил только версию 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; 
} 

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