我deque::insert()从C++标准2003(第23.2.1.3章)中了解到如下复杂性:
在最坏的情况下,将单个元素插入到双端队列中需要时间在从插入点到双端队列开始的距离的最小值以及从插入点到双端队列结束的距离的线性.
我总是将stl deque的实现理解为内存块的集合.因此,插入仅影响与插入位置相同的存储块中的元素.我的问题是,标准是什么意思是"从插入点到双端队列开始的距离的最小值和从插入点到双端队列结束的距离的线性"？
我的理解是因为C++标准没有强制实施deque的某种实现.对于最坏的情况,复杂性通常是一般的.但是,在编译器的实际实现中,它与内存块中的元素数量成线性关系,这可能因不同的元素大小而异.
另一个猜测可能是,因为insert()将使所有迭代器无效,deque需要更新所有迭代器.因此它是线性的.
我知道这很荒谬,但我需要它来进行存储优化.有没有什么好的方法在C++中实现它？
它必须足够灵活,以便我可以将它用作普通数据类型,例如Vector< int20 >运算符重载等.
在什么情况下使用哈希表可以提高性能，什么时候不能？什么情况下使用哈希表不适用？
我编写了一个CUDA代码来解决NP-Complete问题,但性能并不像我怀疑的那样.
我知道"一些"优化技术(使用共享memroy,纹理,zerocopy ......)
CUDA程序员应该了解哪些最重要的优化技术？
我想在以下代码中优化随机访问读取和随机访问写入:
__global__ void kernel(float* input, float* output, float* table, size_t size)
{
int x_id = blockIdx.x * blockDim.x + threadIdx.x;
if (x_id > size)
return;
float in_f = input[x_id];
int in_i = (int)(floor(in_f));
int table_index = (int)((in_f - float(in_i)) * 1024000.0f );
float* t = table + table_index;
output[table_index] = t[0] * in_f;
}
如您所见,表和输出的索引在运行时确定,并且完全随机.
我知道我可以使用纹理内存或__ldg()读取这些数据.所以,我的问题是:
__ldg()？output[table_index]如上所述,随机访问写入怎么样？实际上,我在这里添加代码以给出随机访问读写的示例.我不需要代码优化,我只需要高级描述处理这种情况的最佳方法.