Привет,

Есть матрица 2M x 100K элементов. Кол-во непустых NNZ = 2миллиарда.
Элементы битовые 1/0


Вопрос как представить такую матрицу чтобы полностью влезла в память ? (скажем 4GB )

Если стандартный способ хранения разряженных матриц, то Memory = (4+4)*NNZ = 16Gb

Но ведь мы имеем битовые элементы ...
Может есть более компактый способ хранения ?

Здравствуйте, Аноним, Вы писали:

А>Есть матрица 2M x 100K элементов. Кол-во непустых NNZ = 2миллиарда.
А>Может есть более компактый способ хранения ?

Нет такого способа.
Количество возможных матриц 2000000*100000 заполненных 2000000000 элементов
количество = факториал(2E11)/факториал(2E11 — 2E9)
то есть примерно 2E11 в степени 2E9
оценим сколько информации требуется для указания какая матрица сейчас.
ln(N)/ln(2)/8 байт
ln(2E+11^2E+9)/ln(2)/8=2E+9*ln(2E+11)/ln(2)/8
Считаем на калькуляторе и понимаем что меньше 9 гигов не получиться и думать нечего.

P.S.
Разве что не все варианты заполнения матриц возможны.

Здравствуйте, Аноним, Вы писали:

А>Привет,

А>Есть матрица 2M x 100K элементов. Кол-во непустых NNZ = 2миллиарда.
А>Элементы битовые 1/0

А>Вопрос как представить такую матрицу чтобы полностью влезла в память ? (скажем 4GB )

А>Но ведь мы имеем битовые элементы ...
А>Может есть более компактый способ хранения ?

Гарантированного способа не существует, но можно попробовать хранение с компрессией на лету:
http://bmagic.sourceforge.net/

Будет ли оно влезать в память — это надо проверять на реальных задачах.

Здравствуйте, Аноним, Вы писали:

А>Привет,

А>Есть матрица 2M x 100K элементов. Кол-во непустых NNZ = 2миллиарда.
А>Элементы битовые 1/0


А>Вопрос как представить такую матрицу чтобы полностью влезла в память ? (скажем 4GB )

А>Если стандартный способ хранения разряженных матриц, то Memory = (4+4)*NNZ = 16Gb

А>Но ведь мы имеем битовые элементы ...
А>Может есть более компактый способ хранения ?



рипдется все же работать файловыми мапами, иначе в 32 битных машинах больше 2-х гигов не адресуешь, или со спец ключем — 3 гига
а если 64 битная машина — то ограничений не вижу. но уже вряд ли это будет оперативка, емкие оперативки дорогие