2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Операция ИЛИ и поиск max для нескольких матричных столбцов
Сообщение02.09.2024, 15:51 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Операция ИЛИ и поиск max для нескольких матричных столбцов
Сообщение02.09.2024, 18:14 
Заслуженный участник
Аватара пользователя


01/09/13
4656
zgemm в сообщении #1652793 писал(а):
в реальном времени, и ...(!) на встраиваемых системах

Хм, а можно поточнее?
zgemm в сообщении #1652702 писал(а):
Каждый матричный элемент - это или 0, или 1.

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

 Профиль  
                  
 
 Re: Операция ИЛИ и поиск max для нескольких матричных столбцов
Сообщение02.09.2024, 22:00 


23/02/23
124
Geen в сообщении #1652831 писал(а):
Как распределены 1? Как хранится матрица?

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

Geen в сообщении #1652831 писал(а):
zgemm в сообщении #1652793 писал(а):
в реальном времени, и ...(!) на встраиваемых системах

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

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

 Профиль  
                  
 
 Re: Операция ИЛИ и поиск max для нескольких матричных столбцов
Сообщение02.09.2024, 22:12 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Операция ИЛИ и поиск max для нескольких матричных столбцов
Сообщение02.09.2024, 23:02 


23/02/23
124
dgwuqtj в сообщении #1652877 писал(а):
Если у вас единички идут несколькими блоками, то можно сжимать столбцы, сохраняя только количества единиц и нулей в блоках. В случае, когда блоков совсем мало, вы и память сэкономите, и считать количество строк для набора столбцов можно будет быстро.

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

 Профиль  
                  
 
 Re: Операция ИЛИ и поиск max для нескольких матричных столбцов
Сообщение02.09.2024, 23:10 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Операция ИЛИ и поиск max для нескольких матричных столбцов
Сообщение03.09.2024, 00:25 


23/02/23
124
dgwuqtj в сообщении #1652881 писал(а):
Всё верно, но если у вас 10к строк, то несколько десятков сравнений (независимо от количества строк) может быть и быстрее сотен битовых операций. Вам же не надо перебирать строку и проверять, есть в ней единичка, когда можно сразу считать количество нужных строк.

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

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

 Профиль  
                  
 
 Re: Операция ИЛИ и поиск max для нескольких матричных столбцов
Сообщение03.09.2024, 00:32 
Заслуженный участник


07/08/23
1099
А, это я неправильно прочитал.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group