调用std :: adjacent_difference()时的隐式转换

Question

我想得到一个向量中相邻点之间距离的向量:

struct Point { double x, y, z; } 

vector<double> adjacent_distances( vector<Point> points ) {
    ...
}

stl::adjacent_difference()如果我只提供一个找到2点之间距离的函数,我认为这对我来说会有所帮助:

double point_distance( Point a, Point b ) {
     return magnitude(a-b);  // implementation details are unimportant 
}

因此,我希望这会奏效,

vector<double> adjacent_distances( vector<Point> points ) 
{
    vector<double> distances;

    std::adjacent_difference( points.begin(), points.end(), 
                        std::back_inserter(distances), 
                        ptr_fun( point_distance ) );
    return distances; 
}

只是为了找到它,input并且output向量必须是(实际上)相同类型,因为 adjacent_difference()调用

 output[0] = input[0];            // forces input and output to be of same value_type 
 output[1] = op( input[1], input[0] ); 
 output[2] = op( input[2], input[1] ); 
 ....

遗憾的是,这与std::adjacent_find()工作方式不一致.

所以,我不得不将我的代码转换为

double magnitude( Point pt );
Point  difference( Point a, Point b ); // implements b-a

vector<double> adjacent_distances( vector<Point> points ) 
{
    vector<Point> differences;

    std::adjacent_difference( points.begin(), points.end(), 
                        std::back_inserter(differences), 
                        ptr_fun( point_difference ) ); 


    vector<double> distances;

    std::transform( differences.begin(), differences.end(),
                        std::back_inserter(distances), 
                        ptr_fun( magnitude ) );

    return distances; 
}

注意:differences为了使函数正常运行,必须删除第一个元素,但为了简洁起见,我跳过了实现细节.

问:有没有办法,我可以含蓄地实现一些改造,使我没有创造额外的载体,并实现调用adjacent_difference()与input_iterator和output_iterator不同value_types？

Answer 1

事实上，该adjacent_difference算法在逻辑上是错误的（为什么元素的相同时间应该存在差异？为什么第一个输出元素等于第一个元素，而不是得到比输入元素短一项的输出序列（更合乎逻辑）？

无论如何，我不明白为什么你要通过使用 C++ 的函数式方法来惩罚自己，很明显，代码会更难编写、更难阅读、编译速度更慢，而不是执行速度更快。哦..我们不要谈论如果您输入的内容有任何错误您将面临的那种笑话错误消息。

不好的部分是什么

std::vector<double> distances;
for (int i=1,n=points.size(); i<n; i++)
    distances.push_back(magnitude(points[i] - points[i-1]));

？

它更短，更具可读性，编译速度更快，执行速度可能更快。

编辑

我想检查一下我的主观感受“更短、更易读、编译速度更快并且执行速度可能更快”。结果如下：

~/x$ time for i in {1..10}
>   do
>     g++ -Wall -O2 -o algtest algtest.cpp
>   done

real    0m2.001s
user    0m1.680s
sys 0m0.150s
~/x$ time ./algtest

real    0m1.121s
user    0m1.100s
sys 0m0.010s
~/x$ time for i in {1..10}
>   do
>     g++ -Wall -O2 -o algtest2 algtest2.cpp
>   done

real    0m1.651s
user    0m1.230s
sys 0m0.190s
~/x$ time ./algtest2

real    0m0.941s
user    0m0.930s
sys 0m0.000s
~/x$ ls -latr algtest*.cpp
-rw-r--r-- 1 agriffini agriffini  932 2011-11-25 21:44 algtest2.cpp
-rw-r--r-- 1 agriffini agriffini 1231 2011-11-25 21:45 algtest.cpp
~/x$ 

以下是公认的解决方案（我修复了按值传递点向量的明显愚蠢的问题）。

// ---------------- algtest.cpp -------------
#include <stdio.h>
#include <math.h>
#include <functional>
#include <algorithm>
#include <vector>

using std::vector;
using std::ptr_fun;

struct Point
{
    double x, y;
    Point(double x, double y) : x(x), y(y)
    {
    }

    Point operator-(const Point& other) const
    {
        return Point(x - other.x, y - other.y);
    }
};

double magnitude(const Point& a)
{
    return sqrt(a.x*a.x + a.y*a.y);
}

double point_distance(const Point& a, const Point& b)
{
    return magnitude(b - a);
}

vector<double> adjacent_distances( const vector<Point>& points ) {
    if ( points.empty() ) return vector<double>();

    vector<double> distances(
      1, point_distance( *points.begin(), *points.begin() ) );

    std::transform( points.begin(), points.end() - 1,
                    points.begin() + 1,
                    std::back_inserter(distances),
                    ptr_fun( point_distance ) );
    return distances;
}

int main()
{
    std::vector<Point> points;
    for (int i=0; i<1000; i++)
        points.push_back(Point(100*cos(i*2*3.141592654/1000),
                               100*sin(i*2*3.141592654/1000)));

    for (int i=0; i<100000; i++)
    {
        adjacent_distances(points);
    }

    return 0;
}

这是显式循环解决方案；它需要少两个include，少一个函数定义，函数体也更短。

// ----------------------- algtest2.cpp -----------------------
#include <stdio.h>
#include <math.h>

#include <vector>

struct Point
{
    double x, y;
    Point(double x, double y) : x(x), y(y)
    {
    }

    Point operator-(const Point& other) const
    {
        return Point(x - other.x, y - other.y);
    }
};

double magnitude(const Point& a)
{
    return sqrt(a.x*a.x + a.y*a.y);
}

std::vector<double> adjacent_distances(const std::vector<Point>& points)
{
    std::vector<double> distances;
    if (points.size()) distances.reserve(points.size()-1);
    for (int i=1,n=points.size(); i<n; i++)
        distances.push_back(magnitude(points[i] - points[i-1]));
    return distances;
}

int main()
{
    std::vector<Point> points;
    for (int i=0; i<1000; i++)
        points.push_back(Point(100*cos(i*2*3.141592654/1000),
                               100*sin(i*2*3.141592654/1000)));

    for (int i=0; i<100000; i++)
    {
        adjacent_distances(points);
    }

    return 0;
}

概括：

1. 代码大小更短（algtest2.cpp 小于 algtest.cpp 的 76%）
2. 编译时间更好（algtest2.cpp 需要少于 algtest.cpp 的 83%）
3. 执行时间更好（algtest2.cpp 的运行时间不到 algtest.cpp 的 85%）

因此，显然在我的系统（不是精心挑选的）上，除了执行速度（带有“也许”的那个）之外，我在所有方面都是正确的，从稍微慢到快得多，我必须调用reserve结果数组。即使进行了这种优化，代码当然也会更短。

我还认为这个版本更具可读性这一事实也是客观的，而不是一种观点……但我很高兴通过遇到一个能够理解功能性事物正在做什么而无法理解功能性事物的人来证明我是错误的。明确的人正在做相反的事情。

Answer 2

不过，这可能不是那么简洁，在这种特定情况下，std::transform 使用 2 个输入序列可能会满足目的。例如：

vector<double> adjacent_distances( vector<Point> points ) {
    if ( points.empty() ) return vector<double>();

    vector<double> distances(
      1, point_distance( *points.begin(), *points.begin() ) );

    std::transform( points.begin(), points.end() - 1,
                    points.begin() + 1,
                    std::back_inserter(distances), 
                    ptr_fun( point_distance ) );
    return distances; 
}

希望这可以帮助