SQL挑战/谜题：给定一个堆栈跟踪 - 如何在每个时间点找到顶部元素？ [英] SQL Challenge/Puzzle: Given a stack trace - How to find the top element at each point in time?
本文介绍了SQL挑战/谜题：给定一个堆栈跟踪 - 如何在每个时间点找到顶部元素？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
- 我的真实生活用例是合并嵌套范围。
我画了一些草图，然后我看到了开始和结束叠加PUSH和POP操作的范围之间的相似之处。我明白解决这个问题也会解决原来的问题。 列实际上可以从问题中删除。当val为NULL时，它是一个POP操作，否则它是一个PUSH操作。
拼图
表格 stack_trace 包含以下列： val - in/push操作插入的值或out/pop操作的NULL值。 目标是在每个时间点（ i ）找到堆叠顶部的值。
例如
（NULL值在这里表示为空格）
data：
i op val
- - -
1 IA
2 IB
3 O
4 IC
5 O
6 O
需要的结果：
i top_of_stack_val
- ----------------
1 A
2 B
3 A
4 C
5 A
6
要求
- 解决方案应该是一个单一的SQL查询（子查询很好）。 仅允许使用以下子句： SELECT ， FROM ， WHERE ， GROUP BY ， HAVING ， ORDER BY 。 WITH 公用表格表达式）不允许。
- 使用T-SQL，PL / SQL等是不允许的。
- 使用UDF用户定义的函数）不允许。
- 不允许使用变量 。
示例数据
create table stack_trace
（
i int
，op char（1）
，val char（1）
）
;
插入到stack_trace（i，op，val）值（1，'I'，'A'）;
插入到stack_trace（i，op，val）值（2，'I'，'B'）;
插入到stack_trace（i，op，val）值（3，'I'，'C'）;
插入到stack_trace（i，op，val）值（4，'I'，'D'）;
插入到stack_trace（i，op，val）值（5，'I'，'E'）;
插入到stack_trace（i，op）的值（6，'O'）;
插入到stack_trace（i，op）的值（7，'O'）;
插入到stack_trace（i，op）的值（8，'O'）;
插入到stack_trace（i，op，val）值（9，'I'，'F'）;
插入到stack_trace（i，op）的值（10，'O'）;
插入到stack_trace（i，op，val）值（11，'I'，'G'）;
插入到stack_trace（i，op，val）值（12，'I'，'H'）;
插入到stack_trace（i，op）的值（13，'O'）;
插入到stack_trace（i，op）的值（14，'O'）;
插入到stack_trace（i，op，val）值（15，'I'，'I'）;
插入到stack_trace（i，op，val）值（16，'I'，'J'）;
插入到stack_trace（i，op，val）值（17，'I'，'K'）;
插入到stack_trace（i，op，val）值（18，'I'，'L'）;
插入到stack_trace（i，op，val）值（19，'I'，'M'）;
插入到stack_trace（i，op）的值（20，'O'）;
插入到stack_trace（i，op，val）值（21，'I'，'N'）;
插入到stack_trace（i，op）的值（22，'O'）;
插入到stack_trace（i，op，val）值（23，'I'，'O'）;
插入到stack_trace（i，op）的值（24，'O'）;
插入到stack_trace（i，op，val）值（25，'I'，'P'）;
插入到stack_trace（i，op）的值（26，'O'）;
插入到stack_trace（i，op）的值（27，'O'）;
插入到stack_trace（i，op，val）值（28，'I'，'Q'）;
插入到stack_trace（i，op，val）值（29，'I'，'R'）;
插入到stack_trace（i，op）的值（30，'O'）;
插入到stack_trace（i，op）的值（31，'O'）;
插入到stack_trace（i，op）的值（32，'O'）;
插入到stack_trace（i，op）值（33，'O'）;
插入到stack_trace（i，op）的值（34，'O'）;
插入到stack_trace（i，op）的值（35，'O'）;
插入到stack_trace（i，op，val）值（36，'I'，'S'）;
插入到stack_trace（i，op）值（37，'O'）;
插入到stack_trace（i，op）的值（38，'O'）;
插入到stack_trace（i，op，val）值（39，'I'，'T'）;
插入到stack_trace（i，op，val）值（40，'I'，'U'）;
插入到stack_trace（i，op）的值（41，'O'）;
插入到stack_trace（i，op，val）值（42，'I'，'V'）;
插入到stack_trace（i，op，val）值（43，'I'，'W'）;
插入到stack_trace（i，op，val）值（44，'I'，'X'）;
插入到stack_trace（i，op）的值（45，'O'）;
插入到stack_trace（i，op）的值（46，'O'）;
插入到stack_trace（i，op，val）值（47，'I'，'Y'）;
插入到stack_trace（i，op）的值（48，'O'）;
插入到stack_trace（i，op）的值（49，'O'）;
插入到stack_trace（i，op，val）值（50，'I'，'Z'）;
插入到stack_trace（i，op）的值（51，'O'）;
插入到stack_trace（i，op）的值（52，'O'）;
所需结果
i top_of_stack_val
- ----------------
1 A
2 B
3 C
4 D
5 E
6 D
7 C
8 B
9 F
10 B
11 G
12 H
13 G
14 B
15 I
16 J
17 K
18 L
19 M
20 L
21 N
22 L
23 O
24 L
25 P
26 L
27 K
28 Q
29 R
30 Q
31 K
32 J
33 I
34 B
35 A
36 S
37 A
38
39 T
40 U
41 T
42 V
43 W
44 X
45 W
46 V
47 Y
48 V
49 T
50 Z
51 T
52
解决方案个人而言，我怀疑你最终会发现SQL，你可以在所有的SQL Server中使用Teradata ，Postgres和Oracle，并且如果表大小可以接受。
SQL Server解决方案（<一个href =http://rextester.com/SMW81388 =nofollow> demo ）如下所示：
SELECT i，
SUBSTRING（MAX（FORMAT（i，'D10'）+ val）OVER（由POS $ ORDER BY BY
ROWS UNBOUNDED PRECEDING），$ 11 $ b FROM（SELECT st。*，
sum（CASE WHEN op ='I'then 1 ELSE -1 END）
OVER（ORDER BY i ROWS UNBOUNDED PRECEDING）as pos
FROM stack_trace st ）t1
ORDER BY i;
- My real life use-case was to merge nested ranges. I've drew some sketches and then I saw the resemblance between ranges starting and ending to stack PUSH and POP operations. I understood that solving this problem will also solve the original problem.
- The op column can actually be removed from the question. When val is NULL then it is a POP operation otherwise it is a PUSH operation.
The Puzzle
A table, stack_trace ,contains the following columns:
- i - Integer value that represents a point in time.
- op - 2 possible operations: I ("in"/"push") and O ("out"/"pop").
val - The value inserted by the "in"/"push" operation or NULL for "out"/"pop" operation.
The goal is to find what was the value at the top of the stack, at each point in time (i).
e.g.
(NULL values are represented here as empty spaces)
data:
i op val
-- -- --
1 I A
2 I B
3 O
4 I C
5 O
6 O
required result:
i top_of_stack_val
-- ----------------
1 A
2 B
3 A
4 C
5 A
6
Requirements
- The solution should be a single SQL query (sub-queries are fine).
- Only the following clauses are allowed: SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY.
- The use of WITH clause (CTE - Common Table Expression) is not allowed.
- The use of T-SQL, PL/SQL etc. is not allowed.
- The use of UDF (User Defined Functions) is not allowed.
- The use of variables is not allowed.
Sample data
create table stack_trace
(
i int
,op char(1)
,val char(1)
)
;
insert into stack_trace (i,op,val) values (1,'I','A');
insert into stack_trace (i,op,val) values (2,'I','B');
insert into stack_trace (i,op,val) values (3,'I','C');
insert into stack_trace (i,op,val) values (4,'I','D');
insert into stack_trace (i,op,val) values (5,'I','E');
insert into stack_trace (i,op) values (6,'O');
insert into stack_trace (i,op) values (7,'O');
insert into stack_trace (i,op) values (8,'O');
insert into stack_trace (i,op,val) values (9,'I','F');
insert into stack_trace (i,op) values (10,'O');
insert into stack_trace (i,op,val) values (11,'I','G');
insert into stack_trace (i,op,val) values (12,'I','H');
insert into stack_trace (i,op) values (13,'O');
insert into stack_trace (i,op) values (14,'O');
insert into stack_trace (i,op,val) values (15,'I','I');
insert into stack_trace (i,op,val) values (16,'I','J');
insert into stack_trace (i,op,val) values (17,'I','K');
insert into stack_trace (i,op,val) values (18,'I','L');
insert into stack_trace (i,op,val) values (19,'I','M');
insert into stack_trace (i,op) values (20,'O');
insert into stack_trace (i,op,val) values (21,'I','N');
insert into stack_trace (i,op) values (22,'O');
insert into stack_trace (i,op,val) values (23,'I','O');
insert into stack_trace (i,op) values (24,'O');
insert into stack_trace (i,op,val) values (25,'I','P');
insert into stack_trace (i,op) values (26,'O');
insert into stack_trace (i,op) values (27,'O');
insert into stack_trace (i,op,val) values (28,'I','Q');
insert into stack_trace (i,op,val) values (29,'I','R');
insert into stack_trace (i,op) values (30,'O');
insert into stack_trace (i,op) values (31,'O');
insert into stack_trace (i,op) values (32,'O');
insert into stack_trace (i,op) values (33,'O');
insert into stack_trace (i,op) values (34,'O');
insert into stack_trace (i,op) values (35,'O');
insert into stack_trace (i,op,val) values (36,'I','S');
insert into stack_trace (i,op) values (37,'O');
insert into stack_trace (i,op) values (38,'O');
insert into stack_trace (i,op,val) values (39,'I','T');
insert into stack_trace (i,op,val) values (40,'I','U');
insert into stack_trace (i,op) values (41,'O');
insert into stack_trace (i,op,val) values (42,'I','V');
insert into stack_trace (i,op,val) values (43,'I','W');
insert into stack_trace (i,op,val) values (44,'I','X');
insert into stack_trace (i,op) values (45,'O');
insert into stack_trace (i,op) values (46,'O');
insert into stack_trace (i,op,val) values (47,'I','Y');
insert into stack_trace (i,op) values (48,'O');
insert into stack_trace (i,op) values (49,'O');
insert into stack_trace (i,op,val) values (50,'I','Z');
insert into stack_trace (i,op) values (51,'O');
insert into stack_trace (i,op) values (52,'O');
Required results
i top_of_stack_val
-- ----------------
1 A
2 B
3 C
4 D
5 E
6 D
7 C
8 B
9 F
10 B
11 G
12 H
13 G
14 B
15 I
16 J
17 K
18 L
19 M
20 L
21 N
22 L
23 O
24 L
25 P
26 L
27 K
28 Q
29 R
30 Q
31 K
32 J
33 I
34 B
35 A
36 S
37 A
38
39 T
40 U
41 T
42 V
43 W
44 X
45 W
46 V
47 Y
48 V
49 T
50 Z
51 T
52
解决方案
Personally I doubt that you will end up finding SQL that you can just use in all of SQL Server, Teradata, Postgres, and Oracle and that has acceptable performance if the table is at all large.
A SQL Server solution (demo) would be as follows
SELECT i,
SUBSTRING(MAX(FORMAT(i, 'D10') + val) OVER (PARTITION BY Pos ORDER BY i
ROWS UNBOUNDED PRECEDING), 11, 8000)
FROM (SELECT st.*,
sum(CASE WHEN op = 'I' THEN 1 ELSE -1 END)
OVER (ORDER BY i ROWS UNBOUNDED PRECEDING) AS pos
FROM stack_trace st) t1
ORDER BY i;
这篇关于SQL挑战/谜题：给定一个堆栈跟踪 - 如何在每个时间点找到顶部元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
