标签: algorithm

在使用PHP一段时间后,我注意到并非所有PHP内置函数都如预期的那样快.考虑下面两个可能的函数实现,它使用缓存的素数数组来查找数字是否为素数.

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $prime_array => $number ) {
    $result_array[$number] = in_array( $number, $large_prime_array );
}

//speed is much less dependent on size of $prime_array, and runs much faster.
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
                       11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $prime_array => $number ) …

的std::sort算法(及其同类std::partial_sort和std::nth_element从C++标准库)是在大多数实现的更基本的排序算法复杂和混合合并,如选择排序,插入排序,快速排序,归并排序,或堆排序.

这里和姐妹网站上有很多问题,例如https://codereview.stackexchange.com/,与错误,复杂性以及这些经典排序算法的实现的其他方面有关.大多数提供的实现包括原始循环,使用索引操作和具体类型,并且在正确性和效率方面分析通常是非常重要的.

问:如何使用现代C++实现上述经典排序算法？

• 没有原始循环,但结合了标准库的算法构建块<algorithm>
• 迭代器接口和模板的使用,而不是索引操作和具体类型
• C++ 14风格,包括完整的标准库,以及语法降噪器,如auto模板别名,透明比较器和多态lambda.

备注:

• 有关排序算法实现的进一步参考,请参阅Wikipedia,Rosetta Code或http://www.sorting-algorithms.com/
• 根据Sean Parent的惯例(幻灯片39),原始循环for比使用运算符的两个函数的组合更长.所以f(g(x));或f(x); g(x);或f(x) + g(x);不生循环,也不是在环路selection_sort和insertion_sort下方.
• 我遵循Scott Meyers的术语来表示当前的C++ 1y已经作为C++ 14,并且将C++ 98和C++ 03都表示为C++ 98,所以不要因此而激怒我.
• 正如@Mehrdad的评论中所建议的那样,我在答案的最后提供了四个实现作为实例:C++ 14,C++ 11,C++ 98和Boost and C++ 98.
• 答案本身仅以C++ 14的形式呈现.在相关的地方,我表示各种语言版本不同的语法和库差异.

我正在尝试编写一个C++程序,它从用户那里获取以下输入来构造矩形(2到5之间):高度,宽度,x-pos,y-pos.所有这些矩形将平行于x轴和y轴存在,即它们的所有边都将具有0或无穷大的斜率.

我试图实现这个问题中提到的但我没有太多运气.

我目前的实现如下:

// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2

// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2]; 
pnt_y = arrRect1[3]; …

我正在寻找获得π值的最快方法,作为个人挑战.更具体地说,我使用的方法不涉及使用#define常量M_PI,或者对数字进行硬编码.

下面的程序测试了我所知道的各种方式.从理论上讲,内联汇编版本是最快的选择,但显然不便于携带.我已将其作为基线与其他版本进行比较.在我的测试中,使用内置4 * atan(1)函数,在GCC 4.2上版本最快,因为它会自动将其折叠atan(1)为常量.根据-fno-builtin指定,atan2(0, -1)版本最快.

这是主要的测试程序(pitimes.c):

#include <math.h>
#include <stdio.h>
#include <time.h>

#define ITERS 10000000
#define TESTWITH(x) {                                                       \
    diff = 0.0;                                                             \
    time1 = clock();                                                        \
    for (i = 0; i < ITERS; ++i)                                             \
        diff += (x) - M_PI;                                                 \
    time2 = clock();                                                        \
    printf("%s\t=> %e, time => %f\n", #x, diff, diffclock(time2, time1));   \
}

static inline double
diffclock(clock_t time1, clock_t time0)
{ …

我理解DFS和BFS之间的区别,但是我很想知道何时使用一个比另一个更实用？

任何人都可以举例说明DFS如何胜过BFS,反之亦然？

我问的更多关于这对我的代码意味着什么.我在数学上理解这些概念,我只是很难在概念上围绕它们的意思.例如,如果要对数据结构执行O(1)操作,我理解它必须执行的操作量不会增加,因为有更多项.而O(n)操作意味着您将对每个元素执行一组操作.有人可以在这里填空吗？

• 就像O(n ^ 2)操作究竟会做什么一样？
• 如果一个操作是O(n log(n)),这意味着什么呢？
• 有人必须抽烟才能写出O(x!)？

Big-O表示法O(n)和Little-O表示法有o(n)什么区别？

我想在一个明确的清单中回答两个问题:

1. Redis使用的基础数据结构是什么？
2. 每种类型的主要优点/缺点/用例有哪些？

所以,我读过Redis列表实际上是用链表实现的.但对于其他类型,我无法挖掘任何信息.此外,如果有人偶然发现了这个问题并且没有对修改或访问不同数据结构的优缺点进行高级概述,那么他们就会有一个完整的列表,列出何时最好地使用特定类型来引用.

具体来说,我想概述所有类型:字符串,列表,集,zset和哈希.

哦,到目前为止,我已经看过这些文章,其中包括:

• http://redis.io/topics/data-types
• http://redis.io/topics/data-types-intro
• http://redis.io/topics/faq

我最近参加了一次采访,我被问到"编写一个程序,从10亿个数字中找出100个最大的数字."

我只能给出一个强力解决方案,即以O(nlogn)时间复杂度对数组进行排序并获取最后100个数字.

Arrays.sort(array);

面试官正在寻找更好的时间复杂性,我尝试了其他一些解决方案但未能回答他.有更好的时间复杂度解决方案吗？

新的iTunes 11可以很好地查看专辑的歌曲列表,选择专辑封面功能的字体和背景颜色.有谁想出算法是如何工作的？