2 posts tagged with "algo"

表连接算法概览

November 6, 2023 · 5 min read

一般连接

形式语言与 SQL

连接两个表

R \bowtie_\theta S

select *
from R, S
where theta

select *
from R
join S on theta

连接多个表

\Large \bowtie_\theta \normalsize(R_1, R_2, \cdots, R_n)

select *
from R1, R2, ... Rn
where theta

R_1 \bowtie_{\theta_2} R_2 \cdots \bowtie_{\theta_{n}} R_n

select *
from R1
join R2 on theta2
...
join Rn on thetan

\theta=\bigwedge_{i=2}^n\theta_i

Nested Loop Join

对于一般情况，多重循环是最朴素的算法

for r in R.tuples():
    for s in S.tuples():
        if predicate(r, s):
            yield join(r, s)

可以通过分块遍历降低 IO 的性能损失

for rb in R.blocks():
    for sb in S.blocks():
        for r in rb:
            for s in sb:
                if predicate(r, s):
                    yield join(r, s)

等值连接

形式语言与 SQL

一种常见的连接是等值连接

关于一个属性的等值连接

R(id, \cdots), S(id, \cdots)\\ R \bowtie_{R.id=S.id} S

select *
from R, S
where R.id = S.id

select *
from R
join S on R.id = S.id

select *
from R
join S using (id)

select *
from R
natural join S

关于多个属性的等值连接

R(id1, id2, \cdots), S(id1, id2, \cdots)\\ R \bowtie_{R.id1=S.id1 \land R.id2=S.id2 \land \cdots} S

select *
from R, S
where R.id1 = S.id1 and R.id2 = S.id2 and ...

select *
from R
join S on R.id1 = S.id1 and R.id2 = S.id2 and ...

select *
from R
join S using (id1, id2, ...)

select *
from R
natural join S

涉及等值查询问题，呼之欲出的就是两种方法：

排序方法
哈希方法

这两种方法在关联容器（即有序和无序的 set 和 dict）的构造中相当有用，在表连接中也是如此。

如果其中一个关系在连接键上有索引，则可以直接采取 Index Nested Loop Join，否则则需要进行下面两种额外的工作。

Sort-Merge Join

对 $R$ 和 $S$ 按照等值连接所需键排序，随后分别遍历两个关系；当遇到左右等值时，将等值的区间取出求笛卡尔积。

import functools
import itertools


def join(p):
    r, s = p
    return *r, *s


def smj(R, S, cmp):
    R.sort(key=functools.cmp_to_key(cmp))
    S.sort(key=functools.cmp_to_key(cmp))
    ri = iter(R)
    si = iter(S)
    r = next(ri, None)
    s = next(si, None)
    while True:
        if r is None or s is None:
            return
        while (c := cmp(r, s)) != 0:
            if c < 0:
                if (r := next(ri, None)) is None:
                    return
            else:
                if (s := next(si, None)) is None:
                    return

        rc = [r]
        sc = [s]

        while (r := next(ri, None)) is not None and cmp(rc[0], r) == 0:
            rc.append(r)

        while (s := next(si, None)) is not None and cmp(sc[0], s) == 0:
            sc.append(s)

        yield from map(join, itertools.product(rc, sc))

如果连接的键是唯一的，则可以更进一步省去笛卡尔积的部分：

def join(r, s):
    return *r, *s


def smj(R, S, cmp):
    ri = iter(R)
    si = iter(S)
    while True:
        if (r := next(ri, None)) is None or (s := next(si, None)) is None:
            return
        while (c := cmp(r, s)) != 0:
            if c < 0:
                if (r := next(ri, None)) is None:
                    return
            else:
                if (s := next(si, None)) is None:
                    return

        yield join(r, s)

如果不想编写笛卡尔积的代码，又需要考虑到键不唯一的情况，可以考虑使用迭代器标记恢复之前的过程，但需要谨慎处理其中的边界条件：

struct iterator {
    int *p = nullptr, *q = nullptr;
    operator bool() const {
        return p < q;
    }
    int operator*() const {
        return *p;
    }
    iterator& operator++() {
        ++p;
        return *this;
    }
};

void smj(iterator r, iterator s) {
    iterator mark;
    while (r and s) {
        if (!mark) {
            while (*r != *s) {
                if (*r < *s) {
                    ++r; 
                    if (!r) return;
                } else {
                    ++s;
                    if (!s) return;
                }
            }
            mark = s;
        }
        if (*r == *s) {
            emit(*r, *s);
            ++s;
            if (s) {
                continue;
            }
        } 
        s = mark;
        ++r;
        mark = {};
    }
}

Hash Join

用等值连接所需的键的哈希值建立 $R$ 的哈希表，再用 $S$ 等值连接的键去查询这个哈希表，得到的相同的行进行连接。

def join(r, s):
    return *r, *s


def hj(R, S, hsh, eq):
    build = {}
    for s in S:
        build.setdefault(hsh(s), []).append(s)
    for r in R:
        for s in build.get(hsh(r), []):
            if eq(r, s):
                yield join(r, s)

光线—三角形相交算法

July 3, 2023 · 3 min read

背景

在图形学编程中，经常需要求玩家准心对准的物体。该问题可转化为求与玩家视线相交且离玩家最近的三角形面片所对应的物体。因此需要一种光线-三角形相交算法来求出视线是否与某三角形相交、若相交，距离又是多少。下面介绍一种简单的基于参数和矩阵求解的算法。

原理

已知三角形的三个顶点 $\pmb v_0,\pmb v_1,\pmb v_2$ ，可以给出三角形内点的参数方程：

\pmb h=\pmb v_0+\alpha(\pmb v_1- \pmb v_0)+\beta(\pmb v_2- \pmb v_0)

其中参数 $\alpha,\beta$ 满足下面的条件：

\alpha\ge0,\beta\ge0,\alpha+\beta\le1

令

\pmb e_1=\pmb v_1-\pmb v_0\\ \pmb e_2=\pmb v_2-\pmb v_0\\

则可简记为：

\pmb h=\pmb v_0+\alpha\pmb e_1+\beta\pmb e_2

玩家从 $\pmb p$ 点往 $\pmb r$ 方向看去，与三角形所在平面的交点为 $\pmb h$ 的参数方程：

\pmb h=\pmb p+t\pmb r

其中参数 $t$ 满足：

t\ge0

如图所示：

联立两个方程

\pmb v_0+\alpha\pmb e_1+\beta\pmb e_2=\pmb p+t\pmb r

移项

\alpha\pmb e_1+\beta\pmb e_2-t\pmb r=\pmb p-\pmb v_0

即

(\pmb e_1,\pmb e_2,-\pmb r) \left(\begin{array}{r} \alpha\\ \beta\\ t\\ \end{array}\right)=\pmb p-\pmb v_0

记

\pmb A=(\pmb e_1,\pmb e_2,-\pmb r)\\ \pmb x=\left(\begin{array}{r} \alpha\\ \beta\\ t\\ \end{array}\right)\\ \pmb b=\pmb p-\pmb v_0

也就是说

\pmb A\pmb x=\pmb b

根据克拉默法则

x_j=\dfrac{\det \pmb A_j(\pmb b)}{\det \pmb A}

得

\begin{array}{lll} \alpha&=&\dfrac{\det(\pmb b,\pmb e_2,-\pmb r)}{\det(\pmb e_1,\pmb e_2,-\pmb r)}\\ \beta&=&\dfrac{\det(\pmb e_1,\pmb b,-\pmb r)}{\det(\pmb e_1,\pmb e_2,-\pmb r)}\\ t&=&\dfrac{\det(\pmb e_1,\pmb e_2,\pmb b)}{\det(\pmb e_1,\pmb e_2,-\pmb r)} \end{array}

如果计算得出的参数在其限制范围内，则可以认为玩家的视线与三角形相交。解出的参数 $t$ 即为三角形面片与玩家的距离。

实现

该实现使用了 GLM 库。这里构造的矩阵实际上是所需矩阵的转置，但由于 $\det A^T=\det A$ ，因此不影响结果。

函数返回 -1 表示光线与三角形不相交，返回非负数表示三角形面片与玩家的距离。

#include <glm/glm.hpp>

float raytrace(glm::vec3 v0, glm::vec3 v1, glm::vec3 v2, glm::vec3 p, glm::vec3 r) {
    glm::vec3 e1 = v1 - v0;
    glm::vec3 e2 = v2 - v0;
    glm::vec3 b = p - v0;
    float den = glm::determinant(glm::mat3(e1, e2, -r));
    if (den == 0) return -1;
    float nom_u = glm::determinant(glm::mat3(b, e2, -r));
    float nom_v = glm::determinant(glm::mat3(e1, b, -r));
    float nom_t = glm::determinant(glm::mat3(e1, e2, b));
    float u = nom_u / den;
    float v = nom_v / den;
    float t = nom_t / den;
    if (u >= 0.0 && v >= 0.0 && u + v <= 1.0 && t >= 0) {
        return t;
    }
    return -1;
}

一般连接​

形式语言与 SQL​

Nested Loop Join​

等值连接​

形式语言与 SQL​

Sort-Merge Join​

Hash Join​

背景​

原理​

实现​

一般连接

形式语言与 SQL

Nested Loop Join

等值连接

形式语言与 SQL

Sort-Merge Join

Hash Join

背景

原理

实现