如何加快我的 Libsvm 向量到 std::vector<float> 的转换?

How to speedup my Libsvm vector to std::vector<float> conversion?

简介

我有以下形式的 libsvm 向量:

{i_1:v_1; i_2:v_2;...; i_n:v_n}

其中i_j:v_j分别代表index。如果该值为 null 则不会给它任何索引。

My objective is to compute the euclidean distance between two libsvm vectors. For that I have to convert them to vector<float> of the same size. In the following example i'll be showing the function that I used in order to convert the libsvm vector into vector<float>.


例子

第一列有一个索引 = 2648 和一个值 = 0.408734 意味着它之前的所有值都是零。

LIBSVM 向量 = 2648:0.408734;4157:0.609588;6087:0.593104;26747:0.331008


源代码

#include <vector>
#include <string>
#include <chrono>
#include <boost/algorithm/string.hpp>

using namespace std;
using namespace chrono;
//convert libsvm vector to float vector in order to compute the similarity
vector<float> splitVector(const vector<string> &);

int main()
{
   vector<string> libsvm {"2648:0.408734","4157:0.609588","6087:0.593104","26747:0.331008" };
   high_resolution_clock::time_point t1 = high_resolution_clock::now();
   vector<float> newVec = splitVector(libsvm);
   high_resolution_clock::time_point t2 = high_resolution_clock::now();
   auto duration = chrono::duration_cast<chrono::microseconds>( t2 - t1 ).count();
   cout <<"construction time: " << duration << endl;
   return 0;
}

vector<float> splitVector(const vector<string> & v)
{
    int numberofterms = 266373;
    vector<float> values;
    vector<int> previous_idx;
    for(int i = 0; i < v.size(); i++)
    {
        vector<string> tmpv;
        boost::split(tmpv, v[i] , boost::is_any_of(":"));
        //idx:value
        int idx = atoi(tmpv[0].c_str());
        float val = atof(tmpv[1].c_str());

        //summation of previous indices
        int sum = accumulate(previous_idx.begin(), previous_idx.end(), 0);
        int n = idx - (sum + i + 1);
        //fill vector with 0s
        for(int k = 0; k < n; k++)
            values.push_back(0.0);
        //add value
        values.push_back(val);
        previous_idx.push_back(n);
    }//end for

    int paddingsize = numberofterms - values.size();

    for(int i = 0; i < paddingsize;i++)
    {
      values.push_back(0.0);
    }
    return values;
}//end function

问题

转换的时间大约是 0,00866 秒,当我有大约 1000 向量时它会变慢。有没有更快的方法将 libsvm 向量转换为 vector<float>?


修改函数

values.resize(266373,0.0);
void splitVector(const vector<string> & v, vector<float> & values)
{
    vector<string> tmpv;
    for(int i = 0; i < v.size(); i++)
    {
        boost::split(tmpv, v[i] , boost::is_any_of(":"));
        //idx:value
        int idx = atoi(tmpv[0].c_str());
        float val = atof(tmpv[1].c_str());
        tmpv.clear();
        values[idx] = val;
    }//end for

}//end function

您可以通过重用 vector 来减少内存分配的时间成本。 更具体地说,

  • 通过在 for 循环之前声明它来重用 tmpv,并在每个循环的开头调用 tmpv.clear()
  • 通过values.reserve()预分配values;并用 values.resize(266373, 0.0) 填充它而不是重复 push_back().
  • 尽可能重复使用 previous_idx。这可能会对代码结构和可维护性产生负面影响。