• 关于

    局部优化什么意思

    的搜索结果

回答

机器学习方面的面试主要分成三个部分: 1. 算法和理论基础 2. 工程实现能力与编码水平 3. 业务理解和思考深度 1. 理论方面,我推荐最经典的一本书《统计学习方法》,这书可能不是最全的,但是讲得最精髓,薄薄一本,适合面试前突击准备。 我认为一些要点是: 统计学习的核心步骤:模型、策略、算法,你应当对logistic、SVM、决策树、KNN及各种聚类方法有深刻的理解。能够随手写出这些算法的核心递归步的伪代码以及他们优化的函数表达式和对偶问题形式。 非统计学习我不太懂,做过复杂网络,但是这个比较深,面试可能很难考到。 数学知识方面,你应当深刻理解矩阵的各种变换,尤其是特征值相关的知识。 算法方面:你应当深刻理解常用的优化方法:梯度下降、牛顿法、各种随机搜索算法(基因、蚁群等等),深刻理解的意思是你要知道梯度下降是用平面来逼近局部,牛顿法是用曲面逼近局部等等。 2. 工程实现能力与编码水平 机器学习从工程实现一般来讲都是某种数据结构上的搜索问题。 你应当深刻理解在1中列出的各种算法对应应该采用的数据结构和对应的搜索方法。比如KNN对应的KD树、如何给图结构设计数据结构。如何将算法map-red化等等。 一般来说要么你会写C,而且会用MPI,要么你懂Hadoop,工程上基本都是在这两个平台实现。实在不济你也学个python吧。 3. 非常令人失望地告诉你尽管机器学习主要会考察1和2 但是实际工作中,算法的先进性对真正业务结果的影响,大概不到30%。当然算法必须要足够快,离线算法最好能在4小时内完成,实时算法我没搞过,要求大概更高。 机器学习大多数场景是搜索、广告、垃圾过滤、安全、推荐系统等等。对业务有深刻的理解对你做出来的系统的结果影响超过70%。这里你没做过实际的项目,是完全不可能有任何体会的,我做过一个推荐系统,没有什么算法上的高大上的改进,主要是业务逻辑的创新,直接就提高了很明显的一个CTR(具体数目不太方便透露,总之很明显就是了)。如果你做过实际的项目,一定要主动说出来,主动让面试官知道,这才是最大最大的加分项目。 最后举个例子,阿里内部机器学习挑战赛,无数碾压答主10000倍的大神参赛。最后冠军没有用任何高大上的算法而是基于对数据和业务的深刻理解和极其细致的特征调优利用非常基本的一个算法夺冠。所以啥都不如真正的实操撸几个生产项目啊。

马铭芳 2019-12-02 01:21:30 0 浏览量 回答数 0

问题

【精品问答】前端开发必懂之JS技术二百问

茶什i 2019-12-01 22:05:04 146 浏览量 回答数 0

问题

不搞清这8大算法思想,刷再多题效果也不好的 7月23日 【今日算法】

游客ih62co2qqq5ww 2020-07-29 11:10:09 3 浏览量 回答数 1

阿里云试用中心,为您提供0门槛上云实践机会!

0元试用32+款产品,最高免费12个月!拨打95187-1,咨询专业上云建议!

回答

tl; dr:您可能应该使用一维方法。 注意:在不填充书本的情况下比较动态1d或动态2d存储模式时,无法深入研究影响性能的细节,因为代码的性能取决于很多参数。如有可能,进行配置文件。 1.什么更快? 对于密集矩阵,一维方法可能更快,因为它提供了更好的内存局部性以及更少的分配和释放开销。 2.较小的是? 与2D方法相比,Dynamic-1D消耗的内存更少。后者还需要更多分配。 备注 我出于以下几个原因给出了一个很长的答案,但我想首先对您的假设做一些评论。 我可以想象,重新计算1D数组(y + x * n)的索引可能比使用2D数组(x,y)慢 让我们比较这两个函数: int get_2d (int **p, int r, int c) { return p[r][c]; } int get_1d (int *p, int r, int c) { return p[c + C*r]; } Visual Studio 2015 RC为这些功能(启用了优化功能)生成的(非内联)程序集是: ?get_1d@@YAHPAHII@Z PROC push ebp mov ebp, esp mov eax, DWORD PTR _c$[ebp] lea eax, DWORD PTR [eax+edx*4] mov eax, DWORD PTR [ecx+eax*4] pop ebp ret 0 ?get_2d@@YAHPAPAHII@Z PROC push ebp mov ebp, esp mov ecx, DWORD PTR [ecx+edx*4] mov eax, DWORD PTR _c$[ebp] mov eax, DWORD PTR [ecx+eax*4] pop ebp ret 0 区别是mov(2d)与lea(1d)。前者的延迟为3个周期,最大吞吐量为每个周期2个,而后者的延迟为2个周期,最大吞吐量为每个周期3个。(根据指令表-Agner Fog, 由于差异很小,我认为索引重新计算不会产生很大的性能差异。我希望几乎不可能将这种差异本身确定为任何程序的瓶颈。 这将我们带到下一个(也是更有趣的)点: ...但是我可以想象一维可能在CPU缓存中... 是的,但是2d也可能在CPU缓存中。有关为什么1d仍然更好的说明,请参见缺点:内存局部性。 长答案,或者为什么对于简单 /小的矩阵,动态二维数据存储(指针到指针或向量矢量)是“不好的” 。 注意:这是关于动态数组/分配方案[malloc / new / vector等]。静态2D数组是一个连续的内存块,因此不受我将在此处介绍的不利影响。 问题 为了能够理解为什么动态数组的动态数组或向量的矢量最有可能不是选择的数据存储模式,您需要了解此类结构的内存布局。 使用指针语法的示例案例 int main (void) { // allocate memory for 4x4 integers; quick & dirty int ** p = new int*[4]; for (size_t i=0; i<4; ++i) p[i] = new int[4]; // do some stuff here, using p[x][y] // deallocate memory for (size_t i=0; i<4; ++i) delete[] p[i]; delete[] p; } 缺点 内存位置 对于此“矩阵”,您分配一个包含四个指针的块和四个包含四个整数的块。所有分配都不相关,因此可以导致任意存储位置。 下图将使您了解内存的外观。 对于真正的二维情况: 紫色正方形是其p自身占据的存储位置。 绿色方块将存储区域p点组装为(4 x int*)。 4个连续的蓝色方块的4个区域是每个int*绿色区域所指向的区域 对于在1d情况下映射的2d: 绿色方块是唯一需要的指针 int * 蓝色方块组合了所有矩阵元素的存储区域(16 x int)。 实际2D与映射2D内存布局 这意味着(例如,使用左侧布局时)(例如,使用缓存),与连续存储模式(如右侧所示)相比,您可能会发现性能较差。 假设高速缓存行是“一次传输到高速缓存中的数据量”,并想象一个程序一个接一个地访问整个矩阵。 如果您具有正确对齐的32位值的4 4矩阵,则具有64字节高速缓存行(典型值)的处理器能够“一次性”读取数据(4 * 4 * 4 = 64字节)。如果您开始处理而缓存中还没有数据,则将面临缓存未命中,并且将从主内存中获取数据。由于且仅当连续存储(并正确对齐)时,此负载才能装入整个缓存行,因此可以立即读取整个矩阵。处理该数据时可能不会再有任何遗漏。 在动态的“真实二维”系统中,每行/列的位置都不相关,处理器需要分别加载每个内存位置。即使只需要64个字节,在最坏的情况下,为4个不相关的内存位置加载4条高速缓存行实际上会传输256个字节并浪费75%的吞吐量带宽。如果使用2d方案处理数据,您将再次在第一个元素上遇到缓存未命中(如果尚未缓存)。但是现在,从主内存中第一次加载后,只有第一行/列会在缓存中,因为所有其他行都位于内存中的其他位置,并且不与第一行/列相邻。一旦到达新的行/列,就会再次出现高速缓存未命中,并从主内存执行下一次加载。 长话短说:2d模式具有较高的缓存未命中率,而1d方案由于数据的局部性而具有更好的性能潜力。 频繁分配/取消分配 N + 1创建所需的NxM(4×4)矩阵需要多达(4 + 1 = 5)个分配(使用new,malloc,allocator :: allocate或其他方法)。 也必须应用相同数量的适当的各自的重新分配操作。 因此,与单个分配方案相比,创建/复制此类矩阵的成本更高。 随着行数的增加,情况变得更加糟糕。 内存消耗开销 我假设int的大小为32位,指针的大小为32位。(注意:系统依赖性。) 让我们记住:我们要存储一个4×4 int矩阵,表示64个字节。 对于NxM矩阵,使用提出的指针对指针方案存储,我们消耗了 NMsizeof(int) [实际的蓝色数据] + Nsizeof(int) [绿色指针] + sizeof(int**) [紫罗兰色变量p]字节。 444 + 44 + 4 = 84在本示例的情况下,这会使字节变多,使用时甚至会变得更糟std::vector<std::vector >。对于4 x 4 int ,它将需要N * M * sizeof(int)+ N * sizeof(vector )+ sizeof(vector<vector >)字节,即4 44 + 416 + 16 = 144总共字节,共64个字节。 另外-根据所使用的分配器-每个单独的分配可能(并且很可能会)还有16个字节的内存开销。(一些“信息字节”用于存储已分配的字节数,以进行适当的重新分配。) 这意味着最坏的情况是: N*(16+Msizeof(int)) + 16+Nsizeof(int*) + sizeof(int**) = 4*(16+44) + 16+44 + 4 = 164 bytes ! Overhead: 156% 开销的份额将随着矩阵大小的增加而减少,但仍然存在。 内存泄漏的风险 一堆分配需要适当的异常处理,以避免在其中一个分配失败的情况下发生内存泄漏!您需要跟踪分配的内存块,并且在释放内存时一定不要忘记它们。 如果new无法运行内存并且无法分配下一行(特别是在矩阵很大时),std::bad_alloc则抛出a new。 例: 在上面提到的new / delete示例中,如果要避免发生bad_alloc异常时的泄漏,我们将面临更多代码。 // allocate memory for 4x4 integers; quick & dirty size_t const N = 4; // we don't need try for this allocation // if it fails there is no leak int ** p = new int*[N]; size_t allocs(0U); try { // try block doing further allocations for (size_t i=0; i<N; ++i) { p[i] = new int[4]; // allocate ++allocs; // advance counter if no exception occured } } catch (std::bad_alloc & be) { // if an exception occurs we need to free out memory for (size_t i=0; i<allocs; ++i) delete[] p[i]; // free all alloced p[i]s delete[] p; // free p throw; // rethrow bad_alloc } /* do some stuff here, using p[x][y] */ // deallocate memory accoding to the number of allocations for (size_t i=0; i<allocs; ++i) delete[] p[i]; delete[] p; 摘要 在某些情况下,“真实的2d”内存布局适合并且有意义(即,如果每行的列数不是恒定的),但是在最简单和常见的2D数据存储情况下,它们只会使代码的复杂性膨胀,并降低性能和程序的内存效率。 另类 您应该使用连续的内存块,并将行映射到该内存块。 做到这一点的“ C ++方式”可能是编写一个类来管理您的内存,同时考虑诸如 什么是三法则? 资源获取是什么意思初始化(RAII)? C ++概念:容器(在cppreference.com上) 例 为了提供这样一个类的外观的想法,下面是一个具有一些基本功能的简单示例: 二维尺寸可构造 2d可调整大小 operator(size_t, size_t) 用于2行主要元素访问 at(size_t, size_t) 用于检查的第二行主要元素访问 满足容器的概念要求 资源: #include #include #include #include namespace matrices { template class simple { public: // misc types using data_type = std::vector ; using value_type = typename std::vector ::value_type; using size_type = typename std::vector ::size_type; // ref using reference = typename std::vector ::reference; using const_reference = typename std::vector ::const_reference; // iter using iterator = typename std::vector ::iterator; using const_iterator = typename std::vector ::const_iterator; // reverse iter using reverse_iterator = typename std::vector ::reverse_iterator; using const_reverse_iterator = typename std::vector ::const_reverse_iterator; // empty construction simple() = default; // default-insert rows*cols values simple(size_type rows, size_type cols) : m_rows(rows), m_cols(cols), m_data(rows*cols) {} // copy initialized matrix rows*cols simple(size_type rows, size_type cols, const_reference val) : m_rows(rows), m_cols(cols), m_data(rows*cols, val) {} // 1d-iterators iterator begin() { return m_data.begin(); } iterator end() { return m_data.end(); } const_iterator begin() const { return m_data.begin(); } const_iterator end() const { return m_data.end(); } const_iterator cbegin() const { return m_data.cbegin(); } const_iterator cend() const { return m_data.cend(); } reverse_iterator rbegin() { return m_data.rbegin(); } reverse_iterator rend() { return m_data.rend(); } const_reverse_iterator rbegin() const { return m_data.rbegin(); } const_reverse_iterator rend() const { return m_data.rend(); } const_reverse_iterator crbegin() const { return m_data.crbegin(); } const_reverse_iterator crend() const { return m_data.crend(); } // element access (row major indexation) reference operator() (size_type const row, size_type const column) { return m_data[m_cols*row + column]; } const_reference operator() (size_type const row, size_type const column) const { return m_data[m_cols*row + column]; } reference at() (size_type const row, size_type const column) { return m_data.at(m_cols*row + column); } const_reference at() (size_type const row, size_type const column) const { return m_data.at(m_cols*row + column); } // resizing void resize(size_type new_rows, size_type new_cols) { // new matrix new_rows times new_cols simple tmp(new_rows, new_cols); // select smaller row and col size auto mc = std::min(m_cols, new_cols); auto mr = std::min(m_rows, new_rows); for (size_type i(0U); i < mr; ++i) { // iterators to begin of rows auto row = begin() + i*m_cols; auto tmp_row = tmp.begin() + i*new_cols; // move mc elements to tmp std::move(row, row + mc, tmp_row); } // move assignment to this *this = std::move(tmp); } // size and capacity size_type size() const { return m_data.size(); } size_type max_size() const { return m_data.max_size(); } bool empty() const { return m_data.empty(); } // dimensionality size_type rows() const { return m_rows; } size_type cols() const { return m_cols; } // data swapping void swap(simple &rhs) { using std::swap; m_data.swap(rhs.m_data); swap(m_rows, rhs.m_rows); swap(m_cols, rhs.m_cols); } private: // content size_type m_rows{ 0u }; size_type m_cols{ 0u }; data_type m_data{}; }; template void swap(simple & lhs, simple & rhs) { lhs.swap(rhs); } template bool operator== (simple const &a, simple const &b) { if (a.rows() != b.rows() || a.cols() != b.cols()) { return false; } return std::equal(a.begin(), a.end(), b.begin(), b.end()); } template bool operator!= (simple const &a, simple const &b) { return !(a == b); } } 请注意以下几点: T需要满足使用的std::vector成员函数的要求 operator() 不执行任何“范围”检查 无需自己管理数据 不需要析构函数,复制构造函数或赋值运算符 因此,您不必费心为每个应用程序进行适当的内存处理,而只需为编写的类一次即可。 限制条件 在某些情况下,动态“真实”二维结构是有利的。例如,如果 矩阵非常大且稀疏(如果甚至不需要分配任何行,但可以使用nullptr对其进行处理),或者 这些行没有相同数量的列(也就是说,如果您根本没有矩阵,而只有另一个二维结构)。

保持可爱mmm 2020-02-09 13:47:55 0 浏览量 回答数 0
阿里云大学 云服务器ECS com域名 网站域名whois查询 开发者平台 小程序定制 小程序开发 国内短信套餐包 开发者技术与产品 云数据库 图像识别 开发者问答 阿里云建站 阿里云备案 云市场 万网 阿里云帮助文档 免费套餐 开发者工具 企业信息查询 小程序开发制作 视频内容分析 企业网站制作 视频集锦 代理记账服务 企业建站模板