一个使用机器学习算法的框架，在特征处理模块，往往需要对原始特征进行特征交叉。对于简单的单值特征来说，只需要将需要交叉的特征组合起来即可；但是对于多值特征之间的交叉，则需要穷举多值特征每一个值的组合。例如，如果一个包含2个值的特征和一个包含3个值的特征组合，那么将会产生出6个组合。
一般的，我们可以把这些多值特征描述为
vector<vector<Feature>>那么给定这样的一个数据结构，如何输出所有的特征组合呢？
直观想法，这好像是直接遍历就可以解决，但是稍微细想一下，简单的N重for循环，无法解决这个问题。
在纸上画了一会儿之后，突然发现，这不就是一个输出全排列的问题吗？
把问题抽象出来之后，我先是按照手工枚举全排列的思路，写了一个非递归的循环版本，但是可读性不好。然后又实现了一个可读性更好的递归版本。
上面这个问题，只是一个引子。
我相信，程序员在大学毕业找工作的时候，一定刷过各种各样的算法题、数据结构题，什么贪心算法、动态规划、快排、二分查找，现在算法工程师们还要手推SVM、反向传播算法等等，面试时也是历尽千辛万苦；然而工作后却发现，正是应了题目那句话：面试造核弹，工作拧螺丝。
Read full article from 后端技术小黑屋
No comments:
Post a Comment