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

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

Respuesta aceptada

埃博拉酱
埃博拉酱 el 1 de Mayo de 2022
Editada: 埃博拉酱 el 2 de Mayo de 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转换且仅索引一次。

Más respuestas (0)

Categorías

Más información sobre Parallel Computing Fundamentals en Help Center y File Exchange.

Community Treasure Hunt

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

Start Hunting!