多元一次不定方程的强力算法:同余筛数法

今天朋友问了一个问题, 已知正整数 s 和正整数集合 j1 j2 j3… jn , 未知正整数 k1 k2 k3…kn,使得s = j1 * k1 + j2 * k2 + j3 * k3 + jn * kn,要求 k1 k2 k3…kn的值。 这个凑单时经常用到,如定好每件商品的单价以及总金额,要求出每样商品的数量。 一个简单的例子 看一个简单的例子,有若干的 1块,2块,5块的纸币,凑100块钱。 即 1x + 2y + 5*z = 100 这个是多元一次不定方程。这在数论里面有研究,通过通解来求解特定范围的解理论上虽然可行,但遗憾的是其求解效率几乎与穷举法相当的。 同余筛数法 下面介绍一种比上述方案更快速的强力快速算法。这是一种基于同余理论的快速算法,同余筛数法。 原理 我们知道二元不定方程 a * x + b * y = c 其实是与同余方程 a * x = c (mod b) 等价的。 同理对于三元不定方程 a * x + b * y + c * z = d ,实际上也可以理解成 a * X = p (mod c),b * Y = q (mod c),设d = d' (mod c),则有 p + q = d' (mod d)。 为什么会有这样的结论?原因很简单:d - a * x + b * y = c * t0 + d' - a * c * t - p - b * c * t' - q = c * z = 0 (mod c)。...

March 29, 2022 · 1 分钟 · ming

manjaro-setup

manjaro 设置 切换到 manjaro 已经好几年, 有时换机器或者重装系统总有几个相同的步骤要设置,故写此文记录一下。 针对中文环境,版本为 Manjaro 21.2.3 Qonos KDE。 设置 manjaro 镜像源为中国 可以在 Pamac 图形界面中直接设置。 设置显示缩放 如果是高分辨率屏幕,可以在系统 > 显示 中设置全局缩放,这样看上去字体不会太小。 时间同步 虚拟机和宿主机时间相差 8 个小时,可以在 manjaro 时间设置页面 “勾选自动设定日期和时间”, 启用时间同步后即可修复该问题。 安装中文输入法 #安装 Fcitx5主体、配置工具、输入法引擎及中文输入法模块,可参考 https://www.bilibili.com/read/cv14016623 sudo pacman -S fcitx5-im fcitx5-chinese-addons fcitx5-qt fcitx5-gtk sudo vim ~/.pam_environment #加入以下内容(中间是一个 Tab键,一般情况下只需要前三行) GTK_IM_MODULE DEFAULT=fcitx QT_IM_MODULE DEFAULT=fcitx XMODIFIERS DEFAULT=\@im=fcitx INPUT_METHOD DEFAULT=fcitx SDL_IM_MODULE DEFAULT=fcitx #安装中文维基百科词库 sudo pacman -S fcitx5-pinyin-zhwiki 配置完成后,建议注销或重启一下。 安装 aur 助手 AUR 是针对基于 Arch 的 Linux 发行版用户的社区驱动的仓库,很多官方仓库没有收录的软件包要从 AUR安装。 安装 yay 后可以方便的从 AUR 安装软件。...

February 7, 2022 · 1 分钟 · ming

tidb tools

很开心最近以不错的成绩过了 tidb 的 PCTA 认证, 该认证是 tidb 的基础运维能力认证. 除了理解 tidb 的基本概念, 使用 tiup 部署管理集群, 还有很大一块就是学会使用TiDB生态工具,进行数据迁移和校验,例如:数据迁入、全量导出、全量导入、备份恢复、校验等等。 它们的特性更有不同, 如上游下游是啥, 速度和数据量, 是否需要停机或者只读, 是否支持异构, 兼容的版本, 是否需要额外部署组件等, 理解它们的异同及各自的使用场景, 是考试中容易丢分的点, 故结合 301 视频和官方文档, 稍作整理如下. BR BR 全称 backup & restore, 是 tidb 分布式备份恢复的命令行工具, 用于对 tidb 集群进行数据备份和恢复. BR 属于物理备份,数据由 TiKV 从各个 region 的 leader 生成 SST 格式的 KV 数据,它是专用的 TiDB 格式,不能用于 MySQL 的还原。TiKV 进行数据还原时,没有固定的节点对应关系,所有的节点都需要访问完整的数据,所以 BR 最好使用 NFS/S3 共享存储存储。支持按库, 表过滤, 支持全量增量, 支持限速. Dumpling 数据导出工具 dumpling 可以把存储在 tidb/mysql 中的数据导出为 sql 或者 csv, 可以用于完成逻辑上的全量备份或者导出....

December 5, 2021 · 2 分钟 · ming

tidb 与 tdsql 比较  [draft]

tidb 是优秀的国产开源分布式数据库, 因为其开放和拥抱开源的态度, 我也得以参与其中, 成为社区一员. tidb 到底咋样, 有没有它说的那么厉害, 有啥优缺点, 需要找一个合适的对手来比较. 通过比较也可以取长补短, 互相学习. 因为我用腾讯的产品比较多, 也有同学参与了 tdsql 的开发, 对 tdsql 有少量的了解, 所以找它作为比较对象. 首先申明, 我不是数据库专家, 仅仅是入行不久的爱好者, 也没有深度参与两家数据库的开发工作, 所以仅仅是一个仰望者的视角, 会做尽量多的调研, 但主要基于双方公开资料. 简介 tidb tidb 是 pingcap 公司的产品, 创始人刘奇, 黄东旭, 崔秋 均为技术出身, 有多个流行的开源项目, 这可能为 tidb 打下了开放和开源的基因. tidb 历史 先来说说数据库的发展史. 架构 特性 优缺点 生态 总结 参考 腾讯云TDSQL助力金融核心系统数字化转型 TDSQL inside之路 腾讯云TDSQL高可用技术解决方案介绍 TDSQL怎么实现迁移TDSQL云原生

October 10, 2021 · 1 分钟 · ming

some tips for golang range

There are 2 types of range, with index and without index. Let’s see an example for range with index. func TestRangeWithIndex(t *testing.T) { rows := []struct{ index int }{{index: 0}, {index: 1}, {index: 2}} for _, row := range rows { row.index += 10 } for i, row := range rows { require.Equal(t, i+10, row.index) } } the output is: Error Trace: version_test.go:39 Error: Not equal: expected: 10 actual : 0 Test: TestShowRangeWithIndex Above test fails since when range with index, the loop iterator variable is the same instance of the variable with a clone of iteration target value....

September 17, 2021 · 3 分钟 · ming

golang i18n的不同思路

传统的解决方案 i18n是软件开发中常见的一个需求, 很多流行的开发框架如 ruby on rails, springboot 对它有内置的支持。 rails 的 i18n 是其中的佼佼者, 我们看看它解决了哪些问题,是如何解决的。 i18n 资源文件 通常开发者需要按照框架的约定创建资源文件,一般会在目录或文件名中包含如 es, en 等 locale 信息,方便框架按需加载。 |---books |-----es.yml |-----en.yml |---users |-----es.yml |-----en.yml key 的定义和查找优先级 通常每个翻译文本会对应一个有意义的key,通过 key + locale 的组合得到当前 locale 下的翻译文本. I18n.t 'activerecord.models.user' # => 'Customer' I18n.t 'activerecord.models.user' # => '客户' en: activerecord: models: user: "Customer" attributes: user: login: "Login" zh: activerecord: models: user: "客户" attributes: user: login: "登陆" 当项目到一定规模, key 的数量很多时,key 的命名就显得格外重要,否则重用 key 时很难查找。 而且除了用户自定义的 key, 框架一些内置的 key 如日期, 错误消息等, 也需要用户提供翻译。 所以 key 的命名 rails 也做了约定,如下...

June 30, 2021 · 2 分钟 · ming

博客迁移到 hugo

折腾博客的那些事 2012年开始折腾博客,转眼已经8个年头,一开始用的 jekyll, 期间在简书上面也写了少量文章,再基于 halo 搭建了动态站点 topcoder, 然后最近受 苏洋的博客 启发基于 hugo 搭建了本博客。 hola 是带后端的博客程序, 本意是搞一点动态内容和互动进去, 可是本身的懒惰导致写博客都没有好好坚持, 动态站点一年多也跟一个静态站点差不多,没什么动态内容。 而像 苏洋的博客 这样的静态站点, 内容却挺吸引我, 可见重要的是内容。 选型 go 是一门有活力有前途的语言,我最近也正在学习, 这是我选择 hugo 的一个原因, 另一个原因是 hugo 确实很快, 我现在80多篇文章 300 毫米左右, 估计 10000 篇博客以内, 都在一秒内就够了。 Start building sites … | ZH -------------------+------ Pages | 161 Paginator pages | 17 Non-page files | 0 Static files | 1 Processed images | 0 Aliases | 41 Sitemaps | 1 Cleaned | 0 Built in 362 ms 但它的模板语法写起来还是挺繁琐, 做主题, 做静态站点这块前端有一定成本。...

March 27, 2021 · 1 分钟 · ming

multispeack 简单研究

multispeack 简单研究 MultiSpeak Specification 是一个广泛用于北美企业和公用事业部门(如水电)的企业应用互联规范,帮助它们定义接口, 让不同供应商的软件可以不需额外开发接口就可以互联。 为了达成这个目标, 该规范有3个主要部分组成: 通用数据模型 通用数据模型是对某一业务流程的数据的规范,如停电事件模型。通用数据模型使用 XML 描述。 消息结构 为了交换数据,需要定义消息结构,MultiSpeak 使用 WSDL 来描述消息, 用 web service 来交换消息, 支持实时的,或者批量。 业务流程 不同的 web service 调用组成了单个业务流程中的一个步骤,多个步骤组成了一个业务流程, 多个业务流程组成了一个完整的业务。 一个业务流程 和 一个完整的业务分别在模块用户案例和完整用户案例中描述。 使用情况 超过 90 家企业和公用事业部门贡献和使用该规范, 有超过 360 家经过训练的软件供应商 需要注册会员, 不知道是否收费, 未注册尝试 下载规范文档需要收费, 按模块, 每个模块 300 美金, 页面上共 12 个收费模块, 3个免费模块, 详情 费用情况 未见开源产品, 它有一个官方市场, 有一些产品供购买,包括:...

March 19, 2021 · 2 分钟 · ming

rust 和 go 语言调研

java 的弊端 做软件开发已经 10 多年了,主要是偏业务的 web 应用开发, 主要语言是 java, js(typescript),ruby,shell, sql等, 主要框架为 springboot, jquery, vue, rails 等。 随着微服务和云原生的发展,容器成为新一代的虚拟单元,传统 java 技术栈在这一块的不足越发明显: 镜像大 内存占用高 启动慢,跟语言和框架层面都有关系 运行慢 高并发不容易 分发不方便 这些不足跟 java 的虚拟机,面向对象,反射,垃圾回收等语言特性有关。这些特性并不都是坏处, 但随着外部环境的变化,有些特性变的不适用或者不再有优势。 java 社区也在做一些改进,如 java 的反应式编程框架 vertx, 可直接将 java 代码编译成可执行文件的 GraalVM 虚拟机等,但总归是有不少历史包袱,只能在某一些方面做有限改进。 新兴语言 反观一些新兴语言,在运行速度, 资源占用,分发便利性等方面有全面的优势,比较典型的就是 go 和 rust。 go 在网络领域有惊人的表现, 出现了一大堆优秀框架,如 docker, k8s, traefik, canddy 等。 rust 知名项目少一点,有 deno, tikv,libra,ripgrep 等 其中 tidb 作为 new sql 的代表数据库产品之一获得了巨大的成功,它使用 rust 作为存储引擎开发语言, go 作为解析执行引擎开发语言,是两种语言使用的集大成者。...

February 10, 2021 · 1 分钟 · ming

2021年小公司技术架构选型

企业web应用技术讨论 基于兴趣和职业发展的考虑,我参加了上次关于“增量配网产品”架构的讨论会议,对公司现有的产品,人员,技术储备有了一定的了解。 会上对未来几年公司使用的技术栈有了指导性的意见,但候选项只有项目中已经使用的几个非常成熟的技术,个人认为欠缺广度和深度。 仅有限的几个同事参与,意味着可能公司有人掌握了某项技术,但没有成为一个候选项。 除了手边会用的工具, 也应该到市面上找更合适的工具。 一定的技术预研和储备是非常必要的 故写了这篇文章,抛出我的观察和思考,然后看看“沉默的大多数"中有没有志同道合的人,可以将一些更先进(合适)的技术引入公司业务, 助力公司发展。 由于我们讨论的是企业web应用,所以需要关心的问题大概有下面几类,我们依次讨论。 web, 即前端 一些传统的企业开发不重视前端,觉得能用就行,分工上也没有专门的前端工程师,而是由后端工程师一把梭。 但前端的工作量并不小,开发维护成本很高,且易用性美观度等也大大影响用户对软件的整体印象。 如果有多端显示,小程序等需求,则难度和成本更是直线上升。 传统的 js 和 jquery 应用缺乏模块管理,依赖管理,组件化支持等关键特性, 为了解决这些问题,前端的生态发展很快,工程化和模块化水平已经不输后端,出现了 angular, reactjs, vue, svelet 等优秀的 mvvm 框架, 以及 typescript 这样的强类型编译语言,解决了前端大代码量下的开发效率问题。 对于需要 seo 的应用, 纯静态页面和后台生成页面还有一定市场,但对于企业开发,mvvm是完美的解决方案, 也就意味着前后端的完全分离, 后端只提供数据,展示和交互逻辑完全由前端负责。下面简单介绍一下几个 mvvm 框架的特点。 相同点 组件化 响应式数据绑定 状态和路由管理 不同点 reactjs,facebook 出品,生态丰富,使用 jsx 抽象程度高,学习成本高,大公司使用较多。 vue,华人出品,生态较丰富,使用模板抽象程度较高,学习成本低,中小公司和国内使用较多。 svelet 较新,基于一种新的思路,即将运行时的问题提前到编译器解决,目前在前后端均出现了这样的案例。优势是没有运行时,代码小,性能高,很适合做组件开发。 应用层,即后端 移动互联网的发展催生了很多高并发和大数据量的业务,也造就了云厂商的繁荣和容器技术的发展,devops 和云原生等技术被提出,用于解决后端日益复杂的开发运维问题。以 k8s 的出现为标志,基本解决了云环境下的cpu,内存,网络,存储这些计算资源管理和分配问题,有人说 k8s 是云环境下的操作系统,所以后端的开发不得不考虑基础设施到底是啥的问题。...

February 1, 2021 · 1 分钟 · ming