在字符串中 快速查找

很多時候,我們需要在字符串中執行查找,以判斷過濾指定的內容出來。比如過在落格輸入法當中,就需要用輔碼過濾出需要的候選詞。

一般來說,查找和對比肯定是數字來的最快,不過在詞庫上總不能把所有的詞彙都轉換為數字(雖然理論上可行……)在字符串的搜索上,我們有很多種辦法來實現,這裡我就說一下我自己的思路:

組<String>

由於我的詞庫輔碼篩選只對兩字或者三字詞彙生效,那麼我考慮把它們作為集合(Set)來檢測,把詞彙拆成單字。很遺憾,不說拆分的單獨開銷,本以為哈希表的set集合會很快,但速度並不行,可能它的優勢是在於大量的時候吧,不過很可惜,它的速度是最慢的。

我用一個簡短的集合來多次遍歷然後統計時間,得到結果如下:

結果 8.90186786651611 值得一提的是,無論是命中還是丟失,速度是一樣的。當然,速度慢也得考慮字符串比較自身的開銷問題。

a.contains(“一個”)

字符串自帶了包含方法,它可以檢測字符串 一個 中是否包含了 "一個" ,如果包含了,就返回 true 。這是很直接的辦法:

用這樣簡單的遍歷得到結果 7.06464505195618 秒。

那麼能不能更快一些呢?我們換一種思路,如果說我們僅僅是查找,那其實還有一種方法可以考慮,那就是

a.range(的: “一個”)

斯威夫特中 String 還有一個自帶的方案,那就是獲取指定字符串在另一字符串的範圍,用來提取活著修改字符串用,如果找不到,那麼就返回

這裡我們用返回值是否為空來判斷字符串是否包含,速度會是多少呢?

執行的結果是 6.38309478759766 秒。顯然,這種方法的查找速度是比上邊兩種專門的查找要快的。

總結

  • 用什麼方法是手段不是目的,總之我們能得到想要的結果就好了,哪個好?最快的那個;
  • 多個功能類似可以互相替代的方法要做測試,不能靠猜來判斷性能;
  • Set是唯一命中和丟失速度都一致的方法,但 範圍 丟失時也比 Set 要快;
  • 以上結果是建立在字符串查找上的,不是所有情況 :)

本文由 落格博客 原創撰寫:落格博客 » 在字符串中 快速查找

轉載請保留出處和原文鏈接:https://www.logcg.com/archives/2348.html

通過 落格博客

如非聲明,本人所著文章均為原創手打,轉載請註明本頁面鏈接和我的名字。

1 評論

發表評論

您的電子郵件地址不會被公開. 必填字段標 *