![]() |
Модераторы: Daevaorn |
![]() ![]() ![]() |
|
hello19 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 42 Регистрация: 13.7.2011 Репутация: нет Всего: нет |
Мне нужно работать с матрицей порядка 100 000. Она сильно разреженная, по этому хранить все коэффициенты - не вижу смысла. Стало быть нужно хранить только не нулевые элементы матрицы. Но вот как это сделать лучше всего, чтобы было задействовано как можно меньше памяти?
Элементы матрицы типа double |
|||
|
||||
feodorv |
|
||||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 11 Всего: 45 |
Хрантите 2 массива: один для double значений, другой для их индексов.
count означает число ненулевых элементов матрицы, reserved - число элементов, под которое выделена память (count <= reserved). Плюс подпрограмма бинарного поиска элемента с данным индексом. Плюс подпрограммы вставки/удаления элементов. Гм. Только что дошло: у Вас матрица многомерная? Это немного более сложный случай... -------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
||||
|
|||||
hello19 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 42 Регистрация: 13.7.2011 Репутация: нет Всего: нет |
Нет, матрица обычная 100 000 * 100 000
Что-то не соображу как реализовать поиск элементов... |
|||
|
||||
feodorv |
|
||||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 11 Всего: 45 |
Если размер матрицы фиксирован, то её можно превратить в линейный список: [i][j] => [i*N+j], хотя 100 000 * 100 000 в int уже не влезают... Тогда можно хранить два набора индексов:
Список индексов - отсортированный, поэтому можно воспользоваться бинарным поиском:
Если элемент [x][y] не найден, значит его значение 0.0, иначе m->values[*pindex]. Добавлено @ 14:48 Аналогично пишется spmatrixAdd( m, x, y, value):
Это сообщение отредактировал(а) feodorv - 29.2.2012, 15:15 -------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
||||
|
|||||
feodorv |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 11 Всего: 45 |
Если нет желания возиться с отсортированным списком индексов, тогда можно в лоб сравнивать все пары m->x[i], m->y[i] с x, y. Но это потребует много времени...
Если же ненулевых значений мотрицы не так уж и мало (>10000), то можно воспользоваться (например) красно-чёрным деревом для хранения ненулевых значений матрицы, тогда каждый лист дерева будет содержать набор (x,y,value). Дерево удобнее тем, что при добавлении новых ненулевых элементов не нужно будет перезаказывать память (правда, и потребует больше памяти по сравнению со списками). Это сообщение отредактировал(а) feodorv - 26.2.2012, 15:00 -------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
|||
|
||||
rumit7 |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 71 Регистрация: 16.6.2011 Репутация: 6 Всего: 7 |
Может быть вам будет интересно решение описанное здесь http://evgeny-lazin.blogspot.com/2011/06/blog-post.html |
|||
|
||||
feodorv |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 11 Всего: 45 |
Да, решение интересное (подобно можно организовать нечёткий поиск подстроки длинной не более 32 символов в строке произвольной длины). Но:
-------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
|||
|
||||
rumit7 |
|
||||
Шустрый ![]() Профиль Группа: Участник Сообщений: 71 Регистрация: 16.6.2011 Репутация: 6 Всего: 7 |
Что-то я не очень понимаю в чем проблема? std::bitset и разные другие готовые штучки уже не в моде? |
||||
|
|||||
Фантом |
|
|||
![]() Вы это прекратите! ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 1516 Регистрация: 23.3.2008 Репутация: нет Всего: 49 |
Технически, наверное, проще всего будет организовать массив 10^5 указателей (так что доступ по одной координате будет "прямым"), на которые повесить деревья (те же красно-черные или сразу B-), обеспечивающие поиск по второй координате. Скорость доступа по сравнению с чисто древесным вариантом будет в среднем в два раза больше, а одномерный массив из 10^5 указателей - это пустяк даже при 64-битной адресации. В принципе, если памяти не очень жалко, можно сделать аналогичную вещь, "сбросив" в линейный доступ еще и часть второй координаты (когда каждое дерево будет содержать не полную строку или столбец, а лишь некоторую часть).
|
|||
|
||||
volatile |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 37 Всего: 85 |
Я бы первом делом попробовал на std::map, (или лучше на хеш.мап), что нибудь организовать.
на записи поставить иф. если нулевой коэф, просто не записывать в мап. на чтении, обратное, если нет в мапе, возвращать 0. Это сообщение отредактировал(а) volatile - 26.2.2012, 20:16 |
|||
|
||||
Earnest |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 53 Всего: 183 |
Ну да, map (хэш-мап) с ключом pair <int, int>.
-------------------- ... |
|||
|
||||
azesmcar |
|
|||
![]() uploading... ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 81 Всего: 211 |
Тут вопрос в том, насколько она разреженная? Если там допустим половина элементов НЕ нулевые, то в итоге с map мы только теряем. std::map - это +3 указателя для каждого НЕ нулевого элемента да еще плюс к нему сам индекс, а это немало, в итоге может выйти так, что расход будет больше, чем при обычной матрице, да еще и поиск становиться не константным. В данном случае опять такие теряется константность поиска, но если хранить массив индексов отсортированным, то можно будет применить бинарный поиск. Мне кажется данных мало для однозначного ответа. hello19 Что для тебя важнее? Скорость нахождения элемента или размер расходуемой памяти, какой процент нулевых элементов ожидается в матрице? Что предполагается делать с матрицей? Какие действия? |
|||
|
||||
math64 |
|
||||||
Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2505 Регистрация: 12.4.2007 Репутация: 8 Всего: 72 |
Ещё зависит от того, где расположен ненулевые элементы.
Если ненулевые элементы находятся около главной диалогали - хранить по диагоналям полностью. индекс диагонали - (x-y-minDiagonal), индекс на диагонали - max(x,y);
Если ненулевые элементы расположены блоками возле определеных координат
Добавлено через 12 минут и 50 секунд При делении на блоки для поиска удобно, чтобы они были одного размера и выравнены по своему размеру:
|
||||||
|
|||||||
baldina |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
||||
|
||||
![]() ![]() ![]() |
Правила форума "С++:Общие вопросы" | |
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |