用SQL高性能解决字符串的连续匹配

高性能解决有序集合的连续匹配问题

场景:

A集合有8个元素:ali、boy、c、dog、e、f、g、h,

B集合有5个元素:boy、c、dog、e、h

问B中是否包含连续4个以上的A集合元素?是即符合要求。

查阅网络资料甚至咨询论坛、技术群里的朋友,尽管方法各异,本质上还是循环遍历,最多考虑了利用bitmap提升下循环匹配性能。

难点:连续4个以上的计算与匹配

不论是集合还是字符串,4个连续的判断与匹配基本都依赖循环遍历算法,不论是KMP还是Boyer-Moore算法,如果一行记录都需要这么复杂的循环才能得出,那对千万级甚至亿级的数据时的性能?

绝对原创的独特解法

《SQL沉思录》一书明确指出,循环是过程化的思维方式,数据集是集合思维方式,就不用能集合思维也就是sql的方式高效解决问题?

但没有现成轮子的时候,那只有自己发明轮子。

连续4个,试试分区函数的滑动分窗?当原、现尺码都高效拆分出连续4个后,匹配就是一个简单的join关联问题。

思路

1、滑动分窗求出连续4个元素

2、两表关联,能关联到即为合格

实现代码

1、构造2张测试表

2、构造连续4个元素集合

3、匹配

本文来自企鹅号 - 全球大搜罗媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏F_Alex

数据结构与算法(一)-初识

前言:一个程序员前期可能需要各种业务和编程的能力,但是后期如果想要提高就需要有一个扎实的基础,厚积薄发,所以最近抽空学了下数据结构与算法,颇有感触,学习过程虽然...

12320
来自专栏一个会写诗的程序员的博客

用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

17140
来自专栏程序员互动联盟

【答疑解惑】失之毫厘谬以千里

1、scanf使用陷阱 ? ? 如果scanf中%d是连着写的如“%d%d”,在输入数据时,数据之间不可以加逗号,只能是空格或tab键或者回车键“1 2” 或 ...

30970
来自专栏take time, save time

你所能用到的数据结构(二)

      周末开始更新了,首先感谢各位对我写的东西还能保持兴趣,先回答几个留言中的一个问题和我对无损编码那一节的一个留言的一个看法,第一个是推荐算法书,首先,...

31960
来自专栏落影的专栏

程序员进阶之算法练习(二十八)

前言 四道题,分别锻炼哈希、贪心、贪心+排序、二分四个能力。 第一题较为简单,后续的题目都需要一定的基础。 贪心是最基础的能力,codeforce有专门的 ...

46690
来自专栏Albert陈凯

MapReduce编程思想通俗理解

综述 Map(映射)与Reduce(化简)来源于LISP和其他函数式编程语言中的古老的映射和化简操作,MapReduce操作数据的最小单位是一个键值对。用户在使...

31880
来自专栏懒人开发

(6.4)James Stewart Calculus 5th Edition:Work

牛顿第二定律: F = ma (这里 dv = ds/dt, da=dv/dt) 于是有

11020
来自专栏数据结构与算法

1026 逃跑的拉尔夫

1026 逃跑的拉尔夫 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 年轻的...

38480
来自专栏数据结构与算法

Day2上午解题报告

预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

45840
来自专栏C语言及其他语言

[每日一题]最多约数问题(1228)

本次的题目正确率可是低到了一个境界呢!快来试试吧! 题目描述 正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如,1,2, 5...

40060

扫码关注云+社区

领取腾讯云代金券