Complexity comparison: remove a key-value pair from a containers.map vs removing an item from an array.

2 ビュー (過去 30 日間)
Xiaoqi Liu
Xiaoqi Liu 2022 年 1 月 4 日
編集済み: Walter Roberson 2022 年 1 月 6 日
Hi there,
I have an array (dataArr) of integers and I want to remove a specific integer (a) from it. A simple way to achieve this is by setting dataArr(dataArr == a) = []. Since the logical indexing here costs O(n) to compute, I think this way of removing a takes O(n) runtime.
A second possible approach is to store integers as the values of a containers.map and then use the "remove" function to remove a. I'm wondering if this approach will be more efficient? What will the complexity of this approach be?
I'll be grateful for any suggestions :)
Thanks,
Shirley

回答 (1 件)

Jan
Jan 2022 年 1 月 5 日
編集済み: Jan 2022 年 1 月 5 日
You can run a short test:
function [] = MapTest
figure;
len = 1e3:5e4:1e6;
tMap = zeros(1, numel(len));
for idx = 1:numel(len)
n = len(idx);
M = containers.Map(1:n, 1:n);
r = randperm(n, 1e3);
tic
for k = 1:1e3
remove(M, r(k));
end
tMap(idx) = toc;
end
yyaxis left
H(1) = plot(len, tMap);
tInd = zeros(1, numel(len));
for idx = 1:numel(len)
n = len(idx);
M = 1:n;
r = randperm(n, 1e3);
tic
for k = 1:1e3
M(M == r(k)) = [];
end
tInd(idx) = toc;
end
yyaxis right
H(2) = plot(len, tInd);
legend(H, {'Map', 'Array'});
tMap(end)
tInd(end)
end
Result (R2018b, Win10):
The relations between the runtime and the data size look equivalent and like O(n), but the absolute run-time for arrays is much higher than for the map. I assume the arrays need much more time, because deleting one element let Matlab create a new array and copy the other elements. For Maps it seems, like the elements are stored independently, such that removing one element does not need to touch the rest, or the inplace-processing helps to save time. I do not know, how the container.Map is implemented internally.
  3 件のコメント
Jan
Jan 2022 年 1 月 6 日
Finding the matching key needs more time for larger maps. The timings look like an O(n) realtion also.

サインインしてコメントする。

Community Treasure Hunt

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

Start Hunting!

Translated by