matlab - matlab - 数组中值和索引之间的高效一对一映射

我需要获取索引( 例如 一个值,它包含了一些映射或者查询表,通过构造包含值和索引之间映射的表,我想知道它们是否比使用 find 命令更快。

例如这个数组:


th = [0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90];



现在,假设我有一个变量,它的值为

我想知道这个值在数组( 正确答案是 idx = 12 ) 中的位置。

我想知道这个值在 array ( 正确答案是 idx = 12 ) 中的位置。 现在,我当然可以使用 find:


idx = find(th==angle)



相反,我希望有一些方法来设置one-to-one映射或者查找表,我可以立即获取对应于 angle 中值的索引。 ( 注意:我知道我在 angle 中的值总是对应于 th 中的一个值) 。


idx = angle2i(angle)



执行这里映射的步骤:


0 -> 1


5 -> 2


10 -> 3


15 -> 4


20 -> 5


25 -> 6



但我不知道应该如何实现这样的( 我有几个非常优雅的想法,我希望和猜测这个方法必须有一些智能的方法。) 。

或者我还是在这里浪费我的时间,我是不是应该使用 find 命令? 还是我浪费我的时间在这里,我应该使用 find 命令?

时间:

你正在寻找 containers.Map

你可以执行以下操作:


th = [0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90];


angle2i = containers.Map(th,1:numel(th));


index = angle2i(55)



这是一个通用解决方案,只要求 th 包含唯一的元素。 不需要排序,并且不需要为整数( 在比较浮点值时一定要小心) 。 对于大型数组,这个解决方案应该比 find 快得多,因为这个解决方案是O 并且 find 解决方案是 O(n) 。 但是对于非常小的数组,使用 containers.Map的将显示开销。

如果 th 是保证排序,那么这个问题的解决方案也可能是有用的。

当然,如果存在简单的数学关系( 如示例 th 所示),则无法用计算索引的@mattesyo 解决方案来击败这个索引。

如果键是整数,也许你可以使用稀疏的array ! 请考虑以下情况:


function t = q55725607


%% Define the mapping(s):


keys = (1:60).*5; % Keys must be integers!


values = 1:numel(keys); 


% Construct an array such that `map(key) == value`


map = sparse(ones(numel(keys),1), keys, values);



% Compare to containers.Map:


hashmap = containers.Map(keys, values);



%% Try this out:


queryKeys = randi(60,5000000,1).*5;


queryKeysCell = num2cell(queryKeys);



t = [timeit(@f1,1), timeit(@f2,1)];



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


function queryVals = f1()


 queryVals = reshape(full(map(queryKeys)), size(queryKeys));


end



function queryVals = f2


 queryVals = hashmap.values(queryKeysCell);


end



end



我不知道我所做的比较是否公平,但是如果是,稀疏方法是我系统( 0.1549 vs 1.5685 )的一个数量。

顺便说一句,如果不清楚,使用稀疏数组的原因是因为它只占用非零值的空间(粗略地说, 所以即使你有像1和10E5这样的索引,你只会存储2值)。

如果在索引和值之间存在数值上下文,则可以使用该函数作为函数而不是查找表:


function idx=angle2i(angle)


idx=angle/5+1;


end



但我不知道这是否解决了你的问题, 因为我不知道你的具体问题。

如果你手头有 angle的所有( 几百万) 值,你可以使用 ismember:


[~, idx] = ismember(angle, th);



基准

本文从Dev-iL 基准开始,添加了op方法和rahnema1的方法find,并查看了方法的规模如何与数据大小( 键的数目) 进行比较。 我还比较了两种不同的用例: 一次查找 5000个键,并在每次查找 5000键时查找。

以下是结果:


 One key at the time Many keys at once


 ------------------------------------- -------------------------------------


size sparse c.Map find ismember sparse c.Map find ismember 


---- ------- ------- ------- ------- ------- ------- ------- -------


 50 5.1681 54.3091 3.7766 28.8590 0.0956 1.2973 0.5578 0.0537


 500 5.0864 54.7872 6.9310 32.5554 0.0977 1.6847 3.6726 0.0499


5000 5.2052 56.4472 35.1449 60.6480 0.1140 2.0886 38.7444 0.0789



我的期望相反, containers.Map 有很多开销,而且并不适合这种用途。 即使 array的键为 5000,O(n) find 方法实际上比O ( 日志n ) 哈希映射快。 containers.Map 是一个定制类,而JIT仍然不具备优化这种代码类型的能力。 但是,可以清楚地看到扩展的效果,因为 find 方法是唯一增加数据大小的运行时间。

有趣的是,在矢量化时,"稀疏"方法是 ~50x 。 通常情况下,使用矢量化的情况不是这样的。 例如 find 方法在向量( 对于较大的数据大小,矢量化需要太多内存,并且最终会证明非常慢) 时的速度大约为 1 x-2x 。

向量和循环代码之间最大的区别是 ismember 函数。 这一个对输入数据进行排序,所以我们看到这一次之间的差异,并进行了 5000次。 这种方法只适用于多次调用时。 但在这种情况下, ismember 也是最快捷的方法。

当获取一个密钥时,如果不考虑数据大小,则方法是最快的,除非数据大小很小,否则 find 方法将赢得。 然而,稀疏方法是唯一需要键为正整数( 。对于 0,负值或者非整数值,它将不起作用)的方法。 其他方法都使用任意类型( 包括字符串)的值。

基准代码:


function t = so(N)


% Define the mapping(s):


keys = (1:N).*5; % Keys must be positive integers!


values = 1:N; 



% Sparse lookup table


sparseMap = sparse(ones(numel(keys),1), keys, values);



% containers.Map lookup table


hashMap = containers.Map(keys, values);



% Try this out:


queryKeys = keys(randi(numel(keys),5000,1));


queryKeysCell = num2cell(queryKeys); % trick to read many values from the hashMap at once



t = [timeit(@f1,1), timeit(@f2,1), timeit(@f3,1), timeit(@f4,1),.. .


 timeit(@f1q,1), timeit(@f2q,1), timeit(@f3q,1), timeit(@f4q,1)] * 1000;



% Functions that do the lookup one at the time:



 function queryVals = f1


 queryVals = zeros(size(queryKeys));


 for ii=1:numel(queryKeys)


 queryVals(ii) = full(sparseMap(queryKeys(ii)));


 end


 end



 function queryVals = f2


 queryVals = zeros(size(queryKeys));


 for ii=1:numel(queryKeys)


 queryVals(ii) = hashMap(queryKeys(ii));


 end


 end



 function queryVals = f3


 queryVals = zeros(size(queryKeys));


 for ii=1:numel(queryKeys)


 queryVals(ii) = find(keys==queryKeys(ii));


 end


 end



 function queryVals = f4


 queryVals = zeros(size(queryKeys));


 for ii=1:numel(queryKeys)


 [~, queryVals(ii)] = ismember(queryKeys(ii), keys);


 end


 end



% Functions that do the lookup all at once:



 function queryVals = f1q


 queryVals = reshape(full(sparseMap(queryKeys)), size(queryKeys));


 end



 function queryVals = f2q


 queryVals = hashMap.values(queryKeysCell);


 end



 function queryVals = f3q


 [queryVals,~] = find(keys.'==queryKeys);


 end



 function queryVals = f4q


 [~,queryVals] = ismember(queryKeys, keys);


 end



end



...