С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.60
Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 247
#1

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

02.07.2013, 16:29. Просмотров 2005. Ответов 45
Метки нет (Все метки)

Всем добрый день. Решил коллективно подумать))) есть матрица из [100000][100000] в ней у меня значения 0 или 1
я представил её как char матрицу допустим если 0 это А если 1 это В занимает она в памяти 10 гигов, как сделать более компактней. Ещё осложняет ситуацию что мне к этим значениям нужно обращаться как [x][x]. Может как то можно сделать в битовом представлении такую матрицу и сжать до 8 раз или более? Кто что подскажет? пожалуйста выскажитесь по этому поводу.

Добавлено через 14 минут
Есть ещё мысль создать таблицу всех вариантов типа
[0] = "AAAAAAAAAAAAAAAAAAAA"
[1] = "AAAAAAAAAAAAAAAAAAAB"
....
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.07.2013, 16:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) (C++):

Отгадывание числа от 0 до 100000 - C++
Добрый день! Помогите пожалуйста поправить код, для тех, кто знает язык, наверное, сразу будут видны ошибки. скажу сразу, язык знаю...

fail sort za 0.5 sek 100000 - C++
#include <conio.h> #include <stdio.h> #include <math.h> #include <stdlib.h> #include <time.h> struct el { int val; ...

Игра на С++. Как лучше представить дорогу? - C++
Пишу игру,если это так можно назвать) Все алгоритмы вобщем то готовы, но вот некоторые как по мне, не очень. -КАРТА. То что я сделал...

Какова конфигурация РС лучше (до 100000 рублей)? - Игровой компьютер
Как лучше собрать ПК за 100000 рублей? Вот моя предполагаемая конфигурация (не влезает в пределы 100000 рублей из-за SSD). Я пока...

Оцените, пожалуйста, конфигурацию компьютера (до 100000 рублей) - Игровой компьютер
Здравствуйте, Город: Санкт-Петербург Магазин: "КЕЙ" (http://key.ru/) Цели: одновременная работа с несколькими программами (например,...

Моделирование выполнения 100000 заданий - GPSS
На двух процессорную вычислительную систему в интервале 10-20 секунд (закон равномерный) поступают задания. Задание выполняется любым...

45
Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 247
02.07.2013, 17:55  [ТС] #16
я выделяю память а не вектора завожу))))
0
CheshireCat
Эксперт С++
2896 / 1245 / 78
Регистрация: 27.05.2008
Сообщений: 3,405
02.07.2013, 17:55 #17
Цитата Сообщение от Tulosba Посмотреть сообщение
Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит.
Только не должна, а может (23.3.7/3) - "A space-optimized representation of bits is recommended".
1
Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 247
02.07.2013, 18:01  [ТС] #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;
}
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
02.07.2013, 18:01 #19
Цитата Сообщение от CheshireCat Посмотреть сообщение
Только не должна, а может
Цитата Сообщение от Tulosba Посмотреть сообщение
Нормальная реализация
ключевое слово
0
Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 247
02.07.2013, 18:03  [ТС] #20
надо что то там делать чтоб ужалось это дело???)

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

Добавлено через 1 минуту
ну да поджалось в 10 раз где то))))))) но это на первый взгляд, будет пробывать, спасибо всем что помогли)
0
Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 247
02.07.2013, 18:20  [ТС] #21
так
vector< vector< bool > > verified( 1000000, vector<bool>( 1000000, false ) );
софтина конечно падает

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

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

Не по теме:


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

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

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

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

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

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

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

Добавлено через 3 минуты
Ребята я уже всё проверил и получилось "то что доктор прописал" ))))
0
Dr_Quake
Заблокирован
03.07.2013, 01:02 #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 - так вообще приличная...
1
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
03.07.2013, 03:54 #29
Про bitset вспоминали?
1
Миниатюры
Есть матрица из [100000][100000] как лучше ее представить в голове компьютера)  
Ko
-65 / 5 / 0
Регистрация: 23.12.2011
Сообщений: 247
03.07.2013, 13:02  [ТС] #30
Цитата Сообщение от Dr_Quake Посмотреть сообщение
Ну это и есть битмаска, 1:8 эффективность всего, мало... При том что это ВДОБАВОК к массиву будет использоваться, если массив заполнен хотя бы на 80% - уже предел, очень от ситуации зависит. Плюс переходники if bit==0/1 - они время занимают на активных вычислениях.

Как говорил один мой знакомый(не покойный ещё) писатель time critical вещей, лучшая функция - её отсутствие, и это факт, будет как минимум call-ret задержка с таким переходником в основном цикле позже, а уж если с pushf/popf - так вообще приличная...
да я тоже в первую очередь задумался о скорости получения результатов из таких массивов, сегодня сделаю думаю реализацию и замерю скорость вычислений и сюда выскажусь
0
03.07.2013, 13:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.07.2013, 13:02
Привет! Вот еще темы с ответами:

Тряска объектов на 100000 координатах - Unity, Unity3D
Сделал игру с открытым космосом, звёздной системой и кораблём, но когда далеко отлетаешь от нулевых координат все чаcти корабля начинают...

Системный блок за 100000 рублей - Игровой компьютер
Здравствуйте! Только системный блок. 1. Бюджет: на 100000 рублей +5000 рублей(если не хватит). 2. Задачи для системного блока: Хочу...

Сборка игрового ПК бюджет 100000 - Игровой компьютер
Продолжение темы http://www.cyberforum.ru/config-game-pc/thread1649436.html Хочу брать сегодня-завтра. Бюджет 105000 рублей, но...

Вычислительный центр, до 100000 рублей - Домашний компьютер
Здравствуйте. Необходимо собрать сервер - вычислительный центр, в задачи которого входят вычисления большого объёма математики, без ПО....


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.