普通视图

Parquet 文件简介: Python 读写 Parquet 文件实战

Parquet 文件入门 Python 读写 Parquet 文件实战 大数据存储优化:Parquet 格式解析 Python 数据分析必备:Parquet 文件处理技巧 列式存储揭秘:Parquet 文件与性能优化 使用 Python 和 PyArrow 处理嵌套 Parquet 数据 从 CSV 到 Parquet:Python 数据格式转换教程

什么是 Parquet 文件?

Parquet 是一种列式存储文件格式,优化用于大规模数据处理。它常用于 Apache Spark、Hadoop 和 Pandas 等大数据框架,以实现高效存储和快速检索表格数据。 Parquet 格式可以简单认为是CSV的转置/Transpose。不过CSV是文本的,而Parquet是二进制的。从存储方式上理解列式存储就像把行列交换,但需要注意 Parquet 是二进制、支持压缩和嵌套类型,不仅仅是“转置”。

为什么使用 Parquet?

  • 列式存储:按列存储数据,提高分析任务的查询性能。
  • 压缩:支持高效的压缩技术,减少存储空间。
  • 兼容性:可与多种数据处理框架配合使用。
  • 模式演进:支持增加或删除列而不破坏现有数据。

安装所需库

要在 Python 中使用 Parquet,需要 pandaspyarrow(或 fastparquet):
pip install pandas pyarrow

在 Python 中读取 Parquet 文件

以下示例演示如何使用 pandaspyarrow 读取 Parquet 文件:
import pandas as pd
import pyarrow.parquet as pq

# Parquet 文件路径
file_path = "example.parquet"

# 读取 Parquet 文件到 DataFrame
df = pd.read_parquet(file_path)

# 显示前 5 行
print(df.head())

写入 Parquet 文件

你也可以轻松地将 DataFrame 保存为 Parquet 文件:
import pandas as pd

# 创建示例 DataFrame
data = {
    "name": ["Alice", "Bob", "Charlie"],
    "age": [25, 30, 35],
    "city": ["London", "Paris", "New York"]
}
df = pd.DataFrame(data)

# 保存为 Parquet
df.to_parquet("output.parquet", engine="pyarrow", index=False)

处理嵌套数据

Parquet 支持嵌套数据,如列表或结构体。可以使用 pyarrow 直接读取:
import pyarrow.parquet as pq
from io import BytesIO

# 直接读取 Parquet 文件
table = pq.read_table("example.parquet")
df = table.to_pandas()
print(df.head())

总结

Parquet 文件在存储和处理大规模表格数据时非常高效。使用 Python 的 pandaspyarrow,你可以轻松地读取、写入并处理 Parquet 文件,用于数据分析、ETL 流程和大数据应用。 [show_file file="/var/www/wp-post-common/justyy.com/python.php"] 英文:Introduction to Parquet Files: Read & Write using Python

相关文章:

  1. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
  2. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
  3. 第一次私校家长会: 原来家长比孩子还卷 前几天参加了娃的第一次家长会,和几位家长聊下来,真是个个都很厉害。不光孩子们卷,家长也一样卷,一眼望去基本都是 Dr/博士。娃还调侃我一句:“这有什么的,你不也是 Dr 吗?” 我心里默默想:还好没写学校名字,不然我这野鸡大学的头衔真拿不出手 😂。 私校里真是人才济济,乐器过 8 级的太常见了,卷得不得了。我还问过娃,是想当 big fish in a small pond...
  4. 如何通过二分查找搜索在区块链上根据时间戳定位区块? 前两天,我想查一下自己在 STEEM 区块链上一些重要记录对应的区块号,比如: 注册了我的账号 #4253590 成为见证人 #20190755 挖到我的第一个区块 #20390040 被孙宇晨大佬代理了 SP #41676911 收到一笔 DAO 收入...
  5. MySQL参数一键配置脚本: 有效提升数据库性能 我一直是自己租用VPS服务器,然后搭建各种服务,比如博客就是Apache2+MySQL数据库。一般来说就是默认参数,没有去管,不过最近发现MySQL的性能参数都很保守,不能发挥整个服务器的性能。 然后我就网上搜索了一下,根据参数配置建议,用ChatGPT写了以下Python和BASH脚本。只需要在需要优化的服务器上,跑一下该脚本,然后就会显示参数配置,然后直接把参数添加到MySQL数据库配置参数文件上: /etc/mysql/mysql.conf.d/mysqld.cnf 然后运行: service mysql restart 重启MySQL服务器。 运行了几周,发现效果很好,博客反应速度也快了很多,这很大原因是根据了内存增加了MySQL缓存大小。 Python脚本优化MySQL数据库参数 把下面的Python脚本存成 mysql_config.py 然后运行 python3 mysql_config.py...
  6. 英国抓捕比特币ATM主犯: 所有与法币挂钩的加密活动必须获得许可 英国查获比特币ATM主犯:所有与法币挂钩的加密业务必须持牌 案件回顾:比特币ATM运营者被判四年 在2025年2月,英国金融行为监管局(FCA)宣布成功起诉并判刑首位非法运营比特币ATM的个人——Olumide Osunkoya。该男子未经授权在伦敦多地运营加密ATM,处理交易金额达260万英镑。他曾试图注册合法业务但被拒,随后伪造身份文件绕过监管,最终被法院判处4年有期徒刑。 最新行动:7台ATM被查封,两人被捕 紧接着在2025年7月,FCA与伦敦警察再次联合行动,在西南伦敦多个地点查封7台非法加密ATM,并拘捕2人。FCA重申:在英国,没有任何加密ATM获得合法运营许可,所有涉及法币兑换的活动必须事先注册并获得批准。 英国FCA官网原文指出:“我们提醒所有经营者,若他们继续运营未注册的加密ATM,将面临刑事起诉。”(原文链接见参考资料) 为什么这些ATM是非法的? 在英国,只要涉及“加密货币 ↔ 法币”的兑换行为,就会被纳入《反洗钱条例(MLRs)》的监管框架。运营者必须: 向FCA注册为加密资产公司 实施KYC(身份验证)和AML(反洗钱)程序 接受FCA的持续监管与合规审核 未经注册即开展此类活动,属于违法行为。...
  7. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. /** MySQL...
  8. 比特币最近波动有点大: 一天牛市一天熊 比特币10万美金以内都是最后上车的机会! 比特币近期的价格波动可以归因于多个关键因素,包括地缘政治动态、监管变化以及加密行业内的重大安全事件。其中一个主要影响因素是美国前总统唐纳德·特朗普对乌克兰和加密货币监管的立场变化。据报道,特朗普再次当选,他可能会推动减少美国对乌克兰的支持,这可能会影响全球金融市场和风险偏好。同时,特朗普正在将自己塑造为亲加密货币的候选人,表示有意让美国成为一个更加友好的加密货币环境。这一立场引发了市场对监管政策可能发生变化的猜测,导致市场情绪在乐观和不确定性之间波动。 特朗普对俄乌战争的态度 美国第43届总统唐纳德·特朗普已经在2025年1月当选并正式上任(第二次),那么他的政策可能会对比特币价格的波动产生更加直接和显著的影响。他政府对乌克兰和加密货币监管的立场已经不再是猜测,而是正在实际塑造市场的关键力量。 特朗普(Donald Trump)减少美国对乌克兰的支持,全球投资者可能会预期地缘政治稳定性发生变化,从而增加对比特币作为避险资产的需求。同时,他的亲加密货币立场可能正在推动市场的乐观情绪。如果他的政府推出有利于加密行业的监管政策,例如明确的合规指南或减少监管审查,可能会吸引更多机构投资者进入市场,并促进更广泛的加密货币采用。然而,政策的快速变化也可能导致短期市场剧烈波动,因为市场需要时间来消化新的政策动向。 朝鲜黑客盗取Bybit交易所15亿美元的ETH 另一个显著影响比特币价格的事件是近期涉及朝鲜黑客组织“Lazarus”的15亿美元以太坊被盗案件。据报道,Bybit交易所(全球第二)这些被盗的ETH已经被清洗,此次大规模黑客攻击引发了人们对加密行业安全性的担忧。此类安全事件不仅会削弱投资者信心,还可能引发更严格的监管审查,导致短期市场动荡。此外,被盗资金的大规模流动和出售可能对市场流动性造成冲击,进一步加大价格波动。随着这些事件的持续发酵,比特币价格正受到政治决策、监管预期以及安全挑战等多重因素的影响。 与此同时,与朝鲜黑客组织 Lazarus 相关的 15 亿美元以太坊被盗事件仍在影响加密市场。由于这些被盗 ETH 已被清洗,人们对加密行业安全漏洞的担忧持续存在,同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起,共同导致了比特币近期的剧烈价格波动。...

使用原子 TAS 指令实现自旋锁

使用原子 TAS 指令实现自旋锁

使用原子 TAS 指令实现自旋锁 Implementing a Spinlock Using the Atomic TAS Instruction 从零实现自旋锁:基于 TAS 的最小同步原语 Building a Spinlock from Scratch with Atomic TAS 用 test-and-set 实现最简单的互斥锁 Implementing a Minimal Mutex Using Test-and-Set 自旋锁的底层原理:TAS、原子性与忙等待 Inside Spinlocks: TAS, Atomicity, and Busy Waiting 原子操作与自旋锁:用 C 语言实现线程同步 Atomic Operations and Spinlocks: Thread Synchronization in C 从原子指令到锁:全面理解 TAS 和自旋锁 From Atomic Instructions to Locks: A Complete Guide to TAS and Spinlocks 动手写一个自旋锁:tryLock / lockAcquire / lockRelease 全实现 Hands-On Spinlock Implementation: tryLock, lockAcquire, and lockRelease 你的第一个自旋锁:基于 C 语言的 TAS 实现 Your First Spinlock: A TAS-Based Implementation in C 原子交换与线程互斥:自旋锁实现指南 Atomic Exchange and Thread Mutual Exclusion: A Guide to Implementing Spinlocks
假设我们有一个 TAS(Take-And-Set)函数。该操作返回内存中原来的值,并以原子方式将其替换为新值。原子性(atomicity)意味着没有其他线程能够观察到中间状态;整个读-写操作是一体不可分的。 在 C++ 中,标准库函数 std::exchange 在逻辑上表现相同,但它不是原子操作。同步原语需要硬件级别的原子性。
int TAS(int* memory, int newVal) {
    int old = *memory;
    *memory = newVal;
    return old;
}
我们想使用这个原语来实现一个简单的自旋锁,包括:
  • lockAcquire()
  • lockRelease()
线程将调用这些函数来保护对共享变量的访问:
typedef struct {
    int lock;
} lockType;

typedef struct {
    int val;
} threadArgType;

void threadFunc(void* arg) {
    lockAcquire((static_cast<lockType*>arg)->lock);
    (static_cast<threadArgType*>arg)->val++;
    lockRelease((static_cast<lockType*>arg)->lock);
}

实现 tryLock

tryLock 函数尝试获取锁一次。如果锁为空(值为 0),TAS 将其设置为 1 并返回原值(0)。如果锁已被占用,TAS 返回 1。tryLock 函数是非阻塞的——它会立即返回。 因此 tryLock() 只有在 TAS 返回 0 时才会成功:
enum {
    UNLOCKED = 0,
    LOCKED = 1
}

int tryLock(lockType* lock) {
    // 如果之前已锁定返回 1,如果之前未锁定返回 0
    int old = TAS(lock->lock, LOCKED);
    return (old == UNLOCKED);   // true (1) = 成功获取锁
}

实现 lockAcquire()

普通的锁获取应当“自旋”直到 tryLock() 成功。这称为 自旋锁,因为 CPU 会忙等待。必要时可以加入短暂的 sleep。例如,sleep(0) 并不会真正暂停执行,而是让出 CPU,允许其他线程运行。 它通常用于实现跨线程的互斥自旋锁。
void lockAcquire(lockType* lock) {
    while (!tryLock(lockType* lock)) {
        // 自旋直到锁可用
    }
}
另一种实现:
void lockAcquire(lockType* lock) {
    do {
       if (tryLock(lockType* lock)) {
          break;
       }
    } while (1);
}
展开 tryLock:
void lockAcquire(lockType* lock) {
    do {
       int old = TAS(lock->lock, LOCKED);
       // 无论锁是否已被获取,锁都已设置为 LOCKED
       if (old == UNLOCKED) {
           break;
       }
    } while (1);
}
这是使用 TAS 实现的最简单方法。在实际系统中,我们可能会加入 pause 指令或退避策略,但基本思路是相同的。

实现 lockRelease()

释放锁时,持有者只需将锁变量写为 0。由于 TAS 是“设置新值并返回旧值”,它同样适用于释放锁:
void lockRelease(lockType* lock) {
    TAS(lock->lock, UNLOCKED);
}
或者使用简单的原子存储也足够,但由于 TAS 是我们唯一的工具,我们重用它。请注意,在这里重复释放锁是安全的,因为再次将其设置为 UNLOCKED=0 不会产生副作用。

总结

仅使用原子 TAS 指令,我们实现了:
  • 一个 tryLock() 尝试
  • 一个 lockAcquire() 自旋锁
  • 一个 lockRelease() 解锁操作
这种锁的实现方式对于理解低级并发、内存顺序以及高层互斥锁库的构建方式非常基础。 [show_file file="/var/www/wp-post-common/justyy.com/cpp.php"] 英文:Implement a Lock Acquire and Release in C++

相关文章:

  1. 简易教程: C++的智能指针 C++ 智能指针教程 C++ 中的智能指针提供了自动且安全的内存管理。它们通过 RAII(资源获取即初始化)机制,帮助开发者避免内存泄漏和悬空指针的问题,确保对象在生命周期结束时被正确释放。 本教程将介绍 C++ 中三种主要的智能指针: std::unique_ptr:独占式所有权 std::shared_ptr:共享式所有权 std::weak_ptr:非拥有式弱引用 1. std::unique_ptr unique_ptr 拥有独占所有权。一个资源只能被一个...
  2. C++中的 const和constexpr 比较 C++ const 与 constexpr:真正的区别是什么? 一眼看都是定义常量。 为什么这很重要 现代 C++ 鼓励编写不可变、高效且表达力强的代码。两个关键字—const 和 constexpr—是这一理念的核心。它们看起来很相似,但理解它们的不同语义,对于正确利用编译期与运行期行为至关重要。 高层次对比 特性 const constexpr...
  3. 被动收入之: 微博红包 今年开始重新经营我的微博帐号 drlai 收到两笔微信红包,应该是来自于官方的支持,150元(成功提现到支付宝)。虽然这不能持久,也没多少,但毕竟实现了零的突破,意义重大。 如果流量上来,内容创作者可能会接受到比较多的赞赏,这也是一个比较简单的变现方法。这也能作为一种被动收入,不过如果不是头部网红,可能杯水车薪,但如果你有好几个类似这样的,也能积少成多! 在用户中心,微博用户可以每天登陆手机微博APP打卡,获取点数和少量的红包钱(几分钱),积少成多! 微博做些小任务可获得积分和几分钱。聊胜于无。 微博的主要盈利模式 微博的主要盈利模式主要包括以下几个方面: 广告收入:微博的大部分收入来源于广告,尤其是品牌广告和效果广告。广告形式包括信息流广告(类似于推文广告)、热门话题广告、开屏广告和视频广告。品牌和企业可以利用微博庞大的用户群和社交互动来提升曝光率、推广品牌和产品。 会员服务:微博提供的VIP会员服务,用户可以支付订阅费用来享受更多的特权,比如个性化的主题、特有的表情包、私密权限设置等。这些会员服务主要面向个人用户,提升其社交体验。 直播和打赏:微博提供直播平台,用户可以通过购买虚拟礼物来支持主播,微博会从这些打赏中抽取一定比例的分成。此外,微博与内容创作者分成,通过内容付费、知识付费等形式变现。 增值服务:针对企业和大V(拥有大量粉丝的用户),微博还提供增值服务,如账号认证、粉丝数据分析、精准推送、推广和营销工具等。这些服务帮助企业提升营销效果,同时也增加了微博的收入来源。 电商和导流:微博上有大量的电商导流业务,尤其是和明星、网红的合作推广。微博用户在浏览社交内容时,可以直接跳转到商品购买链接,微博通过这种方式赚取导流佣金。 游戏联运:微博也会与一些游戏公司合作推出联合运营的游戏,微博负责推广和流量引入,用户充值或付费时,微博可以获得一部分的分成。 这些模式相结合,使得微博能够在广告市场、内容创作和电商等多个领域获利。...
  4. 借助AI快速开源了N个小工具: 写代码越来越像做产品了, AI 真把我宠坏了(Vibe Coding) 程序员的未来?Vibe Coding + AI 一起上! 借助 AI 快速开源了三个小工具 最近,我利用 ChatGPT-4o 和 o4-mini 快速开发并开源了几个小工具。起因其实很简单——每次想转换 YAML/JSON 或进行...
  5. 豪车的修理费用就是贵一些 去年买了保时捷卡宴SUV(Porsche Cayenne)后,我一直担心将来修车费用会很高。当时购车时,车厂做了一次全面保养,把车里里外外都清洁了一遍。虽然这辆车已经三年车龄,但看上去几乎和新车没区别。 在英国,三年以内的新车通常不需要做MOT年检。而且很多这类新车会通过PCP(个人合同购车)方式出租给车主。简单来说,就是车主每月支付一笔租金,租期通常为三年,期满后可以选择一次性付清尾款买下车辆,也可以继续换租一辆新车。 举个例子,如果一辆新车售价是10万英镑,车厂可能按未来三年折旧后的50%残值来计算每月租金。三年后,如果车主不想买断,车厂就会将车辆作为二手车卖出,回收那5万英镑的残值。这样一来,车厂基本不会亏钱。此外,PCP合同中还有附加条款,比如每年限行1万英里,超出的部分需要额外付费,这些内容都会写在合同里。 车龄到了三年,车辆需要首次做MOT年检,同时车辆的市场价值也会首次出现较大幅度的贬值(一般是50%,甚至更多)。修车厂老板告诉我,相比玛莎拉蒂等其他豪车,保时捷的保值率相对较高。 这一年我开这辆保时捷基本没出什么问题。今年年初做了年检,顺利通过。随后又做了一次常规保养,修车厂老板告诉我,前后刹车片已经磨损了80%–85%。我们住剑桥村里,开车比较多(上班、送娃、家庭旅游都要用车),一年大概能开1-2万英理。 几周后我将车送回去更换刹车片。修完后账单是将近900英镑。我觉得有点贵,车行老板解释说,不仅换了前后刹车片,还有一个前雷达的传感器掉进了车体内部,为了修这个传感器需要拆掉前保险杠等部件,花了6个小时人工费。 我当时质疑说为啥这次修这么贵,他说:“因为这是保时捷。”我说:“那和别的车有什么区别?”他说:“It is not the same.” 我说不都一样么,他说:“It is not...
  6. 重要通知: 弃用 FeedBurner RSS 请改用 https://justyy.com/feed 最近我发现原本的 RSS(/rss、/feed)没有按时更新。 进一步检查后发现这些地址都被 301 重定向到了 FeedBurner(https://feeds.feedburner.com/zhihua-xblog),而 FeedBurner 已经久未维护,偶有抓取失败或延迟,导致读者无法及时收到新文章。 造成这次重定向的原因是我们使用的第三方主题/插件(mytheme)里曾经内置了将站点 feed 转发到 FeedBurner 的功能。 当时之所以做 301...
  7. 换了个奥迪Q5大灯花了我1000英镑 我那辆奥迪Q5 SUV今年年检没通过,原因是左前车灯坏了,需要更换。车厂告诉我,光是订购零件就要700多英镑,加上人工费,总费用得1000英镑。但没办法,如果不修,车辆年检(MOT)就过不了,车也不能上路。 MOT是英国的机动车强制性安全检测(Ministry of Transport Test)的简称。 近侧前位置灯不工作 drl/位置灯集成(4.2.1(a)(ii)) Nearside Front Position lamp not working drl/position...
  8. 你给SteemIt中文微信群拖后腿了么? 这年头不缺算法, 就缺数据. 这两天花了很多时间在整API上, 整完之后自己用了一下还觉得真是挺方便的. 今天就突然想看一看自己是否给大家拖后腿了, 于是调用每日中文区微信群排行榜单的API, 刷刷拿着 NodeJs 练手: // @justyy var request = require("request")...

数学之美: Sigma 函数的推导公式与 Python 实现

理解 Sigma 函数:因子、乘法性与公式推导

一文看懂 Sigma 函数:因子分解的终极威力! σ(n) 完全解析:为什么求和函数能“自动”变成乘积? 数学之美:Sigma 函数的推导、公式与 Python 实现 从几何级数到质因数:Sigma 函数的魔法公式大揭秘 搞懂 σ(n) 的那一天,我看到了数学的秩序 为什么 σ(n) = 乘积?带你走进数论的核心思想 Divisor 终极指南:Sigma 函数推导 + 代码 一篇搞定
Sigma 函数,记作 [math]\sigma(n)[/math],表示一个整数所有正因子的和。 例如 12 的因子有 1、2、3、4、6、12,因此 [math]\sigma(12)=28[/math]。 本文解释什么是 Sigma 函数、为什么它满足乘法性、如何从质因数分解推导出通用公式,并给出高效的 Python 实现。

可除性符号

在数论中,符号 “|” 表示“整除”。 [math]d \mid a \quad \Longleftrightarrow \quad \exists k \in \mathbb{Z},\; a = dk[/math] 因此表达式 [math]\sum_{d \mid n} d[/math] 的意思是“对所有能整除 n 的 d 求和”。

质因数分解与因子的结构

任意正整数 [math]n[/math] 都可以唯一写成: [math]n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}[/math] 它的一个因子必须从每个质数的指数中“选择”一个: [math]d = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, \qquad 0 \le e_i \le a_i[/math] 所有因子结构的规律都来自这个事实。

关键性质:Sigma 函数是乘法性的

当两个整数互质时,Sigma 函数满足: [math]\sigma(mn) = \sigma(m)\,\sigma(n) \qquad \text{if} \gcd(m,n)=1[/math] 原因是:若 [math]m[/math] 和 [math]n[/math] 的质因数互不相同, 那么 [math]mn[/math] 的每个因子都能唯一写成: [math]d = d_m d_n, \quad d_m \mid m, \; d_n \mid n[/math] 因此对所有因子求和可以写成二重求和: [math]\sigma(mn) = \sum_{d_m \mid m} \sum_{d_n \mid n} d_m d_n[/math] 接下来把二重求和“拆开”。固定某个 [math]d_m[/math],则: [math]\sum_{d_n \mid n} (d_m d_n) = d_m \sum_{d_n \mid n} d_n = d_m \sigma(n)[/math] 再对所有 [math]d_m[/math] 求和: [math]\sigma(mn) = \sum_{d_m \mid m} d_m \sigma(n) = \sigma(n) \sum_{d_m \mid m} d_m = \sigma(n)\sigma(m)[/math] 这就证明了 Sigma 的乘法性。

质数幂的 Sigma 公式

利用乘法性,只需计算 [math]\sigma(p^k)[/math]。 其因子为: [math]1, p, p^2, \ldots, p^k[/math] 这是一个几何级数: [math]\sigma(p^k) = 1 + p + p^2 + \cdots + p^k = \frac{p^{k+1} - 1}{p - 1}[/math] 把所有质因数幂的贡献相乘,就得到通用公式: [math]\sigma(n) = \prod_{i=1}^k \frac{p_i^{a_i+1} - 1}{p_i - 1}[/math] 这就是任意正整数的因子和公式。

示例:计算 σ(12)

质因数分解: [math]12 = 2^2 \cdot 3^1[/math] 分别计算: [math]\sigma(2^2) = 1 + 2 + 4 = 7[/math] [math]\sigma(3^1) = 1 + 3 = 4[/math] 相乘: [math]\sigma(12) = 7 \cdot 4 = 28[/math]

Python 实现:高效的 Sigma 函数

以下是基于质因数分解与乘法性的高效Python实现,时间复杂度约为 [math]O(\sqrt{n})[/math]。
def sigma(n: int) -> int:
    """高效计算因子和函数 σ(n)。"""
    total = 1
    x = n

    # 处理质因数 2
    count = 0
    while x % 2 == 0:
        x //= 2
        count += 1
    if count > 0:
        total *= (2 ** (count + 1) - 1) // (2 - 1)

    # 处理奇质数
    p = 3
    while p * p <= x:
        if x % p == 0:
            count = 0
            while x % p == 0:
                x //= p
                count += 1
            total *= (p ** (count + 1) - 1) // (p - 1)
        p += 2

    # 若剩下的是质数
    if x > 1:
        total *= (x**2 - 1) // (x - 1)

    return total

结语

Sigma 函数展示了因子结构的优雅与质因数分解的力量。通过理解乘法性与几何级数求和,我们得到一个漂亮的闭式公式,并能编写高效的计算程序。有了理论与代码,你就能深入探索更多数论中的算术函数了。 [show_file file="/var/www/wp-post-common/justyy.com/math.php"] 英文:Understanding the Sigma Function: Divisors, Multiplicativity, and the Formula

相关文章:

  1. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
  2. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
  3. 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
  4. 第一次私校家长会: 原来家长比孩子还卷 前几天参加了娃的第一次家长会,和几位家长聊下来,真是个个都很厉害。不光孩子们卷,家长也一样卷,一眼望去基本都是 Dr/博士。娃还调侃我一句:“这有什么的,你不也是 Dr 吗?” 我心里默默想:还好没写学校名字,不然我这野鸡大学的头衔真拿不出手 😂。 私校里真是人才济济,乐器过 8 级的太常见了,卷得不得了。我还问过娃,是想当 big fish in a small pond...
  5. Python 有序数据结构完整指南(Sorted Containers) 有序数据结构在编程中(尤其是算法竞赛和竞技编程)非常实用。在 Python 中,主要由 Sorted Containers 库提供三种有序数据结构:SortedDict、SortedSet 和 SortedList。 深入理解 Python 有序数据结构:从内置到 SortedContainers Python 有序数据结构完整指南 Python...
  6. 如何通过二分查找搜索在区块链上根据时间戳定位区块? 前两天,我想查一下自己在 STEEM 区块链上一些重要记录对应的区块号,比如: 注册了我的账号 #4253590 成为见证人 #20190755 挖到我的第一个区块 #20390040 被孙宇晨大佬代理了 SP #41676911 收到一笔 DAO 收入...
  7. 北爱尔兰的黑暗树篱 Dark Hedges 是摄影的取景之地 老实说, 去北爱尔兰当天我才了解到黑暗树篱这个地方(Dark Hedges), 因为都是媳妇做的功课, 日程安排上了, 我当上司机, 然后被普及了知识. 北爱尔兰的黑暗树篱是我们访问北爱尔兰的第一站, 从机场开车过去大概50分钟(黑暗树篱在机场的北面40英里左右). 黑暗树篱 Dark Hedges地址: Bregagh Rd, Stranocum,...
  8. 一张图告诉你北京的雾霾有多严重 一北京的朋友朋友圈发的: 左上为全新口罩;右上为全新口罩本周一到周五每天室外戴20分钟左右;左下为全新口罩今早室外+公交车戴一个半小时;右下为全新口罩今早开车戴一小时左右. 还有这图 空气污染 – 红色的是严重的.中国,尤其是华北地区,是全球最红的地区,没有”之一”. 本文一共 113 个汉字, 你数一下对不对. 一张图告诉你北京的雾霾有多严重. (AMP 移动加速版本) 赞赏我的几个理由. ¥...

为什么并行不是无限的: 简单解释 Amdahl vs Gustafson

Amdahl 定律 vs Gustafson 定律 — 完整教程、推导、应用场景及 Python 绘图

Amdahl 定律 vs Gustafson 定律:完整教程、推导、应用场景及 Python 绘图 理解并行加速:通过代码讲解 Amdahl 定律和 Gustafson 定律 并行计算基础:Amdahl 定律、Gustafson 定律及加速建模 并行加速原理:Amdahl 和 Gustafson 定律完整指南 并行扩展解析:推导并比较 Amdahl 和 Gustafson 定律 Amdahl vs Gustafson:并行加速完整指南(含 Python 代码) 并行性能建模:Amdahl 定律、Gustafson 定律及实际应用 学习并行加速:数学、直觉、应用场景及 Python 可视化 并行计算:必须掌握的两条定律(Amdahl & Gustafson) 工程师的并行加速:Amdahl 定律、Gustafson 定律及 Python 实现 从理论到代码:用 Amdahl 和 Gustafson 建模并行加速 实用并行加速指南:Amdahl 定律、Gustafson 定律及可视化 为什么并行不是无限的:简单解释 Amdahl vs Gustafson 并行加速真相:Amdahl 限制 vs Gustafson 扩展 并行计算神话与现实:Amdahl 和 Gustafson 的教训

引言

并行计算在现代计算中至关重要:多核 CPU、GPU、分布式集群、云工作负载、LLM 训练以及 HPC 模拟。 为了分析程序在更多处理器下能加速多少,主要有两种数学模型:
  • Amdahl 定律 — 固定规模工作负载的性能
  • Gustafson 定律 — 可扩展规模工作负载的性能
这两条定律并不矛盾,它们回答的是 不同的问题。 本教程涵盖推导、直觉、比较、实际应用场景,以及展示两条定律的 Python 绘图脚本。

1. 什么是加速比?

加速比衡量程序在 N 个处理器上运行速度提升多少: [math]S(N) = \frac{T_1}{T_N}[/math] 如果程序在一个处理器上运行 10 秒,两处理器运行 5 秒,则加速比为: [math]S(2) = \frac{10}{5} = 2[/math] 完美线性加速为: [math]S(N) = N[/math] 但实际系统存在串行瓶颈,这正是 Amdahl 定律和 Gustafson 定律描述的内容。

2. Amdahl 定律(固定工作量)

2.1 直觉

Amdahl 假设:
  • 总工作量保持 不变
  • 部分工作是串行的,无法并行化
设:
  • f = 串行比例
  • 1 - f = 可并行比例

2.2 推导

一个处理器的运行时间: [math]T_1 = T_s + T_p[/math] 定义: [math]f = \frac{T_s}{T_1}[/math] 因此: [math]T_s = fT_1[/math] [math]T_p = (1 - f)T_1[/math] N 个处理器的运行时间: [math]T_N = fT_1 + \frac{(1 - f)T_1}{N}[/math] 加速比: [math] S(N) = \frac{T_1}{T_N} = \frac{1}{f + \frac{1 - f}{N}} [/math] 其中 f 是串行工作比例,[math] 1-f [/math] 是可并行工作。Amdahl 公式也可以写成: [math] S(N) = \frac{T_1}{T_N} = \frac{1}{(1-p) + \frac{p}{N}} [/math] 其中 [math] p=1-f [/math],[math] f=1-p [/math]

2.3 当 N → ∞ 时的极限

[math]S(\infty) = \frac{1}{f}[/math] 如果串行比例为 10%(f = 0.1): [math]S_\infty = 10[/math] 即使处理器无限,也无法超过该值。

2.4 Amdahl 定律的实际应用场景

Amdahl 适合优化固定任务的 延迟
  • GPU 内核优化固定张量大小
  • 单次请求推理延迟降低
  • 视频编码、压缩、排序
  • 加速固定批量作业
  • 数据库查询加速

3. Gustafson 定律(可扩展工作量)

3.1 直觉

Gustafson 反过来问: “增加处理器,我能在相同时间内解决多大的问题?” 这反映了真实 HPC 工作负载:更多 CPU → 更高分辨率 → 更大模拟。

3.2 推导

假设程序在 N 个处理器上运行 1 个时间单位。 设:
  • f = 串行比例(按规模测量)
可并行部分随处理器数量扩展,因此其运行时间保持与 N 成比例。 一个处理器的时间: [math]T_1 = f + N(1 - f)[/math] 加速比: [math]S(N) = f + N(1 - f)[/math] Gustafson 公式的 “N 减” 形式: [math]S(N) = N - (N - 1)f[/math] 或者,如果定义并行比例 [math]p = 1 - f[/math],公式也可写为: [math]S(N) = f + N(1-f) = f + Np [/math] “N 减” 形式用 p 表示: [math] S(N) = N-(N-1)f = N - (N-1)(1-p) [/math]

3.3 解释

随着 N 增加,加速比趋近于: [math]S(N) \approx N(1 - f)[/math] 对于小串行比例,几乎呈线性增长。

3.4 Gustafson 定律的实际应用场景

Gustafson 适用于 吞吐量扩展 或可增加问题规模的工作负载:
  • 天气和气候模拟
  • 粒子模拟、CFD、有限元分析
  • LLM 训练:更多 GPU → 更长序列或更大模型
  • 大数据分析(Spark, Dask, Flink)
  • 蒙特卡洛模拟

4. Amdahl 定律 vs Gustafson 定律(比较表)

项目AmdahlGustafson
工作负载固定随 N 扩展
目标降低延迟增加吞吐量
加速比上限有界: [math]1/f[/math]近似线性: [math]N(1-f)[/math]
悲观/乐观悲观乐观
应用场景优化现有任务扩展大规模工作量

5. 实际应用场景(综合视角)

Amdahl(延迟优化)

  • 减少单次 LLM 查询推理时间
  • 加速数据库 join 操作
  • 固定张量 GPU 内核优化
  • 视频编码(相同视频)

Gustafson(吞吐量 / 扩展)

  • LLM 训练(扩展至更多 GPU)
  • 高分辨率天气模型模拟
  • 大数据 ETL 扩展
  • 科学 HPC 工作负载

6. Python 绘图脚本(显示两条定律)

下面代码生成 Amdahl 与 Gustafson 加速比曲线图。 可以调整 f(串行比例)和处理器数量 N。 脚本绘制两条曲线在同一张图上。 包括部分 [math]f[/math] 的值,例如串行部分: import numpy as np import matplotlib.pyplot as plt def amdahl_speedup(N, s): return 1.0 / (s + (1 - s) / N) def gustafson_speedup(N, s): return s + (1 - s) * N # Number of processors N = np.arange(1, 65) # Serial fractions to consider Serial = [0.05, 0.1, 0.2, 0.3, 0.5, 0.8, 0.9, 1.0] plt.figure(figsize=(10, 6)) for f in Serial: plt.plot(N, amdahl_speedup(N, f), linestyle='-', label=f"Amdahl Serial={f}") plt.plot(N, gustafson_speedup(N, f), linestyle='--', label=f"Gustafson Serial={f}") plt.title("Amdahl's Law") plt.xlabel("Number of Processors (N)") plt.ylabel("Speedup") plt.legend() plt.grid(True) plt.tight_layout() plt.savefig("parallel-speedup-amdahl-vs-gustafson.png") ## plt.show() 下面是 Amdahl 与 Gustafson 曲线图示。 [caption id="attachment_70445" align="alignnone" width="1000"]Amdahl 定律加速曲线 Amdahl 定律加速曲线[/caption] [caption id="attachment_70446" align="alignnone" width="1000"]Amdahl vs Gustafson 加速曲线 Amdahl vs Gustafson 加速曲线[/caption] [caption id="attachment_70447" align="alignnone" width="1000"]Gustafson 定律加速曲线 Gustafson 定律加速曲线[/caption]

图示解读

  • Amdahl 曲线迅速趋于平缓——受串行部分限制。
  • Gustafson 曲线几乎线性上升——适用于可扩展工作负载。
  • 串行比例 f 越高,两种模型差距越大。

结论

Amdahl 定律展示了固定工作负载下的并行 上限,适合延迟优化。Gustafson 定律展示了随工作负载扩展的并行 潜力
  • Amdahl 定律 → 固定规模工作负载 → 收益递减
  • Gustafson 定律 → 可扩展工作负载 → 近似线性加速
  • 结合使用理解硬件极限与算法特性
  • Python 工具使可视化直观易懂
它们共同构成现代并行系统性能分析基础,从 HPC 到 LLM 训练,再到 GPU 计算。 英文:The Truth About Parallel Speedup: Amdahl’s Limits vs Gustafson’s Scaling

相关文章:

  1. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
  2. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
  3. 力扣刷题获得一件衣服奖励(Leetcode DCC Winner) 我每天都在力扣上刷题。力扣有国服和美服,我两边都会打卡。每天打卡可以获得积分,而积分可以兑换各种礼物,比如T恤、卫衣、水壶,甚至可以用来抵扣一个月的会员费用。 我从2018年8月开始刷题找工作(当时去伦敦面试亚马逊),从那时起每年都会续费会员,费用是159美元,相当于每月13.25美元。我觉得这是对自己最值得的投资。买了力扣会员,就会有动力刷题、思考,通过不断练习让自己熟能生巧,保持一定的竞争力。 到目前为止,我已经用积分兑换了7-8件力扣的衣服,其中有2-3件是卫衣。国内的礼物我都寄到姐姐家。 前不久,我收到了力扣的邮件,说我获得了DCC奖励。我也不知道为什么会获得这个奖,随手回了邮件。没多久,就收到了一件新版的力扣衬衫。 英文:Leetcode DCC Winner T-shirt 本文一共 291 个汉字, 你数一下对不对. 力扣刷题获得一件衣服奖励(Leetcode DCC Winner)....
  4. 第一次私校家长会: 原来家长比孩子还卷 前几天参加了娃的第一次家长会,和几位家长聊下来,真是个个都很厉害。不光孩子们卷,家长也一样卷,一眼望去基本都是 Dr/博士。娃还调侃我一句:“这有什么的,你不也是 Dr 吗?” 我心里默默想:还好没写学校名字,不然我这野鸡大学的头衔真拿不出手 😂。 私校里真是人才济济,乐器过 8 级的太常见了,卷得不得了。我还问过娃,是想当 big fish in a small pond...
  5. 如何通过二分查找搜索在区块链上根据时间戳定位区块? 前两天,我想查一下自己在 STEEM 区块链上一些重要记录对应的区块号,比如: 注册了我的账号 #4253590 成为见证人 #20190755 挖到我的第一个区块 #20390040 被孙宇晨大佬代理了 SP #41676911 收到一笔 DAO 收入...
  6. 花钱让人换汽车钥匙的电池真是个智商税 今天想不到我这么聪明的人也被人狠狠的收了一把智商税. 今天被收智商税了, 去 Tesco 换车钥匙的电池. . 才发现如此的简单, 那人直接2分钟搞定2个, 然后收了我25英镑. . 服了. . 我还以为很复杂…… 网友说 “1....
  7. 比特币最近波动有点大: 一天牛市一天熊 比特币10万美金以内都是最后上车的机会! 比特币近期的价格波动可以归因于多个关键因素,包括地缘政治动态、监管变化以及加密行业内的重大安全事件。其中一个主要影响因素是美国前总统唐纳德·特朗普对乌克兰和加密货币监管的立场变化。据报道,特朗普再次当选,他可能会推动减少美国对乌克兰的支持,这可能会影响全球金融市场和风险偏好。同时,特朗普正在将自己塑造为亲加密货币的候选人,表示有意让美国成为一个更加友好的加密货币环境。这一立场引发了市场对监管政策可能发生变化的猜测,导致市场情绪在乐观和不确定性之间波动。 特朗普对俄乌战争的态度 美国第43届总统唐纳德·特朗普已经在2025年1月当选并正式上任(第二次),那么他的政策可能会对比特币价格的波动产生更加直接和显著的影响。他政府对乌克兰和加密货币监管的立场已经不再是猜测,而是正在实际塑造市场的关键力量。 特朗普(Donald Trump)减少美国对乌克兰的支持,全球投资者可能会预期地缘政治稳定性发生变化,从而增加对比特币作为避险资产的需求。同时,他的亲加密货币立场可能正在推动市场的乐观情绪。如果他的政府推出有利于加密行业的监管政策,例如明确的合规指南或减少监管审查,可能会吸引更多机构投资者进入市场,并促进更广泛的加密货币采用。然而,政策的快速变化也可能导致短期市场剧烈波动,因为市场需要时间来消化新的政策动向。 朝鲜黑客盗取Bybit交易所15亿美元的ETH 另一个显著影响比特币价格的事件是近期涉及朝鲜黑客组织“Lazarus”的15亿美元以太坊被盗案件。据报道,Bybit交易所(全球第二)这些被盗的ETH已经被清洗,此次大规模黑客攻击引发了人们对加密行业安全性的担忧。此类安全事件不仅会削弱投资者信心,还可能引发更严格的监管审查,导致短期市场动荡。此外,被盗资金的大规模流动和出售可能对市场流动性造成冲击,进一步加大价格波动。随着这些事件的持续发酵,比特币价格正受到政治决策、监管预期以及安全挑战等多重因素的影响。 与此同时,与朝鲜黑客组织 Lazarus 相关的 15 亿美元以太坊被盗事件仍在影响加密市场。由于这些被盗 ETH 已被清洗,人们对加密行业安全漏洞的担忧持续存在,同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起,共同导致了比特币近期的剧烈价格波动。...
  8. 和媳妇约个会: 剑桥的过桥米线 Dumpling Trees Dumpling Trees 是位于剑桥 Cherry Hilton 附近的一家中式餐厅,以云南特色的过桥米线闻名。店内环境宽敞整洁,菜品丰富,除了经典的米线,还有各类小吃、烧烤和炒饭,味道地道,分量十足。过桥米线的汤底鲜香,配料新鲜,包括鸡肉、鱿鱼、虾等食材,顾客可以自己下锅涮熟,既好吃又有趣。餐厅提供免费停车,但需在店内登记车牌,适合家庭聚餐或周末小聚。 剑桥 Cherry Hilton 那边有一家叫 Dumpling Trees 的过桥米线店,两三年前的冬天我们去吃过一次(剑桥 Dumpling Tree...

组合数学: 简介一(帕斯卡三角/二项式系数)

组合简介(组合数学入门)

视频:油管/Youtube | B站/小破站 | 微博视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook 组合计数是在顺序不重要时选择项目的方式。我们从一个简单的格子行走示例出发建立直觉,介绍二项式记号,推导公式,解释递推关系 [math]C(n,m)=C(n-1,m-1)+C(n-1,m)[/math],并把所有内容联系到帕斯卡三角。

格子行走示例 — 从左下到右上路径

想象你只能向右(R)或向上(U)移动。要从左下走到需要三次向右和两次向上的点,每一条最短路径都是由五步组成的序列,其中包含三个 R 和两个 U。 [caption id="attachment_70414" align="alignnone" width="512"]走格子: 排列组合 走格子: 排列组合[/caption] 每条有效路径只是从五个位置中选择两个放 U(其余为 R)。所以这样的路径数就是“从 5 中选 2”,记作 [math]C(5,2)[/math](等于 [math]C(5,3)[/math])。 示例序列:
R R U R U U R R R U R U R R U R R R U U U U R R R 

二项式系数(组合)表示法

从 [math]n[/math] 个项目中选出 [math]m[/math] 个(顺序不重要)的方式数记为 [math]C(n,m)[/math] 或 [math]\binom{n}{m}[/math] 两者都表示“从 n 中选 m”。

组合公式 — 基于阶乘的推导

先计算有序选择(排列):从 n 个不同项目中取出长度为 [math]m[/math] 的有序列表的数量为 [math] n\times(n-1)\times\cdots\times(n-m+1)=\dfrac{n!}{(n-m)!} [/math] 每一个无序的 [math] m [/math] 项集合对应 [math] m! [/math] 个有序列表(即这 m 项的排列)。除以 [math] m! [/math] 得到组合数: [math]C(n,m)=\dfrac{n!}{m!(n-m)!}.[/math]

把公式应用到格子示例

对于总步数 [math]n=5[/math] 和向上步数 [math]m=2[/math]: [math]C(5,2)=\dfrac{5!}{2!,3!}=\dfrac{120}{2\times 6}=10 [/math] 因此共有 10 条不同的最短路径。

为什么这个公式直观上合理

  • 视角一 — 选择位置:从 [math]n[/math] 个位置中选择放置 U 的 [math]m[/math] 个位置;这就是 [math]C(n,m)[/math]。
  • 视角二 — 用排列除以顺序:先计算 n 步的所有排列,然后除去相同步序的重排(比如相同类型步的交换)。

帕斯卡三角与递推关系

把 [math]C(n,k)[/math] 写成行可以形成帕斯卡三角:
 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 
[caption id="attachment_70413" align="alignnone" width="847"]Pascal/帕斯卡三角形 Pascal/帕斯卡三角形[/caption] 这些项满足递推关系 [math] C(n,m)=C(n-1,m-1)+C(n-1,m) [/math] 然后,我们可以很容易的写出至顶向下的动态规划算法实现(用@cache实现记忆化式的递归搜索):
from functools import cache

@cache
def C(n, m):
    if m == 0:
        return 1  # C(n, 0) = 1
    if m == n:
        return 1  # C(n, n) = 1
    return C(n-1, m-1) + C(n-1, m)
当然,也可以用自底向上的方式实现:
def C_bottom_up(n, m):
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1  # C(i, 0) = 1
        for j in range(1, min(i, m)+1):
            if j == i:
                dp[i][j] = 1  # C(i, i) = 1
            else:
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    return dp[n][m]
这个自底向上的实现直接从小问题累加到大问题,避免了递归开销,同时也很容易扩展到计算整个帕斯卡三角。 组合数的自底向上 DP 可以用 一维数组优化,利用 滚动数组 原理,因为每一行的计算只依赖上一行。重点是从 右往左更新,这样不会覆盖还没用到的数据。 下面是实现示例:
def C_one_dim(n, m):
    dp = [0] * (m+1)
    dp[0] = 1  # C(i, 0) = 1

    for i in range(1, n+1):
        # 从右往左更新,避免覆盖上一行数据
        for j in range(min(i, m), 0, -1):
            dp[j] = dp[j] + dp[j-1]
    
    return dp[m]
示例:
print(C_one_dim(5, 2))  # 输出 10
✅ 优点:
  • 空间复杂度 O(m)
  • 时间复杂度 O(n*m)
  • 可以方便扩展计算整行或整列组合数

组合证明 — 采苹果

想要从 [math]n[/math] 个苹果中选 [math]m[/math] 个。考虑最后一个苹果(编号为 n): 如果你选了它,那就必须从前面的 [math]n-1[/math] 个中选剩下的 [math]m-1[/math] 个:有 [math]C(n-1,m-1)[/math] 种方法。 如果你不选它,那就必须从前面的 [math]n-1[/math] 个中选出全部 [math]m[/math] 个:有 [math]C(n-1,m) [/math] 种方法。 这两个互不相交的情况覆盖了所有可能,因此 [math] C(n,m)=C(n-1,m-1)+C(n-1,m) [/math] (该恒等式正是构造帕斯卡三角的规则。)

递推关系的格子解释

在格子上,观察到达某点的任意路径的最后一步:要么是 R,要么是 U。以 R 结尾的路径来自某个前一点,以 U 结尾的路径来自另一个前一点。把这两组路径分别计数并相加就得到相同的加法规则。

常见的小值与说明

[math]C(n,0)=1[/math](选择零个)。 [math]C(n,1)=n[/math](选择一个)。 [math]C(n,n)=1[/math](选择全部)。 当 [math]n=5[/math] 时的小表:
 C(5,0)=1 C(5,1)=5 C(5,2)=10 C(5,3)=10 C(5,4)=5 C(5,5)=1 

结语

组合出现在路径计数、二项式展开(系数)、概率与选择问题中。阶乘公式提供直接计算方法,而帕斯卡三角与递推关系则提供归纳直觉和高效构造数值的方式。格子行走示例是将“选择位置”等同于“选择步序”这一组合核心思想可视化的具体方法。 英文:Teaching Kids Programming - Introduction to Combinatorial Mathematics 1

相关文章:

  1. 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
  2. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
  3. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
  4. 第一次私校家长会: 原来家长比孩子还卷 前几天参加了娃的第一次家长会,和几位家长聊下来,真是个个都很厉害。不光孩子们卷,家长也一样卷,一眼望去基本都是 Dr/博士。娃还调侃我一句:“这有什么的,你不也是 Dr 吗?” 我心里默默想:还好没写学校名字,不然我这野鸡大学的头衔真拿不出手 😂。 私校里真是人才济济,乐器过 8 级的太常见了,卷得不得了。我还问过娃,是想当 big fish in a small pond...
  5. 拔牙后的注意事项(图, 慎入) Care of Mouth after Extraction 昨天又拔了两颗牙, 初步定在5月4号装牙套. 这是牙医诊所给的术后注意事项: 拔完后需要等3-4小时麻醉失效后才能吃喝. 稍微流点血是很正常的. 但是请不要漱口吐出, 因为这会加速流血. 你只要轻轻的含着口水并咽下即可. 如果一直流血, 请拿着纱布(并不是纸巾)放在拔牙处20分钟. 24小时内请不要运动, 术后几小时内回家静静坐着. 12小时内不要吸烟, 喝酒或者喝热饮, 因为这会让伤口流血....
  6. WP中检查白名单的用户是否登陆? WordPress 提供了一个方法 is_user_logged_in() 用于检查用户是否是登陆状态. 但是很可惜 这个方法在 pluggable.php 中定义. 也就是说如果你需要在插件中使用, 那么这个函数是没有被定义的. 我们来看一下 is_user_logged_in() 的实现: function is_user_logged_in()...
  7. 北爱尔兰的黑暗树篱 Dark Hedges 是摄影的取景之地 老实说, 去北爱尔兰当天我才了解到黑暗树篱这个地方(Dark Hedges), 因为都是媳妇做的功课, 日程安排上了, 我当上司机, 然后被普及了知识. 北爱尔兰的黑暗树篱是我们访问北爱尔兰的第一站, 从机场开车过去大概50分钟(黑暗树篱在机场的北面40英里左右). 黑暗树篱 Dark Hedges地址: Bregagh Rd, Stranocum,...
  8. 比特币最近波动有点大: 一天牛市一天熊 比特币10万美金以内都是最后上车的机会! 比特币近期的价格波动可以归因于多个关键因素,包括地缘政治动态、监管变化以及加密行业内的重大安全事件。其中一个主要影响因素是美国前总统唐纳德·特朗普对乌克兰和加密货币监管的立场变化。据报道,特朗普再次当选,他可能会推动减少美国对乌克兰的支持,这可能会影响全球金融市场和风险偏好。同时,特朗普正在将自己塑造为亲加密货币的候选人,表示有意让美国成为一个更加友好的加密货币环境。这一立场引发了市场对监管政策可能发生变化的猜测,导致市场情绪在乐观和不确定性之间波动。 特朗普对俄乌战争的态度 美国第43届总统唐纳德·特朗普已经在2025年1月当选并正式上任(第二次),那么他的政策可能会对比特币价格的波动产生更加直接和显著的影响。他政府对乌克兰和加密货币监管的立场已经不再是猜测,而是正在实际塑造市场的关键力量。 特朗普(Donald Trump)减少美国对乌克兰的支持,全球投资者可能会预期地缘政治稳定性发生变化,从而增加对比特币作为避险资产的需求。同时,他的亲加密货币立场可能正在推动市场的乐观情绪。如果他的政府推出有利于加密行业的监管政策,例如明确的合规指南或减少监管审查,可能会吸引更多机构投资者进入市场,并促进更广泛的加密货币采用。然而,政策的快速变化也可能导致短期市场剧烈波动,因为市场需要时间来消化新的政策动向。 朝鲜黑客盗取Bybit交易所15亿美元的ETH 另一个显著影响比特币价格的事件是近期涉及朝鲜黑客组织“Lazarus”的15亿美元以太坊被盗案件。据报道,Bybit交易所(全球第二)这些被盗的ETH已经被清洗,此次大规模黑客攻击引发了人们对加密行业安全性的担忧。此类安全事件不仅会削弱投资者信心,还可能引发更严格的监管审查,导致短期市场动荡。此外,被盗资金的大规模流动和出售可能对市场流动性造成冲击,进一步加大价格波动。随着这些事件的持续发酵,比特币价格正受到政治决策、监管预期以及安全挑战等多重因素的影响。 与此同时,与朝鲜黑客组织 Lazarus 相关的 15 亿美元以太坊被盗事件仍在影响加密市场。由于这些被盗 ETH 已被清洗,人们对加密行业安全漏洞的担忧持续存在,同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起,共同导致了比特币近期的剧烈价格波动。...

性能的隐藏引擎: 一切都取决于数据存储的位置(缓存为王)

性能隐藏的引擎:数据存放在哪里决定一切

1. 性能的真正秘密:数据放在哪里决定一切 2. 决定系统快慢的不是 CPU,而是数据的距离 3. 缓存才是现代计算性能的核心 4. 忽视数据局部性,一切性能优化都是徒劳 5. 性能瓶颈不在算力,而在内存层级 6. 数据局部性:被低估的性能决定因素 7. CPU 在等你的内存:缓存层级的真实代价 8. 系统速度快的真正原因:一切都与缓存有关 9. 别再关注 CPU 速度了——数据局部性才是制胜关键 10. 为什么缓存是所有高性能系统的幕后引擎 11. 性能的关键不在于 GHz,而在于距离 12. 你的 CPU 正在等待内存:缓存不为人知的故事 13. 数据局部性:计算机领域最重要却鲜为人知的因素 14. 数据存储位置决定一切 15. 缓存主宰一切:性能指南 16. 内存层次结构:性能的隐形杀手(或救星) 17. 为什么现代性能之战是与延迟的较量,而非与计算能力的较量
我们喜欢讨论 CPU 频率,但在实际系统中,关键问题是:你的数据存放在哪里? 现代 CPU 依赖一个分层的内存体系(寄存器 → L1 → L2 → L3 → DRAM)。L1 访问可能只需约 4 个周期;而 DRAM 访问可能需要 200+ 个周期——那是 50× 更慢。如果你的工作集能放进缓存,一切飞快;如果不能,CPU 就会阻塞等待。

为什么缓存主导一切

分组处理是一个典型例子。每个数据包都会触发表查找。如果这些表能保持在缓存中,你可以每秒处理数百万个包;一旦溢出到 DRAM,吞吐量会崩塌。
真正的设计问题: 它能放进缓存吗?
[caption id="attachment_70404" align="alignnone" width="476"]CPU寄存器/缓存/架构 CPU寄存器/缓存/架构[/caption] 缓存不仅仅关乎数据。指令缓存未命中也会毁掉尾延迟。有些高频交易系统会让热路径持续执行,只在需要发包时才打开网卡,从而保持 指令缓存持续命中。在交易环路中,一个 I-cache 停顿就可能占据全部延迟预算。

抽象失灵的地方

“全都上云”这类高层策略常忽略底层现实。虚拟化网络功能依赖于诸如:
  • 独占核亲和(core pinning) —— 保持线程在同一 CPU 上以维持缓存热度
  • 中断合并(interrupt coalescing) —— 降低中断率但以延迟为代价
  • NUMA 局部性 —— 跨插槽访问会严重削弱性能
  • 物理网卡与虚拟网卡 行为不同
销售演示会说“可以工作”,但细则通常是:需要 3 倍硬件、3 倍许可证,性能仍然无法与裸机匹配。 一旦你依赖缓存行为、核亲和和 NUMA 局部性,平台就不再可互换。

AI 也碰到同样的问题

即便在 AI 领域,物理规律也没变。模型越来越大,但数据移动依旧主导计算。局部性仍然是王道
  • 数组优于指针密集的结构,因为内存是连续的
  • 硬件预取器只有在访问可预测时才有用
  • 当内存布局合理时,缓存行被更高效地利用

在机器人控制中也能看到

在多轴运动控制中,第一个轴会“预热”缓存并承担缺失惩罚;后续轴的计算因为数据已经热化而耗时减半。相同的原理:局部性 = 速度。

IBM Telum:不同量级的缓存

IBM 的 Telum 处理器把这个想法推到了极端:
  • 十个 36 MB 的 L2 缓存
  • 360 MB 的虚拟 L3
  • 2.8 GB 的虚拟 L4
[caption id="attachment_70405" align="alignnone" width="480"]IBM Telum 处理器 IBM Telum 处理器[/caption] 该架构可以按需将 L2 转作 L3 使用。IBM 尚未公开这些缓存层的具体访问延迟,但在如此大规模的缓存下,大小、互连距离与命中延迟之间的折衷会非常有趣。

结论

性能归根结底由数据和指令能离核心多近来决定。 为局部性而设计,你的系统会表现出色。忽视它,再多的 GHz 或再多的云抽象也救不了你。
我们经常谈论 CPU 速度,却很少关注数据存储的位置。 性能主要取决于数据存储的便利程度。寄存器、L1 缓存、L2 缓存、L3 缓存、主内存——每一步都会增加延迟并降低吞吐量。访问主内存可能需要 200 个时钟周期,比 L1 缓存慢 50 倍。 当工作集能够放入缓存时,代码运行速度极快。否则,CPU 只能等待。 在数据包处理中,这种差异决定了一切。每个数据包都会触发表查找。如果这些表保存在 缓存 中,您可以每秒处理数百万个数据包。否则,吞吐量将急剧下降。 所以,下次设计数据结构时,请问问自己: 它能放进缓存吗? 因为在对性能要求极高的系统中,缓存不仅仅是一种优化手段,它定义了整个系统。 而且不仅是数据,指令也一样!我见过高频交易工程师讨论他们的策略,他们将热路径编程为始终处于激活状态,并且只在数据包需要离开系统时才启用网卡。这样也能保持指令缓存处于热状态。 保持指令缓存处于热状态与保持数据缓存处于热状态同样重要,尤其是在对可预测性要求很高的工作负载中。优化热路径,使 CPU 始终保持在指令缓存中至关重要,因为即使是很小的停顿也可能导致尾延迟显著增加。这很好地提醒我们,架构设计的真正目的是尽可能地将指令和数据都放在靠近核心的位置。 很多技术决策者都固守一刀切的策略:例如……万物皆可云——他们认为任何虚拟化工作负载都可以在任何虚拟化环境中运行,底层硬件和虚拟化技术都只是商品而已。但这并不适用于虚拟化网络功能,因为厂商们早就知道,独占线程核心绑定可以让执行线程独占使用 CPU 缓存。厂商们也知道,在虚拟化环境中,中断合并可以降低“CPU 使用率”,但会增加延迟。他们了解 NUMA 局部性,甚至把这些都写进了文档里。当然,销售人员来了之后,他们希望与高层战略保持一致,使用最佳优化基准测试,然后就云或虚拟机管理程序支持的问题展开另一场不加任何细节的讨论。没错,这行得通*但附注:你需要三倍的许可证/硬件,而且仍然无法获得最佳性能。人们对底层性能如此缺乏兴趣,技能差距如此之大,以至于似乎只能通过增加抽象层和厂商来掩盖责任。如果珠穆朗玛峰是检验技术领导力还是厂商责任的试金石,那么我们很想知道,究竟是哪一方会坚持到底,还是会在山脚下卖羽绒服。完全正确。一旦你依赖缓存行为、核心绑定和NUMA局部性,平台就不再具有可互换性了。底层细节远比大多数高层策略重要得多。 大多数繁重的AI工作负载仍然会遇到相同的内存层次结构限制。模型规模不断扩大,但芯片内部数据传输的物理机制并没有发生太大变化。理解局部性仍然是获得良好性能的关键。 数组能够为CPU提供它真正需要的东西:连续的内存和可预测的访问模式。这意味着预取器可以真正发挥作用,缓存行可以得到高效利用,并且避免了分散结构带来的指针追踪惩罚。这是保持缓存友好性的最简单方法之一。 机器人多轴运动控制也是如此。第一个轴预热缓存并承受缓存未命中的影响,下一个轴的计算时间缩短了一半。 IBM Telum处理器可以验证这一点,它能够按需将L2缓存转换为L3缓存,并且L4缓存可以被任何其他CPU访问。此外,该芯片的时钟频率始终保持在 5.5 GHz。它包含十个 36 MB 的二级缓存¹,以及扩展的虚拟三级缓存(360 MB)和四级缓存(2.8 GB)。 这是一款令人着迷的芯片。与大多数架构相比,其缓存容量巨大,这让我不禁好奇这会对各级缓存的访问延迟产生怎样的影响。可惜的是,我找不到任何关于 Telum 缓存的公开延迟数据,否则我很想了解 IBM 在实际应用中是如何平衡缓存容量、交换空间距离和命中延迟的。
英文:The Hidden Engine of Performance: It’s All About Where the Data Lives (Cache is the King)

相关文章:

  1. 英国银行透支申请/Overdraft详解: 以HSBC为例的真实申请经历 我在英国申请HSBC Overdraft的全过程与心得 什么是HSBC Overdraft?我的申请经验与使用体会 英国银行Overdraft详解:以HSBC为例的真实申请经历 英国HSBC Overdraft申请记:为啥我也办了个透支额度 账户差点扣不上学费,我才去申请了HSBC Overdraft 英国银行透支服务(Overdraft)到底有啥用?我的真实体验 理财角度看HSBC Overdraft:短期周转的小帮手 透支不是坏事?谈谈HSBC Overdraft的利与弊 我最近申请了汇丰银行(HSBC)的透支额度(Overdraft),最高限额是5000英镑。我在网上填写完申请表后,系统提示大概需要一到两个工作日才能出结果。后来我收到一条短信,让我打电话联系HSBC。...
  2. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
  3. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
  4. 第一次私校家长会: 原来家长比孩子还卷 前几天参加了娃的第一次家长会,和几位家长聊下来,真是个个都很厉害。不光孩子们卷,家长也一样卷,一眼望去基本都是 Dr/博士。娃还调侃我一句:“这有什么的,你不也是 Dr 吗?” 我心里默默想:还好没写学校名字,不然我这野鸡大学的头衔真拿不出手 😂。 私校里真是人才济济,乐器过 8 级的太常见了,卷得不得了。我还问过娃,是想当 big fish in a small pond...
  5. GoPro运动相机可以拿来做什么? GoPro运动相机因其小巧、耐用、防水和高性能的特点,被广泛用于各种极限运动和户外活动的拍摄。它可以用来拍摄滑雪、冲浪、潜水、山地骑行、跑步、攀岩等运动的高清动态影像。此外,GoPro还适合用于日常生活记录,像是旅行、背包客探险、家庭聚会等场景。它强大的稳定性和防水功能让它在水下和恶劣环境下表现出色,甚至可以通过配件安装在头盔、无人机或车载支架上,提供独特的视角。随着最新型号的推出,GoPro还支持4K视频录制和慢动作拍摄,进一步扩展了它的应用场景。 自从新年打折入了GoPro Hero+运动相机以来, 也没怎么用上, 基本上是几天的热性就和其它电子产品一样被冷落到一旁. GoPro运动相机可以拿来做什么, 主要的几个用途是: GoPro 不太适合拍人像 拍孩子孩子容易动, 特别容易就糊了, GoPRO的摄像参数可以调的很少, 所以不要期望有大光圈能背景虚化, 唯一能拍的可能是大长腿, GoPro是广角镜头,...
  6. 小赌怡情 – GPS还是挺靠谱的 小赌怡情 偶尔赌赌没关系 只要不贪婪就好. 不过我赌运真的很差,都没有什么印象自己有赌赢什么过.赌过两次世界杯,结果都是输的比赢的多(还好只输几十镑). 新家和现在暂时住的公寓(公司提供的) 有 10英理左右.开车大概20分钟 每天下班都会和老婆孩子一起搬些东西过去.今天 回来的时候 错过了一个路口 走了另一条路.记得刚开始的时候 GPS是推荐下图中的蓝色这条路的.后来我和我老婆就赌说哪条近,谁也没能说服回,于是答应回家查 GOOGLE 按 谷哥...
  7. 理解 C++ 中的 dynamic_cast: 安全的向下转型与向上转型 C++ 中的 dynamic_cast 是什么? 用途 在运行时在多态类型之间安全地进行转换 通常用于将基类指针转换为派生类指针(向下转型) 使用 RTTI(运行时类型识别)进行类型检查 基本语法 Derived* d = dynamic_cast<Derived*>(basePtr); 如果...
  8. 比特币最近波动有点大: 一天牛市一天熊 比特币10万美金以内都是最后上车的机会! 比特币近期的价格波动可以归因于多个关键因素,包括地缘政治动态、监管变化以及加密行业内的重大安全事件。其中一个主要影响因素是美国前总统唐纳德·特朗普对乌克兰和加密货币监管的立场变化。据报道,特朗普再次当选,他可能会推动减少美国对乌克兰的支持,这可能会影响全球金融市场和风险偏好。同时,特朗普正在将自己塑造为亲加密货币的候选人,表示有意让美国成为一个更加友好的加密货币环境。这一立场引发了市场对监管政策可能发生变化的猜测,导致市场情绪在乐观和不确定性之间波动。 特朗普对俄乌战争的态度 美国第43届总统唐纳德·特朗普已经在2025年1月当选并正式上任(第二次),那么他的政策可能会对比特币价格的波动产生更加直接和显著的影响。他政府对乌克兰和加密货币监管的立场已经不再是猜测,而是正在实际塑造市场的关键力量。 特朗普(Donald Trump)减少美国对乌克兰的支持,全球投资者可能会预期地缘政治稳定性发生变化,从而增加对比特币作为避险资产的需求。同时,他的亲加密货币立场可能正在推动市场的乐观情绪。如果他的政府推出有利于加密行业的监管政策,例如明确的合规指南或减少监管审查,可能会吸引更多机构投资者进入市场,并促进更广泛的加密货币采用。然而,政策的快速变化也可能导致短期市场剧烈波动,因为市场需要时间来消化新的政策动向。 朝鲜黑客盗取Bybit交易所15亿美元的ETH 另一个显著影响比特币价格的事件是近期涉及朝鲜黑客组织“Lazarus”的15亿美元以太坊被盗案件。据报道,Bybit交易所(全球第二)这些被盗的ETH已经被清洗,此次大规模黑客攻击引发了人们对加密行业安全性的担忧。此类安全事件不仅会削弱投资者信心,还可能引发更严格的监管审查,导致短期市场动荡。此外,被盗资金的大规模流动和出售可能对市场流动性造成冲击,进一步加大价格波动。随着这些事件的持续发酵,比特币价格正受到政治决策、监管预期以及安全挑战等多重因素的影响。 与此同时,与朝鲜黑客组织 Lazarus 相关的 15 亿美元以太坊被盗事件仍在影响加密市场。由于这些被盗 ETH 已被清洗,人们对加密行业安全漏洞的担忧持续存在,同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起,共同导致了比特币近期的剧烈价格波动。...

用 Python 学强化学习: Q-Learning 迷宫示例

[caption id="attachment_70386" align="alignnone" width="2017"]Q Learning强化学习算法(机器学习/人工智能) Q Learning强化学习算法(机器学习/人工智能)[/caption] 强化学习(Reinforcement Learning, RL)是一种让智能体/Agent通过与环境交互、试错学习来获得最优行为策略的机器学习方法。本文用一个简单的 Q-learning 迷宫示例,帮助你快速理解强化学习的基本原理。

强化学习入门:从试错中学习的艺术 Reinforcement Learning 101: The Art of Learning by Trial and Error 深度解析强化学习:Q-Learning算法详解 Deep Dive into Reinforcement Learning: Understanding the Q-Learning Algorithm 机器如何学会自己做决定?强化学习告诉你答案 How Do Machines Learn to Make Their Own Decisions? Reinforcement Learning Explained 从奖励中学习:人工智能的“试错智慧” Learning from Rewards: The Trial-and-Error Intelligence Behind AI

一、什么是强化学习?

强化学习的世界中包含五个关键要素:
  • Agent(智能体):做决策、执行动作的主体
  • Environment(环境):智能体所处的世界
  • State(状态):当前环境的描述
  • Action(动作):智能体可采取的操作
  • Reward(奖励):环境反馈,用来衡量动作的好坏
智能体的目标是学习一个策略 π(a|s),让它在每个状态下选择最优动作,从而获得最大的累积奖励。 [math]J(\pi) = \mathbb{E}\pi \left[ \sum{t=0}^{\infty} \gamma^t r_t \right][/math] 其中 [math]\gamma[/math](0 ≤ [math]\gamma[/math] ≤ 1)是折扣因子,用于衡量未来奖励相对于即时奖励的重要程度。

二、Q-Learning 原理

Q-learning 是最经典的强化学习算法之一。它通过学习一个 Q 表(Q-table)来记录每个“状态-动作”对的价值。 更新公式如下: [math] Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s', a') - Q(s,a)] [/math] 其中:
  • [math] \alpha [/math]:学习率(Learning Rate)
  • [math] \gamma [/math]:折扣因子(Discount Factor)
  • [math] r [/math]:奖励(Reward)
  • [math] s' [/math]:下一状态(Next State)

三、迷宫环境设计

定义一个 3×5 的迷宫
  • 0:空地
  • -1:墙
  • 1:出口(目标)

四、完整 Python 实现代码


import numpy as np
import random

# 1️⃣ 定义迷宫
maze = np.array([
    [0,  0,  0, -1,  1],
    [0, -1,  0, -1,  0],
    [0,  0,  0,  0,  0]
])

n_rows, n_cols = maze.shape
actions = ['up', 'down', 'left', 'right']
Q = np.zeros((n_rows, n_cols, len(actions)))

# 2️⃣ 超参数
alpha = 0.1
gamma = 0.9
epsilon = 0.1
episodes = 500

# 3️⃣ 辅助函数
def is_valid(state):
    r, c = state
    return 0 <= r < n_rows and 0 <= c < n_cols and maze[r, c] != -1

def next_state(state, action):
    r, c = state
    if action == 'up': r -= 1
    elif action == 'down': r += 1
    elif action == 'left': c -= 1
    elif action == 'right': c += 1
    return (r, c)

def get_reward(state):
    r, c = state
    if maze[r, c] == 1: return 10
    elif maze[r, c] == -1: return -1
    return -0.1

# 4️⃣ 训练循环
for episode in range(episodes):
    state = (2, 0)
    done = False

    while not done:
        if random.uniform(0, 1) < epsilon:
            action_idx = random.randint(0, len(actions)-1)
        else:
            action_idx = np.argmax(Q[state[0], state[1]])

        action = actions[action_idx]
        next_s = next_state(state, action)

        if not is_valid(next_s):
            reward = -1
            next_s = state
        else:
            reward = get_reward(next_s)

        Q[state[0], state[1], action_idx] += alpha * (
            reward + gamma * np.max(Q[next_s[0], next_s[1]]) - Q[state[0], state[1], action_idx]
        )

        state = next_s
        if maze[state[0], state[1]] == 1:
            done = True

print("✅ 训练完成!")

# 5️⃣ 查看学到的路径
state = (2, 0)
path = [state]

while maze[state[0], state[1]] != 1:
    action_idx = np.argmax(Q[state[0], state[1]])
    next_s = next_state(state, actions[action_idx])
    if not is_valid(next_s) or next_s in path:
        break
    state = next_s
    path.append(state)

print("🗺️ 学到的路径:", path)

五、运行结果

运行上面的代码后,你会看到类似输出: ✅ 训练完成! 🗺️ 学到的路径: [(2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (0, 4)] 这说明智能体成功学会了走出迷宫 🎯

六、总结

强化学习使机器能够通过反馈学习最优策略,这类似于人类通过经验学习的方式。 Q-Learning 是许多现代强化学习算法的基础,包括深度 Q 网络(Deep Q-Networks, DQN)。 这个简单的示例展示了完整的强化学习循环:探索 → 反馈 → 改进。
  • Q 表:保存每个状态-动作的价值
  • ε-greedy 策略:平衡探索与利用
  • 奖励函数设计:引导智能体形成目标导向行为
  • 强化学习思想:通过试错和奖励反馈不断改进策略
强化学习的魅力在于,它不需要显式答案,而是让机器自己“摸索”出最优策略。你可以在此基础上继续扩展,比如加入 matplotlib 动画可视化 或使用 神经网络(Deep Q-Learning) 解决更复杂的任务。 英文:How Do Machines Learn to Make Their Own Decisions? Reinforcement Learning Explained

相关文章:

  1. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
  2. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
  3. 第一次私校家长会: 原来家长比孩子还卷 前几天参加了娃的第一次家长会,和几位家长聊下来,真是个个都很厉害。不光孩子们卷,家长也一样卷,一眼望去基本都是 Dr/博士。娃还调侃我一句:“这有什么的,你不也是 Dr 吗?” 我心里默默想:还好没写学校名字,不然我这野鸡大学的头衔真拿不出手 😂。 私校里真是人才济济,乐器过 8 级的太常见了,卷得不得了。我还问过娃,是想当 big fish in a small pond...
  4. 给孩子第一台NUC小电脑 Next Unit of Computing Next Unit of Computing (NUC) is a line of small-form-factor computers...
  5. 和媳妇约个会: 剑桥的过桥米线 Dumpling Trees Dumpling Trees 是位于剑桥 Cherry Hilton 附近的一家中式餐厅,以云南特色的过桥米线闻名。店内环境宽敞整洁,菜品丰富,除了经典的米线,还有各类小吃、烧烤和炒饭,味道地道,分量十足。过桥米线的汤底鲜香,配料新鲜,包括鸡肉、鱿鱼、虾等食材,顾客可以自己下锅涮熟,既好吃又有趣。餐厅提供免费停车,但需在店内登记车牌,适合家庭聚餐或周末小聚。 剑桥 Cherry Hilton 那边有一家叫 Dumpling Trees 的过桥米线店,两三年前的冬天我们去吃过一次(剑桥 Dumpling Tree...
  6. 微信PC端程序占用了1.39 TB的空间! 快速清理微信占用空间 前两天我的 C 盘剩余空间突然变红了,我随手一查,竟然发现微信 PC 端程序居然占用了 1.39 TB 的空间,简直不可思议。在手机上,微信同样是名列前茅的“吞空间大户”,在 设置 → 通用 → 手机存储空间 里几乎稳居第一。 更离谱的是,这些空间大多并不是因为聊天记录,而是各种缓存文件、视频、图片和被动接收的文件所堆积起来的。平时我们只是点开看一眼,就算没保存下来,微信也会悄悄把它们留在本地,占据大量磁盘。尤其是群聊里转发的视频和文件,日积月累就成了一个“隐形黑洞”。...
  7. C++的左值/lvalue, 右值/rvalue和右值引用/rvalue references C++ 左值(lvalue)、右值(rvalue)与右值引用(rvalue reference) 理解 C++ 中的左值、右值及其引用形式,是掌握现代 C++(尤其是 C++11 以后的移动语义/move和完美转发/perfect forwarding)必不可少的基础。 📌 什么是左值(lvalue) 左值指的是有名字、可寻址的对象,通常可以出现在赋值语句的左侧。 int x...
  8. 比特币最近波动有点大: 一天牛市一天熊 比特币10万美金以内都是最后上车的机会! 比特币近期的价格波动可以归因于多个关键因素,包括地缘政治动态、监管变化以及加密行业内的重大安全事件。其中一个主要影响因素是美国前总统唐纳德·特朗普对乌克兰和加密货币监管的立场变化。据报道,特朗普再次当选,他可能会推动减少美国对乌克兰的支持,这可能会影响全球金融市场和风险偏好。同时,特朗普正在将自己塑造为亲加密货币的候选人,表示有意让美国成为一个更加友好的加密货币环境。这一立场引发了市场对监管政策可能发生变化的猜测,导致市场情绪在乐观和不确定性之间波动。 特朗普对俄乌战争的态度 美国第43届总统唐纳德·特朗普已经在2025年1月当选并正式上任(第二次),那么他的政策可能会对比特币价格的波动产生更加直接和显著的影响。他政府对乌克兰和加密货币监管的立场已经不再是猜测,而是正在实际塑造市场的关键力量。 特朗普(Donald Trump)减少美国对乌克兰的支持,全球投资者可能会预期地缘政治稳定性发生变化,从而增加对比特币作为避险资产的需求。同时,他的亲加密货币立场可能正在推动市场的乐观情绪。如果他的政府推出有利于加密行业的监管政策,例如明确的合规指南或减少监管审查,可能会吸引更多机构投资者进入市场,并促进更广泛的加密货币采用。然而,政策的快速变化也可能导致短期市场剧烈波动,因为市场需要时间来消化新的政策动向。 朝鲜黑客盗取Bybit交易所15亿美元的ETH 另一个显著影响比特币价格的事件是近期涉及朝鲜黑客组织“Lazarus”的15亿美元以太坊被盗案件。据报道,Bybit交易所(全球第二)这些被盗的ETH已经被清洗,此次大规模黑客攻击引发了人们对加密行业安全性的担忧。此类安全事件不仅会削弱投资者信心,还可能引发更严格的监管审查,导致短期市场动荡。此外,被盗资金的大规模流动和出售可能对市场流动性造成冲击,进一步加大价格波动。随着这些事件的持续发酵,比特币价格正受到政治决策、监管预期以及安全挑战等多重因素的影响。 与此同时,与朝鲜黑客组织 Lazarus 相关的 15 亿美元以太坊被盗事件仍在影响加密市场。由于这些被盗 ETH 已被清洗,人们对加密行业安全漏洞的担忧持续存在,同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起,共同导致了比特币近期的剧烈价格波动。...

教孩子编程: 证明根号2是个无理数的两种方法(反证法/几何无限下降法)

视频:油管/Youtube | B站/小破站 | 微博视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook

如何证明 √2 是无理数 — 两种方法(反证法与几何无限下降)

“√2 是无理数”这一说法的意思是不存在整数 [math]a[/math] 和 [math]b\neq 0[/math] 且 [math]\gcd(a,b)=1[/math],使得 [math]\sqrt{2}=\dfrac{a}{b}[/math]。

方法一 — 反证法

假设相反,认为 [math]\sqrt{2}[/math] 是有理数。则存在整数 [math]a[/math] 和 [math]b[/math],满足 [math]b\neq 0[/math] 且 [math]\gcd(a,b)=1[/math],使得 [math]\sqrt{2}=\dfrac{a}{b}.[/math] 两边平方得: [math]2=\dfrac{a^2}{b^2}\quad\Rightarrow\quad a^2 = 2b^2.[/math] 由 [math]a^2 = 2b^2[/math] 可知 [math]a^2[/math] 为偶数,因此 [math]a[/math] 必为偶数。设 [math]a=2k[/math],其中 [math]k[/math] 为某整数。 代回去: [math] ^2 = 2b^2 \quad\Rightarrow\quad 4k^2 = 2b^2 \quad\Rightarrow\quad b^2 = 2k^2.[/math] 因此 [math]b^2[/math] 为偶数,故 [math]b[/math] 亦为偶数。 于是 [math]a[/math] 和 [math]b[/math] 都为偶数,这与我们假设的 [math]\gcd(a,b)=1[/math] 矛盾(它们至少有公因子 2)。该矛盾说明原假设错误;因此 [math]\sqrt{2}[/math] 为无理数。

方法二 — 几何无限下降(等腰直角三角形中线构造)

[caption id="attachment_70110" align="alignnone" width="575"]等腰直角三角形边向斜边作垂线证明根号2不是有理数 等腰直角三角形边向斜边作垂线证明根号2不是有理数[/caption] 设一个等腰直角三角形 [math]\triangle ABC[/math],其中直角在 [math]C[/math],两条直角边 [math]AC=BC=b[/math],斜边 [math]AB=a[/math],因此有 [math]a^2=b^2+b^2=2b^2[/math]。 取 [math]BC[/math] 的中点 [math]E[/math],从 [math]E[/math] 向斜边 [math]AB[/math] 作垂线,垂足为 [math]D[/math]。 则 [math]\triangle BDE[/math] 也是一个等腰直角三角形,并且与原三角形 [math]\triangle ABC[/math] 相似。记小三角形的斜边和直角边分别为 [math]a'=BE[/math] 与 [math]b'=BD[/math]。 有 [math]a'^2=2b'^2[/math],从而验证了 [math]\triangle BDE\sim\triangle ABC[/math]。 关键点在于相似(固定比例缩放),小三角形的尺寸是原三角形的一定比例。 从 [math]BC[/math] 取中点 [math]E[/math],向斜边 [math]AB[/math] 作垂线,交于 [math]D[/math]。 于是 [math]\triangle BDE[/math] 与 [math]\triangle ACB[/math] 相似。我们可以通过“重复减法”来表达边长关系: 因为 [math]\triangle ACE = \triangle ADE[/math],所以 [math]AC = AD[/math],因此 [math]AB - AC = AB - AD = BD[/math]。 进一步有 [math]AC - BD = BC - BD = BC - DE = BC - CE = BE[/math]。 因此 [math]AB - AC [/math] 辗转相减 [math] BE - BD[/math],即 [math]a - b \quad\Rightarrow\quad a' - b'[/math],其中 [math]a' = BE[/math],[math]b' = BD[/math]。 由于 [math]\triangle BED \sim \triangle ABC[/math],我们可以无限次重复这一构造过程。 每次重复相同的操作(取直角边的中点并作垂线到斜边),都会得到一个与原三角形相似的新等腰直角三角形,其边长都按某个固定比例 [math]r[/math] 缩小。 因此,斜边和直角边都会在每一步以几何级数的方式缩小。 这在整数情况下导致“无限下降”矛盾
  • 如果假设存在整数边长满足 [math]a^2=2b^2[/math],则这种几何构造(或等价的、保持整数关系的中点构造)会产生一个更小的正整数解。
  • 无限重复下去会得到一个严格递减的正整数序列,这显然不可能。
因此,不存在这样的整数解,即 [math]\sqrt{2}[/math] 是无理数。 两种方法均证明了 [math]\sqrt{2}[/math] 不能写成两个整数之比。
  • 方法一(反证法)利用奇偶性,说明若假设分数为最简形式则会导致分子和分母都为偶数,从而矛盾。
  • 方法二(几何无限下降)通过在等腰直角三角形中作中线并利用相似性得到更小的整数解,从而与最小性矛盾。
任一方法都给出清晰而严谨的证明,表明 [math]\sqrt{2}[/math] 是无理数。 [show_file file="/var/www/wp-post-common/justyy.com/math.php"] 英文:Teaching Kids Programming - Two Ways to Prove Square Root of Two is Irrational (proof by contradiction and geometric infinite descent)

相关文章:

  1. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
  2. 第一次私校家长会: 原来家长比孩子还卷 前几天参加了娃的第一次家长会,和几位家长聊下来,真是个个都很厉害。不光孩子们卷,家长也一样卷,一眼望去基本都是 Dr/博士。娃还调侃我一句:“这有什么的,你不也是 Dr 吗?” 我心里默默想:还好没写学校名字,不然我这野鸡大学的头衔真拿不出手 😂。 私校里真是人才济济,乐器过 8 级的太常见了,卷得不得了。我还问过娃,是想当 big fish in a small pond...
  3. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
  4. 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
  5. 时间是你的朋友: 延时满足 Time Is Your Friend: The Power of Delayed Gratification” 最近,比特币又创下历史新高,突破 12.5 万美元。美股同样表现强劲——微软的股价已来到 518.81 美元,而我刚入职那会儿,它还在 280...
  6. 比特币最近波动有点大: 一天牛市一天熊 比特币10万美金以内都是最后上车的机会! 比特币近期的价格波动可以归因于多个关键因素,包括地缘政治动态、监管变化以及加密行业内的重大安全事件。其中一个主要影响因素是美国前总统唐纳德·特朗普对乌克兰和加密货币监管的立场变化。据报道,特朗普再次当选,他可能会推动减少美国对乌克兰的支持,这可能会影响全球金融市场和风险偏好。同时,特朗普正在将自己塑造为亲加密货币的候选人,表示有意让美国成为一个更加友好的加密货币环境。这一立场引发了市场对监管政策可能发生变化的猜测,导致市场情绪在乐观和不确定性之间波动。 特朗普对俄乌战争的态度 美国第43届总统唐纳德·特朗普已经在2025年1月当选并正式上任(第二次),那么他的政策可能会对比特币价格的波动产生更加直接和显著的影响。他政府对乌克兰和加密货币监管的立场已经不再是猜测,而是正在实际塑造市场的关键力量。 特朗普(Donald Trump)减少美国对乌克兰的支持,全球投资者可能会预期地缘政治稳定性发生变化,从而增加对比特币作为避险资产的需求。同时,他的亲加密货币立场可能正在推动市场的乐观情绪。如果他的政府推出有利于加密行业的监管政策,例如明确的合规指南或减少监管审查,可能会吸引更多机构投资者进入市场,并促进更广泛的加密货币采用。然而,政策的快速变化也可能导致短期市场剧烈波动,因为市场需要时间来消化新的政策动向。 朝鲜黑客盗取Bybit交易所15亿美元的ETH 另一个显著影响比特币价格的事件是近期涉及朝鲜黑客组织“Lazarus”的15亿美元以太坊被盗案件。据报道,Bybit交易所(全球第二)这些被盗的ETH已经被清洗,此次大规模黑客攻击引发了人们对加密行业安全性的担忧。此类安全事件不仅会削弱投资者信心,还可能引发更严格的监管审查,导致短期市场动荡。此外,被盗资金的大规模流动和出售可能对市场流动性造成冲击,进一步加大价格波动。随着这些事件的持续发酵,比特币价格正受到政治决策、监管预期以及安全挑战等多重因素的影响。 与此同时,与朝鲜黑客组织 Lazarus 相关的 15 亿美元以太坊被盗事件仍在影响加密市场。由于这些被盗 ETH 已被清洗,人们对加密行业安全漏洞的担忧持续存在,同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起,共同导致了比特币近期的剧烈价格波动。...
  7. 拔牙后的注意事项(图, 慎入) Care of Mouth after Extraction 昨天又拔了两颗牙, 初步定在5月4号装牙套. 这是牙医诊所给的术后注意事项: 拔完后需要等3-4小时麻醉失效后才能吃喝. 稍微流点血是很正常的. 但是请不要漱口吐出, 因为这会加速流血. 你只要轻轻的含着口水并咽下即可. 如果一直流血, 请拿着纱布(并不是纸巾)放在拔牙处20分钟. 24小时内请不要运动, 术后几小时内回家静静坐着. 12小时内不要吸烟, 喝酒或者喝热饮, 因为这会让伤口流血....
  8. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. /** MySQL...

Dart 语法要点(3) —— 类和对象

2025年9月20日 11:58

Dart 是一种面向对象的编程语言,支持类和基于混入(Mixin)的继承机制。在 Dart 中除 Null 以外的所有类都继承自 Object 类。

1. 基本用法

Dart 中类的基本用法和大部分面向对象语言差不多,这里不作详细介绍,直接从一个简单的示例开始:

// 导入依赖库
import 'dart:math';

class Point {
  // 成员变量
  double? x;    // 默认值初始值为null
  double y = 0; // 初始值为0

  // 构造函数
  Point(double x, double y) {
    this.x = x;
    this.y = y;
  }

  //成员方法
  double distanceTo(Point other) {
    double dx = (this.x ?? 0) - (other.x ?? 0);
    var dy = this.y - other.y;
    return sqrt(dx * dx + dy * dy);
  }

  // 静态方法
  static double distanceBetween(Point a, Point b) {
    return a.distanceTo(b);
  }

  // 重写toString方法
  @override
  String toString() {
    return 'Point($x, $y)';
  }
}

调用也很简单,代码如下:

void main() {
  Point p1 = new Point(0, 0); 
  Point p2 = new Point(3, 4);
  print(p1.distanceTo(p2));             // 5.0
  print(Point.distanceBetween(p1, p2)); // 5.0
  print(p1);                            // Point(0.0, 0.0)
  print(p2);                            // Point(3.0, 4.0)
  print(p2.y);                          // 4.0
}

单看上述代码,几乎分不清究竟是 JavaScriptJava, 还是 Dart,下文主要介绍一些 Dart 相对独特的地方。

[...]

Dart 语法要点(2) —— 函数

2025年9月15日 16:51

下面是一个简单的函数示例:

bool isNoble(int atomicNumber) {
  return _nobleGases[atomicNumber] != null;
}

虽然 返回值类型参数类型 都可以省略,但建议加上,省略后的代码如下:

isNoble(atomicNumber) {
  return _nobleGases[atomicNumber] != null;
}

如果函数体 只有一条语句,也可以使用 箭头函数

bool isNoble(int atomicNumber) => _nobleGases[atomicNumber] != null;

其中,=> expr; 语法就是 { return expr; } 的简写形式,与其它语言不同,如果函数体有多条语句,就不能使用这种语法了。

[...]

Dart 语法要点(1) —— 注释、变量、常量、数据类型

2025年9月14日 14:56

1. 注释

  • 单行注释:以两个斜杠(//)开头,持续到行尾。
  • 多行注释:以 /* 开头,以 */ 结尾,可以跨越多行。
  • 文档注释:以 ////** 开头,用于为代码生成文档,在文档注释中使用[](如 [Food][feed]),生成文档时,会转换为指向类、方法、变量等的超链接。

2. 变量

以下是变量声明和初始化的示例:

var name = 'Bob';

Dart 是强类型语言,示例中,name 变量的类型会在编译时被推断为 String,也可在声明时显式指定类型,对于局部变量,建议使用 var。如果对象不限于单一类型,可以在声明时指定为 Objectdynamic 类型。

[...]

Dart 开发环境搭建

2025年9月12日 11:44

Dart 介绍

Dart 是一种由 Google 开发的开源编程语言,于 2011 年首次发布,目前稳定版本为 Dart 3.x,曾经号称要取代 JavaScript,但过去的几年中一直不温不火,真正使其声名大噪并得到广泛应用的原因是其与 Flutter 框架的完美结合。

如今,Flutter 已成为构建高性能、高质量跨平台应用(Android、IOS、Web、桌面)的首选技术方案之一,尤其是针对希望快速实现跨平台应用的中小团队或个人开发者,Flutter 更是不二之选,而学习 Flutter 的第一步就是先学习其官方编程语言 --- Dart

边学边记,这篇文章先把 Dart 的开发环境搭建起来!

[...]

❌