eleven26

jenssegers mongodb 记录查询语句

Posted on 2020-02-12 Edited on 2020-12-08

机制：

jenssegers mongodb 是否记录查询语句依赖于 \Illuminate\Database\Connection 里面的 loggingQueries 属性是否为 true，而这个属性可以使用 DB::connection('xx')->enableQueryLog() 来设置，我们调用了这个方法之后，该扩展包底层会 fire 一个 \Illuminate\Database\Events\QueryExecuted 事件，所以如果我们想把查询语句记录到日志文件，可以考虑，监听这个事件，然后在回调里面写入日志。

\Jenssegers\Mongodb\Collection

/**
 * Handle dynamic method calls.
 *
 * @param  string $method
 * @param  array $parameters
 * @return mixed
 */
public function __call($method, $parameters)
{
    $start = microtime(true);
    $result = call_user_func_array([$this->collection, $method], $parameters);

    if ($this->connection->logging()) {
        // Once we have run the query we will calculate the time that it took to run and
        // then log the query, bindings, and execution time so we will report them on
        // the event that the developer needs them. We'll log time in milliseconds.
        $time = $this->connection->getElapsedTime($start);

        $query = [];

        // Convert the query parameters to a json string.
        array_walk_recursive($parameters, function (&$item, $key) {
            if ($item instanceof ObjectID) {
                $item = (string) $item;
            }
        });

        // Convert the query parameters to a json string.
        foreach ($parameters as $parameter) {
            try {
                $query[] = json_encode($parameter);
            } catch (Exception $e) {
                $query[] = '{...}';
            }
        }

        $queryString = $this->collection->getCollectionName() . '.' . $method . '(' . implode(',', $query) . ')';

        $this->connection->logQuery($queryString, [], $time);
    }

    return $result;
}

启用查询 log

1
2
3

DB::connection('yy')->enableQueryLog();
$model = app(xx::class);
$model->limit(10)->get();

监听事件

在哪里写这个可以参考官方文档，这里只展示具体代码：

1
2
3

\DB::listen(function (QueryExecuted $sql) use ($logSql) {
    \Log::info('time: ' . $sql->time . '  ' . $sql->sql);
});

C 结构体传参

Posted on 2020-01-15 Edited on 2020-12-08

我们知道，在 C 中，函数参数传递只有两种方式，值传递、引用传递。

值传递的时候，会把对应的值复制一份传到函数中，形参和原变量是不同的两个变量，而引用传递只是把原变量的地址传递给形参，形参根据这个地址拿到对应的变量。

引用传递的时候，我们需要通过解引用 (*xxx) 的方式拿到变量，这个时候我们就拿到了原始变量，我们在函数中所有针对该变量的操作都是针对原始变量的操作，因为它们是同一个变量。

那这个规则对结构体变量来说是否还适用呢？

#include <stdio.h>

typedef struct User {
    char *name;
    int age;
} User;

void test1(User user)
{
    user.name = "name1";
    printf("test1: user address = %p\n", (void*)&user);      // 0x7ffee7aae760
    printf("test1: name address = %p\n", (void*)&user.name); // 0x7ffee7aae760
}

void test2(User *user)
{
    user->name = "name2";
    printf("test2: user address = %p\n", (void*)&user);       // 0x7ffee7aae768 (这个是参数变量的地址)
    printf("test2: name address = %p\n", (void*)&user->name); // 0x7ffee7aae798
}

int main()
{
    User user = {.age = 23, .name = "name"};
    printf("origin: user address = %p\n", (void*)&user);      // 0x7ffee7aae798
    printf("origin: name address = %p\n", (void*)&user.name); // 0x7ffee7aae798 (因为 name 是结构体的第一个成员，所以和结构体的地址一样)

    test1(user);
    printf("test1: user.name = %s\n", user.name);             // name

    test2(&user);
    printf("test2: user.name = %s\n", user.name);             // name2

    return 0;
}

输出：

origin: user address = 0x7ffee7aae798
origin: name address = 0x7ffee7aae798
test1: user address = 0x7ffee7aae760
test1: name address = 0x7ffee7aae760
test1: user.name = name
test2: user address = 0x7ffee7aae768
test2: name address = 0x7ffee7aae798  // 和原始 user 的地址一致
test2: user.name = name2

有人会发现 printf("test2: user address = %p\n", (void*)&user); 输出的地址并不是原始 user 的地址，这是为什么呢？

其实实际上 void test2(User *user) test2(&user); 这两句还是值传递，只是传递的值是一个指针的地址。而上面的打印 &user 的地址实际上是打印保存这个指针地址变量的地址，听起来有点拗口，但实际上就是这样，我们在 test2 内拿到了一个地址，我们会根据这个地址拿到原始的变量。

如何证实这一点呢？

在 test2 里面加上这一行，获取解引用后的 user 的地址，发现指向是原始 user 的地址。

1	printf("test2: user address = %p\n", (void)&(user)); // 0x7ffee7aae798

结论：值传递、引用传递的规则对于结构体变量传参同样适用。

双向链表

Posted on 2020-01-08 Edited on 2022-06-15

我们在单链表中，有了 next 指针，这就使得我们要查找下一节点的时间复杂度为 O(1)。可是如果我们要查找的是上一节点的话，那最坏的时间复杂度就是 O(n) 了，因为我们每次都要从头开始遍历查找。

为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。

双向链表（double linked list）是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。所以在双向链表中的节点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

// 线性表的双向链表存储结构
typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior; // 直接前驱指针
    struct DulNode *next;  // 直接后继指针
} DulNode, *DuLinkList;

既然单链表也可以有循环链表，那么双向链表当然也可以是循环链表。

双向链表的循环带头节点的空链表如下图所示：

非空的循环的带头节点的双向链表如下所示：

由于这是双向链表，那么对于链表中的某一个节点 p，它的后继的前驱是谁？当然还是它自己。它的前驱的后继自然也是它自己，即：

1	p->next->prior = p = p->prior->next;

双向链表是单链表中扩展出来的结构，所以它的很多操作和单链表相同，比如求长度的 ListLength，查找元素的 GetElem，获得元素位置的 LocateElem 等，这些操作都只涉及一个方向的指针即可，另一指针多了也不能提供什么帮助。

我们现在假设存储元素 e 的节点为 s，要实现将节点 s 插入到节点 p 和 p->next 之间需要下面几步：

s->prior = p; // 把 p 赋值给 s 的前驱
s->next = p->next; // 把 p->next 赋值给 s 的后继
p->next->prior = s->next; // 把 s 赋值给 p->next 的前驱
p->next = s;  // 把 s 赋值给 p 的后继

总体来说，就是先正向连接起来，再反向连接起来。

关键在于它们的顺序，由于第 2 步和第 3 步都用到了 p->next。如果第 4 步先执行，则会使得 p->next 提前变成 s，使得插入的工作完不成。因为这样一来我们就没有办法找到原始的 p->next 了。所以我们不妨把上面这张图在理解的基础上记忆，顺序是先搞定 s 的前驱和后继，再搞定后节点的前驱，最后搞定前节点的后继。

若要删除节点 p，只需要下面两步骤：

1
2
3

p->prior->next = p->next;
p->next->prior = p->prior;
free(p);

好了，简单总结一下，双向链表相对于单链表来说，要更复杂一些，毕竟它多了 prior 指针，对于插入和删除时，需要格外小心。另外它由于每个节点都需要记录两份指针，所以在空间上是要占用多一些的。不过，由于它良好的对称性，使得对某个节点的前后节点的操作，带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。

循环链表

Posted on 2020-01-08 Edited on 2022-06-15

将单链表中终端节点的指针由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）

循环链表解决了一个很麻烦的问题。如何从当中一个节点出发，访问到链表的全部节点。

为了使空链表与非空链表处理一致，我们通常设一个头节点，当然，这并不是说，循环链表一定要头节点，这需要注意。

空循环链表：

非空循环链表：

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断 p->next 是否为空，现在则是 p->next 不等于头节点，则循环未结束。

在单链表中，我们有了头节点时，我们可以用 O(1) 的时间访问第一个节点，但对于要访问到最后一个节点，却需要 O(n) 时间，因为我们需要将单链表全部扫描一遍。

有没有用 O(1) 的时间由链表指针访问到最后一个节点呢？当然可以。

不过我们需要改造一下这个循环链表，不用头指针，而是用指向终端节点的尾指针来表示循环链表，此时查找开始节点和终端节点都很方便了。

从上图中可以看到，终端节点用尾指针 rear 指示，则查找终端节点是 O(1)，而开始节点，其实就是 rear->next->next，其时间复杂度也为 O(1)。

举个程序的例子，要将两个循环链表合并成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是 rearA 和 rearB：

要想将它们合并，只需要如下的操作即可：

p = rearA->next; // 保存 A 链表的头节点
rearA->next = rearB->next->next; // 将本是指向 B 的第一个节点（不是头节点）赋值给 rearA->next
rearB->next = p; // 将原 A 表的头节点赋值给 rearB->next
free(p); // 释放 p

静态链表

Posted on 2020-01-07 Edited on 2022-06-15

单链表可以用指针来存储节点间的关联。如果不使用指针的话，我们也可以用数组来代替指针，描述单链表。

首先我们让数组的元素都是由两个数据域组成，data 和 cur。也就是说，数组的每个下标都对应一个 data 和一个 cur。数据域 data，用来存放输出，也就是通常我们要处理的数据；而游标 cur 相当于单链表中的 next 指针，存放该元素的后继在数组中的下标。

我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。

为了我们方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。

// 线性表的静态链表存储结构
#define MAXSIZE 1000 // 假设链表的最大长度是 1000
typedef struct
{
    ElemType data;
    int cur; // 游标，为 0 时表示无指向
} Component, StaticLinkList[MAXSIZE];

另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为 0 的元素的 cur 就存放备用链表的第一个节点的下标；而数组的最后一个元素的 cur 则存放第一个有数值的元素的下标，相当于单链表中的头节点作用，当整个链表为空时，则为 0。

我们已经知道了静态链表实际上是一个数组，现在来考虑一下静态链表的逻辑存储结构，思考一下以下问题：

1、初始化的时候除了分配一个数组的空间外，还需要做哪些操作？

我们知道，在链表中，初始化的时候有一个头节点。这个头节点是链表存储的起始位置，而静态链表初始化的时候，我们就已经分配了一个数组，而这个数组的位置是否就可以拿来做静态链表的头节点呢？我们知道，头节点是不存储具体数据的，存储的只是指向链表第一个元素的指针。

这样的话，如果我们把数组第一个元素来做头节点，事实上就意味着，链表的实际数据是从数组的第二个元素（下标为 1）开始存储的，这样其实会给我们理解上带来一定的困难，不是很直观。

当然实际上，数组里面也不一定是按顺序存储的。

如果我们把数组第一个元素拿来做实际存储的起始元素的时候，我们就可以很直观的知道链表的存储位置。

所以，我们还需要一个节点来作为头节点，数组起始位置不合适，那中间的元素呢？也是不合适，大家想想，你在中间拿出一个元素来做头节点，这样一来破坏了线性表的连续性（链表实际上还是线性表的），二来我们需要记忆是哪一个位置的元素是头节点，会给我们的开发维护带来很多问题。

既然起始和中间的元素都不适合做头节点，那就只有最后一个元素了。一来我们不需要记忆，没有记忆的心智负担，而来，数组的结构和线性表的存储结构刚好对应上，非常的直观，对我们写入等各种操作带来很多便利。

如何找到空闲的节点？

我们已经知道，静态链表中的每一个元素都保存了下一个元素的下标。刚初始化的时候，除了数组最后一个元素（头节点外），其它的都是空闲的节点，我们自然地想到存储的时候，先存入数组第一个位置，然后第二个，第三个... 这样一直插入，直到下标到达了 i-1 （i 为数组长度）的时候，我们发现链表已经满了，这个时候就不能再插入了。但是还有一种情况就是，如果我们中途从中删除了某一个元素的话，我们怎么知道当前哪一个位置已空可以插入新数据呢？

因为通过每个元素我们只能找到下一个元素，而不知道物理存储结构是否是连续的。

我们想起了，在我们未插入元素的时候，我们的数组起始也是可以看作一个链表，这个链表全都是空闲的元素，可以插入新的数据。直到我们开始插入数据的时候，这个空闲链表的长度 -1，这个时候我们似乎明白了，一个静态链表中实际上存在了两个链表，一个是空闲节点的链表，另外一个是实际有数据的链表。

要实现这种目的，我们已经有了一个实际有数据链表的头节点，我们还需要一个节点来作为空闲链表的头节点。

因此，我们插入新数据的时候，需要同时变更数据链表和空闲节点链表。

可以通过空闲节点链表找到空闲的节点，但是怎么找呢？在刚初始化的时候，我们可以把第一个节点当作是空闲链表的头节点；但是一旦我们插入了新的数据，空闲链表的头节点就变了，到这个时候我们就完全没有办法知道空闲链表头节点在哪里了，这个时候我们可以考虑借助外部变量来记录空闲链表的起始位置，但是这就脱离了链表本身了。从其它地方操作链表的时候，也需要传递该变量，所以不考虑这种方式。

还有一种方式就是，在数组中专门留出一个节点来记录空闲链表的起始位置，这样一来，我们的数组，就真的是有一个数据链表、一个空闲链表了，这才是合理的做法。

结论：使用数组第一个元素来保存空闲链表的起始节点。

如何知道静态链表是否已满？

通过上面的讨论，我们知道了，保存静态链表的数组中第一个元素保存了空闲链表的起始节点。我们可以通过查看该起始节点的 cur 是否等于 0 来判断静态链表是否已满。

上图相当于初始化的数组状态：

// 将一维数组 space 中各分量链成一备用链表
// space[0].cur 为头指针，"0" 表示空指针
Status InitList(StaticLinkList space)
{
    int i;
    for (i = 0; i < MAXSIZE - 1; i++)
        space[i].cur = i + 1;
    space[MAXSIZE - 1].cur = 0; // 目前静态链表为空，最后一个元素的 cur 为 0
    return OK;
}

假设我们已经将数据存入静态链表，比如分别存放着 "甲"、"乙"、"丁"、"戊"、"己"、"庚" 等数据：

此时 "甲" 这里就存有下一元素 "乙" 的游标 2，"乙" 则存有下一元素 "丁" 的下标 3。而 "庚" 是最后一个有值元素，所以它的 cur 设置为 0。而最后一个元素的 cur 则因 "甲" 是第一有值元素而存有它的下标为 1。而第一个元素则因空闲空间的第一个元素下标为 7，所以它的 cur 存有 7。

静态链表的插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

我们前面说过，在动态链表中，节点的申请和释放分别借用 malloc() 和 free() 两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的节点申请和释放问题，所以我们需要自己实现这两个函数，才可以做插入和删除的操作。

为了辨明数组中，哪些分量未被使用，解决的办法是将所有未被使用过的以及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个节点作为待插入的新节点。

// 若备用空间链表非空，则返回分配的节点下标，否则返回 0
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur; // 当前数组第一个元素的 cur 存的值，就是要返回的第一个备用空闲的下标
    if (space[0].cur)
        space[0].cur = space[i].cur; // 由于要拿出一个分量来使用了，所以我们就得把它的下一个分量用来做备用
    return i;
}

这段代码有意思，一方面它的作用就是返回一个下标值，这个值就是数组头元素的 cur 存的第一个空闲的下标。从上面的图来看，其实就是 7。

那么既然下标为 7 的分量要准备使用了，就得有接替者，所以就把分量 7 的 cur 值赋值给头元素，也就是把 8 给 space[0].cur，之后就可以继续分配新的空闲分量，实现类似 malloc() 函数的作用。

现在我们如果需要在 "乙" 和 "丁" 之间，插入一个值为 "丙" 的元素，按照以前顺序存储结构的做法，应该要把 "丁"、"戊"、"己"、"庚" 这些元素都往后移一位。但目前不需要，因为我们有了新的手段。

新元素 "丙"，想插队是吧？可以，你先悄悄地在队伍最后一排第 7 个游标位置待着，我一会就能帮你搞定。我接着找到了 "乙"，告诉它，你的 cur 不是游标为 3 的 "丁" 了，你把你的下一位的游标改为 7 就可以了。此时再回到 "丙" 那里，说你把你的 cur 改为 3。就这样，在绝大多数人都不知道的情况下，整个排队的次序发生了改变。

步骤： * 判断下标合法性 * 获取空闲节点的下标 * 写入数据到空闲节点 * 将上面空闲节点的 cur 修改为原 i 位置的 cur * 将写入位置前一个节点的 cur 修改为新节点所在位置

实现代码如下：

// 在 L 中第 i 个元素之前插入新的数据元素 e
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
    int j, k, l;
    k = MAX_SIZE - 1; // 注意 k 首先是最后一个元素的下标
    if (i < 1 || i > ListLength(L) + 1)
        return ERROR;
    j = Malloc_SLL(L); // 获得空闲分量的下标
    if (j) {
        L[j].data = e; // 将数据赋值给此分量的 data
        for (l = 1; l < i - 1; l++) // 找到第 i 个元素之前的位置 
            k = L[k].cur;
        L[j].cur = L[k].cur;  // 把第 i 个元素之前的 cur 赋值给新元素的 cur
        L[k].cur = j; // 把新元素的下标赋值给第 i 个元素之前元素的 cur
        return OK;
    }
    return ERROR;
}

当我们执行插入语句时，我们的目的是要在 "乙" 和 "丁" 之间插入 "丙"。调用代码时，输入 i 值为 3。
第 4 行让 k = MAX_SIZE - 1 = 999
第 7 行，j = Malloc_SLL(L) = 7。此时下标为 0 的 cur 也因为 7 要被占用而更改备用链表的值为 8。
第 11～12 行，for 循环 l 由 1 到 2，执行两次。代码 k = L[k].cur; 使得 k = 999，得到 k = L[999].cur = 1，再得到 k = L[1].cur = 2
第 13 行，L[j].cur = L[k].cur; 因 j=7，而 k = 2 得到 L[7].cur = L[2].cur = 3。这就是刚才说的 "丙" 把它的 cur 修改为 3 的意思。
第 14 行，L[k].cur = j; 意思就是 L[2].cur = 7。把它的 cur 改为指向 "丙" 的下标 7。

就这样，我们实现了在数组中，实现不移动元素，却插入了数据的操作。

静态链表的删除操作

和前面一样，删除元素时，原来是需要释放节点的函数 free()。现在我们也得自己实现它：

// 删除在 L 中第 i 个数据元素 e
Status ListDelete(StaticLinkList L, int i)
{
    int j, k;
    if (i < 1 || i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 1;
    for (j = 0; j <= i - 1; j++) { // 找到第 i 个元素之前的位置
        k = L[k].cur;
    }
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SLL(L, j);
    return OK;
}

有了刚才的基础，这段代码就很容易理解了。前面代码都一样，for 循环因为 i = 1 而不操作，j=k[999].cur=1, L[k].cur=L[j].cur 也就是 L[999].cur = L[1].cur = 2。这其实就是告诉计算机现在 "甲" 已经离开了，"乙" 才是第一个元素。

释放节点代码：

// 将下标为 k 的空闲节点回收到备用链表
void Free_SLL(StaticLinkList space, int k)
{
    space[k].cur = space[0].cur; // 把第一个元素 cur 值赋给要删除的分量
    space[0].cur = k; // 把要删除的分量下标赋值给第一个元素的 cur
}

意思就是 "甲" 现在要走，这个位置就空出来了，也就是，未来如果有新人来，最优先考虑这里，所以原来的第一个空位分量，即下标是 8 的分量，它降级了，把 8 给 "甲" 所在下标为 1 的分量的 cur，也就是 space[1].cur = space[0].cur = 8，而 space[0].cur = k = 1，其实就是让这个删除的位置称为第一个优先空位，把它存入第一个元素的 cur 中。

当然，静态链表也有相应的其它操作的相关实现。比如我们代码中的 ListLength 就是一个：

// 初始条件：静态链表 L 已存在。操作结果是：返回 L 中数据元素个数
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while(i) {
        i = L[i].cur;
        j++;
    }
    return j;
}

静态链表的优缺点

优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

缺点：没有解决连续存储分配带来的表长难以确定的问题。失去了顺序存储结构随机存取的特性。

总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。