Форум программистов, компьютерный форум 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"
....
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 18:20  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #21
так
vector< vector< bool > > verified( 1000000, vector<bool>( 1000000, false ) );
софтина конечно падает

Добавлено через 1 минуту
Имя модуля с ошибкой: MSVCR110.dll

Добавлено через 5 минут
Цитата Сообщение от alsav22 Посмотреть сообщение

Не по теме:


Спасибо не булькает...+1 жать не умеем?

чё там у Вас не булькает ?)

Добавлено через 5 минут
так то в класс к объекту запихнуть
vector< bool > verified( 100000000, false );
и всё будет отлично, только как они это сделали в векторе теперь интересно
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soican
49 / 23 / 1
Регистрация: 16.11.2011
Сообщений: 329
Записей в блоге: 5
02.07.2013, 19:44     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #22
Здесь явно напрашивается bool.
Bool - тип данных, который может принимать два возможных значения, иногда называемых правдой - true(в вашем случае 1) и ложью -false( соответственно 0).
И пишешь свой массив, где каждая ячейка - это mass[i][j] = true или mass[i][j] = false
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.07.2013, 20:12     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #23
опишите конкретно задачу. готов поспорить, что хранение такого объема данных здесь излишне.
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
02.07.2013, 20:45  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #24
Ребята всё задача решена, конкретно была задача сделать компактней массив 01010, всем спасибо.

Добавлено через 34 секунды
Цитата Сообщение от salam Посмотреть сообщение
опишите конкретно задачу. готов поспорить, что хранение такого объема данных здесь излишне.
задача была представить массив [100000][100000] как можно компактней в памяти.

Добавлено через 1 минуту
Цитата Сообщение от soican Посмотреть сообщение
Здесь явно напрашивается bool.
Bool - тип данных, который может принимать два возможных значения, иногда называемых правдой - true(в вашем случае 1) и ложью -false( соответственно 0).
И пишешь свой массив, где каждая ячейка - это mass[i][j] = true или mass[i][j] = false
проще прикрепить к каждому объекту по массиву в нужную длину и будет всё работать и занимать мизер по сравнению с предыдущим вариантом.
Dr_Quake
Заблокирован
02.07.2013, 23:20     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #25
Вообще - если некритично время заполнения проще взять свой класс с базовым не сжатием, а malloc'ом, у него memmap будет массив в битовом виде как минималка, по ней проверять заполненность, если 0 - возвращаем 0 на гет метод, если не 0 - значение, но это достаточный бред во ВСЕХ видах если элемент массива - 8 бит, оверхед превысит это дело.

Аналогично полный бред брать boolean - он будет минимум байт, а может и весь регистр битности приложения в зависимости от опций компилятора.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.07.2013, 00:04     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #26
статический массив bool-ей будет занимать по байту на ячейку
vector bool-ей сжимает все восьмёрки ячеек до 1 байта
vector <vector <bool> > из 100000x100000
посчитаем :
10^5 * 10^5 = 10^10
(10^10 / 8 * 1024^3) Гигабайт = 1,16415321826934814453125 GB
И никакие не 10 ГБ
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
03.07.2013, 00:10  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #27
Цитата Сообщение от Dr_Quake Посмотреть сообщение
Вообще - если некритично время заполнения проще взять свой класс с базовым не сжатием, а malloc'ом, у него memmap будет массив в битовом виде как минималка, по ней проверять заполненность, если 0 - возвращаем 0 на гет метод, если не 0 - значение, но это достаточный бред во ВСЕХ видах если элемент массива - 8 бит, оверхед превысит это дело.

Аналогично полный бред брать boolean - он будет минимум байт, а может и весь регистр битности приложения в зависимости от опций компилятора.
Это в памяти vector< bool > verified( 100000000, false ); должно занимать по вашему 100 мегабайт? но ребята кто делал stl сделали что если правильно как до этого уважаемый форумчанин сказал использовать vector+bool то всё будет ужато в 8 раз до битовых значений, очень кстати супер получилось, вместо 12 гигов в памяти теперь занимает где то 1.25 гига

Добавлено через 3 минуты
Ребята я уже всё проверил и получилось "то что доктор прописал" ))))
Dr_Quake
Заблокирован
03.07.2013, 01:02     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #28
Цитата Сообщение от Ternsip Посмотреть сообщение
статический массив bool-ей будет занимать по байту на ячейку
vector bool-ей сжимает все восьмёрки ячеек до 1 байта
vector <vector <bool> > из 100000x100000
посчитаем :
10^5 * 10^5 = 10^10
(10^10 / 8 * 1024^3) Гигабайт = 1,16415321826934814453125 GB
И никакие не 10 ГБ
Ну это и есть битмаска, 1:8 эффективность всего, мало... При том что это ВДОБАВОК к массиву будет использоваться, если массив заполнен хотя бы на 80% - уже предел, очень от ситуации зависит. Плюс переходники if bit==0/1 - они время занимают на активных вычислениях.

Как говорил один мой знакомый(не покойный ещё) писатель time critical вещей, лучшая функция - её отсутствие, и это факт, будет как минимум call-ret задержка с таким переходником в основном цикле позже, а уж если с pushf/popf - так вообще приличная...
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
03.07.2013, 03:54     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #29
Про bitset вспоминали?
Миниатюры
Есть матрица из [100000][100000] как лучше ее представить в голове компьютера)  
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
03.07.2013, 13:02  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #30
Цитата Сообщение от Dr_Quake Посмотреть сообщение
Ну это и есть битмаска, 1:8 эффективность всего, мало... При том что это ВДОБАВОК к массиву будет использоваться, если массив заполнен хотя бы на 80% - уже предел, очень от ситуации зависит. Плюс переходники if bit==0/1 - они время занимают на активных вычислениях.

Как говорил один мой знакомый(не покойный ещё) писатель time critical вещей, лучшая функция - её отсутствие, и это факт, будет как минимум call-ret задержка с таким переходником в основном цикле позже, а уж если с pushf/popf - так вообще приличная...
да я тоже в первую очередь задумался о скорости получения результатов из таких массивов, сегодня сделаю думаю реализацию и замерю скорость вычислений и сюда выскажусь
-=ЮрА=-
Заблокирован
Автор FAQ
03.07.2013, 14:13     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #31
Цитата Сообщение от Ko Посмотреть сообщение
Может как то можно сделать в битовом представлении такую матрицу и сжать до 8 раз или более? Кто что подскажет? пожалуйста выскажитесь по этому поводу.
- правильно мыслишь, только bool это не битовое представление.
На счёт представить - юзай bitset http://www.cplusplus.com/reference/bitset/bitset/ и битовые операции
Цитата Сообщение от Ko Посмотреть сообщение
Всё таки может кто поможет написать класс с битами?
- начни а там точно кто то поможет.
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
03.07.2013, 23:29  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #32
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- правильно мыслишь, только bool это не битовое представление.
На счёт представить - юзай bitset http://www.cplusplus.com/reference/bitset/bitset/ и битовые операции - начни а там точно кто то поможет.
Мне vector<bool> в полне нравиться, думаю нет смысла на это тратить время
-=ЮрА=-
03.07.2013, 23:44
  #33

Не по теме:

Цитата Сообщение от Ko Посмотреть сообщение
Мне vector<bool> в полне нравиться, думаю нет смысла на это тратить время
- если хочешь в 8-мь раз больше места под объект то юзай и vector<bool>

Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
03.07.2013, 23:49  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #34
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение

Не по теме:

- если хочешь в 8-мь раз больше места под объект то юзай и vector<bool>

да на оборот вектор заживает место на 8 раз как надо я выделял в начале по 1 байту руками для булла, а взял вектор и он сживает мои до этого 12 гигов в 1.25 гига памяти, меня устраивает. я сейчас провожу тест насколько это будет быстрей или медленней, замеряю скорость, если упадёт хотя бы на 20% придётся отказаться от вектора
XRuZzz
Антикодер
577 / 478 / 23
Регистрация: 15.09.2012
Сообщений: 2,429
04.07.2013, 00:01     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #35
лучше бы рассказали зачем вам это нужно, и не морочили себе и людям голову )
Просто из вашего вопроса уже очевидно, что вы совершенно не в ту степь зашли.

Добавлено через 6 минут
Я конечно особо не работал с матрицами, но я сильно сомневаюсь, что вам потребуется матрица больше чем 10 на 10 элементов.

Добавлено через 5 минут
инициализация такими цифрами уже запутывает код
C++
1
vector< vector< bool > > verified( 1000000, vector<bool>( 1000000, false ) );
1000000 лучше заменять на enum, define и т п
массивы(матрицы) больше 255 должны настараживать разработчика.
-=ЮрА=-
Заблокирован
Автор FAQ
04.07.2013, 00:06     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #36
Цитата Сообщение от Ko Посмотреть сообщение
да на оборот вектор заживает место на 8 раз как надо я выделял в начале по 1 байту руками для булла, а взял вектор и он сживает мои до этого 12 гигов в 1.25 гига памяти, меня устраивает. я сейчас провожу тест насколько это будет быстрей или медленней, замеряю скорость, если упадёт хотя бы на 20% придётся отказаться от вектора
- прочти ещё раз себя сам
100000*100000 = 1010*8 ~ 1011 ~100 Гб какие 12?

замеряю скорость, если упадёт хотя бы на 20% придётся отказаться от вектора - откажись лучше от неправильного механизма хранения данных, при котором думаю ещё и их потеря идёт.
Цитата Сообщение от Ko Посмотреть сообщение
Может как то можно сделать в битовом представлении такую матрицу и сжать до 8 раз или более? Кто что подскажет? пожалуйста выскажитесь по этому поводу.
- это была мысль.
Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
04.07.2013, 00:06  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #37
Есть вопрос + есть ответ, смысл выяснять зачем требуются такие большие матрицы? на вопрос ответил чётко уважаемый форумчанин Tulosba и его подход меня удовлетворил.
-=ЮрА=-
04.07.2013, 00:07
  #38

Не по теме:

Цитата Сообщение от XRuZzz Посмотреть сообщение
массивы(матрицы) больше 255 должны настараживать разработчика.
- т.е скриншот экрана 1024х768 должен меня насторожить?

Ko
 Аватар для Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 246
04.07.2013, 00:08  [ТС]     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) #39
100000*100000 = 10*000*000*000 байт.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.07.2013, 00:11     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера)
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
-=ЮрА=-
04.07.2013, 00:11     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера)
  #40

Не по теме:

Ko вопрос снял, да ты прав.

Yandex
Объявления
04.07.2013, 00:11     Есть матрица из [100000][100000] как лучше ее представить в голове компьютера)
Ответ Создать тему
Опции темы

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