Quickly get an element from vector2 given an element from vector1

Question

I have two vectors vector<DataPoint> dataand vector<string> labels where DataPoint is just a vector of float: typedef vector<float> DataPoint. Each datapoint data[i] has its associated label labels[i].

Is there any way to get the label of a given datapoint x quickly ? Something like string getLabel(DataPoint x){..} which is fast.

Answer 1

The best you can hope to find your DataPoint's index in data is O(log(n)) complexity (using a binary search) if your data vector is sorted. Otherwise that's a linear search in O(n).

The crux of the problem is that you have two vectors that contain related data, which is always a pain to manage (and a strong hint of bad design). Best replace both vectors with a vector<LabeledDataPoints> (a structure with two members: a DataPoint and a string).

Answer 2

A few notes: you can sort a vector with std::sort(), and search a pre-sorted vector with std::binary_search(), std::unordered_map is the C++11 hash table, std::map is a binary tree, which you could use for insertion-time sorting with O(log2N) lookup, insertion and erase. Google any of them for docs.

With your existing data structures, if dataPoint is pre-sorted, then you have O(log2N) where N is dataPoint.size(), and assuming that on average unequal dataPoints comparison need only compare the first float or two. Unsorted, it's O(N).

Clearly the performance issue is not having to look in labels after the common index is known - it's just finding out what that index is, given a dataPoint object outside the data vector.

If sorting is undesirable or O(log2N) is still too slow, you could consider putting the dataPoints into a hash table with their label.

In the unlikely case that the performance issue is only due to your dataPoints regularly starting with the same leading sequence of floats, then (assuming no trivial solution like comparing from the back of the vector towards the front) you could create some kind of hash or sum of the elements to compare first, only doing a float-by-float comparison if that's already known equal.

Answer 3

Old Answer (it is about getting the values (DataPoint instances) easily):

---

Why don't you use a Map, using labels as keys and DataPoint as values(map)? In this way, you will have the data associated, and depeding on the map type, you can have differentiations on complexities(using a map, will have a lookup complexity O(logn), while a hashmap will have O(1) expected and O(n) worst case). Use what works for you better. For more information on maps and their complexities, look here too: multiset, map and hash map complexity

---

UPDATE:

To get the label for each DataPoint, one idea is to create a separate class (for example DataContainer) that contains as private members your vector of DataPoint instances and a string that contains your label with the appropriate setters/getters.

class DataContainer{
  private:
    DataPoint mDataPoint;
    string mLabel;

  public:
    DataContainer(DataPoint dataPoint,string label): 
      mDataPoint(dataPoint), mLabel(label){}

    void setDataPoint(DataPoint dataPoint){
      mDataPoint = dataPoint;
    }

    void setLabel(string label){
      mLabel = label;
    }

    DataPoint getDataPoint(){
      return mDataPoint;
    }

    //This getter does the job, with O(1) complexity.
    string getLabel(){
      return mLabel;
    }
  }

This way, you can put your DataContainer in any structure you want (and I suggest map in the case you want to get the keys similarily: map), setting the label on instantiation and getting it with the getter method with O(1) complexity. As you can see, your question needs to be approached differently, and there are some ways to do it.