4
\$\begingroup\$

Problem

I have a stream composed of 2 columns and 1000 lines:

  1. Column 1: contains the patterns that I want to find
  2. Column 2: contains the values corresponding the the patterns in Column1

I want to search for the patterns in column 1, extract their corresponding values in column 2 and save them in vectors. I actually have 3 types that I want to look for which are : {type, label, name}. Therefore i'll have 3 vectors for every type .pair<string,string> represents column 1 and column 2.

vector<pair<string,string>>` types
vector<pair<string,string>> Labels
vector<pair<string,string>> names

I read the file sequentially. If I find the pattern that I am looking for in column 1 I extract the value in column 2 and append it with the corresponding vector.

All the other patterns will be saved in a vector called others.

vector<pair<string,string>> others

Sample

Column 1 contains the patterns that I want to look for{type, label, name}. and Column 2 the corresponding values

rdf-syntax-ns#type base.qualia.topic
rdf-syntax-ns#type common.topic
rdf-syntax-ns#type film.producer
rdf-schema#label  สตีฟ จอบส์
rdf-schema#label  ﺎﺴﺗیﻭ ﺝﺎﺑﺯ
rdf-schema#label  Styvas Džobsas
type.object.name ﺎﺴﺗیﻭ ﺝﺎﺑﺯ
type.object.name Styvas Džobsas
type.object.name Steve Jobs
type.object.name Steve Jobs

What is the fastest way to search and extract the values?

The following source code takes 0.04 seconds to read 1000 lines, find the patterns and extract their corresponding values.

void returnValues(const string & file, vector<pair<string,string>> & types, vector<pair<string,string>> & labels, vector<pair<string,string>> & names, vector<pair<string,string>> & others)
{
  istringstream str(file);
  string line;
  //skip first line
  getline(str,line);
  while(getline(str, line))
  {
    
     vector<string> values;
     line.erase(remove( line.begin(), line.end(), '\"' ), line.end());
     boost::split(values, line, boost::is_any_of("\t"));     
     if(contains(values[0],"type"))
     {
         pair<string,string> fact = make_pair(values[0], values[1]);
         types.push_back(fact);
      }
      else if(contains(values[0],"label"))
      {
          pair<string,string> fact = make_pair(values[0], values[1]);
          labels.push_back(fact);
      }
      
      else if(contains(values[0],"name"))
      {
        pair<string,string> fact = make_pair(values[0], values[1]);
        names.push_back(fact);
      }
     else
     {
        pair<string,string> fact = make_pair(values[0], values[1]);
        others.push_back(fact);
      }
   }
}//end function
\$\endgroup\$
8
  • 2
    \$\begingroup\$ Any reason why 0.04 seconds isn't fast enough? Why do you want it reduced to specifically 0.02 seconds? \$\endgroup\$ – Simon Forsberg Jun 26 '15 at 12:31
  • \$\begingroup\$ I have 50,000,000 million records. Every Record Has 1000 lines. So 0.04 x 50 Millions that's a lot. I don't know if I can do better. \$\endgroup\$ – Hani Goc Jun 26 '15 at 12:38
  • \$\begingroup\$ Have you profiled? \$\endgroup\$ – Emily L. Jun 26 '15 at 14:19
  • \$\begingroup\$ @EmilyL. no I didn't \$\endgroup\$ – Hani Goc Jun 26 '15 at 14:21
  • \$\begingroup\$ For future reference. Please post the whole code in a runnable example. \$\endgroup\$ – Emily L. Jun 26 '15 at 14:31
7
\$\begingroup\$

Without profiling data, I can only guess... so here goes:

At a quick glance the biggest inefficiency I can see is that you allocate and de-allocate the vector capacity for values in each iteration. This takes some time, just move the vector outside of the loop and use clear() at the head of the loop.

Like this:

vector<string> values;
while(getline(str, line))
{
   values.clear();

Another thing that you can do (even though I don't believe it will affect your result significantly) is to use emplace_back instead of push_back to avoid the possibility of a copy.

Like this:

 types.emplace_back(values[0], values[1]);

This will construct the pair in place and avoid the pair copy constructor (the compiler might have optimized this for you already). While we're at it, we can realize that values will not be used after this statement until it is cleared. So we can steal the memory and avoid another two new/deletes (unless your STL has SSO and your strings are small, in which case this is moot) just activate the move construction of the pair like this:

 types.emplace_back(std::move(values[0]), std::move(values[1]));
\$\endgroup\$
4
\$\begingroup\$

Hold on.
You are going for speed. BUT you first read the whole file into a string before processing?

void returnValues(const string & file, vector<pair<string,string>> & types, vector<pair<string,string>> & labels, vector<pair<string,string>> & names, vector<pair<string,string>> & others)
                  ^^^^^^^^^^^^^^^^^^^

Why not make the first parameter a stream. That way if it is already in a file you pass a file stream. If it is already a string you pass a stringstream.

You are not checking for errors. So we can assume that each line has been validated and is known to be correctly formed.

So rather than reading a line at a time. Just parse the values you want.

std::string   type;
std::string   label;
std::string   name;

if (stream >> type >> label >> name) {

    // This line is me playing.
    // To make the next line work for all cases.
    std::vector<std::pair<std::string, std::string>>& dst =
          type == "type"
              ? types
              : type == "label"
                  ? labels
                  : type == "name"
                       ? names
                       : others;

     // Use emplace_back to it is built in-place by the vector.
     // So we avoid a copy of the pair into the vector.
     // Also enable move semantics so we don't copy the string.
     dst.emplace_back(std::move(label), std::move(name));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.