【CSP试题回顾】202305-2-矩阵运算

CSP-202305-2-矩阵运算

关键点总结:改变矩阵计算顺序优化时间复杂度

通过先计算 K T × V K ^ T \times V KT×V 而不是先计算 Q × K T Q \times K ^ T Q×KT,有效地减少了计算时间,特别是在处理长序列时。这种优化通常在数据维度一不等时有显著效果,特别是当序列长度显著大于向量维度时。

1.原始的计算顺序

在Transformer的自注意力机制中,给定矩阵 Q Q Q(查询), K K K(键)和 V V V(值),计算首先涉及到以下步骤:

  1. 计算 Q × K T Q \times K ^ T Q×KT(查询和键的点积),得到注意力得分矩阵。
  2. 将注意力得分矩阵乘以 V V V(值矩阵),得到加权的值,这是最终的输出。

原始计算的时间复杂度主要由 Q × K T Q \times K ^ T Q×KT 的计算决定,这个操作的时间复杂度为 O ( n 2 ⋅ d ) O(n ^ 2 \cdot d) O(n2d),其中 n n n 是序列长度(例如,句子中的单词数量或向量数量), d d d 是向量的维度。当 n n n 很大时,这个操作非常耗时。

2.代码中的计算顺序

代码中采取了不同的计算顺序:

  1. 首先,它通过与 W W W 相乘来调整 Q Q Q 中的每个元素(这对应于自注意力机制中的缩放操作,但在这个特定的实现中, W W W 似乎用于不同的目的,比如加权或转换,这并不是标准的自注意力机制的一部分)。

  2. 然后,它计算 K T × V K ^ T \times V KT×V,这个操作的时间复杂度为 O ( n ⋅ d 2 ) O(n \cdot d ^ 2) O(nd2),因为它是在矩阵 K T K ^ T KT(维度 d × n d \times n d×n)和矩阵 V V V(维度 n × d n \times d n×d)之间进行的。

  3. 最后,它计算调整后的 Q Q Q K T × V K ^ T \times V KT×V 的结果,时间复杂度为 O ( n ⋅ d 2 ) O(n \cdot d ^ 2) O(nd2)

3.时间复杂度比较

n > d n > d n>d(即,序列长度大于向量维度)时,代码中的计算顺序比原始计算顺序更有效率。原始方法的复杂度主要是由序列长度的平方决定的,而代码中的方法将这个平方项降低到了 n n n d d d 的乘积,这在大多数实际情况下会减少计算量,尤其是在处理长序列时。

解题思路

搞清楚上面的点后,本质上就是简单的矩阵乘法,留意本题关于矩阵点乘计算规则的定义即可。

完整代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {  

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long long n, d;
    cin >> n >> d;

    vector<vector<long long>>Q(n, vector<long long>(d));
    vector<vector<long long>>K_T(d, vector<long long>(n));
    vector<vector<long long>>V(n, vector<long long>(d));
    vector<long long>W(n);

    // 输入Q
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < d; j++)
        {
            cin >> Q[i][j];
        }
    }
    // 输入K_T
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < d; j++)
        {
            cin >> K_T[j][i];
        }
    }
    // 输入V
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < d; j++)
        {
            cin >> V[i][j];
        }
    }
    // 输入W
    for (int i = 0; i < n; i++)
    {
        cin >> W[i];
    }

    // 计算 W * Q
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < d; j++)
        {
            Q[i][j] *= W[i];
        }
    }
     
    // 计算 K_T * V
    vector<vector<long long>>T1(d, vector<long long>(d));
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < d; j++)
        {
            for (int k = 0; k < n; k++)
            {
                T1[i][j] += K_T[i][k] * V[k][j];
            }
        }
    }

    // 计算 Q * T1
    vector<vector<long long>>T2(n, vector<long long>(d));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < d; j++)
        {
            for (int k = 0; k < d; k++)
            {
                T2[i][j] += Q[i][k] * T1[k][j];
            }
        }
    }

    for (const auto& it : T2) {
        for (const auto& jt : it) {
            cout << jt << " ";
        }
        cout << endl;
    }

    return 0;
}

请添加图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/427974.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

盘点:国家智能算力中心

文章目录 1. Main2. My thoughtsReference 1. Main 按照《中国算力白皮书&#xff08;2022年&#xff09;》的定义&#xff0c;算力主要分为四部分&#xff1a;通用算力、智能算力、超算算力、边缘算力。通用算力以CPU芯片输出的计算能力为主&#xff1b;智能算力以GPU、FPGA、…

DevStack 基于 Ubuntu 部署 OpenStack

Devstack 简介 DevStack 是一系列可扩展的脚本&#xff0c;用于基于 git master 的最新版本快速调出完整的 OpenStack 环境。devstack 以交互方式用作开发环境和 OpenStack 项目大部分功能测试的基础。 devstack 透过执行 stack.sh 脚本&#xff0c;搭建 openstack 环境&…

检修弧形导轨需遵守的原则

弧形导轨被广泛应用在各行各业中&#xff0c;特别是工业自动化领域中&#xff0c;是自动化机械设备中重要的传动零部件。在使用弧形导轨时&#xff0c;为防止意外发生或对机械设备造成损坏&#xff0c;在检修过程中必须遵守以下一些原则&#xff1a; ●安全第一&#xff1a;出现…

java核心面试题汇总

文章目录 1. Java1.1. TCP三次握手/四次挥手1.2 HashMap底层原理1.3 Java常见IO模型1.4 线程与线程池工作原理1.5 讲一讲ThreadLocal、Synchronized、volatile底层原理1.6 了解AQS底层原理吗 2. MySQL2.1 MySQL索引为何不采用红黑树&#xff0c;而选择B树2.2 MySQL索引为何不采…

蓝凌EIS智慧协同平台 rpt_listreport_definefield.aspx SQL注入漏洞复现

0x01 产品简介 蓝凌EIS智慧协同平台是一款专为企业提供高效协同办公和团队合作的产品。该平台集成了各种协同工具和功能,旨在提升企业内部沟通、协作和信息共享的效率。 0x02 漏洞概述 由于蓝凌EIS智慧协同平台 rpt_listreport_definefield.aspx接口处未对用户输入的SQL语句…

一.数据分析简介

目录 一、了解数据分析 1.1 什么是数据分析 1.2 数据分析的重要性 1.3 数据分析的基本流程 数据获取 数据处理 1.4 数据分析的应用场景 客户分析 营销分析 二、数据分析工具 jupyter 2.1 编辑器安装 2.2 Jupyter快捷使用 一、了解数据分析 学习数据分析&#xff0…

【在巴厘岛学点印尼语】日常篇

BINTANG BIR 槟棠啤酒 今天不写代码&#xff0c;在巴厘岛休养&#xff0c;顺便聊点印尼语。 印尼语&#xff0c;Bahasa Indonesia&#xff0c;是印度尼西亚的官方语言&#xff0c;也即印尼化的马来语廖内方言&#xff0c;其变种包括 爪哇语&#xff08;岛民方言&#xff09; 等…

振弦式埋入应变计:工程安全的精准守护者

振弦式埋入应变计是一种先进的工程监测设备&#xff0c;以其卓越的性能和稳定的可靠性&#xff0c;广泛应用于水工建筑物及其他混凝土结构物的长期安全监测中。峟思振弦埋入式应变计的核心部件采用进口钢弦制成&#xff0c;保证了其使用寿命的长久性。同时&#xff0c;主要构件…

Java面试题总结200道(二)

26、简述Spring中Bean的生命周期&#xff1f; 在原生的java环境中&#xff0c;一个新的对象的产生是我们用new()的方式产生出来的。在Spring的IOC容器中&#xff0c;将这一部分的工作帮我们完成了(Bean对象的管理)。既然是对象&#xff0c;就存在生命周期&#xff0c;也就是作用…

【云呐】固定资产条码管理系统有哪些优势

在当今信息时代&#xff0c;企业越来越重视固定资产的管理。传统的固定资产管理方法已经无法满足公司日益增长的需求&#xff0c;固定资产条形码管理系统的出现给企业带来了全新的解决方案。下面我们就讨论固定资产条形码管理系统的优势以及对公司的价值。 提升资产管理效率 固…

【Python】进阶学习:pandas--read_csv()用法详解

&#x1f680;【Python】进阶学习&#xff1a;pandas–read_csv()用法详解&#x1f680; &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教…

有效防止CDN网站被溯源ip的教程

如何反溯源隐藏自己的源IP防止溯源&#xff1f; 还有些大牛会进行渗透攻击、CC攻击&#xff0c;溯源打服务器&#xff0c;各式各样的&#xff0c;防不胜防。所以很多站长套起了cdn&#xff0c;比起cdn提供的加速效果&#xff0c;更多的站长可能还是为了保护那可怜弱小的源站ip…

Docker创建Reids容器

1.默认拉取Redis最新镜像版本 docker pull redis 2.下载redis配置文件 https://download.redis.io/releases/ 3.下载配置文件后手动更改密码&#xff0c;链接时间等信息 绑定地址&#xff08;bind&#xff09;&#xff1a;默认情况下&#xff0c;Redis 只会监听 localhost…

LaTeX排版论文的常见问题汇总(持续更新中)

文章目录 LaTeX排版论文的常见问题汇总&#xff08;持续更新中&#xff09;1.如何上传期刊或会议提供的LaTeX模板&#xff1f;2.模板中各文件的说明3.LaTeX中如何设置字体大小&#xff1f;3.1如何设置表格中的字体大小&#xff1f;3.2如何设置表格、图片标题的字体大小&#xf…

【C++】类和对象之初始化列表与static成员

个人主页 &#xff1a; zxctscl 文章封面来自&#xff1a;艺术家–贤海林 如有转载请先通知 文章目录 1. 前言2. 再谈构造函数2.1 构造函数体赋值2.2 初始化列表2.3 explicit关键字 3. static成员3.1 概念3.2 特性 1. 前言 在前面的博客中已经分享有关构造函数 【C】构造函数和…

数字经济的下一步:Web3的潜力与前景

引言&#xff1a; 随着区块链技术的迅速发展&#xff0c;数字经济正迎来新的变革时代。在这个数字化时代&#xff0c;Web3作为区块链技术的延伸和演进&#xff0c;正在成为全球数字经济发展的重要方向。本文将深入探讨Web3的潜力与前景&#xff0c;以及它对数字经济发展的深远…

Vue2+ElementUI列表、表格组件的封装

Vue2ElementUI列表组件的封装&#xff1a;引言 在日常开发中&#xff0c;我们经常会遇到需要展示列表数据的场景。ElementUI 提供的 el-table 组件是一个功能强大的表格组件&#xff0c;可以满足大部分的需求。但是&#xff0c;在实际应用中&#xff0c;我们往往需要根据业务需…

【嵌入式——QT】QTreeWidget

QTreeWidget类是创建和管理目录树结构的类&#xff0c;QTreeWidget每一个节点都是一个QTreeWidgetItem对象&#xff0c;添加一个节点前需先创建。QTreeWidget类是一个便利类&#xff0c;它提供了一个标准的树widget&#xff0c;具有经典的基于item的界面&#xff0c;类似于Qt 3…

2024智能遥控器行业市场规模及技术水平分析

智能遥控器&#xff0c;主要是由集成电路板和用来生产不同讯息的按钮所组成&#xff0c;内装有一个中央处理器芯片&#xff0c;芯片在制造时就将设备各种菜单码值信息输入其中&#xff0c;遥控发射器只要发出与之对应的密码就可以实现对设备的控制。无线遥控技术原理就是发射机…

【kubernetes】关于k8s集群的污点和容忍,以及k8s集群的故障排查思路

目录 一、污点 关于污点的增删改查 验证污点的作用——NoExecute ​编辑 验证污点的作用——NoSchedule 验证污点的作用——PreferNoSchedule 二、容忍 三、关于cordon 和 drain 四、Pod启动阶段 五、关于pod的五种状态 六、k8s常见的排障手段 针对组件故障 针对pod…