Tag: 算法

数组划分 – 划分存储在数组中的两个数字的最佳方法是什么？: 我有两个数组（被除数，除数）： dividend[] = {1,2,0,9,8,7,5,6,6}; divisor[] = {9,8}; 我需要结果（被除数/除数）： quotient[] = {1,2,3,4,5,6,7}; 我使用数组减法做了这个：将除数从被除数中减去，直到被除数为0或小于除数，每次递数为1，但这需要很长时间。有一个更好的方法吗？

CPU /编程语言使用哪种取幂算法？: 我一直在学习更快的取幂算法（k-ary，滑动门等），并想知道在CPU /编程语言中使用哪些算法？（我对这是否发生在CPU或编译器中都很模糊）只是为了踢，这是最快的？关于广度的编辑：它有意广泛，因为我知道有很多不同的技术可以做到这一点。检查的答案有我想要的。

自动比较两个系列 – 相似性测试: 我有两个系列，series1和series2。我的目标是自动/定量地找出Series2与Series1的不同之处，在bin到bin的基础上（每个bin代表一个特定的特征）。单击此处可以看到此图像的原始大小。 Series1是预期的结果。 Series2是测试/传入系列。我提供了直方图，其中Series2以深棕色表示。您还可以在221和353之间的x轴上注意到有显着的变化。即Series2小于Series1。我正在使用C ++进行编码。我认为，互相关会有所帮助，但会产生一个基于相似性而非不相似性的价值。我看到人们谈论Kolmogorov-Smirnov测试。这是我应该进行的测试吗？更新1：我正在尝试执行模板匹配。我已将模板图像分成8×8块以及我的传入测试图像。我试图将模板图像中的一个块与测试图像中的相同块（基于空间像素位置）进行比较。我计算每个块内的强度和。我获得了模板图像的series1，并且测试图像具有Series2。

仅使用C的分布式系统设计: 我有实现分布式节点系统（如p2p节点）的工作，这些节点中的每一个（比如A，B，C和D）执行某些function，并且需要相互交互以进行各种操作，例如同步操作和其他类似于15个节点的节点与一组5个B节点交互以进入最小负载节点的队列并获得令牌号，然后等待C将它们重定向到空闲节点D，依此类推。关于设计，我有点迷失：我想到的协议是封装操作类型的结构和其他要发送的东西。此外，这是使用确认方案完成的，所以我可以确定对方得到了消息。我如何进行分布式互斥方面，因为我没有中央服务器。我猜每个节点复制数据，但这听起来有点太贵（更不用说愚蠢）。实现p2p系统时遵循的基本设计方法是什么，即如何实现程序，使其在接收时被阻止，但也可以发送进一步的更新等，同时从其他人那里获取有关“状态”的信息。整个系统。我如何确保请求的总排序？此外，我可能需要查看/面对的其他问题是什么。如果您能指出我在实施p2p和分布式系统方面的一些良好的在线资源，我也将不胜感激。谢谢！！

C如何正确测量时间？: 这是“算法”，但是当我想测量执行时间时，它给我零。为什么？ #define ARRAY_SIZE 10000 … clock_t start, end; start = clock(); for( i = 0; i < ARRAY_SIZE; i++) { non_parallel[i] = vec[i] * vec[i]; } end = clock(); printf( "Number of seconds: %f\n", (end-start)/(double)CLOCKS_PER_SEC ); 那么我该怎么做来衡量时间呢？

互补错误函数erfcf（）的可矢量化实现: 互补误差函数erfc是与标准正态分布密切相关的特殊函数。它经常用于统计学和自然科学（例如扩散问题），其中需要考虑这种分布的“尾部”，因此使用误差函数erf是不合适的。补充误差函数在ISO C99标准数学库中可用作函数erfcf ， erfc和erfcl ; 这些随后也被采用到ISO C ++中。因此，源代码可以很容易地在该库的开源实现中找到，例如在glibc中。然而，许多现有的实现本质上是标量的，而现代处理器硬件是面向SIMD的（显式地，如在x86 CPU中，或隐含地，如在GPU中）。出于性能原因，非常需要可矢量化的实现。这意味着需要避免分支，除非作为选择分配的一部分。同样，未指示广泛使用表，因为并行查找通常是低效的。如何构建单精度函数erfcf()的高效矢量化实现？以ulp为单位测量的准确度应与glibc的标量实现大致相同，其最大误差为3.12575 ulps（通过详尽测试确定）。可以假设融合乘法加法（FMA）的可用性，因为此时所有主要的处理器架构（CPU和GPU）都提供它。虽然可以忽略浮点状态标志和errno处理，但应根据ISO C的IEEE 754绑定处理非正规数，无穷大和NaN。

用于找到arrays中元素的最大总和以使得不多于k个元素相邻的算法: 我遇到了这个问题。给定一个仅包含正值的数组，您希望在约束条件下最大化所选元素的总和，使得多于k个选定元素的组不相邻。例如，如果输入是1 2 3 1 7 9（n = 6且k = 2）。输出将是21，它来自挑选元素_ 2 3 _ 7 9.我的简单DP解决方案就是这样 #include #include #include long maxsum(int n,int k,long *sums){ long *maxsums; maxsums = malloc(sizeof(long)*n); int i; long add = 0; for(i=n-1;i>=nk;i–){ add += sums[i]; maxsums[i] = add; } for(i = nk-1;i>=0;i–){ int j; long sum =0,max = 0,cur; […]

元组数量: 我给了N个数a [1..N]和另外2个整数L和H.我如何计算满足i <j <k且L <= a [i] +的元组数（i，j，k） a [j] + a [k] <= H. 1 <= T <= 100 1 <= N <= 1000 1 <= L <= H <= 1000000 1 <= a[i] <= 1000000 PS：需要比N2logn更好的解决方案

我应该使用什么算法进行高性能大整数除法？: 我将大整数编码为size_t数组。我已经有其他操作工作（加，减，乘）; 以及一位数的除法。但是如果可能的话，我想匹配我的乘法算法的时间复杂度（目前是Toom-Cook）。我收集有线性时间算法，用于采用我的红利的乘法逆的各种概念。这意味着我理论上可以在与乘法相同的时间复杂度中实现除法，因为无论如何，线性时间操作通过比较是“无关紧要的”。我的问题是，我该怎么做呢？什么类型的乘法逆在实践中最好？ Modulo 64^digitcount ？当我将乘法逆乘以我的除数时，我可以推卸计算由于整数截断而丢弃的数据部分吗？任何人都可以提供C或C ++伪代码或准确解释应该如何做到这一点？或者是否存在比基于逆的方法更好的专用除法算法？编辑：我挖出了上面提到的“反向”方法。在“Art of Computer Programming，Volume 2：Seminumerical Algorithms”的第312页上，Knuth提供了“算法R”，它是一种高精度的倒数。他说它的时间复杂度小于乘法的时间复杂度。然而，将它转换为C并测试它并且不清楚将消耗多少开销内存等直到我对其进行编码是非常重要的，这将需要一段时间。如果没有人打败我，我会发布它。

用于从RGB值数组中切割平面（就地）的算法: 我有一个平坦的字节RGB值数组，它们是R1 G1 B1 R2 G2 B2 R3 G3 B3 … Rn Gn Bn 。所以我的数据看起来像： char imageData[WIDTH * HEIGHT * 3]; 但我想将WIDTH * HEIGHT数组传递给现有的C库，该C库需要这个数据的单个平面。这将只是R值（或只是G，或只是B）的序列。分配新数组并复制数据（duh）很容易。但是图像非常大。如果它不是一个C库，而是采用某种迭代接口来精细化“切片”遍历，那就太棒了。但是我无法编辑我正在调用的代码……它需要一个指向顺序内存块的普通旧指针。但是我有对这个数组的写访问权限。创建一个将其分类为彩色平面的例程是可行的。我还需要一个可以反转的反向转换，但根据定义，将它分类为平面的相同方法可以应用于取消它。我能够（到位）将这个arrays转换为R1 R2 R3 … Rn G1 G2 G3 … Gn B1 B2 B3 … Bn然后再返回？任何非天真的算法？