链表优化

Question

我正在研究这个模拟限制性内切酶和DNA剪接的程序。我使用DnaSequenceNode[s]作为链表节点。

我有一个问题，在我的代码中的一个函数，cutSplice()应该创建一个新的DnaStrand，是当前DnaStrand的克隆，但酶的每一个实例被splicee取代。

例如，如果LinkedDnaStrand用"TTGATCC"实例化，并且调用cutSplice("GAT"， "TTAAGG")，那么链表应该变成(前面的指针没有显示):

first -> "TT" -> "TTAAGG" -> "CC" -> null

我的函数工作。然而，我的方法cutSplice()需要超过80秒拼接200个dna。我应该把这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个dna样本所需的时间产生关键影响的东西?

Answer 1

嗯，使用字符串方法很舒服，但是在转换到字符串、返回到序列以及(如前面的评论所指出的)使用基于regex的字符串函数时浪费了时间。

直接操作链表肯定会消耗更少的时间，尽管这需要你自己实现替换算法:

@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。如果这些假设中的任何一个不成立，您可能需要适当地调整代码。