跳转至

2025

算法题必备 - Python

输入输出

如果只有若干个元素,可以使用input()方法来获取输入的一行。

如果同质化的元素一行一行的输入并且用空格隔开,可能迭代stdin+split是更简单的方法。

import sys
for line in sys.stdin:
    a = line.split()

输出用print,如果复杂一点用format string。

排序

Python的list.sort是稳定排序,可以通过参数key来将list中的每个元素映射之后再比较。例如:

>>> l = ['a', 'B', 'c']
>>> l.sort()
>>> l
['B', 'a', 'c']
>>> l.sort(key=str.lower)
>>> l
['a', 'B', 'c']

最小堆

Python并没有一个叫堆堆容器。heapq是标准库自带的最小堆算法。他使用的容器就是Python list,heap[0]是最小元素。

和C++类似,我们可以通过重载运算符的方式,把最小堆变成最大堆。修改__lt__方法。

class Item:
    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        # 反转比较逻辑:原数的“小”对应取反后的“大”
        return self.value > other.value

# 使用自定义对象的最大堆
heap = []
heapq.heappush(heap, Item(5))
heapq.heappush(heap, Item(8))
print(heapq.heappop(heap).value)  # 输出 8(最大元素)

eval

eval可以直接执行字符串,可能会有意想不到的帮助。

数组

创建一个一维数组:

>>> [0] * n
[0, 0, 0]
>>> [0 for _ in range(n)]
[0, 0, 0]

创建一个二维数组:

>>> [[0 for _ in range(n)] for _ in range(m)]
[[0, 0, 0], [0, 0, 0]]

但是用[[0]*n]*m是不对的。对list采用乘法是浅拷贝列表的每个元素n次。所以如果list的元素是可变的,这样做可能会不符合你的本意。

tokio异步程序开发笔记

最近在使用Rust+Tokio开发一个流式任务(后文用pipeline指代)调度框架。踩了很多坑,这里记录一些心得。

安全退出

退出一个Shell程序,最最自然的想法是使用Ctrl+C,向程序发送一个SIGINT信号,默认处理就是退出程序。

然而,直接退出可能并不符合你的预期——如果任务执行了一半就退出了,会变成什么样子?

所以我们应该自定义对SIGINT的处理逻辑,这属于系统编程的范畴。还好,tokio库帮我们做了封装,我们可以在程序开始的时候开一个任务去等待SIGINT信号,然后进行处理

tokio::spawn(async move {
    tokio::signal::ctrl_c().await.unwrap();
    tracing::info!("Ctrl+C received, canceling...");
    // 退出逻辑,如果等待程序自然运行完成可以为空。
});

对于我的程序来说,每一个pipeline都会不停的等待新消息,也就是不会主动停止。那么就需要一个方式去通知所有的pipeline,应该停止接受消息了。自然的,你会想到消息队列——当收到 SIGINT 信号时,向所有pipeline 发送取消请求;所以所有的pipeline在等待新消息的同时,也要等待取消请求。这种同时等待两个异步任务的操作就是select

伪代码如下。由于有这个消息有多个consumer,且只需要发送一次。所以可以使用watch::channel

//  logic

let (cancel_tx, cancel_rx) = tokio::sync::watch::channel(false);

// 在多个任务中共享接收端
let task1 = tokio::spawn({
    let mut rx = cancel_rx.clone();
    async move {
        while !*rx.borrow() {
            // 正常工作循环
            tokio::select! {
                _ = rx.changed() => {
                    // 收到取消信号
                    break;
                }
                // 其他工作逻辑
            }
        }
    }
});

// 发送取消信号
cancel_tx.send(true)?;
// pipeline 具体逻辑
loop {
    tokio::select! {
        _ = rx.changed() => { break; }
        message => mq.recv() {
            // 具体的处理逻辑
        }
    }
}

不过我的程序其实使用了一个更高级的封装CancellationToken,我的使用方式和消息队列没有不同,但是事实上它支持多层级的任务取消。

日志记录

tokio团队的tracingtracing-subscriber用来记录异步日志很合适。我个人习惯在tokio::spawn的时候创建一个span

超时

tokio::time::timeout用起来很舒服,用它包裹一个异步任务,如果超时的可以提前返回。我用它来将 回调 和 轮询 机制结合在一起。

性能监控

异步 Drop

流式任务调度框架,如何追踪一个输入的全流程?最简单的办法就是一直使用同一个数据。我称之为Context,定义如下。在消息队列中直接传递Context,等到消息处理完成后,InnerContext就会被 drop。将一些逻辑放在Drop的实现中即可,如归档到数据库。

pub type Context = Arc<Mutex<InnerContext>>

impl Drop for InnerContext {
    fn drop(&mut self) {}
}

但是如果我需要在drop中调用异步函数怎么办?drop不能是异步的。如何阻塞的调用异步函数?

  • 可以使用futures::executor::block_on函数,它会创建一个简单的运行时单线程阻塞的执行异步任务。如果要进行的异步任务简单,可以使用这个方法。例如,将任务的数据通过 channel 传递给真正的工作任务。这是我所使用的。
  • 也许可以使用smol::block_on
  • 也可以使用tokio::task::block_in_place函数。
tokio::task::block_in_place(move || {
    tokio::runtime::Handle::current().block_on( async move {
        // logic
    })
});

数据查询语言

SQL 是一种 声明式 查询语言,用来对关系型数据库进行数据检索。

CSS 其实也是 一种 声明式 查询语言,用来修改HTML的样式。类似与 CSS 之于 HTML,XSL 也可以用来对 XML 进行检索。

对于使用者来说,API 会比命令式的更加简洁容易(想象使用Javascript修改HTML的样式)。并且它隐藏了引擎的实现细节,可以在无需对查询进行任何更改的情况下进行性能提升。最后,声明式语言往往适合并行执行。

MapReduce 是一个由 Google 推广的编程模型,用于在多台机器上批量处理大规模的数据

迭代器失效问题

在看leetcode题解的时候,不明白为什么可以一边持有容器的迭代器,一边对容器进行修改。如下代码的leftright变量。

class MedianFinder {
    multiset<int> nums;
    multiset<int>::iterator left, right;

public:
    MedianFinder() : left(nums.end()), right(nums.end()) {}

    void addNum(int num) {
        const size_t n = nums.size();

        nums.insert(num);
        if (!n) {
            left = right = nums.begin();
        } else if (n & 1) {
            if (num < *left) {
                left--;
            } else {
                right++;
            }
        } else {
            if (num > *left && num < *right) {
                left++;
                right--;
            } else if (num >= *right) {
                left++;
            } else {
                right--;
                left = right;
            }
        }
    }

    double findMedian() {
        return (*left + *right) / 2.0;
    }
};

事实上这和multiset的底层实现相关。mutliset底层实现是红黑树,节点之间用指针连接,插入新的元素不会导致原先节点的位置发生改变。所以代码的操作是安全的。而vector这样的数据结构就不一定了,因为它在插入的过程中需要进行扩容,改变元素的位置。

深入探究

map/set/multimap/multiset的底层实现是红黑树,list是链表。所以对于这些容器来说,插入insert新的元素不会导致原先的迭代器失效,而删除erase一个元素会导致删除元素的迭代器失效。

vector/string 在插入insert元素的时候,如果进行了扩容会导致所有迭代器失效;没有扩容由于需要将后面的元素整体向后移动,也会导致插入元素后面的所有迭代器失效。删除erase元素的时候,由于需要将后面的元素整体向前移动,也会导致删除元素后面的所有迭代器失效。

更详细的内容参考Stackoverflow,参考链接2。原理大同小异。

[!NOTE] 类比于Rust,是不会让你同时持有对一个容器的多个可变引用的。保证了安全的同时,极大的减轻了编程者的心智负担,代价则是灵活性的丧失。孰优孰劣没有答案。

What about Rust

类比于Rust,是不会让你同时持有对一个容器的多个可变引用的。保证了安全的同时,极大的减轻了编程者的心智负担,代价则是灵活性的丧失。孰优孰劣没有答案。

那么Rust需要如何遍历并删除item?如Vec,需要用Vec::retain方法,简化后的伪代码如下。相同的思路适用于C++。

fn retain<F>(&mut self, mut predicate: F)
where
    F: FnMut(&T) -> bool,
{
    let len = self.len();
    let mut write_idx = 0; // 慢指针:记录保留元素的位置
    let mut read_idx = 0;  // 快指针:遍历所有元素

    while read_idx < len {
        if predicate(&self[read_idx]) {
            // 保留元素:将元素移动到 write_idx 位置
            self.swap(write_idx, read_idx);
            write_idx += 1;
        }
        read_idx += 1;
    }

    // 截断向量,移除尾部不需要的元素
    self.truncate(write_idx);
}

Rust的其他容器的遍历并删除的方法也叫retain

参考链接

  1. 关于C++ 迭代器失效特性的研究 – 奇安信技术研究院
  2. Iterator invalidation rules for C++ containers - Stack Overflow

记一次SLOW SQL排查

没有使用ORM框架,也没有对SQL的执行时间进行统计,只是在运行的时候发现瓶颈貌似出现在了Postgresql数据库,于是开始尝试排查。。。

session

首先查看sessions。我用的是dbeaver,如果用SQL语句的话也可以:

SELECT sa.* FROM pg_catalog.pg_stat_activity sa

重点关注xact start记录的当前事务开始时间和query start当前正在执行的查询的开始时间。如果发现他们state=active而且他们较早,说明他们相关的SQL语句执行的很慢。

更好的办法应该是在执行SQL语句的时候进行时间统计,并LOG SLOW SQL,这也是很多ORM框架的自带功能。由于缺乏经验我没有做,只能这样排查。

explain

我找到了执行很慢的SQL,但是我自认为为他们创建了索引,不应该如此之慢。

这个时候可以用explain来看自己的索引到底有没有真正起作用。analyze选项表示真正执行这条SQL语句。

explain analyze  SELECT "from", amount, number
    FROM cashflow
    WHERE "to" = $1 AND is_fund = true
    ORDER BY number ASC LIMIT 1

这是explain analyze的结果:

Limit  (cost=1654659.38..1654659.50 rows=1 width=59) (actual time=154302.162..154654.812 rows=0 loops=1)
  ->  Gather Merge  (cost=1654659.38..1654669.42 rows=86 width=59) (actual time=154045.564..154398.214 rows=0 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Sort  (cost=1653659.36..1653659.47 rows=43 width=59) (actual time=153242.010..153242.104 rows=0 loops=3)
              Sort Key: number
              Sort Method: quicksort  Memory: 25kB
              Worker 0:  Sort Method: quicksort  Memory: 25kB
              Worker 1:  Sort Method: quicksort  Memory: 25kB
              ->  Parallel Seq Scan on cashflow  (cost=0.00..1653659.15 rows=43 width=59) (actual time=153238.328..153238.422 rows=0 loops=3)
                    Filter: (is_fund AND (("to")::text = '0x42be8d8f46f1eeae232f684878bc5506af962637'::text))
                    Rows Removed by Filter: 19661737
Planning Time: 1.949 ms
JIT:
  Functions: 13
  Options: Inlining true, Optimization true, Expressions true, Deforming true
  Timing: Generation 73.339 ms (Deform 6.503 ms), Inlining 369.544 ms, Optimization 114.942 ms, Emission 130.445 ms, Total 688.269 ms
Execution Time: 154701.653 ms

其中的cost=start_time..end_time表示操作开始的代价操作完成的总代价。操作开始的代价看起来有些奇怪,它表示操作可以开始产生任何结果之前预计要花费的代价。对于一些操作,如排序或聚集,数据库需要读入所有相关数据并进行处理才能产生第一行结果。因此,这个 "开始代价" 包括了读取和处理数据直到第一行结果准备就绪所需的预计代价。可以看到执行计划中的每一步的总代价都是十分高昂的。

cost的单位并不是时间,而是对资源成本的抽象统计。具体可以看PostgreSQL: Documentation: 17: 19.7. Query Planning。真正的时间需要添加analyze真正执行后统计。

这是我为to, is_fund, number添加索引后的explain analyze结果。可以看到他用上了索引,效率很高。

Limit  (cost=0.56..4.62 rows=1 width=59) (actual time=1.888..1.888 rows=0 loops=1)
  ->  Index Scan using cashflow_fund_idx on cashflow  (cost=0.56..418.62 rows=103 width=59) (actual time=1.885..1.885 rows=0 loops=1)
        Index Cond: ((("to")::text = '0x42be8d8f46f1eeae232f684878bc5506af962637'::text) AND (is_fund = true))
Planning Time: 355.678 ms
Execution Time: 2.136 ms

C++中的四种多态(翻译)

通常讨论C++的多态,指的是通过基类指针/引用来使用其派生类,这叫做子类多态(subtype polymorphism)。但是实际上还有其他的多态,例如参数多态(parametric polymorphism)特设多态(ad-hoc polymorphism,我翻译的可能不太好,后面还是用ad-hoc原文)强制多态(coercion polymorphism)

这些多态在C++中还有其他名字:

  • 子类多态又称为运行时多态(runtime polymorphism)。(一般多态特指子类多态)
  • 参数多态又称为编译期多态(compile-time polymorphism)
  • ad-hoc多态又称为重载(overloading)
  • 强制转换多态又称为类型转换(casting)

在这篇文章中,我将通过C++语言的示例来阐述所有的多态性,并且解释它们为什么会有各种不同的名称。

子类多态(运行时多态)

当提到C++的多态时,默认指的是子类多态。它指的是通过基类指针/引用来使用其派生类的能力。

下面是一个例子。假设你有各种各样的猫科动物(felid)。由于它们都是猫科动物,并且它们都应该能够喵喵叫,因此它们可以表示为继承自Felid基类并覆盖meow纯虚函数的类,

// file cats.h

class Felid {
public:
 virtual void meow() = 0;
};

class Cat : public Felid {
public:
 void meow() { std::cout << "Meowing like a regular cat! meow!\n"; }
};

class Tiger : public Felid {
public:
 void meow() { std::cout << "Meowing like a tiger! MREOWWW!\n"; }
};

class Ocelot : public Felid {
public:
 void meow() { std::cout << "Meowing like an ocelot! mews!\n"; }
};

现在主程序可以通过Felid(基类)指针来调用Cat, TigerOcelot的方法。

#include <iostream>
#include "cats.h"

void do_meowing(Felid *cat) {
 cat->meow();
}

int main() {
 Cat cat;
 Tiger tiger;
 Ocelot ocelot;

 do_meowing(&cat);
 do_meowing(&tiger);
 do_meowing(&ocelot);
}

在这个程序中,主程序将指向Cat, TigerOcelot的指针传递给一个期望接收指向Felid的指针的do_meowing函数。由于它们都是Felid的子类,程序会为每个Felid调用正确的meow函数,输出结果如下:

Meowing like a regular cat! meow!
Meowing like a tiger! MREOWWW!
Meowing like an ocelot! mews!

子类多态也被称为运行时多态,这个名称的由来有很充分的理由。多态函数调用的解析是在运行时通过虚表(virtual table)的间接引用来完成的。另一种解释是,编译器在编译时并不确定被调用函数的地址,而是在程序运行时,通过在虚表中解引用正确的指针来调用函数。

在类型理论中,它也被称为包含多态

参数多态(编译期多态)

参数多态性提供了一种对任何类型执行相同代码的方法。在C++中,参数多态性是通过模板实现的。一个最简单的例子是一个泛型的max函数,它寻找两个参数中的最大值。

#include <iostream>
#include <string>

template <class T>
T max(T a, T b) {
 return a > b ? a : b;
}

int main() {
 std::cout << ::max(9, 5) << std::endl;     // 9

 std::string foo("foo"), bar("bar");
 std::cout << ::max(foo, bar) << std::endl; // "foo"
}

这里的max函数在类型T上是多态的。但是请注意,它不适用于指针类型,因为比较指针比较的是内存位置而不是内容。要让它为指针工作,你必须为指针类型专门化模板,这将不再是参数多态,而是特殊多态。

由于参数多态发生在编译时,因此也称为编译时多态。

[!NOTE] 关于模板,更多的内容可以参考模板

ad-hoc多态(重载)

ad-hoc多态允许具有相同名称的函数对每种类型有不同的行为。例如,对于两个int+将他们相加;对于两个string+将他们连接。这叫做重载

这里是一个具体的例子,为intstring实现函数add

#include <iostream>
#include <string>

int add(int a, int b) {
 return a + b;
}

std::string add(const char *a, const char *b) {
 std::string result(a);
 result += b;
 return result;
}

int main() {
 std::cout << add(5, 9) << std::endl;
 std::cout << add("hello ", "world") << std::endl;
}

ad-hoc多态也出现在C++的模板特化中。还是以上面的max模板为例,以下是如何为两个char *编写max

template <>
const char *max(const char *a, const char *b) {
 return strcmp(a, b) > 0 ? a : b;
}

现在你可以调用::max("foo", "bar")来查找字符串“foo”和“bar”的最大值。

强制转换多态

当一个对象或基本类型被强制转换为另一个对象类型或基本类型时,就会发生强制转换。例如:

float b = 6; // int gets promoted (cast) to float implicitly
int a = 9.99 // float gets demoted to int implicitly

如果类的构造函数不是explicit,也会发生强制转换。

#include <iostream>

class A {
 int foo;
public:
 A(int ffoo) : foo(ffoo) {}
 void giggidy() { std::cout << foo << std::endl; }
};

void moo(A a) {
 a.giggidy();
}

int main() {
 moo(55);     // prints 55
}

如果你创建了explicit修饰的构造函数,那就不可能了。推荐使用explicit修饰构造函数以避免意外转换。

同样,如果一个类定义了类型T的转换操作符,那么它可以在任何需要类型T的地方使用。例如:

class CrazyInt {
 int v;
public:
 CrazyInt(int i) : v(i) {}
 operator int() const { return v; } // conversion from CrazyInt to int
};

CrazyInt定义了一个类型为int的转换运算符。现在,如果我们有一个函数,比如说,print_int接受int作为参数,我们也可以向它传递一个CrazyInt类型的对象,

#include <iostream>

void print_int(int a) {
 std::cout << a << std::endl;
}

int main() {
 CrazyInt b = 55;
 print_int(999);    // prints 999
 print_int(b);      // prints 55
}

前面讨论的子类型多态实际上也是强制转换多态,因为派生类被转换为基类类型。

祝您在学习这些关于多态性的新知识时玩得开心,下次再见!

参考链接

原文链接:The Four Polymorphisms in C++。作者是一个大佬。