一個簡單算法的效率優化

自由踐行 發佈 2022-12-06T18:21:38.953816+00:00

今天在解決問題的時候遇到這樣一個需求,類似這樣的字符串:data:[{[A,[C]X],[B]X}[C]X{[A]X,[B]X}]XX我需要把data:後面[...]中的嵌套內容提取出來。最初是用正則,由於限定了起始和結尾字符,所以實現 起來很容易:很容易就匹配上了。

今天在解決問題的時候遇到這樣一個需求,類似這樣的字符串:

data:[{[A,[C]X],[B]X}[C]X{[A]X,[B]X}]XX

我需要把data:後面[...]中的嵌套內容提取出來。

最初是用正則,由於限定了起始和結尾字符,所以實現 起來很容易:

很容易就匹配上了。

可是後來,結尾的字符變了,而且變成了動態可變的,比如這種:

data:[{[A,[C]X],[B]X}[C]X{[A]X,[B]X}]X

再用正則匹配就只能匹配到部分字符

無法滿足需求。

我沒學過公式解析那種高級的算法,只能用笨法實現。思路如下:

  • 根據begin設置的字符,每找到一個深度+1;
  • 根據end設置的字符,每找到一個深度-1;
  • 最後如果深度為0,說明提取完成;

代碼用python實現:

調用代碼:

data_content = site.detach(data_content, '[', ']')

結果能夠正確提取。

但問題是,一旦data_content字符很大,比如幾百KB的長度,提取時間就很長,測試一次足足用了4分12秒之巨,我甚至一度認為是死循環了。

這太誇張了,於是著手優化。

最初我懷疑是Python效率低,因為我一直對Python沒有好印象,就感覺出了什麼么蛾子都是它乾的似的。所以兄弟們,第一印象很重要,以後千萬別在評論區給人留差評了:)

於是我吭哧吭哧改成了C#代碼測試:

代碼看著舒服多了。並且我還增加了對字母和數字的跳過判斷。結果運行完一看時間,4分14秒,非但沒減少,還增加了,真是啪啪打臉。看來是錯怪Python兄弟了。

按說這個量級的循環數量不可能這麼慢,檢查代碼,唯一導致數據處理慢的地方就是字符串拼接的處理。都說stringbuilder比string效率高很多,於是我再次進行了優化:

果然可以,秒出!

可問題是python里沒有stringbuilder,我也沒找到類似可替代的函數。不過既然問題找到了,那就想辦法解決唄,沒有條件就創造條件。

其實仔細思考一下,解決這個問題的關鍵在於找到了最後一個]與起始[對應的位置,效率慢在字符串拼接,那中間過程就可以省略了。只需要先找到位置,找到位置就結束循環,根據位置再提取一次就好。

於是再次修改代碼如下:

代碼精簡了,結果一樣秒出:

完美解決:)

兄弟們,技術是手段,思路才是根本。如有更好的想法可以評論區留言。

關鍵字: