Arbitary Lifetime Transmutation via Rust Unsoundness

Do you believe that one can write a function in safe Rust which can arbitrarily change the lifetime of a reference? For clarity, try to implement the following function without using unsafe:

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 { todo!() }

Such intention seems to violate the fundamental principle of Rust’s lifetime system, which is to prevent dangling references and data. However, it is possible to write such a function in safe Rust, and it is not even that hard:

trait Trait {
type Output;

impl<T: ?Sized> Trait for T {
type Output = &'static u64;

fn foo<'a, T: ?Sized>(x: <T as Trait>::Output) -> &'a u64 { x }

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 {
foo::<dyn Trait<Output=&'a u64>>(x)

Read More

Dijkstra 算法的延伸

我们知道 Dijkstra 算法是一个高效的单源最短路径(SSSP)算法,本文将不再赘述他的细节。但同时,Dijkstra 也是一个动态规划算法。Dijkstra 算法的正确性源自无负边权图的若干性质。如果一个问题本身也满足这些性质,那么即使它不是一个图论最短路径问题,也可以使用 Dijkstra 算法解决。那么,这些性质是什么呢?

Read More

Manacher 回文计数算法

以下假设字符串下标从 $0$ 开始,子串记号 $s[i..j]$ 左闭右闭。

给定长度为 $n$ 的字符串 $s$,Manacher 算法可以在 $O(n)$ 的时间复杂度内找到 $s$ 的所有回文子串。

我们先以寻找长度为奇数的子串为例。首先需要明确的是,如果 $s$ 中以第 $i$ 个字符为中心的最长回文子串长度为 $d=2p+1$,则以下皆为 $s$ 的回文子串:

$$s[i-(p-1)..i+(p-1)],\ldots, s[i-1..i+1], s[i..i]$$

因此,我们只需对所有下标 $i$ 求解出以 $s[i]$ 为中心的最长回文子串长度 $2p_i+1$,即可知道 $s$ 的所有回文子串。

Read More





Read More

Go Fact: Zero-sized Field at the Rear of a Struct Has Non-zero Size

There’s a concept in Golang called zero-sized type (or ZST), namely, a type whose variables take up zero bit of memory. One of them is the famous struct{}. People often use map[string]struct{} to efficiently emulate a set structure. Others include zero-length arrays such as [0]int, albeit not very common, are adopted to enforce some properties of a customized type.

Read More

Display *big.Rat Losslessly and Smartly in Golang

Floating-point numbers, as we know, are notorious for losing precision when their values become too large or too small. They are also bad at representing decimals accurately, yielding confusions like 0.1 + 0.2 != 0.3 for every beginner in their programming 101.

Albeit being imprecise, floats are good enough for most daily scenarios. For those not, however, Golang provides *big.Rat to the rescue. Rats are designed to represent rational numbers with arbitary precision, addressing most flaws of floats, yet at a cost of much slower computation speed and bigger memory footprint. For example, we are confident to compare 0.1 + 0.2 to 0.3 using Rats without caring about tolerance:

Read More


我们常能在英文社区看到 coding ceremory 一词,或译为 代码的仪式。Stack Overflow 上有个问题 What does “low ceremony” mean?,作者曾如此提问:

In the Trac Main Features page, Trac is said to emphasize “ease of use and low ceremony”. Can someone please explain what “ceremony” means in the context of software usage?

low ceremony 与 ease of use 作并列短语,可见在程序开发的语境下,代码的仪式不是一个褒义词——过多的仪式并没有好处。用户 Rowan Freeman 则作此回答:

Low ceremony means a small amount of code to achieve something. It means you don’t need to set up a lot of things in order to get going.




依照呈现的形式,代码的仪式可以分为 编写仪式 和 运行仪式 两类。

Read More


前段时间在 V2EX 的一个帖子 /t/943948 中看到了一个有趣的问题:



Read More