#linear-algebra #processing-efficiency
#линейная алгебра #эффективность обработки
Вопрос:
У меня возникли проблемы с подгонкой моего вопроса под ограничение в 150 символов заголовка; Я прошу прощения, если это неясно.
Допустим, у меня есть два вектора одинаковой длины (A и B), полностью состоящих из единиц и нулей. Я хотел бы знать, существует ли какая-либо пара A_i и B_i, такая, что A_i = 0 при B_i = 1.
Моя проблема — эффективность. Тривиально просто написать цикл for, выполнить поэлементное сравнение, установить флаг и прервать, если условие выполнено. Проблема возникает, однако, в том, что я работаю с матрицами длиной до 20000 строк и количеством столбцов аналогичной величины. Я хотел бы иметь способ быстро выполнить эту проверку и удалить любую из строк, которые являются избыточными для моих целей… в этом масштабе поэлементное сравнение занимает непрактичное количество времени.
Есть ли какой-нибудь элегантный прием линейной алгебры для эффективного решения этой проблемы?
Редактировать 1: Столбцы расположены не совсем случайным образом. Я не могу сказать, что они строго отсортированы, но я могу сказать, что при переходе слева направо столбцы слева с большей вероятностью будут покрывать столбцы слева, чем наоборот (под покрытием я подразумеваю, что A покрывает B iff для всех i, если A_i = 1, то B_i = 1 тоже). Я могу попытаться применить к ним какой-то дополнительный вид сортировки, если это упростит решение проблемы (но я бы предпочел избежать этого, если процесс сортировки будет таким же непрактичным).
В отдельных столбцах я не знаю ни о каком шаблоне распределения единиц по индексу.
Комментарии:
1. Известно ли что-нибудь еще о наборах? Они отсортированы?
2. Вроде того… Я немного добавлю об этом в основном сообщении.
3. в любом языке программирования в какой-то момент все операции с матрицами основаны на цикле.
4. Все еще неясно, что вы пытаетесь сделать. Каким должно быть это «покрывающее» отношение? Вы говорите, что A_i = 0, когда B_i = 1. Это для одного i или для каждого i в строке?
5. Если векторы имеют размер int / long / etc, вы можете удобно использовать xor и проверить, что результат равен> 0. Оба действия довольно эффективны. Помимо этого вам следует поискать инструменты, которые могли бы поддерживать такие действия, такие как MATLAB, MATHEMATICA и т.д.