2024年10月

使用 Socket 实现的分布式事件总线,支持 CQRS,不依赖第三方 MQ。

CodeWF.EventBus.Socket
是一个轻量级的、基于 Socket 的分布式事件总线系统,旨在简化分布式架构中的事件通信。它允许进程之间通过发布/订阅模式进行通信,无需依赖外部消息队列服务。

Command

Command

Query

Query

特性

  • 轻量级
    :不依赖任何外部 MQ 服务,减少了系统复杂性和依赖。

  • 高性能
    :基于 Socket 的直接通信,提供低延迟、高吞吐量的消息传递。

  • 灵活性
    :支持自定义事件类型和消息处理器,易于集成到现有系统中。

  • 可扩展性
    :支持多客户端连接,适用于分布式系统环境。

通信协议

通过
TCP
协议进行数据交互,协议包结构如下:

0.0.8@2x

安装

通过
NuGet
包管理器安装
CodeWF.EventBus.Socket

Install-Package CodeWF.EventBus.Socket

服务端使用

运行事件服务

在服务端代码中,创建并启动
EventServer
实例以监听客户端连接和事件:

using CodeWF.EventBus.Socket;

// 创建事件服务器实例
IEventServer eventServer = new EventServer();

// 启动事件服务器,监听指定IP和端口
eventServer.Start("127.0.0.1", 9100);

停止事件服务

当不再需要事件服务时,调用
Stop
方法以优雅地关闭服务器:

eventServer.Stop();

客户端使用

连接事件服务

在客户端代码中,创建
EventClient
实例并连接到事件服务器:

using CodeWF.EventBus.Socket;

// 创建事件客户端实例
IEventClient eventClient = new EventClient();

// 连接到事件服务器,使用eventClient.ConnectStatus检查连接状态
eventClient.Connect("127.0.0.1", 9100));

订阅事件

订阅特定类型的事件,并指定事件处理函数:

eventClient.Subscribe<NewEmailCommand>("event.email.new", ReceiveNewEmailCommand);

private void ReceiveNewEmail(NewEmailCommand command)
{
    // 处理新邮件通知
    Console.WriteLine($"收到新邮件,主题是{message.Subject}");
}

发布命令(Command)

发布事件到指定的主题,供已订阅的客户端处理:

// 发布新邮件通知事件
eventClient.Publish("event.email.new", new NewEmailCommand { Subject = "恭喜您中Github一等奖", Content = "我们很开心,您在2024年7月...", SendTime = new DateTime(2024, 7, 27) });

查询(Query)

查询指定主题,需要有接收查询端订阅相同的主题(即生产者),收到请求后,再以相同的主题发布查询结果:

eventClient.Subscribe<EmailQuery>("event.email.query", ReceiveEmailQuery);

private void ReceiveEmailQuery(EmailQuery query)
{
    // 执行查询请求,准备查询结果
    var response = new EmailQueryResponse { Emails = EmailManager.QueryEmail(request.Subject) };

    // 以相同的主题,发布查询结果
    if (_eventClient!.Publish("event.email.query", response,
        out var errorMessage))
    {
        Logger.Info($"Response query result: {response}");
    }
    else
    {
        Logger.Error($"Response query failed: {errorMessage}");
    }
}

其他端可使用相同的主题查询(即消费者):

var response = _eventClient!.Query<EmailQuery, EmailQueryResponse>("event.email.query",
    new EmailQuery() { Subject = "Account" },
    out var errorMessage);
if (string.IsNullOrWhiteSpace(errorMessage) && response != null)
{
    Logger.Info($"Query event.email.query, result: {response}");
}
else
{
    Logger.Error(
        $"Query event.email.query failed: [{errorMessage}]");
}

取消订阅事件

不再需要接收某类事件时,可以取消订阅:

eventClient.Unsubscribe<NewEmailNotification>("event.email.new", ReceiveNewEmail);

断开事件服务

完成事件处理或需要断开与服务器的连接时,调用
Disconnect
方法:

eventClient.Disconnect();
Console.WriteLine("断开与事件服务的连接");

注意事项

  • 确保服务端和客户端使用的地址和端口号一致,并且端口未被其他服务占用。
  • 在生产环境中,服务端应配置为监听公共 IP 地址或适当的网络接口。
  • 考虑到网络异常和服务重启等情况,客户端可能需要实现重连逻辑。
  • 根据实际需求,可以扩展
    EventServer

    EventClient
    类以支持更复杂的功能,如消息加密、认证授权等。

前言

在最近的Vue Fes大会上,Vue Vapor的作者智子大佬宣布,如果能够得到资金支持,那么Vue Vapor年底就能发布alpha版本了。

关注公众号:【前端欧阳】,给自己一个进阶vue的机会

智子也需要赚钱养活自己

根据尤大透露,过去一年以来智子接受赞助全职在为Vue Vapor工作。现在智子虽然还有赞助,但不再是全职的了。
t3

也就是说现在智子大佬也需要想办法赚钱
养活自己
了,所以上周智子发了一个寻找赞助商的帖子。
t1

智子的目标也很简单,
能够养活他就行了
。并且表示为赞助商服务,开始虽然是封闭开发,最终还是会开源的。
t2

如果不寻求赞助,为了能够养活自己智子就只能去找一份工作了。如果这样Vapor的开发进度可能就会延缓,所以目前来说赞助计划是目前最好的方式了。
t5

目前智子收到的赞助总额不到1000美元(包括尤大的)。

强如智子大佬,做开源也很难养活自己。欧阳也只能略尽绵薄之力(因为我最近也被通知12月底走人了,我们团队将会只剩下leader了)
sponsor

现在的Vue Vapor

现在的Vue Vapor主要有三个特点:没有虚拟DOM、高性能、更小的包体积。

没有虚拟DOM
:意思很简单,就是在Vue Vapor中已经将虚拟DOM给干掉了。

高性能
:因为干掉了虚拟DOM,瓶颈得以突破,所以性能相对提高了很多。
performance

更小的包体积
:包体积大小减少了53.3%。

并且Vue Vapor是目前大家所使用的Vue版本的子集
subset

相比目前的Vue功能要少点,支持Composition API以及
<script setup>

因为Vapor是目前Vue版本的子集,所以无虚拟DOM的Vapor模式和有虚拟DOM的vDom模式之间是互相兼容的。
fusion

在Vapor组件中支持使用vDom模式的组件。同样在vDom组件中也支持使用Vapor模式的组件。并且还支持只使用Vapor模式的情况。

并且Vue生态中的
VueUse

Vue Router

Pinia

Nuxt

组件库
等都会支持Vapor。
compatibility

同样也支持jsx,不过需要引入
unplugin-vue-jsx-vapor

Vapor的机制

先看一个普通的操作DOM的例子:

// Initialize
const container = document.createElement('div')
const label = document.createElement('h1')
const button = document.createElement('button')
button.textContent = 'Increase'

button.addEventListener('click', increase)
let count = 0
const render = () => {
  label.textContent = `Count: ${count}`
}
function increase() {
  count++
  render() // Re-render
}
render() // Initial render

document.body.append(container)
container.append(label, button)

在这个例子中主要有两个元素:
h1
标签和
button
按钮。

h1
标签中渲染了
count
变量的值。

点击
button
按钮触发click事件执行
increase
函数,在函数中首先会执行
count++
,然后再去执行
render
函数。


render
函数中将
h1
标签中的值更新为最新值。

上面这个方案有个弊端,每次在click事件的回调中除了常规的执行
count++
之外,还去手动调用了
render
函数。

设想一下,如果我们的业务代码里面也这样写,那代码中将会到处都在调用
render
函数了,这样的代码光想想都头疼。

还好Vue的设计中有个优秀的响应式机制,并且还将响应式的功能抽取成一个单独的包:
@vue/reactivity

而Vue Vapor就是基于
@vue/reactivity
进行开发的,藉此实现当响应式数据改变后会自动更新DOM,无需去手动执行render函数。

使用
@vue/reactivity
改造后的代码如下:

import { effect, ref } from '@vue/reactivity'

// Initialize
const container = document.createElement('div')
const label = document.createElement('h1')
const button = document.createElement('button')
button.textContent = 'Increase'

button.addEventListener('click', increase)
const count = ref(0)
effect(() => {
  label.textContent = `Count: ${count.value}`
})
function increase() {
  count.value++
}

document.body.append(container)
container.append(label, button)

改造后的代码和原来的代码主要有三个不同:

  • 之前是直接使用
    let count = 0
    定义的变量,而改造后使用
    const count = ref(0)
    定义的响应式变量。

  • 之前的
    increase
    函数中除了执行
    count++
    之外,还需要去手动调用
    render()
    函数。而在新的代码中只会执行
    count.value++

  • 移除了render函数,替代他的是
    effect
    函数。在
    effect
    的回调函数中同样是进行DOM操作更新
    h1
    标签中的值。

    effect
    函数和
    watchEffect
    很相似,当回调中的响应式变量改变后就会重新执行回调函数。这里就是当响应式变量
    count
    改变后会重新执行回调函数,在回调函数中进行DOM操作更新
    h1
    标签中的值。

这也就是Vapor基于
@vue/reactivity
实现的响应式原理,在这个过程中完全没有虚拟DOM的介入。当响应式变量改变后会执行对应的
effect
回调函数,在回调函数中直接去更新DOM即可。

看到这里有的小伙伴会有疑问,这个
effect
函数以及里面操作DOM的代码需要我们自己手写吗?

当然不需要手动去写!!在编译时Vapor会自动生成一个
effect
回调函数,以及回调函数里面更新DOM的代码。

这个是上面的例子在
Vue Vapor SFC Playground
上面经过编译后的js代码,如下图:
playground

从上图中可以看到Vapor模式下经过编译后会自动生成一个effect回调函数,并且在回调函数中会去直接操作DOM。

至于编译时是如何生成effect回调函数,需要等Vapor稳定后欧阳会继续写文章讲解。

总结

无虚拟DOM
的Vapor模式是
有虚拟DOM
的vDom模式的子集,并且他们之间支持component组件混用。抛弃了虚拟DOM,Vapor轻装上阵后,性能以及包体积相比传统的vDom模式有了很大的提升。
最后就是智子现在在寻求赞助商,让他能够全职开发Vue Vapor的同时能够养活自己。

关注公众号:【前端欧阳】,给自己一个进阶vue的机会

另外欧阳写了一本开源电子书
vue3编译原理揭秘
,看完这本书可以让你对vue编译的认知有质的提升。这本书初、中级前端能看懂,完全免费,只求一个star。

来源:晓飞的算法工程笔记 公众号,转载请注明出处

论文: ClearCLIP: Decomposing CLIP Representations for Dense Vision-Language Inference

创新点


  • 发现两个关键因素在将
    CLIP
    适配密集视觉-语言推理中起着至关重要的作用:残差连接影响的减少以及通过自注意力机制的空间信息重组。
  • 提出
    ClearCLIP
    ,在
    CLIP
    的最后一层中进行了三项简单的修改:去除残差连接、最后一个注意力层中采用自注意力机制以及舍弃前馈网络(
    FFN
    )。这些修改旨在增强注意力输出,从而为开放词汇语义分割任务生成更清晰的表示。

内容概述


尽管大规模预训练的视觉-语言模型(
VLMs
),特别是
CLIP
在各种开放词汇任务中取得了成功,但它们在语义分割中的应用仍然面临挑战,常常产生噪声分割图,存在误分割区域。

论文仔细重新审视了
CLIP
的架构,并确定残差连接是降低分割质量的主要噪声源。通过对不同预训练模型中残差连接与注意力输出的统计特性进行比较分析,发现
CLIP
的图像-文本对比训练范式强调全局特征,而牺牲了局部可区分性,从而导致噪声分割结果。

为此,论文提出了
ClearCLIP
,这是一种新颖的方法,旨在分解
CLIP
的表示,以增强开放词汇语义分割。对最终层进行了三项简单的修改:去除残差连接、最后一个自注意力层中采用自注意力机制以及丢弃前馈网络。
ClearCLIP
可以一致地产生更清晰、更准确的分割图,并在多个基准测试中超过现有方法。

ClearCLIP


基于
ViT

CLIP
模型由一系列残差注意力块组成。

舍弃残差连接

通过比较
COCOStuff
数据集中
CLIP-B
/
16

CLIP-L
/
14
模型最后一个模块的残差连接
\(X_{{res}}\)
与不同注意力输出
\(X_{{attn}}\)
的范数来开始分析,可以很容易地观察到这两个子图的共性和差异:

  1. 共性在于
    mIoU
    曲线和
    \(X_{attn}\)
    的范数曲线表现出一定程度的正相关。
  2. 差异包括:
    1

    CLIP-B
    /
    16

    \(X_{res}\)
    的范数远小于
    CLIP-L
    /
    14
    的范数;
    2

    CLIP-B
    /
    16
    中的注意力修改在
    q-k
    基线之上表现出一致的改善,而
    CLIP-L
    /
    14
    中的情况则没有。

因此,当
\(X_{res}\)
的影响(或范数)最小化时,注意力修改才是有效的。换句话说,
\(X_{res}\)
显著削弱了
CLIP
在密集推断任务上的表现。

为了验证这一假设,基于
CLIP-B
/
16
使用
\(X_{{sum}}\)

\(X_{{res}}\)

\(X_{{attn}}\)
进行开放词汇语义分割实验。
COCOStuff
数据集上的实验结果如图
3
所示,发现
\(X_{res}\)

mIoU
接近于零,这表明残差连接可能对图像分割没有帮助。相反,仅使用
\(X_{{attn}}\)

mIoU
显著高于
\(X_{{sum}}\)
。图
3
中的可视化结果表明,
CLIP
的噪声分割图可以分解为一个模糊的
\(X_{{res}}\)
图和一个更清晰的
\(X_{{attn}}\)
图。根据这些实验结果,可以初步得出结论:分割图中的噪声主要来源于残差连接。

为了进一步证明
\(X_{res}\)
如何影响
CLIP
的性能,引入了一个缩放因子
\(\alpha\)
,使得
\(X_{{sum}} = X_{{res}} + \alpha X_{{attn}}\)
,该因子控制
\(X_{attn}\)
相对于
\(X_{res}\)
的相对影响。实验表明表明更大的
\(\alpha\)
显著提升了性能,这清楚地说明了
\(X_{{res}}\)
对性能的不利影响。

最后,论文建议直接舍弃残差连接以在密集的视觉-语言推理任务中实现最佳性能。

舍弃前馈网络(
FFN

Transformer
架构中的前馈网络(
FFN
)在建模数据中的关系和模式方面起着至关重要的作用,但最近的研究显示,
FFN
在推理过程中对图像表示的影响微乎其微。最后一个注意力模块中的
FFN
特征与最终分类特征的余弦角度明显更大,因此建议在密集预测任务中舍弃
FFN

在应用于基础
CLIP
模型时,论文发现移除
FFN
对开放词汇语义分割任务的影响较小。但当与去除残差连接相结合时,舍弃
FFN
会导致结果的改善,特别是在模型规模较大的情况下。这种改进的原理在于,去除残差连接显著改变了
FFN
的输入,从而影响其输出。因此,去除
FFN
的输出可能会减轻其对性能的负面影响。

自注意力机制

基于上述分析,使用最后一个自注意力层的注意力输出用于视觉-语言推理。

\[\begin{equation}
X^{{visual}} = X_{{attn}} = {Proj}({Attn}_{(\cdot) (\cdot)} \cdot v),
\label{eq:solution}
\end{equation}
\]

受到之前工作的启发,可以在注意力机制
\({Attn}_{(\cdot) (\cdot)}\)
中使用不同的查询-键组合。实际上,
\({Attn}_{qq}\)
在大多数情况下始终能够实现更好的性能,因此选择默认使用它。

主要实验




如果本文对你有帮助,麻烦点个赞或在看呗~
更多内容请关注 微信公众号【晓飞的算法工程笔记】

work-life balance.

在数据结构中,队列可以对应我们生活中的排队现象,像买早点排队,上公共汽车排队等。但是有一些情况,我们要优先某些元素,比如:上公共汽车时,虽然在排队,还是要优先老幼病残孕先上车;当有多个电脑向打印机发送打印请求时,一台电脑要打印100页,而其他电脑都是单页打印,此时更合理的做法时,优先打印单页的请求,最后再打印100页的请求。虽然我们都向往公平,在排队时也讲究先来后到,但是在某些特殊的情况下,还是要允许加塞现象的。这就是今天要给大家讲的——
优先队列

优先队列也是队列,那么最基本的两个操作是必须有的,那就是入队和出队操作。我们能想到的几种简单的实现方法有,比如一个简单的链表,入队时就在链表的最后添加元素,那么出队时就要遍历整个链表,找出最小元素,这显然不是一个好的方案。或者我们直接使用AVL平衡二叉树,最小元素就是最左侧的子节点,很容易找到,但是在入队和出队的过程中,涉及到了节点的增加和删除,那么就要进行树的旋转而维持树的平衡,这额外花费了很多开销。那么有没有相对廉价一点的方案呢?这就是
二叉堆
的方案。

二叉堆

优先队列的实现使用二叉堆是相当普遍的,二叉堆是一棵二叉树,但是是有要求的二叉树,它是一棵
完全二叉树
。完全二叉树就是树的节点都是从上到下,从左到右去排列的,而且中间不能隔有空节点。我们看下图中的两个例子:

左图中,J节点并没有按照从左到右依次排列,所以不是完全二叉树,而右图中,满足完全二叉树的特点,是一棵完全二叉树。

二叉堆有连个性质,一个是结构性质,一个是堆序性质。我们先来看结构性质,堆是一棵完全二叉树,是非常有规律的。我们可以直接用数组去表示二叉堆,而不使用链的结构,看下图:

数组中第0个元素我们空着不用,第1个元素是根节点,后面的顺序就是按照完全二叉树的顺序去排。通过观察,我们惊奇的发现了如下的规律,数组中第i个元素的左子节点的位置是2i,右子节点的位置是2i+1,父节点的位置是i/2(根节点除外)。我们可以使用数组的结构表示树,而不是使用链的结构,这使得我们在遍历树的时候操作非常简单。但是数组的结构也有一个问题,那就是数组的长度需要预先估算出来,然后随着数组长度的增加我们还要对其进行扩容操作。这就是二叉堆的结构性质,我们可以使用数组去表示。

接下来我们再看看堆序性质,由于我们快速的找到最小元素,那么最小元素我们要放到根节点上。同理,我们考虑到任意子树也是一个二叉堆,那么子树中的最小元素应当在子树的根节点。那么也就是任意节点都应该小于它的后代节点。所以二叉堆的堆序性质就是,对于二叉堆中的任意节点,它的父节点要小于或等于该节点。我们再看下面两个例子:

左图中节点6的父节点是21,小于6,不满足堆序性质,所以左图不是二叉堆。右图满足堆序性质,是二叉堆。

插入

当我们向二叉堆中插入一个新的元素时,为了满足二叉堆从上到下,从左到右的性质,我们先确定插入元素的位置,然后再和该位置的父节点作比较,如果大于父节点,那么是满足二叉堆性质的,直接插入就好了;如果不满足,则需要交换两个元素的位置,交换后再去和父节点作比较,就这样一直递归下去,直到满足二叉堆性质为止,或者交换到了根节点,是二叉堆中的最小元素。还使用上面的例子,比如我们要插入新的元素14,

由于14小于21,需要继续向上调整,

调整到这个位置时,满足了二叉堆的性质,我们把14插入。这样的一个整个过程就做
上滤
。下面我们编写程序实现这一过程。

/**
 * 二叉堆
 * @param <T>
 */
public class BinaryHeap<T extends Comparable<T>> {

    private static final int DEFAULT_CAPACITY = 10;
    private int currentSize;
    private T[] array;

    public BinaryHeap() {
        this(DEFAULT_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public BinaryHeap(int defaultCapacity) {
        this.currentSize = 0;
        this.array = (T[])new Comparable[defaultCapacity];
    }

    /**
     * 二叉堆是否为空
     * @return
     */
    public boolean isEmpty() {
        return this.currentSize == 0;
    }

    /**
     * 使二叉堆为空
     */
    @SuppressWarnings("unchecked")
    public void makeEmpty() {
        this.currentSize = 0;
        this.array = (T[])new Comparable[DEFAULT_CAPACITY];
    }

    /**
     * 扩展数组
     * @param newSize 扩展数组大小
     */
    @SuppressWarnings("unchecked")
    private void enlargeArray(int newSize) {
        if (newSize < this.array.length) {
            throw new RuntimeException("扩展数组小于原始数组");
        }

        T[] tmpArray = (T[])new Comparable[newSize];
        System.arraycopy(this.array,0,tmpArray,0,this.array.length);
        this.array = tmpArray;
    }


    /**
     * 二叉堆插入元素
     * @param element 插入元素
     */
    public void insert(T element) {
        if (currentSize == this.array.length-1) {
            enlargeArray(this.array.length * 2 - 1);
        }

        int hole = ++currentSize;
        for (this.array[0] = element;element.compareTo(this.array[hole/2]) < 0;hole /= 2) {
            this.array[hole] = this.array[hole/2];
        }
        this.array[hole] = element;
    }
}

由于二叉堆中的元素是可比较的,所以我们定义了泛型,必须实现了
Comparable
接口。然后我们定义数组
array
,和数组的初始长度
DEFAULT_CAPACITY
。最后再定义二叉堆当前的节点数
currentSize
。两个构造函数和
isEmpty

makeEmpty
方法比较简单,这里不做过多介绍了。接下来我们看一下数据扩容的方法
enlargeArray
,先比较一下新的长度和数组当前长度,如果小于,则抛出异常。然后就是创建新数据,数据复制,替换老数据。

接下来我们重点看一下
insert
方法,先判断
currentSize
和数组长度-1,这里为什么要减1呢?因为数据的第0个元素是不用的,二叉堆的根节点在第1个元素。如果相等,说明数组已经用尽,需要扩容,扩容的时候也是采用2倍扩容,这里减1还是因为不用根节点。然后先确定空穴的位置,
hole=++currentSize
,下面的for循环,就是上滤的过程,也是这一段的精华。大家在实现的时候,可能都会和父元素作比较,然后进行交换,这种方法没有问题,但是交换两个元素要用3行代码来完成,先把第一个变量赋值给临时变量,再把第二个变量赋值给第一个变量,最后把临时变量赋值给第二个变量。而这里只使用了1行代码,这就是使用空穴位置的好处。在for循环中,将新元素赋值给第0个元素,这里使用第0个元素是有用处的,我们接着看,然后新元素和父节点作比较,父节点的下标是hole/2,这个在前面介绍过,如果小于,当前空穴位置的值就是父节点的值,然后处理空穴的位置,就是父节点的位置,hole /=2。如果这样一直到了根节点,也就是hole=1的时候,父节点是不存在的,但是程序中写的是hole/2,那么就是第0个元素,第0个元素就是新插入的元素,等于是自己和自己比较,是相等的,所以就跳出了循环。最后把空元素的值赋给空穴位置。这里我们巧妙的使用第0个元素,实现了根节点的比较,使得跳出循环。

删除最小值

删除最小值,就是我们的出队操作,由于我们使用二叉堆,所以最小值就在根节点,删除之后,在根节点产生了一个空穴,我们把二叉堆的最后一个元素,也就是currentSize的元素放到空穴位置,再和两个子节点的最小元素作比较,如果大于,则交换两个元素,空穴位置下移,直到满足二叉堆的性质为止。这个过程叫
下滤

删除根节点13后,产生一个空穴,同时,整个数组长度减1,我们用最后一个元素31,和空穴的最小子节点14作比较,31大于14,所以交换位置,如下:

继续比较,31大于最小子节点21,空穴位置下移,

最后,31小于子节点32,那么31就放在空穴位置,满足了二叉堆的性质,整个下滤过程结束。我们用代码实现一下,

/**
 * 取出最小值
 * @return 根元素
 */
public T deleteMin() {
    if (isEmpty()) {
        throw new RuntimeException("二叉堆为空");
    }
    T minItem = this.array[1];
    this.array[1] = this.array[currentSize--];
    perlocateDown(1);

    return minItem;
}

/**
 * 下滤过程
 * @param hole
 */
private void perlocateDown(int hole) {
    int child;
    T tmp = this.array[hole];
    for (;hole * 2 <= currentSize;hole=child) {
        child = hole * 2;
        if (child != currentSize && this.array[child].compareTo(this.array[child+1]) > 0) {
            child += 1;
        }
        if (this.array[child].compareTo(tmp) < 0) {
            this.array[hole] = this.array[child];
        } else {
            break;
        }
    }
    this.array[hole] = tmp;
}

deleteMin
方法很简单,就是取根节点元素,将最后一个元素赋值给根节点,节点个数减1,然后调用下滤方法。我们重点要看的就是下滤方法,入参是空穴的位置,传入的是1,也就是根节点的位置,我们将值赋给临时变量,这里根节点的值是二叉堆的最后一个元素。接下来我们进入循环,循环成立的条件是空穴位置有子节点,
hole*2 <= currentSize
。那么左子节点的位置是hole*2,右子节点是hole*2+1。这里我们特殊处理的是空穴是不是只有一个子节点,只有一个子节点的情况只会发生在二叉堆的最后的位置,如果
hole*2 == currentSize
,说明后只有一个子节点,而且只能是左子节点,这样,我们就能够找出hole的最小子节点了,判断的逻辑是:如果
hole*2 == currentSize
,那么hole只有一个左子节点,最小子节点就是hole*2;其他情况就需要比较左右子节点,谁小就用谁。这就是我们for循环中第一个if处的逻辑。后面的逻辑就比较简单了,如果hole的值大于最小子节点,就进行交换,hole下移,等于最小子节点的位置,直到跳出循环。最后将临时值赋给空穴位置。这就是整个的删除和下滤的过程。

构建二叉堆

最重点的插入和删除方法我们已经讲完了,那么如果给我们一个数组,我们怎么去构建一个二叉堆呢?我们还是要从二叉堆的性质入手,也就是结构性质和堆序性质。结构性质比较容易我们将第0个元素空着就可以了,那么堆序性质怎么解决呢?由于上面我们已经将下滤过程抽象成了一个方法,这也就不难实现了。我们先将最小的子树,通过下滤方法变成二叉堆,最小的子树的节点就是树中倒数第二层的节点,倒数第二层的节点中,有的节点有子节点,有的节点没有子节点,没有子节点的不用下滤,那么怎么找到有子节点的节点呢?我们之前有个变量currentSize,这是最后一个节点的位置,它的父节点是currentSize/2,也是最后一个有子节点的节点,然后我们向前循环,每个节点执行一遍下滤方法,直到根节点下滤完,那么整棵树就是一个二叉堆了。我们实现一下,

/**
 * 构建二叉堆
 * @param items
 */
@SuppressWarnings("unchecked")
public BinaryHeap(T[] items) {
    this.currentSize = items.length;
    this.array = (T[])new Comparable[this.currentSize * 2 +1];
    int i = 1;
    for (T item: items) {
        this.array[i++] = item;
    }
    buildHeap();
}

/**
 * 构建二叉堆
 */
private void buildHeap() {
    for (int i = this.currentSize / 2;i>0;i--) {
        perlocateDown(i);
    }
}

实现起来很简单,这里注意一下循环的时候,条件是
i>0
,不是大于等于,因为第0个元素是不用的。

总结

好了,到这里二叉堆就介绍完了,它是实现优先队列最基本的方法,有问题的小伙伴欢迎评论区留言~~

C# 13 即 .Net 9 按照计划会在2024年11月发布,目前一些新特性已经定型,今天让我们来预览其中的一个新特性:

作者注:该特性虽然随着 C# 13 发布,但是仍然是处于 preview 状态的特性,请谨慎使用

半自动属性 Semi-auto properties

大家都知道,C# 早在 3.0 时候就添加了
自动属性
这个特性,让我们一起来回顾一下自动属性 :

public string Name { get; set; }

以上代码等价于下面的全手动实现的属性:

private string _name;

public string Name
{
    get
    {
        return _name;
    }
    set
    {
        _name = value;
    }
}

然后在C# 6.0 中,支持了 lambda 表达式来稍微简化一下

private string _name;

public string Name
{
    get => _name;
    set => _name = value;
}

可以看到,自动属性这个特性极大的方便了属性的书写,省略了大量的繁琐代码,手动属性需要自己手动声明属性背后对应的私有字段。

但是,当我们需要在获取或设置属性时自定义一些逻辑时,自动属性就无能为力了,只好退化成手动实现的属性,例如

 private string _name;

 public string Name
 {
     get => _name;
     set => _name = "Hello " + value;
 }

现在,C# 13 通过引入 field 关键字来解决这个问题,在允许自定义逻辑的基础上,可以不必自行声明对应的字段。

以上代码可以写成:

public string Name
{
    get => field;
    set => field = "Hello " + value;
}

进一步的,我们可以把 get 改成全自动属性的写法,也是支持的

public string Name
{
    get;
    set => field = "Hello " + value;
}

可以看到,半自动属性将极大的方便我们在拥有自定义逻辑字段上的代码编写。提高了代码的可读性,以及避免了字段名称的污染。

题外话,field 是一个上下文关键字,只在属性代码块中有效,例如在方法中使用 field 将不产生任何效果

public string Test()
{
    return field; // ERROR: The name 'field' does not exist in the current context
}

破坏性更新

需要注意的是,引入这个 field 关键字是一个破坏性更新,例如你的原有代码:

public int Age
{
    get
    {
        var field = 18;
        return field;
    }
}

原有代码里存在以 field 为名字的变量的话,当升级到 C# 13 时将改变行为,现在这个属性将返回 field 默认值"
0"
而不是期望的 "
18 "

你需要进行如下修改以避免变量 field 被识别为关键字

public int Age
{
    get
    {
        var field = 18;
        return @field;
    }
}

结尾

这个特性经过数次的易稿,field 关键字也经过数次变更才最终确定,终于在今年推出了。

看起来一个简单的功能,但是在背后有千丝万缕的关系,以及存在的破坏性更新,可以看出 C# 团队在推出功能时需要考虑及照顾的东西有很多,所以速度难免会被拖慢。

最后,当前这个特性已经在 Visual Studio 2022 17.12 Preview 3.0 中实装,需要把 C# 语言版本设置为preview,大家可以自行尝试一下。

参考

csharplang/proposals/field-keyword.md at main · dotnet/csharplang

Proposal:
field
keyword in properties · Issue #140 · dotnet/csharplang