Эффективное взаимно-однозначное сопоставление между значением и индексом в массиве

Question

Мне нужно получить индекс (то есть положение) значения в массиве, и мне интересно, есть ли какой-нибудь более быстрый способ, чем использовать команду find, путем создания какой-либо карты или справочной таблицы, котораясодержит отображение между значениями массива и индексами.

Возьмем, к примеру, этот массив:

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

Теперь, допустим, у меня есть переменная со значением

angle = 55

, и я хочу знать, гдеэто значение позиционируется в массиве (правильный ответ idx = 12).Теперь я, конечно, мог бы просто использовать find:

idx = find(th==angle)

Но моя проблема в том, что в моем коде мне нужно выполнить этот поиск, чтобы получить индекс в th для значения вangle, несколько (миллион) раз, и кажется постоянной тратой ресурсов на то, чтобы постоянно вызывать функцию find, которая, я думаю, проходит по th и выполняет какое-то сравнение.

Вместо этого я надеялся, что есть какой-то способ настроить карту «один к одному» или справочную таблицу, где я могу сразу же извлечь индекс, соответствующий значению, которое у меня есть в angle.(Примечание: я знаю, что значение, которое у меня есть в angle, всегда будет точно соответствовать одному из значений в th.) Так что просто используйте некоторую функцию

idx = angle2i(angle)

, которая выполняет это отображение:

0 -> 1
5 -> 2
10 -> 3
15 -> 4
20 -> 5
25 -> 6

и т. Д.

Но я не понимаю, как мне реализовать такой поиск (ну, у меня есть пара очень не элегантных идей, я надеюсь и догадываюсьчто должен быть какой-то разумный подход для этого).Или я трачу здесь время и должен просто использовать команду find?

Answer 1

Вы ищете 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 (log n), а решение find O (n). Но для очень маленьких массивов издержки использования containers.Map покажут.

Если th гарантированно отсортирован, то решения этого другого вопроса также могут быть полезны.

Конечно, если существует простое математическое соотношение (как в случае примера th, то решение O (1) с помощью @mattesyo из вычисления индекса не может быть побеждено.

Answer 2

Если ваши ключи целые числа, возможно, вы могли бы использовать разреженный массив!Рассмотрим следующую ситуацию:

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 против *)1005 *).

Кстати, если неясно, причина использования массива sparse заключается в том, что он занимает место только для ненулевых значений (поэтому даже если у вас есть такие индексы, как1 и 10E5, вы должны хранить только 2 значения, грубо говоря ).

Answer 3

Benchmark

Начиная с бенчмарка Dev-iL , я добавил метод OP find и метод rahnema1 ismember и посмотрим, как методы масштабируются с размером данных (число ключи). Я также сравниваю два разных варианта использования: нахождение 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

[ Время на MATLAB R2017a, на 3-летнем iMac. Ваш пробег будет варьироваться. ]

Вопреки моим ожиданиям, containers.Map имеет много накладных расходов и не очень подходит для этой цели . Даже с массивом из 5000 ключей метод O (n) find на самом деле быстрее, чем хэш-карта O (log n). containers.Map - это пользовательский класс, и MATLAB JIT все еще не так хорош в оптимизации этого типа кода. Тем не менее, отчетливо виден эффект масштабирования, поскольку метод find является единственным, время выполнения которого значительно увеличивается с увеличением размеров данных.

Интересно, что метод "разреженный" в ~ 50 раз быстрее при векторизации. Обычно это не так с векторизацией. Например, метод find только в 1x-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

Answer 4

Если у вас есть все (несколько миллионов) значений angle, вы можете использовать ismember:

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

Answer 5

Если между индексом и значением есть такой же числовой контекст, как в вашем примере, вы можете просто использовать его как функцию вместо справочной таблицы:

function idx=angle2i(angle)
idx=angle/5+1;
end

Но я не знаю, решит ли это вашу проблему, потому что я не знаю вашей конкретной проблемы.