在每个元素上计算一个值并根据该值对向量进行排序，而不需要对每个元素多次执行计算。

Question

有人能推荐一种简洁明了的方法来实现这个吗：

float CalculateGoodness(const Thing& thing);

void SortThings(std::vector<Thing>& things)
{
    // sort 'things' on value returned from CalculateGoodness, without calling CalculateGoodness more than 'things.size()' times
}

显然，我可以使用一个调用CalculateGoodness的比较函数来使用std::sort，但这样会在每个Thing与其他元素进行比较时多次调用它，如果CalculateGoodness很耗费时间，那就不好了。我可以创建另一个std::vector来存储评分，并对其进行std::sort，然后以相同的方式重新排列things，但我看不到一个整洁的方法来做到这一点。有什么想法吗？

编辑：抱歉，我应该说不修改Thing，否则这是一个相当容易解决的问题 :)

- Ben Hymers

Answer 1

我可以想到两种简单的方法来实现您想要的结果。您可以使用适当的谓词来使用 std::transform。

• std::vector<Thing> 转换为 std::vector< std::pair<Result,Thing> >
• 对第二个向量进行排序（因为一对是由其第一个成员排序的）
• 反转换

完成:)

编辑: 最小化拷贝次数

• std::vector<Thing> 转换为 std::vector< std::pair<Result,Thing*> >
• 对第二个向量进行排序
• 转换回辅助向量（本地）
• 交换原始和本地向量

这样，每个Thing只会被复制一次。值得注意的是，sort 也会执行复制，所以使用它可能是值得的。

因为我感觉很慷慨:

typedef std::pair<float, Thing*> cached_type;
typedef std::vector<cached_type> cached_vector;

struct Compute: std::unary_function< Thing, cached_type >
{
  cached_type operator()(Thing& t) const
  {
    return cached_type(CalculateGoodness(t), &t);
  }
};

struct Back: std::unary_function< cached_type, Thing >
{
  Thing operator()(cached_type t) const { return *t.second; }
};


void SortThings(std::vector<Thing>& things)
{
  // Reserve to only allocate once
  cached_vector cache; cache.reserve(things.size());

  // Compute Goodness once and for all
  std::transform(things.begin(), things.end(),
                 std::back_inserter(cache), Compute());

  // Sort
  std::sort(cache.begin(), cache.end());

  // We have references inside `things` so we can't modify it
  // while dereferencing...
  std::vector<Thing> local; local.reserve(things.size());

  // Back transformation
  std::transform(cache.begin(), cache.end(),
                 std::back_inserter(local), Back());

  // Put result in `things`
  swap(things, local);
}

提供通常的“买方自负”说明：这是我随口说出的，可能会杀死小猫...

- Matthieu M.

---

那就是我想要的整洁程度，谢谢！避免从输入向量复制所有内容肯定会更好，但在这种情况下（以及一般情况下），复制 Thing 要比调用 CalculateGoodness 更便宜，当然，算法复杂性也优于比较函数方法。 - undefined

我已经添加了一种避免过多复制的方法，因为“sort”依赖于复制。 - undefined

太好了，我没有想到swap。我的编译器具有移动语义，这可能使得甚至不需要使用它。而且它还支持lambda表达式，所以我可以让代码变得更加漂亮 :) 我真希望我能给这个点赞两次！ - undefined

Answer 2

在排序之前，您可以为每个元素调用CalculateGoodness，然后CalculateGoodness仅更新内部成员变量。然后您可以基于该成员变量进行排序。

如果无法修改类型，则另一种可能性是为对象和其先前计算的值存储某种std::map。您的排序函数将使用该充当缓存的映射。

- Brian R. Bondy

---

+1 为了缓存结果。将 Thing 类设置为缓存 goodness 的值，并且在对象改变时能够知道必须重新计算。（请自行完成设置 Thing 类的练习） - undefined

对不起，我应该加上“不修改Thing”的条件。虽然如果允许修改Thing的话，这显然是最好的答案，谢谢。 - undefined

Answer 3

我已经点赞了 Brian的答案，因为它清晰地回答了你想要的问题。但是另一个解决方案是简单地编写。处理器每天都在变得更加强大。先确保正确性，然后继续前进。稍后可以进行分析，看看CalculateGoodness是否真的是瓶颈。

- Michael Kristofik

---

Xbox 360的处理器并没有变得更强大 ;) 但是我没有提到这一点，所以还是给你一个赞吧 :)我还应该提到，这不是微观优化，而是将算法复杂度从O(log N)降低到O(N)。虽然我没有进行性能分析，但当运行这段代码时会有轻微的卡顿，所以我知道它是（部分）瓶颈之一。 - undefined

Answer 4

我会创建评分和物品的配对，每个物品调用一次CalculateGoodness函数，并按照评分进行排序。如果适用的话，您还可以将其移动到从评分到物品的映射中。

另一个选择是在Thing本身中缓存CalculateGoodness，可以作为简单字段或将CalculateGoodness作为Thing的方法（确保缓存是可变的，以便const Things仍然有效）。

- jk.

Answer 5

也许一个整洁的做法是创建一个vector< pair<float, Thing*> >，其中第二个元素指向具有相应float值的Thing对象。如果按照float值对这个vector进行排序，您可以遍历它并按正确顺序读取Thing对象，可能将它们播放到另一个vector或list中，以便它们最终按顺序存储。

- suszterpatt

---

请谨慎使用指针，它指向我们在迭代之后要更改的第一个向量。 - undefined