Как создать массив конкатенированного содержимого из массива помеченных массивов

У меня есть следующие данные:

  1. массив ячеек меток (например, массив ячеек из 4 вариантов типов сообщений, где каждый тип представляет собой строку)
  2. массив ячеек сообщений (например, массив ячеек из 5000 сообщений, где каждое сообщение представляет собой массив ячеек из множества строк слов).
  3. массив ячеек меток для каждого сообщения (например, массив ячеек из 5000 строк, где строка в ячейке i является типом сообщения в ячейке i в массиве в части 2).

Моя цель - получить из этих данных массив ячеек размером с число меток, где в каждой ячейке есть объединенное содержимое из всех сообщений типа в качестве метки (например, получить массив ячеек из 4 ячеек, где в ячейке i есть массив ячеек всех слов из всех сообщений, тип которых i).

Я реализовал 3 метода для выполнения этого. Это код для моих трех реализаций:

%...............................................................
% setting data for tic toc tests
messagesTypesOptions = {'type1';'type2';'type3';'type4'};
messages = cell(5000,1);
for i = 1:5000
    messages{i} = {'word1';'word2';'word3';'word4';'word5';'word6';'word7';'word8';'word9';'word10'};
end
messages_labels = cell(5000,1);
for i = 1:5000
    messages_labels{i} = messagesTypesOptions{randi([1 4])};
end
%...............................................................

% start test
% method 1
type_to_msgs1 = cell(size(messagesTypesOptions,1),1);
tic
for i = 1:size(messagesTypesOptions,1)
    type_to_msgs1{i} = messages(strcmp(messages_labels,messagesTypesOptions{i}));

end
type_to_concatenated1 = cell(4,1);
for i = 1:4
    type_to_msgs1{i} = type_to_msgs1{i}';
end
for i =1:4
    label_msgs = type_to_msgs1{i};
    num_of_label_msgs = size(label_msgs,2);
    for j = 1: num_of_label_msgs
        label_msgs{j} = label_msgs{j}';
    end
    type_to_concatenated1{i} = [label_msgs{:}];
end
toc

% method 2
type_to_concatenated2 = cell(4,1);
tic
labelStr_to_labelIndex = containers.Map(messagesTypesOptions,1:4);
for textIndex = 1:5000
    type_to_concatenated2{labelStr_to_labelIndex(messages_labels{textIndex})} = ...
    [type_to_concatenated2{labelStr_to_labelIndex(messages_labels{textIndex})},...
        messages{textIndex}'];
end
toc

% method 3
type_to_concatenated3 = cell(4,1);
tic
labelStr_to_labelIndex2 = containers.Map(messagesTypesOptions,1:4);
matrix_label_to_isMsgFromLabel = zeros(4,5000);
for textIndex = 1:5000
    matrix_label_to_isMsgFromLabel(labelStr_to_labelIndex2(messages_labels{textIndex})...
    ,textIndex) = 1;
end
for i = 1:4
    label_msgs3 = messages(~~matrix_label_to_isMsgFromLabel(i,:))';
    num_of_label_msgs3 = size(label_msgs3,2);
    for j = 1: num_of_label_msgs3
        label_msgs3{j} = label_msgs3{j}';
    end
    type_to_concatenated3{i} = [label_msgs3{:}];
end
toc

Вот результаты, которые я получаю:

Прошедшее время составляет 0,033120 секунд.

Прошедшее время составляет 0,471959 секунды.

Прошедшее время составляет 0,095011 секунды.

Итак, вывод такой, что способ 1 самый быстрый.

Теперь мой вопрос: есть ли способ решить эту проблему быстрее?

Интуитивно кажется, что мой метод1 не очень эффективен, потому что он имеет цикл for с strcmp, а strcmp читает все сообщения, поэтому он читает количество меток, умноженное на все сообщения, т.е. читает < em>количество ярлыков (типов) то же самое.

Итак, есть ли способ изменить один из моих методов, чтобы получить более быстрое решение? Есть ли другой метод, который быстрее?

EDIT: Здесь я использовал для примеров постоянные сообщения. Но мне нужно решение для случая, когда сообщения отличаются друг от друга и могут иметь разный размер.

EDIT2: Кроме того, типы — это строки, которые не обязательно содержат числа. (например, вместо type1, type2,..., которые я использовал для кода примера, это может быть «ошибка», «предупреждение», «действительно»).


person George    schedule 19.12.2014    source источник
comment
Вы уверены, что вам нужны циклы for, содержащие type_to_msgs1{i} = type_to_msgs1{i}'; и label_msgs{j} = label_msgs{j}';?   -  person knedlsepp    schedule 20.12.2014


Ответы (2)


По сути, у вас есть messages, и вам нужно индексировать их, чтобы получить вывод для каждой ячейки массива выходных ячеек и, наконец, объединить элементы. Для индексации вы можете использовать logical indexing, что в большинстве случаев очень эффективно. Для получения массивов логической индексации вы можете воспользоваться помощью bsxfun. Вот код, чтобы завершить обсуждение -

%// Get the parameters
lbls_len = numel(messages_labels);
msgtypeops_len = numel(messagesTypesOptions);

%// Tag messages_labels and messagesTypesOptions with numbers
alltypes = [messages_labels ; messagesTypesOptions];
[~,~,IDs] = unique(alltypes,'stable');
lbls = IDs(1:lbls_len);
typeops = IDs(lbls_len+1:end);

%// Positions of matches for each label IDs against type IDS
pos = bsxfun(@eq,lbls,typeops');  %//'

%// Logically index into messages and select the ones based on positions
%// obtained in the previous step for the final output and finally 
%// concatenate along the rows to get us the final output cell array
out = arrayfun(@(n) vertcat(messages{pos(:,n)})',1:msgtypeops_len,'Uni',0)';

Бенчмаркинг

Вот несколько сред выполнения, сравнивающих Method - 1, которые оказались лучшими, как указано в вопросе, с предлагаемым решением.

1) С длиной messages_labels как 5000:

------------------ With Method - 1
Elapsed time is 0.072821 seconds.
------------------ With Proposed solution
Elapsed time is 0.053961 seconds.

2) С длиной messages_labels как 500000:

------------------ With Method - 1
Elapsed time is 6.998149 seconds.
------------------ With Proposed solution
Elapsed time is 2.765090 seconds.

Почти 1.5x-2.5x ускорения может быть достаточно для вас!

person Divakar    schedule 20.12.2014
comment
Спасибо за ваш ответ! Мой вопрос был недостаточно ясен. Я отредактировал свой вопрос. Содержимое сообщений не является константой. каждое сообщение может иметь разные слова и разное количество слов. Кроме того, типы — это строки, которые не обязательно содержат числа. - person George; 20.12.2014
comment
Благодарю вас! пожалуйста, смотрите мое второе редактирование, которое я добавил к вопросу. Я написал это раньше в комментарии, но не в вопросе. Спасибо. - person George; 20.12.2014

Как всегда, это сводится к простой проблеме индексации, и для массивов ячеек строк в MATLAB есть хороший способ генерировать эти индексы: ismember. Может быть умный способ затем использовать этот индексный вектор для извлечения всех сообщений за один раз, но логическое индексирование является простым и достаточно быстрым, а магия JIT на самом деле делает тривиальный цикл быстрее, чем arrayfun (с использованием R2013b в Linux). Это дает нам следующее:

tic
out = cell(4,1);
[~, idx] = ismember(messages_labels, messagesTypesOptions);
for ii=1:4
    out{ii} = vertcat(messages{idx == ii})';
end
toc

С добавлением вышеизложенного в конец исходного кода:

>> test
Elapsed time is 0.056497 seconds.
Elapsed time is 0.857934 seconds.
Elapsed time is 0.201966 seconds.
Elapsed time is 0.017667 seconds.

Не плохо :D

Замените все 5000 на 50000, и он по-прежнему линейно масштабируется, как № 1 и № 3:

>> test
Elapsed time is 0.550462 seconds.
Elapsed time is 48.685048 seconds.
Elapsed time is 1.965559 seconds.
Elapsed time is 0.162989 seconds.

Просто чтобы быть уверенным:

>> isequal(type_to_concatenated1, type_to_concatenated2, type_to_concatenated3, out)

ans =

     1

И, если вы можете обрабатывать сгруппированные сообщения, представляющие собой векторы-столбцы, а не строки, удалите транспонирование...

...
    out{ii} = vertcat(messages{idx == ii});
...

...и снова вдвое быстрее:

>> test
Elapsed time is 0.552040 seconds.
Elapsed time is <skipped>
Elapsed time is 1.986059 seconds.
Elapsed time is 0.077958 seconds.
person Notlikethat    schedule 20.12.2014