本文主要是介绍FTRL算法性能优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原算法（Worker端）：
1. 对1个mini-batch, 得到每个sample的非0特征值的feature-id，排序(ps-lite要求Key必须有序），去重
2. 以这组feature-id为Key, 从Server上Pull，得到对应的weights
3. 对每个sample[i], 对其所有非0特征值的feature-id对应的weight, 进行加和，得到sum_w[i]
4. 对每个sample[i]的sum_w[i]，得到梯度delta[i] = sigmoid(sum_w[i]) - label[i]
5. 对每个sample[i], 扫描其所有feature-id, 设其对应的weight为weight[k]，累加gradient[k] += delta[i]
6. 把所有gradient[k]，Push给Server, 去更新weights
原实现：
3. 使用feature-id --> weight的map(unordered_map) ，即下面的weight[idx]
5. 使用feature-->gradient的map(unordered_map), 即下面的gradient[idx]
缺点：一个batch大小1000，每个sample个数平均2000， 1000*2000*8Byte=16MB, 在cache中放不下，频繁访问内存，造成速度慢；
原实现代码：
for(int row = start; row < end; ++row){float wx = bias;int sample_size = train_data->fea_matrix[row].size();for(int j = 0; j < sample_size; ++j){idx = train_data->fea_matrix[row][j].fid;wx += weight[idx];}pctr = sigmoid(wx);float delta = pctr - train_data->label[row];for(int j = 0; j < keys_size; j++){gradient[(*keys)[j]] += delta;}}优化实现：
1. 把所有sample的所有key, 放到struct数组里，struct字段：{key, sample-id}
2. 把struct数组（名字为sortedKS)按key从小到大排序
3. 把key单独放在一个数组（名字为keys)里，向Server去Pull Weights, 得到weights数组
4. 对sortedKS和keys进行类归并扫描操作，匹配中的，找到struct对应的sample-id，更新对应的weight:
sum_w[sortedKS[soredKS_id].sample-id] += weights[keys_id]
5. 循环sum_w(长度为sample个数), 得到梯度delta[i] = sigmoid(sum_w[i]) - label[i]
6. 同步骤4，再次类归并扫描，匹配中的，累加对应的gradient:
gradient[keys_id] += delta[sortedKS[soredKS_id].sample-id]
优点：无Hash表；顺序扫描数组；sum_w和gradient只有几KB, 可以放入cache
这篇关于FTRL算法性能优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
