Оптимизация связанного списка

Question

Я работаю над этой программой, которая эмулирует рестрикционные ферменты и сращивание ДНК. Я использую DnaSequenceNode [s] в качестве связанных узлов списка.

У меня проблема с одной из функций в моем коде, cutSplice() должен создать новый DnaStrand, который является клоном текущего DnaStrand, но при этом каждый экземпляр фермента заменяется splicee.

Например, если LinkedDnaStrand создается с «TTGATCC» и cutSplice («GAT», «TTAAGG») вызывается, то связанный список должен стать чем-то вроде (предыдущие указатели не показаны):

первая -> «TT» -> «TTAAGG» -> «CC» -> null

Моя функция работает. Однако мой метод cutSplice() занимает более 80 секунд для сращивания 200 ДНК. Я должен довести это от 80 секунд до 2 секунд.

Это все мой код класса: LinkedDnaStrand.java

А вот код для метода cutSplice()

public DnaStrand cutSplice(String enzyme, String splicee) { 
    DnaStrand newStrand = null; 
    String original_Dna = this.toString(); 
    String new_Dna = original_Dna.replaceAll(enzyme, splicee); 
    String[] splicee_split = new_Dna.split(splicee); // splits the new DNA string DnaStrand 
    newStrand = null; 
    int i = 0; 
    if (original_Dna.startsWith(enzyme)) { 
     newStrand = new LinkedDnaStrand(splicee); 
    } else { 
     newStrand = new LinkedDnaStrand(splicee_split[0]); 
     newStrand.append(splicee); 
    } 
    for (i = 1; i < splicee_split.length - 1; i++) { 

     String node = splicee_split[i]; 
     newStrand.append(node); 
     newStrand.append(splicee); 

    } 
    newStrand.append(splicee_split[splicee_split.length - 1]); 

    if (original_Dna.endsWith(enzyme)) { 
     newStrand.append(splicee); 
    } 


    return newStrand; 
} 

Видит ли кто-нибудь, что могло бы существенно изменить на время эта функция принимает для обработки 200 образцов ДНК?

Answer 1

Ну, удобно использовать строковые методы, но вы теряете время на преобразование в строку, обратно в последовательность и (как указано в предыдущих комментариях) с строковыми функциями на основе регулярных выражений.

Это, безусловно, потребляет меньше времени, чтобы работать на связанный список непосредственно, хотя это потребует от вас реализовать алгоритм замены самостоятельно:

@Override 
public LinkedDnaStrand cutSplice(String enzyme, String splicee) 
{ 
    LinkedDnaStrand strand = new LinkedDnaStrand(); 
    DnaSequenceNode end = null; 
    DnaSequenceNode begin = top; 
    int pos = 0; 
    DnaSequenceNode tmpStart, tmpEnd; 
    for (DnaSequenceNode current = top; current != null; current = current.next) 
    { 
     if(current.value != enzyme.charAt(pos)) 
     { 
      tmpStart = tmpEnd = new DnaSequenceNode(begin.value); 
      for (DnaSequenceNode n = begin.next; n != current.next; n = n.next) 
      { 
       DnaSequenceNode c = new DnaSequenceNode(n.value); 
       tmpEnd.next = c; 
       c.previous = tmpEnd; 
       tmpEnd = c; 
      } 
     } 
     else if(++pos == enzyme.length()) 
     { 
      tmpStart = tmpEnd = new DnaSequenceNode(splicee.charAt(0)); 
      for (int i = 1; i < splicee.length(); ++i) 
      { 
       DnaSequenceNode c = new DnaSequenceNode(splicee.charAt(i)); 
       tmpEnd.next = c; 
       c.previous = tmpEnd; 
       tmpEnd = c; 
      } 
     } 
     else 
     { 
      continue; 
     } 

     if(end == null) 
     { 
      strand.top = end = tmpStart; 
     } 
     else 
     { 
      end.next = tmpStart; 
      tmpStart.previous = end; 
     } 
     end = tmpEnd; 
     begin = current.next; 
     pos = 0; 
    } 

    return strand; 
} 

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

Примечание 1: Я явно создал новую последовательность из строки (вместо использования конструктора) чтобы получить окончание последовательности без необходимости повторять ее снова.

Примечание 2: Я предположил, что существует конструктор DnaSequenceNode(char value) и DnaSequenceNode, имеющий член public char value. Возможно, вам придется соответствующим образом скорректировать код, если какое-либо из этих допущений терпит неудачу.