想问一下,怎样可以处理大型list,而不影响性能?

我最近做一个buffer单词提取然后和本地词库对比的函数。我现在做法Buffer里面的每一个单词都跟整个词库对比,有包含在内就高亮,没有就不高亮,但是这方法好慢,一次调用都要5秒到10秒的时间才能做好处理好一个buffer。

词库有一万个词左右,已经预加载在一个 word-in-list里面了,buffer的单词加载在 word-in-buffer里面了。

想问一下大家怎样处理大型list处理而又保持很好的性能的?

我的实现如下:

    (get-buffer-create  "*english-helper*")
  (with-current-buffer "*english-helper*"
    (erase-buffer))
  (with-current-buffer (current-buffer)
    (let* ((word-car (mapcar 'car word-in-list))
           (highlight-word (seq-intersection word-car word-in-buffer)))
      (dolist (sub highlight-word)
        ;; (write-region  (concat (concatString (assoc sub word-in-list)) "\n" ) nil "~/OneDrive/Org/current-buffer-word-list.txt" 'append)
        (with-current-buffer "*english-helper*"
          (goto-char (point-max))
          (insert (concat (concatString (assoc sub word-in-list)) "\n")))
        (save-excursion
          (goto-char (point-min))
          (while (re-search-forward sub nil t)
            (let* ((beg (match-beginning 0))
                   (xx (make-overlay beg (point))))
              (overlay-put xx 'face 'highlight)))))))

用hash table。

用assoc查找均摊时间复杂度为O(n),用哈希表gethash立降到O(1)。hash test用equal可应付字符串查找。

显得比较牛逼的可以用前缀树,但没必要,内存不值钱

2 个赞

非常感谢大神。我研究一下。 :grinning:

这里有好几种方法:

  1. 简单一点可以将本地词库内的单词有序排序,然后判断一个单词是否在这个序列里面就 二分查找一下。复杂度是O(log n)。但是需要注意,因为是字符串的比较,不像是数 字这种primitive类型,比较的cost不能以O(1)来算。

  2. 可以选择将字符串hash全部扔入hashmap中,比较考验hash function的设计。开 链法解决冲突不可取,因为可能可能会有大量的比较。所以在选择hashmap时选择开放 地址法的实现,复杂度O(1)

  3. 需要注意到,字符串很大可能会有大量的公共前缀,因此可以采用Trie结构来表 示。当然最朴素的Trie比较消耗内存,在数据稀疏情况下的内存使用率非常糟糕。因 此可以选择Ternary search tree。因为它存储的关系里 多了等于,所以会比最朴素的Trie占用内存小一点。

如果当然buffer内的字符串个数不会再增加了,可以将查询范围缩小。即先用查询集的最 小(lexical)、最大的字符串限制搜索集,然后再采用上述说的解法。

5 个赞

按照行分割,异步并发处理应该可以提高速度

1 个赞