数值索引和逻辑索引哪个更快?

33 views (last 30 days)
埃博拉酱
埃博拉酱 on 1 May 2022
Edited: 埃博拉酱 on 2 May 2022
Index=find(Array==Element);
Array(Index)=0
上述代码往往会被提示可以省略find,直接使用逻辑索引而不是数值索引。
省略一个函数调用当然会更快,这不难理解。
但如果Index还将要继续用于后续其它数组的索引呢?
亦或者,满足Array==Element条件的元素个数远远少于Array的元素总数呢?例如,Array中含有10亿个数值,满足条件的却只有1个,此时数值索引一步到位完成操作,逻辑索引却要遍历10亿个逻辑值,此时难道不是数值索引更快吗?

Accepted Answer

埃博拉酱
埃博拉酱 on 1 May 2022
Edited: 埃博拉酱 on 2 May 2022
测试方法
测试函数:
function IndexingTest(FullNumber,SelectNumber)
Set=false(FullNumber,1,'like',logical(FullNumber));
Index=cast(randsample(FullNumber,SelectNumber),'like',FullNumber);
disp('-赋值测试-');
fprintf('数值赋值:');
Start=tic;
Set(Index)=true;
toc(Start);
fprintf('逻辑赋值:');
Start=tic;
Set(Set)=true;
toc(Start);
fprintf('find赋值:');
Start=tic;
Set(find(Set))=true;
toc(Start);
disp('-取值测试-');
fprintf('数值取值:');
Start=tic;
Out=Set(Index);
toc(Start);
Set(Index)=true;
fprintf('逻辑取值:');
Start=tic;
Out=Set(Set);
toc(Start);
fprintf('find取值:');
Start=tic;
Out=Set(find(Set));
toc(Start);
disp('--');
此函数的功能是,在FullNumber个元素中选取SelectNumber个元素操作,显示耗时。此外,当FullNumber为gpuArray时,测试将在GPU上运行。
测试环境:
Intel® Xeon® Platinum 8260 CPU,NVIDIA Quadro RTX 8000
>> ver
------------------------------------------------------------------------------------------------
MATLAB 版本: 9.11.0.1809720 (R2021b) Update 1
操作系统: Microsoft Windows Server 2022 Datacenter Version 10.0 (Build 25083)
Java 版本: Java 1.8.0_202-b08 with Oracle Corporation Java HotSpot(TM) 64-Bit Server VM mixed mode
------------------------------------------------------------------------------------------------
MATLAB 版本 9.11 (R2021b)
Parallel Computing Toolbox 版本 7.5 (R2021b)
Statistics and Machine Learning Toolbox 版本 12.2 (R2021b)
测试结果
每种测试都会重复多次,但只展示代表性结果。测试数据规模为200亿,更大量的数据也不会改变定性结论。
当FullNumber>>SelectNumber时,数值索引最快,逻辑索引最慢,find索引居中
>> IndexingTest(2e10,1)
-赋值测试-
数值赋值:历时 0.000017 秒。
逻辑赋值:历时 37.951261 秒。
find赋值:历时 7.265596 秒。
-取值测试-
数值取值:历时 0.000011 秒。
逻辑取值:历时 27.353507 秒。
find取值:历时 7.255759 秒。
--
>> IndexingTest(2e10,1)
-赋值测试-
数值赋值:历时 0.000019 秒。
逻辑赋值:历时 34.422859 秒。
find赋值:历时 10.772744 秒。
-取值测试-
数值取值:历时 0.000005 秒。
逻辑取值:历时 24.154859 秒。
find取值:历时 10.265218 秒。
--
数值索引的时间几乎可以忽略不计,find取值速度是逻辑取值的2~4倍;而find赋值更可达到逻辑赋值的3~6倍速度!
下面我们逐渐增加SelectNumber,寻找临界条件。
第一临界点:8~9
随着SelectNumber的增加,find取值的速度暴跌,直到SelectNumber=8~9时,find取值便和逻辑取值速度相当了。
>> IndexingTest(2e10,8)
-取值测试-
数值取值:历时 0.000036 秒。
逻辑取值:历时 27.067652 秒。
find取值:历时 25.729763 秒。
--
>> IndexingTest(2e10,9)
-取值测试-
数值取值:历时 0.000014 秒。
逻辑取值:历时 24.468397 秒。
find取值:历时 25.672174 秒。
--
SelectNumber继续增加时,find将成为最慢的取值方法,但变慢的速度将会减缓。这个临界点似乎与FullNumber无关,看来是find内部实现代码中写死的阈值,SelectNumber低于阈值时采用了特殊的优化算法才能比逻辑取值更快,而这个算法不适用于SelectNumber>9的情况。
第二临界点:40~50倍
随着SelectNumber不断增加,find赋值也在逐渐变慢。当FullNumber在SelectNumber的40~50倍附近时,find赋值将减慢到和逻辑赋值相当。
>> IndexingTest(2e10,4e8)
-赋值测试-
数值赋值:历时 20.814275 秒。
逻辑赋值:历时 43.295752 秒。
find赋值:历时 43.025631 秒。
--
>> IndexingTest(2e10,5e8)
-赋值测试-
数值赋值:历时 25.190571 秒。
逻辑赋值:历时 44.776700 秒。
find赋值:历时 45.696227 秒。
--
如果SelectNumber继续增加,find也将成为最慢的赋值方法。
至此,无论取值还是赋值,find都是最慢的,而数值索引始终最快。因此,如果你需要用同样的索引处理多个数组,使用find先得到数值索引仍然优于全部使用逻辑索引。
第三临界点:10~20倍
随着SelectNumber继续增加,数值索引也在迅速变慢。直到FullNumber达到SelectNumber的10~20倍附近时,数值索引和逻辑索引速度相当。
>> IndexingTest(2e10,1e9)
-赋值测试-
数值赋值:历时 44.590711 秒。
逻辑赋值:历时 49.841494 秒。
-取值测试-
数值取值:历时 37.157672 秒。
逻辑取值:历时 40.413882 秒。
--
>> IndexingTest(2e10,2e9)
-赋值测试-
数值赋值:历时 83.901136 秒。
逻辑赋值:历时 61.154660 秒。
-取值测试-
数值取值:历时 73.136612 秒。
逻辑取值:历时 52.245381 秒。
--
如果SelectNumber更大,使得FullNumber还不到SelectNumber的10倍,逻辑索引最快。
GPU测试
因为GPU内存容量有限,数据规模降低到20亿。
>> IndexingTest(gpuArray(2e9),1)
-赋值测试-
数值赋值:历时 0.000311 秒。
逻辑赋值:历时 0.857038 秒。
find赋值:历时 0.834732 秒。
-取值测试-
数值取值:历时 0.000190 秒。
逻辑取值:历时 0.818314 秒。
find取值:历时 0.810822 秒。
--
可以看到当FullNumber>>SelectNumber,数值索引仍然最快,find索引略快于逻辑索引。
随着SelectNumber的增长,我们惊讶地发现,只有数值赋值会逐渐变慢,而其它操作的用时十分稳定,似乎完全与SelectNumber无关。这可能是因为GPU的高度并行化计算。
唯一临界点:2~3倍
当FullNumber只有SelectNumber的2~3倍时,数值赋值才减慢到和逻辑赋值相当。对于更大的SelectNumber,数值赋值最慢。
>> IndexingTest(gpuArray(2e9),7e8)
-赋值测试-
数值赋值:历时 0.768000 秒。
逻辑赋值:历时 0.835305 秒。
find赋值:历时 0.811727 秒。
-取值测试-
数值取值:历时 0.001875 秒。
逻辑取值:历时 1.035965 秒。
find取值:历时 0.911580 秒。
--
>> IndexingTest(gpuArray(2e9),1e9)
-赋值测试-
数值赋值:历时 1.064082 秒。
逻辑赋值:历时 0.973291 秒。
find赋值:历时 0.856092 秒。
-取值测试-
数值取值:历时 0.002114 秒。
逻辑取值:历时 1.303293 秒。
find取值:历时 0.891867 秒。
--
有趣的是,对于取值操作,数值取值始终最快,而且遥遥领先。此外,find索引也十分稳定地略快于逻辑索引。
编码建议
综上我们看到,因为逻辑索引需要遍历,因此速度其实未必比得上数值索引。当选取的元素相比于元素总数较少时,数值索引更具有性能优势。具体判定标准如下,区分CPU和GPU:
CPU
  1. 选取至少10%的元素,始终使用逻辑索引。
  2. 选取2.5%~5%的元素,尽量使用数值索引;但如果必须用find从逻辑索引得到数值索引,且只使用一次,仍用逻辑索引:为这一次操作进行一次find是不划算的。相反,如果得到的索引可以复用,请使用find转换成数值索引。
  3. 选取不到2%的元素,如果是取值,仅当复用索引时转换为数值索引;如果是赋值,果断使用find,即使只用一次也比逻辑索引更快。
  4. 选取元素不到2%且少于8个,果断find,即使只用一次也比逻辑索引更快。
GPU
  1. 永远不要直接使用逻辑索引。即使只用一次,也请务必用find转换成数值索引。
  2. 选取50%以上的元素进行赋值时,不要复用find产生的数值索引,始终使用find。但取值操作应复用数值索引。
  3. 选取1/3或更少的元素时,始终使用数值索引,即使需要用find转换且仅索引一次。

More Answers (0)

Categories

Find more on Matrix Indexing in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!