使用STL容器进行中值计算时,正确的方法是什么？

Question

假设我需要从1000000个随机数值序列中检索中值.

如果使用任何但是 STL ::名单,我没有(内置)的排序方式为中值计算序列.

如果使用STL :: list,我不能随机访问值来检索排序序列的中间(中位数).

是自己实现排序和使用例如STL :: vector更好,还是使用STL :: list并使用STL :: list :: iterator for-loop-walk到中值？后者似乎不那么开销,但也感觉更难看..

或者我有更多更好的选择吗？

Answer 1

任何随机访问容器(如std::vector)都可以使用标头中的标准std::sort算法进行排序<algorithm>.

为了找到中位数,使用起来会更快std::nth_element; 这足以将一个选定的元素放在正确的位置,但不会对容器进行完全排序.所以你可以找到这样的中位数:

int median(vector<int> &v)
{
    size_t n = v.size() / 2;
    nth_element(v.begin(), v.begin()+n, v.end());
    return v[n];
}

Answer 2

中位数比Mike Seymour的答案更复杂.中位数取决于样本中是偶数还是奇数项.如果项目数为偶数,则中位数是中间两项的平均值.这意味着整数列表的中位数可以是一小部分.最后,空列表的中位数未定义.这是通过我的基本测试用例的代码:

///Represents the exception for taking the median of an empty list
class median_of_empty_list_exception:public std::exception{
  virtual const char* what() const throw() {
    return "Attempt to take the median of an empty list of numbers.  "
      "The median of an empty list is undefined.";
  }
};

///Return the median of a sequence of numbers defined by the random
///access iterators begin and end.  The sequence must not be empty
///(median is undefined for an empty set).
///
///The numbers must be convertible to double.
template<class RandAccessIter>
double median(RandAccessIter begin, RandAccessIter end) 
  throw(median_of_empty_list_exception){
  if(begin == end){ throw median_of_empty_list_exception(); }
  std::size_t size = end - begin;
  std::size_t middleIdx = size/2;
  RandAccessIter target = begin + middleIdx;
  std::nth_element(begin, target, end);

  if(size % 2 != 0){ //Odd number of elements
    return *target;
  }else{            //Even number of elements
    double a = *target;
    RandAccessIter targetNeighbor= target-1;
    std::nth_element(begin, targetNeighbor, end);
    return (a+*targetNeighbor)/2.0;
  }
}

Answer 3

这是Mike Seymour答案的更完整版本:

// Could use pass by copy to avoid changing vector
double median(std::vector<int> &v)
{
  size_t n = v.size() / 2;
  std::nth_element(v.begin(), v.begin()+n, v.end());
  int vn = v[n];
  if(v.size()%2 == 1)
  {
    return vn;
  }else
  {
    std::nth_element(v.begin(), v.begin()+n-1, v.end());
    return 0.5*(vn+v[n-1]);
  }
}

它处理奇数或偶数长度的输入.

Answer 4

该算法使用STL nth_element(分摊的O(N))算法和max_element算法(O(n))有效地处理偶数和奇数大小的输入.请注意,nth_element具有另一个保证的副作用,即之前n的所有元素都保证小于v[n],但不一定排序.

//post-condition: After returning, the elements in v may be reordered and the resulting order is implementation defined.
double median(vector<double> &v)
{
  if(v.empty()) {
    return 0.0;
  }
  auto n = v.size() / 2;
  nth_element(v.begin(), v.begin()+n, v.end());
  auto med = v[n];
  if(!(v.size() & 1)) { //If the set size is even
    auto max_it = max_element(v.begin(), v.begin()+n);
    med = (*max_it + med) / 2.0;
  }
  return med;    
}

Answer 5

把这个线程的所有见解放在一起，我最终有了这个例程。它适用于任何 stl 容器或任何提供输入迭代器的类，并处理奇数和偶数大小的容器。它还对容器的副本进行处理，而不是修改原始内容。

template <typename T = double, typename C>
inline const T median(const C &the_container)
{
    std::vector<T> tmp_array(std::begin(the_container), 
                             std::end(the_container));
    size_t n = tmp_array.size() / 2;
    std::nth_element(tmp_array.begin(), tmp_array.begin() + n, tmp_array.end());

    if(tmp_array.size() % 2){ return tmp_array[n]; }
    else
    {
        // even sized vector -> average the two middle values
        auto max_it = std::max_element(tmp_array.begin(), tmp_array.begin() + n);
        return (*max_it + tmp_array[n]) / 2.0;
    }
}