Complexity comparison: remove a key-value pair from a 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 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 :)

回答 (1 件)

Jan 2022 年 1 月 5 日
編集済み: Jan 2022 年 1 月 5 日
You can run a short test:
function [] = MapTest
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);
for k = 1:1e3
remove(M, r(k));
tMap(idx) = toc;
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);
for k = 1:1e3
M(M == r(k)) = [];
tInd(idx) = toc;
yyaxis right
H(2) = plot(len, tInd);
legend(H, {'Map', 'Array'});
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 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