小编Kor*_*van的帖子

寻找最长前缀的算法

我有两张桌子。

第一个是带前缀的表

code name price
343  ek1   10
3435 nt     4
3432 ek2    2
Run Code Online (Sandbox Code Playgroud)

二是带有电话号码的通话记录

number        time
834353212     10
834321242     20
834312345     30
Run Code Online (Sandbox Code Playgroud)

我需要编写一个脚本,从每条记录的前缀中找到最长的前缀,并将所有这些数据写入第三个表,如下所示:

 number        code   ....
 834353212     3435
 834321242     3432
 834312345     343
Run Code Online (Sandbox Code Playgroud)

对于数字 834353212,我们必须修剪 '8',然后从前缀表中找到最长的代码,即 3435。
我们必须始终先删除 '8',并且前缀必须在开头。

我很久以前以非常糟糕的方式解决了这个任务。它是糟糕的 perl 脚本,它对每条记录进行大量查询。这个脚本:

  1. 从调用表中取一个数字,在循环中从 length(number) 到 1 => $prefix 做子串

  2. 执行查询: select count(*) from prefixes where code like '$prefix'

  3. 如果计数> 0,则取第一个前缀并写入表

第一个问题是查询计数 - 它是call_records * length(number). 第二个问题是LIKE表达。恐怕那些很慢。

我试图通过以下方式解决第二个问题:

CREATE EXTENSION pg_trgm;
CREATE INDEX prefix_idx ON prefix USING …
Run Code Online (Sandbox Code Playgroud)

postgresql performance pattern-matching postgresql-9.1 query-performance

11
推荐指数
1
解决办法
8904
查看次数