普通视图

理解C++中的std::transform_reduce及示例

理解 C++ 中的 std::transform_reduce 及示例

std::transform_reduce 是一个强大的 C++17 算法,它结合了 transformreduce(或 accumulate)的功能。它允许你对元素进行转换,然后使用二元操作进行归约,从而写出简洁高效的代码

语法

template<class InputIt1, class InputIt2, class T,
         class BinaryOp1, class BinaryOp2>
T transform_reduce(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, T init,
                   BinaryOp1 binary_op1,
                   BinaryOp2 binary_op2);

template<class InputIt, class T,
         class BinaryOp1, class UnaryOp>
T transform_reduce(InputIt first, InputIt last,
                   T init,
                   BinaryOp1 binary_op1,
                   UnaryOp unary_op);
  • 它可以对每个元素应用 一元转换(可选)。
  • 然后使用 二元操作对结果进行归约,如求和、求积或自定义组合
  • 在 C++17/20 中支持 并行执行策略

示例 1:求平方和

#include <iostream>
#include <vector>
#include <numeric>
#include <execution>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    int sum_of_squares = std::transform_reduce(
        std::execution::seq,   // 顺序执行
        numbers.begin(),
        numbers.end(),
        0,                     // 初始值
        std::plus<>(),    // 二元操作(求和)
        [](int x){ return x*x; } // 一元转换(平方)
    );

    std::cout << "平方和: " << sum_of_squares << std::endl;
    return 0;
}

示例 2:向量点积

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {4, 5, 6};

    int dot_product = std::transform_reduce(
        a.begin(), a.end(),
        b.begin(),
        0  // 初始值
    );

    std::cout << "点积: " << dot_product << std::endl;
    return 0;
}

示例 3:并行 transform_reduce

#include <iostream>
#include <vector>
#include <numeric>
#include <execution>

int main() {
    std::vector<double> numbers(1'000'000, 1.5);

    double sum = std::transform_reduce(
        std::execution::par,  // 并行执行
        numbers.begin(),
        numbers.end(),
        0.0
    );

    std::cout << "并行求和: " << sum << std::endl;
    return 0;
}

关键点

  • transform_reduce 避免了为转换后的值创建中间容器
  • 支持 顺序并行执行策略。
  • 有两种主要形式:单个范围带一元转换,或者两个范围进行成对操作(如点积)。
  • 初始值是必须的,以正确处理空范围。
std::transform_reduce 可以让你的代码更简洁、更高效,尤其适合大数据集或并行计算场景。 [show_file file="/var/www/wp-post-common/justyy.com/cpp.php"] 英文:Understanding std::transform_reduce in Modern 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. 被动收入可遇不可求 被动收入做大了, 就是创业了. 年轻的时候多想想, 积累知识和资源, 有时候真就需要一个想法和机遇. ...
  8. 把年假分成几周请完 – 工作不是全部 我的工作合同里写着 一年享有 25年工作日 带薪假期 这是比较好的福利之一. 搬家的时候请了三天 还有就是零零散散请了几天 比如 看GP 等等. 每年假期可以有 5天能移到 下一年使用 所以我就把剩下的请了 但是是每周请一天...

用 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 已被清洗,人们对加密行业安全漏洞的担忧持续存在,同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起,共同导致了比特币近期的剧烈价格波动。...

对算法工程师一职的思考

2015年10月11日 08:00

如果要我想别人做自我介绍,那么大概我会这样来描述自己:

我是一个热爱幻想小说的理智而沉默的人,目前在一家在线教育公司中从事算法工程师一职。

然而有时候我发现自己并不能向别人很好地解释清楚”算法工程师“的具体含义,进而只好列举自己当前的工作内容。按理说作为算法工程师,我自己应该是对这个职位有足够的理解,但当我自问算法工程师究竟为何时,得到的也是含糊不清的回答。

我尝试去梳理自己对这个职位的理解,并记录下来,如果以后能一直从事相关工作,再回过头来看这篇文章,大概也会别有一番趣味。

从做过的工作说起

作为一个算法工程师的我,做过什么工作呢?从项目的角度上来说,主要有这么几个:

  • 说话人分割(Speaker Diarization): 对一段音频,确定 何人在何时说话
  • 情感识别: 对一段音频,判断说话者在其中表达的是 正面的情感 还是 负面的情感
  • 题库搜索
  • OCR
  • 学生能力评估

以上工作,都需要设计一个完整的算法或“系统”来去解决,然而这里作为一个具体解决方案的“算法”和“系统”,与普通的项目解决方案有什么本质上的区别呢?

第一点不同是,以上问题的“输入”都存在很大的不确定因素,而且对这些不确定因素不易检测和处理。对于普通的软件、APP以及网站来说,所谓的输入(主要为用户操作),是会限定在一个有限集合中的,因而可以按照设计好的逻辑进行处理;但在上述具体项目中,无法保证输入是符合要求的,对输入数据的处理(过滤、规整、变换)——即所谓的“预处理”是系统中的必需部分。

数据的预处理,在算法岗涉及的工作中,是非常重要的。核心的算法,在学术界的推动下,都有很多成熟、可靠的选择,但这些算法,往往都对输入的数据有严苛的要求,数据的预处理如果做得不好,再好的核心算法往往也无能为力。 但由于输入数据天然的不稳定性和复杂性,数据预处理往往也是烦琐而复杂的,需要根据实际的业务情况和数据情况设置各种各样的规则来处理。对于一些成熟的领域如语音、图像,异常数据的种类是有限的,因此也有通用的处理方法,所谓的“去噪”就是图像和语音识别中比较重要的预处理方法;但业务情况却随产品的定位和功能而千变万化,这就需要算法工程师对具体产品的业务有深入的理解。

以我做过的“说话人分割项目“来说,在预处理阶段,需要做这些事情:

  1. 音频格式转换

    收到的客户的音频数据往往格式杂乱,而且这些音频为了便于保存和传输,大都是经过压缩的格式,在进行转换后可能会有一定程度的失真。

  2. 去除明显的非人声和静音,所谓非人声包括: 通信噪音、场景噪音、音乐

    对于与人声不重叠的非人声,可以通过语音活性检测(Voice Activity Detection, VAD)来进行区分,难点在于如何处理与人声混杂在一起的噪声。

  3. 定位不同说话人连续语音的起始和结束点

    如果有两个人(甚至三个人以上)同时在说话,那么这个起始和结束点会不准确。

此外还有一些干扰情况,如音频是无效的、损坏的数据 —— 这种情况往往不多,但由于混杂在大量正常数据中,往往直到造成了问题才会被发现。

其他几个项目同样面临这个问题,甚至在一些项目上,数据如何才算有效、健康都尚待定义,这种情况数据预处理更为艰难。

但数据还不是影响算法工程师工作的首要环节,需求才是。

需求 > 数据 > 系统 > 算法

算法工程师,首先是作为工程师存在的,其工作成果当然也要为实际需求服务;其次,算法工程师的项目不会是孤立的,必然会和其他项目有关联。对项目提出的直接需求,以及对相关联项目的需求,都会对项目有很大影响:

  1. 需求会决定数据的来源和质量
  2. 需求会决定算法实现的复杂性

当然了,这一点不是算法工程师与其他开发人员的工作内容上的差异,因为其他开发人员同样要受到业务需求的影响。

也许有人会觉得算法工程师处理的问题都需要高深的理论基础,但其实不是的,或者说不单纯是。从项目实现角度上来说,现在已经有了非常多的、高效的系统和框架,各种具体的算法也有成熟的实现,单纯想要建立一个解决问题的系统,非算法工程师只要了解一下相关的专有名词,根据业务需求调研使用何种框架或库,熟读相关的文档和 tutorial,也是可以做到的。但得到一个基本可用的系统后,由于之前提到的数据问题,以及系统本身的问题,是无法得到完美的结果的,需要通过大量数据进行持续的调优,而这个过程,是需要对业务情况和相关理论有较深的理解的。

这是第二点不同,即项目需要使用大量的数据进行长期的观察、优化,从一个基本可用的项目到一个令人满意的项目,中间往往需要比较长的时间。

以上是个人根据自身经历得到的一些体会。

再谈这个职位

由于无法进行快速迭代,算法工程师的工作强度不算太大(相对而言),而且一般待遇不错,这算是这个职位的优点了。而相对的,算法工程师的工作会比较枯燥,远没有外行人所想象的那么“酷”,而且大部分时间是在做工程化和调优,其实并没有太多时间去做探索性的工作。

在我看来,要做好算法工程师的工作,首先确实需要有一定的理论基础,其次应该要一定的数据处理能力和意识,然后要有足够的耐心。另外一些人对算法工程师工作的看法的一个误区是,太过重视某种流行的模型、方法的作用,接触到问题后就想直接套用某个模型 —— 选择使用什么模型、方法应当慎之又慎,至少应当在对业务和数据有足够多的认识后再做决定,并且要有全局性的思维,从数据处理,特征工程,到模型,到结果解释,要对各个环节都有考虑。

排序算法——堆排序

2014年1月12日 08:00

堆排序概述

堆排序通过建立大顶堆(或小顶堆)来进行排序,要理解这个算法,首先要明白什么是 大顶堆 或者 小顶堆

这里的堆是一种数据结构,它是一棵完全二叉树(除最后一层外,其他层都是满的),且每个节点都具有同一种特性,那就是该节点的值大于子节点的值,或者节点的值小于子节点的值,前者被称为 大顶堆 ,后者被称为 小顶堆 。大顶堆的根节点的值一定是整个堆中最大的,小顶堆的根节点的值一定是堆中最小的。利用这个特性,如果要对一个数组进行升序排序,那么可以按照以下步骤进行:

  1. 将数组元素视为一个堆,建立大顶堆
  2. 将堆顶元素和堆尾元素交换,并出堆
  3. 对堆进行处理,维持大顶堆性质
  4. 重复2、3步(此时已出堆的元素不再处理),直到堆中只有一个元素

堆排序实现

首先,要从逻辑上建立对堆的相关操作,在排序中并不需要建立一棵二叉树,而是将数组“视为”二叉树即可。对于二叉树而言,最起码的,应该有取得某个节点的父节点及子节点的功能。

节点访问

用python实现如下:

 1: def parent(heap, node):
 2:     if node > 0:
 3:         return (node - 1) / 2
 4:     else:
 5:         return 0
 6: 
 7: def lchild(node):
 8:     return 2 * node + 1
 9: 
10: def rchild(node):
11:     return 2 * node + 2

建立大顶堆

建立大顶堆要从最后一个具有子节点的节点上开始操作,将当前节点作为一个大顶堆的堆顶,进行堆性质维持的处理。并逐步往前对该节点的兄弟节点、父节点进行同样的操作。

首先需要实现一个堆性质维持处理函数,实现如下:

 1: def heapify(heap, root, size):
 2:     max_index = root
 3:     l = lchild(root)
 4:     r = rchild(root)
 5:     if  l < size and heap[l] > heap[max_index]:
 6:         max_index = l
 7:     elif r < size and heap[r] > heap[max_index]:
 8:         max_index = r
 9: 
10:     if root != max_index:
11:         heap[root], heap[max_index] = heap[max_index], heap[root]
12:         heapify(heap, max_index)
13: 
14:     return None

用python实现如下:

1: def build_heap(heap):
2:     size = len(heap)
3:     last = size / 2 - 1
4:     for cur in range(last, -1, -1):
5:         heapify(heap, cur, size)

实现堆排序

根据堆排序概述中的内容,可以大致将堆排序描述如下:

 1: def hsort(arr):
 2:     size = len(arr)
 3:     last = size - 1
 4:     build_heap(arr)
 5: 
 6:     while size > 1:
 7:         arr[0], arr[last] = arr[last], arr[0]
 8:         last = last - 1
 9:         size = size - 1
10:         heapify(arr, 0, size)
11: 
12:     return None

结合前面实现的parent、lchild、rchild、heapify、build_heap几个函数,就可以实现一个完整的堆排序算法了。

发散:TOP K问题

所谓的 TOP K问题 ,是指在大规模数据处理时常遇到的一类问题,要求在海量数据中找出最大的前K个数。这个问题可以通过建立小顶堆来解决——当然了,为了效率和资源的有效利用,这类问题通常还有整体方面的架构设计等工作需要做,远不是只建立一个小顶堆就能解决的,不过这些本文不作讨论。

通过预先读入K个数据并建立小顶堆后,再逐个读入数据,将新元素和堆顶元素进行比较,如果新元素小于堆顶元素,就丢弃;如果新元素大于堆顶元素,则用新元素替代堆顶元素,并且重新调整堆使之保持小顶堆性质。

这样处理后,总可以保证 目前 读到的数据中最大的K个在小顶堆中。

当我一开始接触到这个问题时,我幼稚地认为应该使用大顶堆,但实际上是错误的。用大顶堆可以保证堆顶元素是最大,但不能保证堆中元素是前K个最大的数。

我误认为应该使用大顶堆的原因还有一个,那就是忽视了“海量数据”这个情境。

对于小规模的TOP K问题,可以直接将数据进行排序,然后取出最大的K个数。但海量数据处理中,数据是不可能同时全部进入内存的。

排序算法——归并排序

2014年1月11日 08:00

归并排序

归并排序也是一种使用分治法来实现的有效排序算法,它是现代计算机创始人John von Neumann于1945年发明的。

归并排序在众多排序算法中既是稳定排序,又有不错的效率,同时,归并排序不仅可以用于内排序,还可以用于外排序。所以说归并排序是非常值得学习的。

本文将对归并排序的思想进行阐释,并给出完整的实现,然后对外排序进行探讨。

算法思想

归并排序的思路如下(以二路归并为例):

  1. 将数组划均分为两个子数组;
  2. 对两个字数组进行排序;
  3. 将排序好的两个字数组归并。

所谓 N路归并 是指将数组均分为N个子数组,将字数组排序后再归并。因此二路归并是归并排序的最一般的情况。

这里是二路归并排序的一个图示: merge-sort.png

二路归并排序用python描述如下:

1: def msort(array):
2:     length = len(array)
3:     if length == 1:
4:         return array
5:     else:
6:         mid = length / 2
7:         left = msort(array[0: mid])
8:         right = msort(array[mid: length])
9:         return merge(left, right)

当然,这里描述的是递归版本的算法,实际情况中有时候也会为了效率而使用循环而不是递归来实现归并排序。下面是使用循环的算法描述:

 1: def msort(array):
 2:     length = len(array)
 3:     step = 1
 4:     while step < length:
 5:         for left in range(0, length - step, 2 * step):
 6:             result = merge(array[left:left + step],
 7:                            array[left + step: min(left + 2 * step,
 8:                                                   length)])
 9:             array = array[0:left] + result + array[min(left + 2 *
10:                                                        step, length)]
11:         step = step * 2
12:     return array

msort中的归并部分(merge)的思想是:分别取出字数组中最小的元素,取它们中较小的放入原数组中,然后重复这个过程。《算法导论》中将这个过程类比为整理扑克牌的过程,非常形象。想象一下,桌面上有两堆扑克,它们都朝下扣着,并且按照牌面点数从小到大放置,我们要的是把这两堆扑克都拿到手里,并且按照从小到大的顺序排好序,这个时候要怎么做?

归并的思想可以用python描述如下:

 1: def merge(left, right):
 2:     llen = len(left)
 3:     lcur = 0
 4:     rlen = len(right)
 5:     rcur = 0
 6:     result = []
 7:     while lcur < llen and rcur < rlen:
 8:         lone = left[lcur]
 9:         rone = right[rcur]
10:         result.append(min(lone, rone))
11:         if lone < rone:
12:             lcur += 1
13:         else:
14:             rcur += 1
15:     result += left[lcur:]
16:     result += right[rcur:]
17:     return result

完整实现

下面是综合了非递归与递归版本的二路归并排序的完整实现,结果由org-babel对代码块求值得到。

 1: # -*- coding: utf-8 -*-
 2: def merge(left, right):
 3:     llen = len(left)
 4:     lcur = 0
 5:     rlen = len(right)
 6:     rcur = 0
 7:     result = []
 8:     while lcur < llen and rcur < rlen:
 9:         lone = left[lcur]
10:         rone = right[rcur]
11:         result.append(min(lone, rone))
12:         if lone < rone:
13:             lcur += 1
14:         else:
15:             rcur += 1
16:     result += left[lcur:]
17:     result += right[rcur:]
18:     return result
19: 
20: def msort_rec(array):
21:     length = len(array)
22:     if length == 1:
23:         return array
24:     else:
25:         mid = length / 2
26:         left = msort_rec(array[0: mid])
27:         right = msort_rec(array[mid: length])
28:         return merge(left, right)
29: 
30: def msort_iter(array):
31:     length = len(array)
32:     step = 1
33:     while step < length:
34:         for left in range(0, length - step, 2 * step):
35:             result = merge(array[left:left + step],
36:                            array[left + step: min(left + 2 * step,
37:                                                   length)])
38:             array = array[0:left] + result + array[min(left + 2 *
39:                                                        step, length):]
40:         step = step * 2
41:     return array
42: 
43: if __name__ == '__main__':
44:     L = [1, 4, 2, 6, 3, 5, 8, 7]
45:     print "排序前: %r" %(L)
46:     R = msort_rec(L)
47:     print "排序后(递归): %r" %(R)
48:     I = msort_iter(L)
49:     print "排序后(非递归): %r" %(I)

结果

排序前: [1, 4, 2, 6, 3, 5, 8, 7]
排序后(递归): [1, 2, 3, 4, 5, 6, 7, 8]
排序后(非递归): [1, 2, 3, 4, 5, 6, 7, 8]

发散:外排序应用

归并排序的思想可以用于外排序。外排序是相对内排序而言的。在常规的小规模排序过程中,都是直接在内存中对数据进行排序处理的,而对于数据量极大的排序问题,这种方式是不现实的。这个时候就要通过外排序来进行,先将数据划分成多个规模能在内存中处理的子集,对各个子集排序后存放在临时的磁盘文件上,然后再将这些子集归并到输出文件中。这个过程要使用到多路归并,如下图所示:

external-sort.png

注:该图来自 References 中第一篇文章。

那么来实现一下吧。

首先要创建一个大文件,往里面写入大量的数据,该函数实现如下(因为python不方便读取单个数字,下面的东西都是用C写的):

 1: #include <stdio.h>
 2: #include <stdlib.h>
 3: #include <time.h>
 4: 
 5: int rand_file(char *file, int num)
 6: {
 7:     int i = 0;
 8:     int now;
 9:     FILE *f = fopen(file, "w");
10: 
11:     if (f == NULL) {
12:         perror("fopen");
13:         return 0;
14:     }
15: 
16:     for (; i < num; ++i) {
17:         srand((int)time(0));
18:         now = rand();
19:         fprintf(f, "%d ", now);
20:     }
21: 
22:     fclose(f);
23:     return num;
24: }

然后,我们需要一个将文件读入数组的函数和一个将数组内容写入文件的函数,实现如下:

 1: #include <stdio.h>
 2: #include <stdlib.h>
 3: 
 4: int read_to_mem(FILE *file, int *arr, int len)
 5: {
 6:     int i = 0;
 7:     if (file != NULL) {
 8:         for (; !feof(file) && i < len; ++i) {
 9:             fscanf(file, "%d", arr + i);
10:         }
11:         return i;
12:     }
13:     else
14:         return 0;
15: }
16: 
17: int write_from_mem(FILE *file, int *arr, int len)
18: {
19:     int i = 0;
20:     if (file != NULL) {
21:         for ( ; i < len; ++i) {
22:             fprintf(file, "%d ", arr[i]);
23:         }
24: 
25:         return i;
26:     }
27: 
28:     else
29:         return 0;
30: }

完成这些准备工作后,就可以开始实现外排序了。循环将大文件读入一部分到内存,然后对这一部分进行排序——此时的排序可以使用快速排序、归并排序等各种排序算法,并无限制。

将各部分都排好序并保存为临时文件后的归并步骤是外排序的核心所在。多路归并的思路和二路归并是类似的。可以将归并模块实现为:

 1: #include <stdlib.h>
 2: 
 3: void merge(File *out, File **flist, int fnum)
 4: {
 5:     int i = 0;
 6:     int now = 0;                /* 用于保存当前最小的值 */
 7:     int *fstaus = (int *)calloc(fnum, sizeof(int)); /* 记录文件状态 */
 8:     int *farr =(int *)calloc(fnum, sizeof(int));    /* 记录从各个文件中取出的数 */
 9:     int min = 0;                /* 记录当前值最小的文件索引 */
10: 
11:     for (; i < fnum; ++i) {     /* 检查各个文件指针的状态 */
12:         if (feof(fscanf(flist[i], "%d", farr + i))) {
13:             fstatus[i] = 0;
14:         }
15:         else {
16:             fstatus[i] = 1;
17:         }
18:     }
19: 
20:     while (1) {
21:         now = 0;
22:         for (i = 0; i < fnum && !fstatus[i]; ++i) {}
23:         if (i >= fnum) {     /* 如无可用文件,则退出 */
24:             break;
25:         }
26: 
27:         for (; i < fnum; ++i) { /* 从第一个可用的文件开始读 */
28:             if (fstatus[i] && farr[i] < now) {
29:                 now = farr[i];
30:                 min = i;
31:             }
32:         }
33: 
34:         fprintf(out, "%d ", now); /* 将最小值写入输出文件 */
35: 
36:         /* 读取该文件下一个数,并检查是否读完 */
37:         if (feof(fscanf(flist[min], "%d", farr + min))) {
38:             fstatus[min] = 0;
39:         }
40:     }
41: 
42:     free(farr);                 /* 释放内存 */
43:     free(fstatus);
44: }

完整的实现我就不写了,太累……写这篇文章就用了一整天。

嗯,大概就是这个样子。

排序算法——快速排序

2014年1月10日 08:00

快速排序

快速排序是一种广为使用的排序算法,其算法复杂度为O(NlogN),从效率上来说是很不错的。

刚接触排序算法的新手可能没有办法很快地把它实现出来,但其实在对它的原理有了透彻的了解后,这一步是不难做到的。

不记得是在哪里看到的了,说熟悉算法的最好办法,就是反复地去实现它,写完删掉重写,知道能够不怎么思考就把它写出来就算是掌握了。我就是通过这个方法来掌握排序算法的。

原理

快速排序采用了“分治法”,关于分治法不想说太多,更多的细节可以参考维基百科。 具体来说,快速排序的思想是很简单的,分为两步:

  • 将数组划分为以某个值为分界的两部分
  • 对划分好的两部分各自又进行快速排序

其中第二步就是“分治法”的体现,即所谓“分而治之”。而快速排序的实现工作大多花费在“划分”上。

下面是快速排序的算法描述(python描述)

1: def qsort(array, low, high):
2:     if low < high:
3:         mid = partition(array, low, high)
4:         qsort(array, low, mid - 1)
5:         qsort(array, mid + 1, high)
6:     return array

数组划分

我对这一部分是非常感兴趣的,因为我发现这一部分不仅仅可以用在快速排序中。

划分首先要选定一个值作为分界线。选取这个值的方法有随机选取和固定选取两种,随机选取就不说了,顾名思义;固定选取就是选取当前要划分的区域上特定位置的元素,比如第一个元素或者最后一个元素。本文以选取最后一个元素为例来进行说明。

划分的思想就是,遍历数组,遇到比关键值小的元素,就放到数组前面。在这样的处理过程中,数组前部会有连续的一段空间,其中的所有元素都比关键值小,因此在处理的过程中通常要用一个游标来记录这段空间的最后一个位置,遇到新的小于关键值的元素要放过来时,就将其放到游标后面的位置,并更新游标。如下图所示

partition.png

当然,我这里说的是将比关键值小的元素交换到数组前部,也有将大于关键值的元素交换到数组尾部以及结合这两种做法的。

数组划分的算法描述为:

 1: def partition(array, low, high):
 2:     cur = low - 1
 3:     key = array[high]
 4: 
 5:     for index in range(low, high):
 6:         elem = array[index]
 7:         if elem < key:
 8:             cur = cur + 1;
 9:             array[index], array[cur] = array[cur], array[index]
10: 
11:     cur = cur + 1;
12:     array[cur], array[high] = array[high], array[cur]
13: 
14:     return cur;

完整实现

下面是一个完整的实现,以及对给定数组进行排序的示例。注明一下,这里的结果是通过org-babel对下面的代码块求值得到的。

 1: # -*- coding: utf-8 -*-
 2: def partition(array, low, high):
 3:     cur = low - 1
 4:     key = array[high]
 5: 
 6:     for index in range(low, high):
 7:         elem = array[index]
 8:         if elem < key:
 9:             cur = cur + 1
10:             array[index], array[cur] = array[cur], array[index]
11: 
12:     cur = cur + 1;
13:     array[cur], array[high] = array[high], array[cur]
14: 
15:     return cur;
16: 
17: def qsort(array, low, high):
18:     if low < high:
19:         mid = partition(array, low, high)
20:         qsort(array, low, mid - 1)
21:         qsort(array, mid + 1, high)
22: 
23:     return array
24: 
25: L = [5, 2, 7, 6, 3, 1, 8, 4]
26: print "排序前: %r" %(L)
27: qsort(L, 0, 7)
28: print "排序后: %r" %(L)

结果

排序前: [5, 2, 7, 6, 3, 1, 8, 4]
排序后: [1, 2, 3, 4, 5, 6, 7, 8]

发散

之前说了,快速排序算法中的数组划分其实不仅仅可用于快速排序,那么,它还可以用于什么地方呢?从我的认识来看,很多需要将数据一分为二的情境中都可以使用到这个算法,比如说 删除字符串中的特定字符 以及这个问题的变形 删除字符串中的重复字符 。将快速排序算法中的划分算法稍作修改,就能得到这两个问题的线性复杂度的解决办法。

附上这两个问题的C语言代码

  1. 删除字符串中特定字符

    这里的结果同样是通过org-babel对下面的代码块求值得到的

     1: #include <stdio.h>
     2: #include <string.h>
     3: 
     4: int del_char(char *str, char del)
     5: {
     6:     int cur = -1;
     7:     int index = 0;
     8:     char temp = '\0';
     9:     for (; index < strlen(str); ++index) {
    10:         if (str[index] != del) {
    11:             ++cur;
    12:             temp = str[cur];
    13:             str[cur] = str[index];
    14:             str[index] = str[cur];
    15:         }
    16:     }
    17:     ++cur;
    18:     str[cur] = '\0';
    19:     return cur;
    20: }
    21: 
    22: int main()
    23: {
    24:     char s[] = "abcdaaaaab";
    25:     del_char(s, 'a');
    26:     printf("%s\n", s);
    27:     return 0;
    28: }
    

    得到的结果为:

    bcdb
    
  2. 删除字符串中的重复字符,如将"aabbccdd"处理后得到"abcd"

    这里的结果同样是通过org-babel对下面的代码块求值得到的

     1: #include <stdio.h>
     2: #include <string.h>
     3: 
     4: int del_dup(char *str)
     5: {
     6:     int cur = 0;
     7:     int index = 1;
     8:     char temp = '\0';
     9:     char last = str[0];
    10: 
    11:     for (; index < strlen(str); ++index) {
    12:         if (str[index] != last) {
    13:             ++cur;
    14:             temp = str[cur];
    15:             str[cur] = str[index];
    16:             str[index] = str[cur];
    17:         }
    18:         last = str[index];
    19:     }
    20:     ++cur;
    21:     str[cur] = '\0';
    22: }
    23: 
    24: int main()
    25: {
    26:     char s[] = "aabbccdd";
    27:     del_dup(s);
    28:     printf("%s\n", s);
    29:     return 0;
    30: }
    

    得到的结果为:

    abcd
    

可以看到,这两个函数"del_char"和"del_dup"和之前的qsort中的"partition"函数是非常相似的。

❌