基于链表的词建议程序如何降低执行耗时？

核心问题分析 #

当前程序处理3MB文本耗时12分钟，主要瓶颈在于contains方法遍历整个链表查找词对，时间复杂度为O(n)，随着词库规模增长，查找耗时会急剧增加。此外代码中存在语法错误，会导致大量无效插入，进一步拖慢性能。

优化步骤 #

1. 修复致命语法错误

原代码中if(myList.contains(prevWord, currWord));末尾多了分号，导致else分支永远执行，大量重复词对被插入链表，直接加剧性能问题。修正后代码：

if(myList.contains(prevWord, currWord)) {
    // contains方法已处理order自增，无需额外操作
} else {
    myList.insertTail(prevWord, currWord);
}

2. 优化停用词查找

如果停用词使用ArrayList存储，contains方法是O(n)复杂度，改为HashSet可将其降为O(1)：

Set<String> stopWord = new HashSet<>();
while(stopScan.hasNext()) {
    // 提前转小写，避免后续重复转换
    stopWord.add(stopScan.next().toLowerCase());
}

3. 预编译正则表达式减少开销

文本清理时的replaceAll会重复编译正则表达式，预编译后可节省大量CPU时间：

import java.util.regex.Pattern;

// 预编译正则
Pattern cleanPattern = Pattern.compile("[^a-z ]");

// 替换原文本处理逻辑
prevWord = cleanPattern.matcher(textScan.next().toLowerCase()).replaceAll("");
currWord = cleanPattern.matcher(textScan.next().toLowerCase()).replaceAll("");

4. 引入哈希表加速词对查找（核心优化）

由于必须使用自定义链表，我们可以用HashMap缓存词对与对应节点的映射，将contains方法的O(n)遍历改为O(1)查找：

修改链表类实现：

import java.util.HashMap;
import java.util.Objects;

// 自定义词对类，用于哈希表的键
class WordPair<T> {
    private final T first;
    private final T second;

    public WordPair(T first, T second) {
        this.first = first;
        this.second = second;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        WordPair<?> pair = (WordPair<?>) o;
        return Objects.equals(first, pair.first) && Objects.equals(second, pair.second);
    }

    @Override
    public int hashCode() {
        return Objects.hash(first, second);
    }
}

class CustomLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    // 新增哈希表缓存词对与节点的映射
    private HashMap<WordPair<T>, Node<T>> pairNodeMap;

    public CustomLinkedList() {
        this.pairNodeMap = new HashMap<>();
    }

    // 优化后的contains方法
    boolean contains(T wordOne, T wordTwo) {
        WordPair<T> pair = new WordPair<>(wordOne, wordTwo);
        Node<T> targetNode = pairNodeMap.get(pair);
        if (targetNode != null) {
            targetNode.order++;
            return true;
        }
        return false;
    }

    // 同步维护哈希表的插入方法
    void insertTail(T wordOne, T wordTwo) {
        WordPair<T> pair = new WordPair<>(wordOne, wordTwo);
        // 双重校验避免重复插入
        if (pairNodeMap.containsKey(pair)) {
            pairNodeMap.get(pair).order++;
            return;
        }

        Node<T> newNode = new Node<>(wordOne, wordTwo);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
        pairNodeMap.put(pair, newNode);
    }

    // 排序方法中同步更新哈希表映射
    void sort() {
        Node<T> temp = head;
        while(temp != null) {
            if(temp.prev != null && temp.order > temp.prev.order) {
                swap(temp, temp.prev);
                temp = temp.prev;
            } else {
                temp = temp.next;
            }
        }
    }

    // 交换节点内容并同步更新哈希表
    private void swap(Node<T> a, Node<T> b) {
        // 交换节点的词对与计数
        T tempWordOne = a.wordOne;
        T tempWordTwo = a.wordTwo;
        int tempOrder = a.order;

        a.wordOne = b.wordOne;
        a.wordTwo = b.wordTwo;
        a.order = b.order;

        b.wordOne = tempWordOne;
        b.wordTwo = tempWordTwo;
        b.order = tempOrder;

        // 更新哈希表中的映射
        WordPair<T> pairA = new WordPair<>(a.wordOne, a.wordTwo);
        WordPair<T> pairB = new WordPair<>(b.wordOne, b.wordTwo);
        pairNodeMap.put(pairA, a);
        pairNodeMap.put(pairB, b);
    }

    static class Node<T> {
        T wordOne;
        T wordTwo;
        int order = 1;
        Node<T> prev;
        Node<T> next;

        public Node(T wordOne, T wordTwo) {
            this.wordOne = wordOne;
            this.wordTwo = wordTwo;
        }
    }
}

优化效果说明 #

通过上述改动：

• 停用词查找、词对查找的时间复杂度均从O(n)降至O(1)
• 避免了无效的重复节点插入
• 减少了正则表达式重复编译的开销
  处理3MB文本的耗时会大幅降低，可远低于当前的12分钟。

内容的提问来源于stack exchange，提问作者blurpex