Операция ИЛИ и поиск max для нескольких матричных столбцов

[пианист]

Да, тут надо отталкиваться от того, что есть. Может, никаких MIPовских библиотек и нет. Но даже если есть, не факт, что решаться будет за разумное время.

[Geen]

zgemm в сообщении #1652793 писал(а):

в реальном времени, и ...(!) на встраиваемых системах

Хм, а можно поточнее?

zgemm в сообщении #1652702 писал(а):

Каждый матричный элемент - это или 0, или 1.

Как распределены 1? Как хранится матрица?

[zgemm]

Geen в сообщении #1652831 писал(а):

Как распределены 1? Как хранится матрица?

группами в строках, обычно несколько групп в одной строке. Сумарная заполненность - 10-20%. Возможно буду хранить побитово из-за ограничения по памяти, пока тестируюсь на обычном процессоре.

Geen в сообщении #1652831 писал(а):

zgemm в сообщении #1652793 писал(а):

в реальном времени, и ...(!) на встраиваемых системах

Хм, а можно поточнее?

пока тип контроллера еще не выбран, матрица генерится из приходящих данных с АЦП довольно быстро (за доли секунды), возможно в будущем будет даже быстрее. Надо примерно с такой же скоростью получать ответ. Вес и потребление играют важную роль, от того, как алгоритм будет себя вести, буду ограничивать свои хотелки и ограничивать размер матрицы. Пока в максимуме - матрица около 10к*10к, то есть примерно в 10мбайт впихнуть можно, если побитово, то есть и плиска тоже рассматривается.

[dgwuqtj]

Если у вас единички идут несколькими блоками, то можно сжимать столбцы, сохраняя только количества единиц и нулей в блоках. В случае, когда блоков совсем мало, вы и память сэкономите, и считать количество строк для набора столбцов можно будет быстро.

[zgemm]

dgwuqtj в сообщении #1652877 писал(а):

Если у вас единички идут несколькими блоками, то можно сжимать столбцы, сохраняя только количества единиц и нулей в блоках. В случае, когда блоков совсем мало, вы и память сэкономите, и считать количество строк для набора столбцов можно будет быстро.

с памятью я согласен, у меня по сути около 5 регионов с единичками и хранить в таком формате для больших матриц - будет раз в 100 меньше памяти надо. А вот со скоростью - не уверен, вернее не понял Вашей мысли.
Если я перебираю номер столбца, то чтобы понять есть ли у меня единичка мне надо несколько сравнений сделать вместо одного. Причем если я в слово биты засовываю, то такие опериции ИЛИ идут за такт для 32 бит, а тут надо на каждую строку несколько сравнений. Или я все-таки Вашу мысль не уловил?

[dgwuqtj]

Всё верно, но если у вас 10к строк, то несколько десятков сравнений (независимо от количества строк) может быть и быстрее сотен битовых операций. Вам же не надо перебирать строку и проверять, есть в ней единичка, когда можно сразу считать количество нужных строк.

[zgemm]

dgwuqtj в сообщении #1652881 писал(а):

Всё верно, но если у вас 10к строк, то несколько десятков сравнений (независимо от количества строк) может быть и быстрее сотен битовых операций. Вам же не надо перебирать строку и проверять, есть в ней единичка, когда можно сразу считать количество нужных строк.

продолжаю не понимать...

У меня блоки в строках, а сравниваю я столбцы. Внутри столбцов у меня у меня никакой структуры нет к сожалению. Я пробовал их отсортировать - ну где-то немного блочно получается, но даже после сортировки в среднем по 300-400 блоков, то есть не 5 как в строках.

[dgwuqtj]

А, это я неправильно прочитал.