| by msbeta | No comments

数据结构排序算法-堆排序

1.什么是堆排序

堆排序是利用堆这种数据结构设计的一种排序算法。它的最好、最坏、平均的时间复杂度都是nlogn,是一种非稳定排序算法。

2.什么是堆

堆(heap)是计算机科学中一类特殊的数据结构的统称,它满足以下的性质:

1) 堆中某个节点的值总是不大于或不小于其父节点的值;

2)堆总是一棵完全二叉树。

将根节点最大的堆叫做大顶堆,根节点最小的堆叫做小顶堆。

用公式来描述堆的定义就是:

大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆:arr[[……]

继续阅读

Read More
| by msbeta | No comments

自动驾驶硬件系统(十)- Inertial Measurement Unit (IMU)

惯性测量单元(Inertial measurement unit,简称 IMU),是测量物体三轴姿态角及加速度的装置。一般IMU包括三轴陀螺仪及三轴加速度计,部分IMU还包括三轴磁力计。IMU在小至手机、VR,大至航空、航天领域都得到了广泛的应用。手机中的微信运动记录步数使用了IMU;VR中随着头部姿态变换切换视野场景用到了IMU;在GPS之前,航运轮船跨海航行确认航向依赖IMU;Apollo登月中依赖IMU实现位置追踪和朝向确认等等。

在自动驾驶中,IMU同样不可或缺,它在其它传感器不可用的情况下,提供车辆位置和姿态信息。

IMU通常包含陀螺仪(Gyroscope)、加速度计[……]

继续阅读

Read More
| by msbeta | No comments

链表的二分搜索实现-跳跃表

跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。

—-by 发明者

在redis中有序集合就使用到了跳跃表。

跳跃表允许快速查询一个有序连续元素的数据链表,它的效率可以做到和二分相同,都是O(logn)的平均时间复杂度,其空间复杂度为O(n)。

跳跃表具有如下性质:

  • 由很多层结构组成
  • 每一层都是一个有序的链表
  • 最底层(Level 1)的链表包含所有元素
  • 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现
  • 每个节点包含两个指针,一个指向同一链[……]

    继续阅读

Read More
| by msbeta | No comments

STL标准容器中内容的打印技巧

在调试C++代码的过程中经常需要打印容器内容,怎么打印才能更加方便。

1、简单直接的方法

采用索引遍历

或者使用迭代器

2、高级的打印方法

用for_each和Lamda表达式

采用ostream_iterator

[……]

继续阅读

Read More
| by msbeta | No comments

自动驾驶定位算法(九)-直方图滤波(Histogram Filter)定位

1、直方图滤波(Histogram Filter)的算法思想

直方图滤波的算法思想在于:它把整个状态空间dom(x(t))切分为互不相交的部分$b_1、b_2、…,b_{n-1}$,使得:

然后定义一个新的状态空间$y_t \in \{0,…,n−1\}$,当且仅当$x(t)∈b_i$时,$y_t=i$,由于$y_t$是一个离散的状态空间,我们就可以采用离散贝叶斯算法计算$bel(y_t)$。$bel(y_t)$是对$bel(x_t)$的近似,它给出x(t)在每一个$b_i$的概率,$b_i$划分的越精细,计算的结果就越精确,当然精确的代价是计算成本的上升。

2、1D[……]

继续阅读

Read More
| by msbeta | No comments

从零开始学习自动驾驶系统(八)-基础知识之车辆姿态表达

车辆位置和姿态是自动驾驶中的一个基础问题,只有解决了车辆的位置和姿态,才能将自动驾驶的各个模块关联起来。车辆的位置和姿态一般由自动驾驶的定位模块输出。

以Apollo为例,对车辆的Pose的定义如下:

1.车辆的位置

车辆的位置(VRP, Vehicle Reference Point)一般选取一个车辆的基准点在世界坐标系的位置作为车辆位置。

Apollo中的世界坐标系采用WGS-84坐标系(the World Geodetic System dating from 1984),如下图所示。

Apollo的Pose的局部坐标系是ENU(East-Nor[……]

继续阅读

Read More
| by msbeta | No comments

高效的多维空间点索引算法 — Geohash 和 Google S2

引子

每天我们晚上加班回家,可能都会用到滴滴或者共享单车。打开 app 会看到如下的界面:

app 界面上会显示出自己附近一个范围内可用的出租车或者共享单车。假设地图上会显示以自己为圆心,5公里为半径,这个范围内的车。如何实现呢?最直观的想法就是去数据库里面查表,计算并查询车距离用户小于等于5公里的,筛选出来,把数据返回给客户端。

这种做法比较笨,一般也不会这么做。为什么呢?因为这种做法需要对整个表里面的每一项都计算一次相对距离。太耗时了。既然数据量太大,我们就需要分而治之。那么就会想到把地图分块。这样即使每一块里面的每条数据都计算一次相对距离,也比之前全表都计算一次要快[……]

继续阅读

Read More
| by msbeta | No comments

数据结构算法-多叉树遍历算法及其在路径查找中的应用(c++)

1、多叉树遍历算法的代码实现

树是数据结构中的一个基础的算法,课本上一般以二叉树为例,讲解树的各种遍历算法,那么针对于n叉树(n>2),如何实现对应的算法呢。它们的道理其实是完全相通的。

首先定义树的节点的结构。树的节点结构大体可以分为两个部分:数据域和链接域。数据域中包含所有的数据内容;链接域包含指向子节点的指针。

递归深度优先遍历算法实现:

多叉树的非递归遍历算法利用栈数据结构先进后出的特性,在遍历过程中,将先入栈的节点弹出,依次遍历子结构,从而实现深度优先遍历算法。非递归深度优先遍历算法实现:

非递归广度优先算法利用了队列先进先出的特性,在[……]

继续阅读

Read More
| by msbeta | No comments

C++11中如何让自定义的类支持Range-Based for循环

C++11支持range-based for循环,这是一个很方便的特性,可以节省不少代码。

1.基本语法

for ( range_declaration : range_expression) loop_statement

可以遍历的对象包括:

  • 原始数组
  • 定义了begin()和end()方法,且该方法返回迭代器的类对象。

2.让自定义的类支持Range-Based for循环

自定义的类要在ranged-based for loops中进行循环,需要满足以下条件:

1、定义自定义类的迭代器;

2、该类型拥有b[……]

继续阅读

Read More
| by msbeta | No comments

C++进阶之道-提升程序的运行效率之emplace_back

在C++中我们经常需要使用STL的std::vector容器,大量的std::vector插值操作,对应用程序的编码提出了极高的要求。如何利用C++的语言特性,写出更加高效的代码呢?本文主要分析如何高效的将数值插入到std::vector中。

C++98中的push_back函数

函数原型:

看如下一段代码:

代码编译和执行:

代码执行结果:

可以看到在push_back过程中,先调用构造函数构造了一个临时对象,然后调用拷贝构造函数将临时对象放入std::vector中,再将临时对象析构掉。可以看到函数执行过程中申请到的临时对象资源完全就浪费[……]

继续阅读

Read More