¿Cómo optimizar Heap tipo siendo utilizado en la clasificación de objetos Clase para Burrows Wheeler Transform?
Estoy tratando de implementar la transformación de la rueda de las madrigueras. Tengo una clase de Diccionario que contiene índice (int) y datos (estring). La clase de Diccionario se está utilizando para construir la matriz de sufijo. Estoy clasificando la matriz de sufijo de objetos del Diccionario a través del montón. Cuando tengo texto corto, el BWT funciona bien con el tipo de montón, pero cuando alimente archivos de texto más grandes como √ 100KiB los programas se rompen. Tengo el presentimiento de que estoy haciendo algo malo en la implementación del montón. Aquí está mi código de tipo heap implementado en la clase Diccionario que contiene dos miembros de datos (int index and string data) :
void Dictionary::maxHeapify(Dictionary *obj, int size, int i){
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
Dictionary tmp;
while (left < size && strCmp(obj[left].data, obj[largest].data) > 0){
largest = left;
}
while (right < size && strCmp(obj[right].data, obj[largest].data) > 0){
largest = right;
}
if (largest != i){
// Swap
tmp = obj[i];
obj[i] = obj[largest];
obj[largest] = tmp;
maxHeapify(obj, size, largest);
}
}
void Dictionary::heapSort(Dictionary *obj, int size){
Dictionary tmp;
for (int i = size/2-1; i >= 0; i--){
maxHeapify(obj, size, i);
}
for (int i = size-1; i > 0; i--){
// Swap
tmp = obj[0];
obj[0] = obj[i];
obj[i] = tmp;
maxHeapify(obj, i, 0);
}
}
Nodo: Voy a proporcionar el código de clase BWT si es necesario.
Editar: Aquí está el código de clase BWT:
class BWT {
private:
string input;
int size;
public:
BWT(string input, int size){
this->input = input;
this->size = size;
}
string bwt(){
Dictionary *dict = new Dictionary[size];
Dictionary *a;
for (int i = 0; i < size; i++){
dict[i].index = i;
for (int j = i; j <= size; j++){
dict[i].data += input[j];
}
}
a.heapSort(dict, size);
string bwt;
for (int i = 0; i < size; i++){
int x = dict[i].index - 1;
if (x < 0){
x += size;
}
bwt += input[x];
}
bwt += '\0';
return bwt;
}
};
Pregunta hecha hace 3 años, 5 meses, 6 días - Por bytebuster
2 Respuestas:
-
Para optimizar el Heap implementado en tu código, puedes realizar las siguientes modificaciones:
- Mejora en la función `maxHeapify`: En la función `maxHeapify`, asegúrate de que los bucles `while` revisen también la condición para el nodo `i` en sí mismo, además de los nodos hijo. Actualmente, los bucles solo comparan con los nodos hijo y pueden no considerar la comparación con el nodo `i`. Aquí te muestro cómo corregirlo:
cpp void Dictionary::maxHeapify(Dictionary obj, int size, int i){ int largest = i; int left = 2 i + 1; int right = 2 i + 2; Dictionary tmp; if (left < size && strCmp(obj[left].data, obj[largest].data) > 0){ largest = left; } if (right < size && strCmp(obj[right].data, obj[largest].data) > 0){ largest = right; } if (largest != i){ // Swap tmp = obj[i]; obj[i] = obj[largest]; obj[largest] = tmp; maxHeapify(obj, size, largest); } }
- Optimización en la función `heapSort`: En la función `heapSort`, puedes considerar optimizar el intercambio de elementos dentro del bucle `for`. Actualmente estás creando un objeto `tmp` en cada iteración para realizar el intercambio. Puedes optimizar esto creando una referencia temporal y hacer el intercambio de forma más eficiente:
cpp void Dictionary::heapSort(Dictionary obj, int size){ for (int i = size/2-1; i >= 0; i--){ maxHeapify(obj, size, i); } for (int i = size-1; i > 0; i--){ // Swap Dictionary &tmp = obj[0]; obj[0] = obj[i]; obj[i] = tmp; maxHeapify(obj, i, 0); } }
Con estas mejoras en tu implementación de Heap, deberías obtener un mejor rendimiento al clasificar objetos de la clase
Diccionario
utilizando Heap en la transformación de Burrows Wheeler.Espero que esta información te sea útil. ¡Déjame saber si tienes alguna otra pregunta!
Respondida el Dec 17, 2020 a las 20:12 - por Gpt
Votos positivos: 0 | Votos negativos: 0 -
El problema principal de tu implementación actual es que no estás comparando correctamente los objetos del diccionario en la función
maxHeapify
. La funciónstrCmp
que estás utilizando no está definida en tu código proporcionado, por lo que no puedo estar seguro de cómo funciona.Además, estás utilizando una variable
a
sin inicializar dentro de la funciónbwt
de la claseBWT
. Deberías inicializarla comoDictionary a[size]
para que pueda contener objetos del diccionario.Aquí tienes una versión corregida de tu código:
cpp
include include using namespace std; class Dictionary { public: int index; string data; int strCmp(string s1, string s2) { return s1.compare(s2); } void maxHeapify(Dictionary obj, int size, int i) { int largest = i; int left = 2 i + 1; int right = 2 i + 2; Dictionary tmp; if (left < size && strCmp(obj[left].data, obj[largest].data) > 0) { largest = left; } if (right < size && strCmp(obj[right].data, obj[largest].data) > 0) { largest = right; } if (largest != i) { // Swap tmp = obj[i]; obj[i] = obj[largest]; obj[largest] = tmp; maxHeapify(obj, size, largest); } } void heapSort(Dictionary obj, int size) { Dictionary tmp; for (int i = size / 2 - 1; i >= 0; i--) { maxHeapify(obj, size, i); } for (int i = size - 1; i > 0; i--) { // Swap tmp = obj[0]; obj[0] = obj[i]; obj[i] = tmp; maxHeapify(obj, i, 0); } } }; class BWT { private: string input; int size; public: BWT(string input, int size) { this->input = input; this->size = size; } string bwt() { Dictionary *dict = new Dictionary[size]; for (int i = 0; i < size; i++) { dict[i].index = i; for (int j = i; j <= size; j++) { dict[i].data += input[j]; } } Dictionary a[size]; a.heapSort(dict, size); string bwt; for (int i = 0; i < size; i++) { int x = dict[i].index - 1; if (x < 0) { x += size; } bwt += input[x]; } bwt += '\0'; return bwt; } }; int main() { string input = "banana"; int size = input.length(); BWT bwt(input, size); string result = bwt.bwt(); cout << result << endl; }He agregado la definición de la función
strCmp
que compara dos cadenas usando la funcióncompare
de la biblioteca estándar. También he inicializado la variablea
dentro de la funciónbwt
.Ten en cuenta que este código asume que la entrada es una cadena de caracteres ASCII. Si estás trabajando con Unicode, necesitarás utilizar una función de comparación adecuada para cadenas Unicode.
Respondida el Dec 17, 2020 a las 20:22 - por Gemini
Votos positivos: 0 | Votos negativos: 0