1
cy18 2023-09-05 21:51:03 +08:00 1
先 O(n^2)建个字典树,再做 n 次 O(n)的查询,总计 O(n^2),不知道有没有其他更快或者更简单的办法。
|
2
blueboyggh OP @cy18 虽然看不懂,但还是谢谢
|
3
ladypxy 2023-09-05 22:05:00 +08:00
这是要做关键词过滤/审核?
|
4
xuanbg 2023-09-05 22:11:54 +08:00 1
字符串转成字符的集合,取交集。
|
5
cdwyd 2023-09-05 22:11:59 +08:00
才几千个,循环完全扛得住。除非你对比的字符串长度不是你举例的长度
|
6
cy18 2023-09-05 22:16:32 +08:00 1
接收 O(n^3)的话,用 set 实现估计 10 行以内代码就能搞定。
搜了下有个现成的库 https://pygtrie.readthedocs.io/en/latest/,先把第一个字符串的按照起始位置生成 n 个字符串全塞到字典树里,再用对第二个字符串用 longest_prefix 函数做 n 次查询就搞定了。 |
7
blueboyggh OP @cdwyd 确实不是举例的长度,字符串字数可能一百多字,甚至更多
|
8
blueboyggh OP @ladypxy 没必要什么都往这上面想吧
|
9
ClericPy 2023-09-05 22:27:47 +08:00 1
使用 Python 提取两个字符串中长度超过 4 个字符的公共子串. 问了俩 gpt 类的答案都是遍历.
先抄答案实现一个试试, 性能不够再考虑 KMP 或者 trie 树优化, 还有那种带缓存的递归优化优化 |
10
em70 2023-09-05 22:30:23 +08:00 1
最长公共子序列( Longest Common Subsequence ,简称 LCS )是一种常见的字符串匹配问题,可以用动态规划来解决。下面是 Python 中求解最长公共子序列的示例代码:
```python def longest_common_subsequence(str1, str2): m = len(str1) n = len(str2) # 创建一个二维数组来存储最长公共子序列的长度 dp = [[0] * (n + 1) for _ in range(m + 1)] # 填充 dp 数组 for i in range(1, m + 1): for j in range(1, n + 1): if str1[i - 1] == str2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 从 dp 数组中恢复最长公共子序列 i, j = m, n lcs = [] while i > 0 and j > 0: if str1[i - 1] == str2[j - 1]: lcs.append(str1[i - 1]) i -= 1 j -= 1 elif dp[i - 1][j] > dp[i][j - 1]: i -= 1 else: j -= 1 return ''.join(reversed(lcs)) # 测试示例 str1 = "ABCBDAB" str2 = "BDCAB" result = longest_common_subsequence(str1, str2) print("最长公共子序列:", result) ``` 这段代码中,`longest_common_subsequence` 函数接受两个字符串 `str1` 和 `str2`,并返回它们的最长公共子序列。动态规划的核心思想是创建一个二维数组 `dp`,其中 `dp[i][j]` 表示 `str1` 的前 `i` 个字符和 `str2` 的前 `j` 个字符的最长公共子序列的长度。然后,通过填充这个数组,最终可以从 `dp` 数组中找到最长公共子序列。 在示例中,最长公共子序列为 "BCAB"。 from chatgpt |
11
NoOneNoBody 2023-09-05 23:18:37 +08:00 1
这个我写过好几个方案,基本没跳出两个思路
这两个思路都是定位一个尾字符向前或向后组 n 个字符,然后再匹配,跟 #6 所说是一样的 1. itertools.accumulate 2. 是 numpy 模拟 pandas.rolling 载入 pandas/numpy 很耗时,但如果项目本身就需要载入的话,用这个比较大量文字数据,倒是很好用 这个用的是向量函数,没什么优化空间,但数据量很大的话,反而有有优势 还有一个想法是 AC 自动机,主要是有些项目一早就预载了 AC 自动机的字典,匹配目标主要也是在字典范围内,没必要再去各个文字语句都拆解一遍,不过这个没有去做,因为这个暂时没有应用场景,前两个已经很快了 |
12
Pipecraft 2023-09-06 00:51:14 +08:00 8
OP 想要的是提取所有长度大于 4 的公共子序列,而上面一些回复说的是最长公共子序列,两个是不同问题。
如果只是执行一次的任务,那可以怎么简单怎么来。 比如,利用正则表达式可以 1 行代码解决。 ```python import re str1 = "我今天特别开心啊,因为今天是个好日子,我中了 500 万彩票。" str2 = "今天不是个好日子,因为邻居中了 500 万彩票,我今天不开心。" result = re.compile(r'([^,.,。]{4,})(?=.*####.*?(?=\1))').findall(str1 + "####" + str2) print(result) # 输出: ['是个好日子', '中了 500 万彩票'] ``` 正则的贪婪匹配,比较契合 OP 这个的问题。 |
13
blueboyggh OP @Pipecraft 十分感谢,再麻烦问一下,如果长度要求不是 4 ,而是 8 ,是不是只把正则代码里的 4 改成 8 就行了?
|
14
flyqie 2023-09-06 07:17:29 +08:00 via Android
要求相同部分在原字符串中是连续的,而且长度要达到 4 个字符
你这个提取结果是固定的吗,还是说根据句子动态调整? |
15
blueboyggh OP @flyqie 不太理解您的固定和动态调整的意思?
|
16
flyqie 2023-09-06 07:21:53 +08:00 via Android
|
17
blueboyggh OP @flyqie 我测试了一下,好像不用改#号数量也能用
|
18
Pipecraft 2023-09-06 08:49:14 +08:00 2
@blueboyggh #17 如果长度要求不是 4 ,而是 8 , `{4,}` 改成 `{8,}` 即可。
`####` 是分割两个字符串的,可以换成其他任意字符串。 `[^,.,。]` 可以把其他要排除的标点符号加进去,比如 !?; 等。 正则表达式里的 `?=\1` 改成 `?:\1` 可能性能会更好一点。 后来想了想,有些情况,提取的不完整。 比如 str1 = "我今天特别开心啊,因为今天是个好日子,我中了 500 万彩票。" str2 = "今天不是个好日子,因为邻居中了 500 万彩票,我今天不开心,我也想中 500 万彩票。" 只提取了 '是个好日子', '中了 500 万彩票'。 ‘ 500 万彩票’ 没有提取出来。 要完整的提取,str1, str2 换个位置,再执行一次,然后两个结果取并集就完整了。 ```python import re pattern = re.compile(r'([^,.,。]{4,})(?=.*####.*?(?:\1))') def find_common_subsequences(str1, str2): result1 = pattern.findall(str1 + "####" + str2) result2 = pattern.findall(str2 + "####" + str1) return list(set(result1).union(set(result2))) # TEST str1 = "我今天特别开心啊,因为今天是个好日子,我中了 500 万彩票。" str2 = "今天不是个好日子,因为邻居中了 500 万彩票,我今天不开心,我也想中 500 万彩票。" result = find_common_subsequences(str1, str2) print(result) # 输出: ['是个好日子', ' 500 万彩票', '中了 500 万彩票'] ``` |
19
szdosar 2023-09-06 09:40:09 +08:00 1
试试这个,运行结果是:['是个好日子,', '中了 500', '中了 500 万彩票', '中了 500 ', '是个好日', '中了 500 万', '中了 50', '是个好日子', '中了 5', '中了 500 万彩']
[Finished in 89ms] ``` def find_common_substrings(s1, s2, min_length=4): # 创建一个二维数组,用于存储公共子串的长度 dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)] longest = 0 common_substrings = set() for i in range(1, len(s1) + 1): for j in range(1, len(s2) + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] >= min_length: common_substrings.add(s1[i - dp[i][j]:i]) else: dp[i][j] = 0 return list(common_substrings) # 示例 s1 = "我今天特别开心啊,因为今天是个好日子,我中了 500 万彩票。" s2 = "今天不是个好日子,因为邻居中了 500 万彩票,我今天不开心。" print(find_common_substrings(s1, s2)) ``` |
20
blueboyggh OP @Pipecraft 十分感谢您!祝您中 500 万!
|
21
blueboyggh OP @szdosar 好的,我先用了楼上老哥的代码,先测试,回头再试试您的
|
22
maocat 2023-09-06 09:58:22 +08:00
这种需求以前我会安心写代码,现在我只想扔给 langchain
|
23
ruanimal 2023-09-06 10:12:12 +08:00
用 difflib.SequenceMatcher
|
24
MoYi123 2023-09-06 10:13:39 +08:00
1. 把 A 变成 suffix array, => O(A)
2. 遍历 B[idx :idx+4] ,找出所有的起始 index => O((4 * B) * log(A)) 3 对 A 和 B 都算出 rabin-karp 数组 => O(A+B) 4. 遍历第二步得到的起始 index, 用二分算法 + 第三步的哈希, 确定结束位置 => O( B * log(B)) |
25
qianckjuan 2023-09-06 10:27:18 +08:00
不是 kmp 算法吗
|
26
blueboyggh OP |
27
szdosar 2023-09-06 11:40:37 +08:00
你改一下 min_length=9 ,结果就是
['中了 500 万彩票', '中了 500 万彩'] [Finished in 133ms] 所以是不是这个的原因,长度问题? |
28
blueboyggh OP @szdosar 实际我的长度需求是 8 ,我改成 8 了,也不行,我题目中这个例子是可以的,但是我实际需要用的字符串不行
|
29
blueboyggh OP @szdosar 我发现了,因为我是从 excel 表格里提取的内容,如果内容里有换行符,就会影响判断,即使换行符并不在需要提取的相同文本内,也不行,这是因为换行符会影响字符串提取吗?
|
30
Pipecraft 2023-09-06 13:11:27 +08:00
@blueboyggh #29 建议删除换行符以后,提取。
正则参数加上 multiline flag 可以匹配带换行符的字符串, 但是有换行符可能会匹配不到一些结果。 比如 str1="ABC\nD123" str2="A\nBCD456" 这两个字符串去掉换行符,应该可以匹配 ‘ABCD’,如果不去掉换行符,就匹配不到了。 |
31
szdosar 2023-09-06 13:46:46 +08:00
你把要比较的内容放在两个文本文件中试试:
''' def find_common_substrings(s1, s2, min_length=8): # 创建一个二维数组,用于存储公共子串的长度 dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)] longest = 0 common_substrings = set() for i in range(1, len(s1) + 1): for j in range(1, len(s2) + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] >= min_length: common_substrings.add(s1[i - dp[i][j]:i]) else: dp[i][j] = 0 return list(common_substrings) # 添加一个函数来读取文件内容 def read_file_content(filename): with open(filename, 'r', encoding='utf-8') as file: return file.read() # 使用上面的函数来读取 file1.txt 和 file2.txt 的内容 s1 = read_file_content('file1.txt') s2 = read_file_content('file2.txt') # 使用 find_common_substrings 函数来对比这两个文件的内容 print(find_common_substrings(s1, s2)) ''' |
32
blueboyggh OP @szdosar 主要是我需要对比的数据是上千条的 excel ,一个一个复制到文本文档,效率太低了吧
|
33
szdosar 2023-09-06 14:23:11 +08:00
方法有不是只有一套,对吧?
''' #find_common_substrings_excel #读取 Excel 文件,使用 pandas 库。确保你已经安装了 pandas 和 xlrd 库。可以使用以下命令进行安装:pip install pandas xlrd openpyxl import pandas as pd def find_common_substrings(s1, s2, min_length=4): # 创建一个二维数组,用于存储公共子串的长度 dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)] longest = 0 common_substrings = set() for i in range(1, len(s1) + 1): for j in range(1, len(s2) + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] >= min_length: common_substrings.add(s1[i - dp[i][j]:i]) else: dp[i][j] = 0 return list(common_substrings) # 添加一个函数来读取 Excel 文件的内容 def read_excel_content(filename): # 读取 Excel 文件的第一个工作表 df = pd.read_excel(filename, sheet_name=0) # 获取第一列的内容并将其转换为字符串 return df.iloc[:, 0].astype(str).str.cat(sep=' ') # 使用上面的函数来读取 Excel 文件的内容 s1 = read_excel_content('file1.xlsx') s2 = read_excel_content('file2.xlsx') # 使用 find_common_substrings 函数来对比这两个文件的内容 print(find_common_substrings(s1, s2)) ''' |
34
blueboyggh OP @szdosar 感谢,目前正在测试之前的代码,跑了 3 个小时,跑了 1300 条数据了
|
35
NoOneNoBody 2023-09-06 16:09:23 +08:00
@Pipecraft
正则的表现让我有点失望,本以为正则比循环快,实测不是 不过你写的这个正则很精彩,我留下了,其他地方有用,先谢 @blueboyggh 下面两个是我之前写的,效率还可以 下面两个 if minlen>l: return [] 及相关可以省略,因为我的应用场景有词语,不少是“没必要比较”的,所以直接返回空。如果基本是长句,这个判断反而没必要 ================== def matchSubstrings(s:str, ss:str, minlen:int=2, reverse:bool=False): ''' 按出现先后顺序,寻找 s 中,与 ss 任意子串相同的子串\n 叠加的部分只选首个匹配,例如 638 vs 63/38 -> 只返回 63\n minlen: int 最短匹配长度\n reverse: bool->True 反向,寻找目标为 ss ,参考为 s ''' if reverse: s, ss = ss, s ac = itertools.accumulate l = len(s) if minlen>l: return [] lll, pos = 0, 0 for i in range(l - minlen + 1): sss = [x for x in ac(s[i:])] sss.reverse() ll = len(sss) for j,x in enumerate(sss[:ll - minlen + 1]): if j>ll-lll and i<pos+lll: break if x in ss: lll = len(x) pos = i yield x break ================== 缩进自行处理,基本是遇到冒号结尾的,后面的都向右缩进,没有向左回退的,大概能看懂 1. 说明中的“叠加”情况是比较麻烦的,如果需求不同,写法就不同了 2. 这个主要考虑“顺序”,是全匹配;匹配长度优先是另一种写法,需要 itertools.accumulate(s[::-1])类似,但思路有点区别,参照#6 ;长度优先可以适时 break 只返回“最长匹配” 下面这个是基于 numpy 和 pandas 的,因为是向量函数列操作,所以是全匹配,如果只需要“最长”的话,在某个 yield 后打 break ,或者要在返回结果中再筛选 =================== def rollingByNumpy(s:pd.Series, window): v = np.lib.stride_tricks.as_strided(s, (len(s) - (window - 1), window), (s.values.strides * 2)) return pd.Series(v.tolist(), index=s.index[window - 1:]) def matchSubstrings4(s:str, ss:str, minlen:int=2, reverse:bool=False, whole:bool=True): ''' 按最大匹配长度的顺序,寻找 s 中,与 ss 任意子串相同的子串\n 叠加的部分默认只选首个匹配,例如 638 vs 63/38 -> 只返回 63 ; whole=False 时则全部返回,返回 63 和 38\n minlen: int 最短匹配长度\n reverse: bool->True 反向,寻找目标为 ss ,参考为 s\n 如果之前已经载入 pandas ,此函数略微快些,否则 载入 pandas 耗时较多 ''' if reverse: s, ss = ss, s s1 = ''.join([x for x in ss if x in s]) l = len(s1) if minlen>l: return [] s2 = pd.Series(list(s)) if whole: for w in range(l, minlen-1, -1): ser = rollingByNumpy(s2, w).str.join('') ii = ser.index.min() for i,x in ser.items(): if i<=ii+w: continue if x in ss: ii = i yield x else: for w in range(l, minlen-1, -1): ser = rollingByNumpy(s2, w).str.join('') for x in ser: if x in ss: yield x ================== 缩进自行处理,遇到冒号结尾的,后面的都向右缩进,基本没有向左回退的,大概能看懂 else 那行和 if whole 对应,没有缩进,其他都是向右缩进,回复没缩进会混乱 1. rollingByNumpy 因为用途很广,我好多地方用到,不仅是字符串,所以独立一个函数分开 pandas.rolling 不能用在整数、浮点以外的类型,所以需要用 numpy 模拟 rollingByNumpy 不是原创,是参考 so 的答案改的 2. 我原来的函数是重组一个 dataframe 返回的(也不需要 ss 参数),因为后续根据需求不同(不一定是求子串),可以整个 dataframe 统一用一个函数(这里才使用到 ss)同时处理,没必要逐个处理;这里只是按 op 需求跑了一遍循环 yield 结果 |
36
RuiCBai 2023-09-06 16:27:59 +08:00 via Android
这不就是最长公共子数列嘛 (比最长公共子序列还简单一些)
|
37
KAAAsS 2023-09-06 17:05:12 +08:00
DP+1 ,稍微调整一下 @szdosar 的代码应该就可以改成同一序列取最长的了。时空复杂都是 O(M * N),滚动数组优化的话空间还可以做到 O(2 * min{M, N})。而且从比较次数来看应该比前缀树之类方法要更快。
```python def find_common_substrings(s1, s2, min_length=4): # 创建一个二维数组,用于存储公共子串的长度 s1 += '\0' s2 += '\1' dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)] common_substrings = set() for i in range(1, len(s1) + 1): for j in range(1, len(s2) + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 elif dp[i - 1][j - 1] >= min_length: common_substrings.add(s1[i - dp[i - 1][j - 1] - 1:i - 1]) return list(common_substrings) ``` |
38
szdosar 2023-09-06 19:07:08 +08:00 via iPhone
「 https://drive.google.com/file/d/1-Kv19SR2HITSiWnzs6XzI_JqyqcjpK2w/view?usp=sharing 」
- - - - - - - - - - - - - - - 感谢指点,我也就是半桶水,上面这个链接是源码。 |
39
RedisMasterNode 2023-09-06 19:20:44 +08:00
可以很暴力解决,如果数据量不太大
https://pastebin.com/raw/q3wf0h23 测试例子: >>> str1 = "abcdefgandhahaok" >>> str2 = "acsdefokokhhaha00" >>> find_common_substrings(str1, str2, 3) ['def', 'hah', 'haha', 'aha'] |
40
RedisMasterNode 2023-09-06 19:21:08 +08:00
>>> find_common_substrings(str1, str2, 4)
['haha'] |
41
RedisMasterNode 2023-09-06 19:24:30 +08:00
补充一句刚刚测试了一下大约 2000 字符的对比,其实很快很快,主要看楼主希望达到什么程度,例如最差最差接受 1 秒执行完,那是非常轻松的,如果是真的有 1ms 内处理的需求再考虑其他方案就是了
|
42
SaberJack 2023-09-06 19:35:56 +08:00
动态规划可以解决
def longest_common_substring(s1, s2, min_length=4): m = len(s1) n = len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)] max_length = 0 end_index = 0 for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] > max_length: max_length = dp[i][j] end_index = i else: dp[i][j] = 0 if max_length >= min_length: return s1[end_index - max_length:end_index] else: return "" A = "我今天特别开心啊,因为今天是个好日子,我中了 500 万彩票。" B = "今天不是个好日子,因为邻居中了 500 万彩票,我今天不开心。" print(longest_common_substring(A, B)) |
43
Tstxxy 2023-09-06 19:44:55 +08:00
两个字符串的公共子序列肯定包含楼主要的连续 4 个以上相同字符的序列。
其实只需要在状态表格中加多一个字段,表示已经有连续几个字符相同了。 以上算法的复杂度为 o(mn) 楼主可以先了解公共子序列的算法。 |
44
blueboyggh OP |
45
liuhai233 2023-09-07 11:37:07 +08:00
|
46
szdosar 2023-09-07 11:37:18 +08:00
|
47
NoOneNoBody 2023-09-07 11:37:36 +08:00
|
48
blueboyggh OP |
49
szdosar 2023-09-07 14:15:29 +08:00
不要执着于用迭代操作,我们来分析一下。
##itertools 是一个非常强大的库,它提供了很多用于处理迭代操作的工具。但是,对于特定的问题,直接的算法可能会更加高效。 ##在我们的情境中,我们要找的是两个字符串之间的所有公共子串。使用 itertools 可能会涉及生成所有可能的子串组合,然后再进行比较,这在某些情况下可能会导致不必要的计算。 ##而我们使用的滑动窗口方法是基于以下观察结果的: ##如果两个字符串在某个位置有一个公共字符,那么我们可以尝试扩展这个匹配,直到找到一个公共子串或匹配失败为止。 ##通过这种方式,我们可以立即找到一个公共子串,而不需要生成和比较所有可能的子串组合。 ##因此,对于这个特定的问题,滑动窗口方法可能会比使用 itertools 更加高效。但这并不意味着 itertools 不是一个有用的库。对于其他类型的问题,itertools 可能会提供更简洁、更高效的解决方案。 ##以下使用滑动窗口方法 ##find_common_substrings_huadong 源代码效率可大幅提高: https://pastebin.com/raw/Qfr31L8a |
50
NoOneNoBody 2023-09-07 14:18:27 +08:00
@blueboyggh #48
你是全部用了 #45 的代码吧? 他最后一句是用 next ,这个只返回第一个,改为 list(gg)是全部返回 如果想按长度排序(倒序),用 sorted(gg, key=len, reverse=True) |
51
blueboyggh OP @NoOneNoBody 谢谢,改成 list 就好了,next 是从网上抄的。
|
52
NoOneNoBody 2023-09-07 14:50:13 +08:00
@szdosar #49
滑动思路没有错,只是 window 的尺寸不定,从 min 到 length 都有,离不开每个 window 尺寸轮询 itertools.accumulate 在这里的作用就是自动生成不同 window 尺寸的切片,省了轮询的时间 如果尺寸固定,例如只找连续 4 个字符的匹配,5 个、6 个……都忽略,那用 pandas.series.shift 是对应最简单的思路 可惜 python 没有移动 window 概念,需要手写切片[start:end] 其实 @Pipecraft #12 写的利用正则贪婪匹配的思路是最精彩,虽然实际运行速度不如理想,但我还是忍不住要赞一个 我花了不少时间在这个上面,这个看上去是字符串问题,但实际是队列问题,如果能找到一个非常高效的方法的话,在 pandas 是非常有用的,大数据中快速寻找连续等值的片段用途多得很,所以我才写了个看上去跟字符串无不相干的 pandas 方案 |
53
juny1998 2023-09-07 15:18:57 +08:00
chatGPT 的回答
|
54
juny1998 2023-09-07 15:19:09 +08:00
def extract_common_substrings(str1, str2):
common_substrings = [] for i in range(len(str1)): for j in range(i + 4, len(str1) + 1): substring = str1[i:j] if substring in str2 and len(substring) >= 4: common_substrings.append(substring) return common_substrings # 例子 A = "我今天特别开心啊,因为今天是个好日子,我中了 500 万彩票。" B = "今天不是个好日子,因为邻居中了 500 万彩票,我今天不开心。" common_substrings = extract_common_substrings(A, B) print(common_substrings) |
55
blueboyggh OP @szdosar
@NoOneNoBody 我从我的样本里取了 100 条数据,用三种方法都进行了测试,测试结果: 滑动窗口方法:13 秒完成 itertools 方法:28 秒完成 正则表达式方法:63 秒完成 其中滑动窗口的方法,取出来的样本是最全的,但是结果 list 里一些子元素有相互包含的情况,比如“中了 500 万彩票”和“了 500 万彩票” itertools 方法的结果更加精简,但是依旧有子元素有相互包含的情况 正则表达式方法则是完全没有子元素有相互包含的情况,但是速度也最慢 以上结果可能因为本人代码小白的问题受影响,不代表三种方法的真实水平,或者有其他隐含的坑我没能力发现 |
56
szdosar 2023-09-07 15:31:21 +08:00 1
可以改进的,返回的子串之间有相互包含的情况。我们在添加子串到结果集之前进行检查,可以检查新找到的子串是否包含在结果集中的任何子串中,或者结果集中的任何子串是否包含在新找到的子串中。
fix 源码 https://pastebin.com/raw/6aKqeUrP |
57
Pipecraft 2023-09-07 15:32:38 +08:00
@NoOneNoBody #52 感谢对这个正则的肯定。
正则内部是通用的算法,肯定会比针对特定问题优化的算法速度慢。 所以上面(#12 )回复里说了“如果只是执行一次的任务,那可以怎么简单怎么来。” 如果是反复执行并且数据量很大,那不建议用正则表达式。 #12 层里的代码并不完整,#18 层里的代码更完整,只是速度更慢。 https://pastebin.com/raw/UgzrPbA7 |
58
Pipecraft 2023-09-07 15:39:25 +08:00
@blueboyggh #55 处理多条数据时,正则表达式要使用 compile 后的结果,如果每次都 compile 一次,会很慢。
即不要直接使用 #12 层的代码,使用 #18 层的代码。 当然,我相信上面的测试是这么做的。 |
59
blueboyggh OP @Pipecraft 我的问题,18#的源码我只应用了前后对比两次的逻辑,其他的没用,估计影响了结果,一会儿我修改一下再测试一下试试
|
60
NoOneNoBody 2023-09-07 16:33:17 +08:00 1
呵呵,发现自己有点钻牛角尖了,不追求 yield 和去叠加就没必要再轮询一次,可以少好多行代码
而且 itertools.accumulate 是先生成后比较,概率上无效的肯定更多,比起滑动跳过无效的,工作量更多 嗯,重练一遍 |
61
blueboyggh OP @NoOneNoBody 期待新代码共享
|
62
blueboyggh OP @Pipecraft 使用 18#的代码后,测试 100 条数据时间从 63 秒变成 59 秒,好像变化不多,是不是我的问题?
|
63
blueboyggh OP @szdosar 感谢,测试使用新代码,结果里没有相互包含的子元素了
|
64
NoOneNoBody 2023-09-07 17:20:07 +08:00
@blueboyggh #63
就此题来说,@szdosar #49 帖的代码足够好了,你是用这个测出最短时间的吧? 我现在只是翻翻 more_itertools 有没有可用的东西,如果没有,也就不会写出更高效率的了 https://stackoverflow.com/questions/66668405/python-sliding-windows-of-a-list 这里有个关于 moving window (移动窗口)的例子,感觉也差不多 |
65
blueboyggh OP @NoOneNoBody 好的,确实是#49 的时间最短,感谢
|
66
NoOneNoBody 2023-09-07 18:22:28 +08:00
more_itertools 有个有趣的东西
more_itertools.substrings(iterable) Yield all of the substrings of iterable. >>> [''.join(s) for s in substrings('more')] ['m', 'o', 'r', 'e', 'mo', 'or', 're', 'mor', 'ore', 'more'] 不过也是完全穷举,字符串越长应该效率越低 |
67
Pipecraft 2023-09-07 18:46:16 +08:00
@blueboyggh #62 差不多会那样,毕竟相比匹配用的时间,compile 表达式的时间没有多少。
|
68
NoOneNoBody 2023-09-07 21:29:10 +08:00
@blueboyggh #65
我这边测还是自己写的快 把 l = len(s) 前面重新加上 s = ''.join([x for x in s if x in ss]) 这个看样子是不能省略的,因为这个逻辑是,原 s 所有和 ss 包含的字符连起来,过滤了不能匹配的字符 意味着最大匹配长度不会超过这个新字符串的长度,而且连续匹配的子串也一定在这个新的字符串内 这样会大幅度降低后面的循环次数 range(l - minlen + 1) PS: 用这个分别过滤 s 和 ss 后,正则的方式就快了很多了……我这里测试反而正则变成最快的方法 |
69
NoOneNoBody 2023-09-07 21:46:30 +08:00
@NoOneNoBody #68
秀逗了,长度 len 可以用这个,但匹配不能用这个,逻辑不对 abcdef vs abdf 结果是 ab 过滤后 abdf vs abdf 结果是 abdf 就不正确了 算了,今天到此为止,脑子都打结了,去娱乐一下 |
70
cy18 2023-09-08 12:55:45 +08:00
用 pygtrie 写了个,这库不支持部分前缀的查找,建树比较慢,查找比较快。优化下 trie 库内部的建树或者查找过程的话应该可以再快几个数量级。
import pygtrie def build_tree(str1, min_len=4): tree = pygtrie.CharTrie() for begin in range(len(str1)): for end in range(begin+min_len, len(str1)): tree[str1[begin:end]] = (begin, end) return tree def find_prefixes(tree, str2, min_len=4): result = set() sub_len = 0 # Used to remove unnecessary substrings for start in range(len(str2)): longest_prefix = tree.longest_prefix(str2[start:]) if (longest_prefix.key is not None and len(longest_prefix.key) >= min_len and len(longest_prefix.key) > sub_len): result.add(longest_prefix.key) sub_len = len(longest_prefix.key) sub_len -= 1 return result str1 = "我今天特别开心啊,因为今天是个好日子,我中了 500 万彩票。"*10 str2 = "今天不是个好日子,因为邻居中了 500 万彩票,我今天不开心。"*10 tree = build_tree(str1) result = find_prefixes(tree, str2) print(result) |
71
blueboyggh OP |
72
NoOneNoBody 2023-09-26 11:19:30 +08:00
@blueboyggh #71
10w 条的话 1. 向量化函数 2. 一些机器学习方向的包,#70 那个不知道是不是,这种包都是需要花时间建模,然后应用很快 3. 多进程并发,多线程因为 GIL 没用 前两个需要学习成本,但学会就很有用,可以用到其他工作,不仅是字符串,尤其是大批量的数值计算 并发的话比较快上手,因为单例函数已经存在,建进程池而已,花点时间比较一下其他并发包的 performance ,有不少比原生更快的 |
73
Pipecraft 2023-09-28 09:37:24 +08:00
|