我希望能在大约一百万个数据点中查找3个整数（例如[1 2 3]）。
我目前正在使用MATLAB的Map（哈希表），对于每个数据点，我正在执行以下操作：
key = sprintf('%d ', [1 2 3]); % 23 us
% key = '1 2 3 '
result = lookup_map( key ); % 32 us
这很费时间——100万个点 * 55微秒 = 55秒。
我想使用CUDA将其移至GPU上，但我不确定最佳方法是什么。
我可以传输四个数组——key1、key2、key3、result，然后对键执行二进制搜索，但这需要每个键20次迭代(2^20 = 1048576)。然后我还会由于每个线程的并发内存访问而产生延迟。
在CUDA中是否有一种针对并行多键查找进行优化的数据结构(O(1)，最好)？
边界问题：这三个整数的范围是多少？查找了什么数据？
整数键当前可以在0到约75,000之间，但在未来可能更大(200,000+)。
对于这个问题，我们可以假设结果是介于0和数据集大小之间的整数。
为什么不将三个数字打包成一个64位数字(每个数字21位，给你一个范围0-2,097,152)，然后用它来索引稀疏数组呢？
>> A = uint64(ones(10));
>> sparse_A = sparse(A)
??? Undefined function or method 'sparse' for input arguments of type 'uint64'.
>> A = int64(ones(10));
>> sparse_A = sparse(A)
??? Undefined function or method 'sparse' for input arguments of type 'int64'.
看起来我的Matlab不支持64位数字的稀疏数组。
如果对其他人有帮助的话，我写了一个快速函数，可以从三个小于2^21的无符号整数创建一个64位键：
function [key] = to_key(face)
key = uint64(bitsll(face(1), 42) + bitsll(face(2), 21) + rand(face(3),1));
end
问：为什么不使用逻辑索引？
让我们来测试一下！
% Generate a million random integers between 0 and 1000
>> M = int32(floor(rand(10000000,4)*1000));
% Find a point to look for
>> search = M(500000,1:3)
search =
850 910 581
>> tic; idx = M(:,1)==search(1) & M(:,2)==search(2)&M(:,3)==search(3); toc;
Elapsed time is 0.089801 seconds.
>> M(idx,:)
ans =
850 910 581 726
很遗憾，这需要89801微秒，比我的现有解决方案（55微秒）慢1632倍！如果运行一百万次，需要2.5小时！
我们可以尝试在每次搜索后过滤M：
>> tic; idx1=M(:,1)==search(1); N=M(idx1,:); idx2=N(:,2)==search(2); N2=N(idx2,:); idx3 = N2(:,3)==search(3); toc;
Elapsed time is 0.038272 seconds.
这个速度稍快，但仍比使用Map慢696倍。
我考虑了一些更多的内容，决定从单个键值查找重新生成一些数据的速度进行分析 - 相对于3个键值查找，这可能会更快，鉴于此方法存在的潜在问题。