-1

我有两个向量vector<DataPoint> data，vector<string> labelswhereDataPoint只是一个 float: 向量typedef vector<float> DataPoint。每个数据点data[i]都有其关联的标签labels[i]。

有什么方法可以x快速获取给定数据点的标签？类似的东西string getLabel(DataPoint x){..}很快。

4

3 回答 3

2

如果您的向量是排序的，那么您希望找到的最好DataPoint的索引data是O(log(n))复杂性（使用二进制搜索）。否则，这是一个线性搜索。dataO(n)

问题的症结在于你有两个包含相关数据的向量，这总是很难管理（并且强烈暗示了糟糕的设计）。vector<LabeledDataPoints>最好用 a （具有两个成员的结构： aDataPoint和 a ）替换两个向量string。

于 2013-10-28T11:43:41.367 回答
0

一些注意事项：您可以使用 对向量进行排序std::sort()，并使用 搜索预先排序的向量std::binary_search()，std::unordered_map是 C++11 哈希表，std::map是二叉树，您可以使用 O(log2N) 查找进行插入时排序，插入和擦除。谷歌其中任何一个文档。

使用您现有的数据结构，如果 dataPoint 是预先排序的，那么您有 O(log2N)，其中 N 是 dataPoint.size()，并假设平均不相等的 dataPoints 比较只需要比较第一个 float 或两个。未排序，它是 O(N)。

显然，性能问题是不必在已知公共索引后查看标签 - 它只是找出该索引是什么，给定向量之外的 dataPoint 对象data。

如果排序不理想或 O(log2N) 仍然太慢，您可以考虑将数据点放入带有标签的哈希表中。

在不太可能的情况下，性能问题仅是由于您的 dataPoints 经常以相同的浮动前导序列开始，然后（假设没有简单的解决方案，例如从向量的背面到前面进行比较），您可以创建某种散列或首先要比较的元素的总和，如果已知相等，则仅进行逐个浮点比较。

于 2013-10-28T11:54:31.293 回答
0

旧答案（它是关于轻松获取值（DataPoint 实例））：

你为什么不使用地图，使用标签作为键和数据点作为值（地图）？通过这种方式，您将拥有关联的数据，并且根据地图类型，您可以对复杂性进行区分（使用地图，查找复杂度为 O(logn)，而哈希图的预期复杂度为 O(1)，并且O(n) 最坏情况）。使用对您更有效的方法。有关地图及其复杂性的更多信息，请参阅此处：多重集、地图和哈希地图复杂性

更新：

要获取每个 DataPoint 的标签，一个想法是创建一个单独的类（例如 DataContainer），其中包含作为私有成员的 DataPoint 实例向量和包含标签的字符串以及适当的 setter/getter。

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;
    }
  }

这样，您可以将 DataContainer 放在您想要的任何结构中（如果您想类似地获取键，我建议使用 map：map），在实例化时设置标签并使用复杂度为 O(1) 的 getter 方法获取它. 如您所见，您的问题需要以不同的方式处理，并且有一些方法可以做到。

于 2013-10-28T12:00:42.177 回答