我正在尝试为Project Euler问题#145编写一个强力解决方案,我无法让我的解决方案在不到1分30秒的时间内运行.
(我知道有各种捷径,甚至是纸笔解决方案;出于这个问题的目的,我不考虑那些).
在迄今为止我提出的最佳版本中,分析显示大部分时间都花在了foldDigits.这个函数根本不需要是懒惰的,在我看来应该优化到一个简单的循环.正如你所看到的,我试图使程序的各个部分严格.
所以我的问题是:在不改变整体算法的情况下,是否有某种方法可以将该程序的执行时间降低到亚分钟？
(或者,如果没有,有没有办法看到代码foldDigits尽可能优化？)
-- ghc -O3 -threaded Euler-145.hs && Euler-145.exe +RTS -N4
{-# LANGUAGE BangPatterns #-}
import Control.Parallel.Strategies
foldDigits :: (a -> Int -> a) -> a -> Int -> a
foldDigits f !acc !n
| n < 10 = i
| otherwise = foldDigits f i d
where (d, m) = n `quotRem` 10
!i = f acc m
reverseNumber :: Int -> Int
reverseNumber !n
= foldDigits accumulate …为(例如)集合创建支持数组时,您并不真正关心所创建数组的确切大小,它只需要至少与您计算的一样大.
但是由于内存分配和VM的数组头,在某些情况下可以创建一个更大的阵列而不消耗更多的内存 - 对于Oracle 32位VM(至少这是互联网上的几个来源声称),内存粒度为8(意味着任何内存分配向上舍入到下一个8字节边界),并且数组头开销为12个字节.
这意味着在分配Object [2]时,它应该消耗20个字节(12 + 2*4),但由于粒度,它实际上需要24个字节.可以为相同的内存成本创建一个Object [3],这意味着集合必须稍后调整其后备阵列的大小.相同的原理可以应用于primitve数组,例如用于I/O缓冲区的byte [],字符串生成器中的char []等.
虽然这种优化不会产生明显的效果,但在最极端的情况下,调用静态方法来"优化"数组大小并不会太麻烦.
问题是,JDK中没有这种"圆形阵列大小直至内存粒度".并且自己编写这样的方法需要确定VM的一些关键参数:内存粒度,数组头开销以及最终每种类型的大小(主要是引用的问题,因为它们的大小可能随架构和VM选项而变化).
那么有没有一种方法来确定这些参数,或通过其他方式实现所需的"向上舍入"？
我有一些代码执行许多日志tan和cos双打操作.我需要这个尽可能快.目前我使用的代码如
#include <stdio.h>
#include <stdlib.h>
#include "mtwist.h"
#include <math.h>
int main(void) {
int i;
double x;
mt_seed();
double u1;
double u2;
double w1;
double w2;
x = 0;
for(i = 0; i < 100000000; ++i) {
u1 = mt_drand();
u2 = mt_drand();
w1 = M_PI*(u1-1/2.0);
w2 = -log(u2);
x += tan(w1)*(M_PI_2-w1)+log(w2*cos(w1)/(M_PI_2-w1));
}
printf("%f\n",x);
return EXIT_SUCCESS;
}
我正在使用gcc.
有两种明显的方法可以加快速度.首先是选择更快的RNG.第二是加快先验功能.
要做到这一点,我想知道
fcos为cos和fptan的tan.)在英特尔优化手册说
如果不需要使用80位的扩展精度来评估超越函数,则应用程序应考虑使用基于软件的替代方法,例如使用插值技术的基于查找表的算法.通过选择所需的数值精度和查找表的大小,并利用SSE和SSE2指令的并行性,可以通过这些技术提高超越性能. …
在C中,如果我有一个看起来像的函数调用
// main.c
...
do_work_on_object(object, arg1, arg2);
...
// object.c
void do_work_on_object(struct object_t *object, int arg1, int arg2)
{
if(object == NULL)
{
return;
}
// do lots of work
}
那么编译器会在main.o中生成很多东西来保存状态,传递参数(在这种情况下希望在寄存器中),以及恢复状态.
但是,在链接时可以观察到arg1和arg2没有用在快速返回路径中,因此清理和状态恢复可以短路.链接器是否会自动执行此类操作,或者是否需要启用链接时优化(LTO)才能使此类工作正常工作？
(是的,我可以检查反汇编代码,但我对编译器和链接器的行为以及多种体系结构感兴趣,所以希望从别人的经验中学习.)
假设分析显示此函数调用值得优化,我们是否应该期望以下代码明显更快(例如,无需使用LTO)？
// main.c
...
if(object != NULL)
{
do_work_on_object(object, arg1, arg2);
}
...
// object.c
void do_work_on_object(struct object_t *object, int arg1, int arg2)
{
assert(object != NULL) // generates no code in release build
// do lots of work
}
问题
使用delete数组元素将其从数组中删除是我意识到从数组中删除元素以使.forEach()调用跳过索引的唯一方法.
问题
deleteon索引exampleArray[i]会导致后续exampleArray.push()增加数组对象的内存消耗吗？删除对象如何影响垃圾收集器？
是否有更有效的方法来消除exampleArray元素？
前者的例子
var exampleArray = [];
var n = 500;
//Does this line imply a memory allocation?
exampleArray.length = n;
exampleArray.fill("Lorem Ipsum", 0);
exampleArray.forEach(function(cur, ind, arr) {
if(ind % 4 === 0) {
delete arr[ind]; //Actually deletes the object itself, index no longer exists
//Length does not change, however. Does available memory?
}
}, this);
n /= 4;
//Where, in memory, are …我有以下功能:
char f1( int a, unsigned b ) { return abs(a) <= b; }
对于执行速度,我想重写如下:
char f2( int a, unsigned b ) { return (unsigned)(a+b) <= 2*b; } // redundant cast
或者使用此签名,即使对于非负面也可能具有微妙含义b:
char f3( int a, int b ) { return (unsigned)(a+b) <= 2*b; }
这两种替代方案都可以在一个平台上进行简单的测试,但我需要便携式.假设非负b且没有溢出风险,这是典型硬件和C编译器的有效优化吗？它对C++也有效吗？
注意:作为C++在gcc 4.8 x86_64上使用-O3,f1()使用6个机器指令并f2()使用4.指令f3()与那些相同f2().同样感兴趣的是:如果b以文字形式给出,则两个函数都编译为3条指令,这些指令直接映射到指定的操作f2().
该DIV指令在现代处理器上很昂贵.有没有更快的方法来减少x86汇编中的64位整数mod 3？
_mm256_lddqu_si256基于我在网上找到的一个例子,我一直在使用.后来我发现了_mm256_loadu_si256.英特尔内在函数指南仅指出lddqu版本在跨越缓存行边界时可能表现更好.可能有什么好处loadu？一般来说,这些功能有何不同？
我发现这len(arr)几乎快了两倍arr.shape[0],我想知道为什么.
我使用的是Python 3.5.2,Numpy 1.14.2,IPython 6.3.1
以下代码演示了这一点:
arr = np.random.randint(1, 11, size=(3, 4, 5))
%timeit len(arr)
# 62.6 ns ± 0.239 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
%timeit arr.shape[0]
# 102 ns ± 0.163 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
我还做了一些比较测试:
class Foo():
def __init__(self):
self.shape = (3, 4, 5)
foo = Foo()
%timeit arr.shape
# 75.6 ns ± 0.107 ns per loop …我试图了解是否删除局部中间变量可以导致更好的优化代码。考虑以下MWE，要特别注意这两个函数f和g：
struct A {
double d;
};
struct B {
double s;
};
struct C {
A a;
B b;
};
A geta();
B getb();
C f() {
const A a = geta();
const B b = getb();
C c;
c.a = a;
c.b = b;
return c;
}
C g() {
C c;
c.a = geta();
c.b = getb();
return c;
}
既f与g呼叫geta()和getb()来填充类的实例C，然后将其返回，但f使用两个本地中间变量来存储的返回值 …