Форум программистов, компьютерный форум CyberForum.ru

Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.60
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 16:29     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #1
Всем добрый день. Решил коллективно подумать))) есть матрица из [100000][100000] в ней у меня значения 0 или 1
я представил её как char матрицу допустим если 0 это А если 1 это В занимает она в памяти 10 гигов, как сделать более компактней. Ещё осложняет ситуацию что мне к этим значениям нужно обращаться как [x][x]. Может как то можно сделать в битовом представлении такую матрицу и сжать до 8 раз или более? Кто что подскажет? пожалуйста выскажитесь по этому поводу.

Добавлено через 14 минут
Есть ещё мысль создать таблицу всех вариантов типа
[0] = "AAAAAAAAAAAAAAAAAAAA"
[1] = "AAAAAAAAAAAAAAAAAAAB"
....
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.07.2013, 16:35     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #2
vector<vector<bool>> для начала. А зачем вообще такая матрица?
Ascendancy
Заблокирован
02.07.2013, 16:36     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #3
char = 1 байт и следовательно 100000 * 100000 ты меньше чем 10 гигабайт не представишь
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,309
02.07.2013, 16:37     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #4
А у тебя все 10000000000 значений будут одновременно присутствовать? Если нет, то прежде всего посмотри в сторону разреженных матриц. И "сжать" в битовое представление тоже можно - нужно будет всего-навсего написать простенький собственный класс и переопределить в нем operator[]. В общем, задача легко решается. Только нужно подумать над теми вариантами использования твоей матрицы, которых в сообщении ничего не сказано....
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 16:51  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #5
Цитата Сообщение от Tulosba Посмотреть сообщение
vector<vector<bool>> для начала. А зачем вообще такая матрица?
производяться расчёты разово и чтоб из 10*000*000*000 000 раз потом не пересчитывать они сохраняются в матрицу потом я беру из неё значения. Вектор нет смысла применять если большое количество расчёт если это програмулинка которая не загружает одно даже ядро в компе то для удобства очень подходит

Добавлено через 1 минуту
Цитата Сообщение от CheshireCat Посмотреть сообщение
А у тебя все 10000000000 значений будут одновременно присутствовать? Если нет, то прежде всего посмотри в сторону разреженных матриц. И "сжать" в битовое представление тоже можно - нужно будет всего-навсего написать простенький собственный класс и переопределить в нем operator[]. В общем, задача легко решается. Только нужно подумать над теми вариантами использования твоей матрицы, которых в сообщении ничего не сказано....
да разряжено это классно, у меня даже компилятор от intela сам создаёт такую матрицу, я беру ему делаю матрицу она должна занимать 5 гигов в памяти он выделяет 700 килобайтов)))

Добавлено через 41 секунду
Дак я и хотел чтоб мы подумали как сделать этот класс, может у кого то есть в этом опыт

Добавлено через 40 секунд
давайте сделаем матрицу 128x128 к примеру

Добавлено через 5 минут
разделить строчку по 8 значений и записать в битовом выражении я в этом направлении думаю
10101010
11111111
00000000
00100101
ну что то в этом хуже
как только потом брать значения нужные
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.07.2013, 17:06     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #6
Цитата Сообщение от Ko Посмотреть сообщение
Вектор нет смысла применять если большое количество расчёт если это програмулинка которая не загружает одно даже ядро в компе то для удобства очень подходит
У Вас с пунктуацией проблемка. Ничего не понятно.
А сравнения проводили, что табличный подход работает быстрее, чем повторное вычисление?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
02.07.2013, 17:09     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #7
Ko, вы орудуете супер-компьютером ЦРУ? Тут дофига операций. Просто оптимизируйте алгоритм решения задачи.
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 17:22  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #8
Цитата Сообщение от Tulosba Посмотреть сообщение
У Вас с пунктуацией проблемка. Ничего не понятно.
А сравнения проводили, что табличный подход работает быстрее, чем повторное вычисление?
) да разница 4-5 раз дольше по этому жертвуем оперативной памятью

Добавлено через 4 минуты
Цитата Сообщение от Dani Посмотреть сообщение
Ko, вы орудуете супер-компьютером ЦРУ? Тут дофига операций. Просто оптимизируйте алгоритм решения задачи.
Если бы алгоритм не был оптимизирован задача не могла быть решена пока компьютер находится в этом материально-физическом мире. И пожалуйста в моей ветке не надо употреблять любых названий не связанных с с++)

Добавлено через 5 минут
Всё таки может кто поможет написать класс с битами?
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.07.2013, 17:29     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #9
Цитата Сообщение от Ko Посмотреть сообщение
Всё таки может кто поможет написать класс с битами?
Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит.
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 17:31  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #10
Цитата Сообщение от Tulosba Посмотреть сообщение
Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит.
интересно как это bool мне поможет и сделает один бит, может 1 байт?)
Dr_Quake
Заблокирован
02.07.2013, 17:36     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #11
10 гигов это немного, но если нету - банальная запись на диск и чтение, запись такого типа - чтобы чтение было линейным и дело в шляпе, всё от алгоритма зависит.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.07.2013, 17:37     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #12
Ko, ознакомьтесь http://www.cplusplus.com/reference/vector/vector-bool/
The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is stored in a single bit.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
02.07.2013, 17:43     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #13
Tulosba, а может и не сопимизить. Пусть проверит. Если нет, то с битами написать не так уж тяжело.
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 17:46  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #14
Цитата Сообщение от Tulosba Посмотреть сообщение
заинтригован))) спасибо) а нет примера?)
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.07.2013, 17:50     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #15
Цитата Сообщение от Ko Посмотреть сообщение
а нет примера?)
Какого примера? Берете vector<char> и vector<bool> и заполняете туеву-хучу элементов, замечая сколько съест памяти тот и другой при одинаковом кол-ве элементов. Это если в реализацию не смотреть.
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 17:55  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #16
я выделяю память а не вектора завожу))))
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,309
02.07.2013, 17:55     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #17
Цитата Сообщение от Tulosba Посмотреть сообщение
Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит.
Только не должна, а может (23.3.7/3) - "A space-optimized representation of bits is recommended".
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 18:01  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #18
http://www.cplusplus.com/reference/bitset/bitset/
тут интересный пример

Добавлено через 1 минуту
CheshireCat пожалуйста сделайте пример матрицы

Добавлено через 1 минуту
vector< vector< bool > > verified( 100000, vector<bool>( 100000, false ) );

вот так генерить?

Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
9
int main()
{
 
 
    vector< vector< bool > > verified( 100000, vector<bool>( 100000, false ) );
 
 
    cout << verified[5][5]<<endl;
}
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
02.07.2013, 18:01     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #19
Цитата Сообщение от CheshireCat Посмотреть сообщение
Только не должна, а может
Цитата Сообщение от Tulosba Посмотреть сообщение
Нормальная реализация
ключевое слово
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.07.2013, 18:03     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера)
Еще ссылки по теме:

C++ Даны 2 стека, присоединить хвост второго к голове первого
Чем лучше открывать .h .И есть ли какие то рекомендации и предостережения в работе с ними? C++
Игра на С++. Как лучше представить дорогу? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 18:03  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #20
надо что то там делать чтоб ужалось это дело???)

Добавлено через 24 секунды
нормальная реализация, а что там может быть не реально?

Добавлено через 1 минуту
ну да поджалось в 10 раз где то))))))) но это на первый взгляд, будет пробывать, спасибо всем что помогли)
Yandex
Объявления
02.07.2013, 18:03     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера)
Ответ Создать тему
Опции темы

Текущее время: 19:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru