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

@Ko · Регистрация: 23.12.2011

Author24 — интернет-сервис помощи студентам

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

Добавлено через 14 минут
Есть ещё мысль создать таблицу всех вариантов типа
[0] = "AAAAAAAAAAAAAAAAAAAA"
[1] = "AAAAAAAAAAAAAAAAAAAB"
....

Tulosba · 02.07.2013, 16:35

vector<vector<bool>> для начала. А зачем вообще такая матрица?

@~~Ascendancy~~ · 02.07.2013, 16:36

char = 1 байт и следовательно 100000 * 100000 ты меньше чем 10 гигабайт не представишь

@CheshireCat · 02.07.2013, 16:37

А у тебя все 10000000000 значений будут одновременно присутствовать? Если нет, то прежде всего посмотри в сторону разреженных матриц. И "сжать" в битовое представление тоже можно - нужно будет всего-навсего написать простенький собственный класс и переопределить в нем operator[]. В общем, задача легко решается. Только нужно подумать над теми вариантами использования твоей матрицы, которых в сообщении ничего не сказано....

@Ko · 02.07.2013, 16:51 **[ТС]**

Сообщение от 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 · 02.07.2013, 17:06

Сообщение от Ko

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

У Вас с пунктуацией проблемка. Ничего не понятно.
А сравнения проводили, что табличный подход работает быстрее, чем повторное вычисление?

@Dani · 02.07.2013, 17:09

Ko, вы орудуете супер-компьютером ЦРУ? Тут дофига операций. Просто оптимизируйте алгоритм решения задачи.

@Ko · 02.07.2013, 17:22 **[ТС]**

Сообщение от Tulosba

У Вас с пунктуацией проблемка. Ничего не понятно.
А сравнения проводили, что табличный подход работает быстрее, чем повторное вычисление?

) да разница 4-5 раз дольше по этому жертвуем оперативной памятью

Добавлено через 4 минуты

Сообщение от Dani

Ko, вы орудуете супер-компьютером ЦРУ? Тут дофига операций. Просто оптимизируйте алгоритм решения задачи.

Если бы алгоритм не был оптимизирован задача не могла быть решена пока компьютер находится в этом материально-физическом мире. И пожалуйста в моей ветке не надо употреблять любых названий не связанных с с++)

Добавлено через 5 минут
Всё таки может кто поможет написать класс с битами?

Tulosba · 02.07.2013, 17:29

Сообщение от Ko

Всё таки может кто поможет написать класс с битами?

Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит.

@Ko · 02.07.2013, 17:31 **[ТС]**

Сообщение от Tulosba

Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит.

интересно как это bool мне поможет и сделает один бит, может 1 байт?)

~~Dr_Quake~~ · 02.07.2013, 17:36

10 гигов это немного, но если нету - банальная запись на диск и чтение, запись такого типа - чтобы чтение было линейным и дело в шляпе, всё от алгоритма зависит.

Tulosba · 02.07.2013, 17:37

Ko, ознакомьтесь http://www.cplusplus.com/refer... ctor-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 · 02.07.2013, 17:43

Tulosba, а может и не сопимизить. Пусть проверит. Если нет, то с битами написать не так уж тяжело.

@Ko · 02.07.2013, 17:46 **[ТС]**

Сообщение от Tulosba

Ko, ознакомьтесь http://www.cplusplus.com/refer... ctor-bool/

заинтригован))) спасибо) а нет примера?)

Tulosba · 02.07.2013, 17:50

Сообщение от Ko

а нет примера?)

Какого примера? Берете vector<char> и vector<bool> и заполняете туеву-хучу элементов, замечая сколько съест памяти тот и другой при одинаковом кол-ве элементов. Это если в реализацию не смотреть.

@Ko · 02.07.2013, 17:55 **[ТС]**

я выделяю память а не вектора завожу))))

@CheshireCat · 02.07.2013, 17:55

Сообщение от Tulosba

Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит.

Только не должна, а может (23.3.7/3) - "A space-optimized representation of bits is recommended".

@Ko · 02.07.2013, 18:01 **[ТС]**

http://www.cplusplus.com/reference/bitset/bitset/
тут интересный пример

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

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

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

Добавлено через 1 минуту

C++

int main()
{
 
 
    vector< vector< bool > > verified( 100000, vector<bool>( 100000, false ) );
 
 
    cout << verified[5][5]<<endl;
}

Tulosba · 02.07.2013, 18:01

Сообщение от CheshireCat

Только не должна, а может

Сообщение от Tulosba

Нормальная реализация

ключевое слово

@Ko · 02.07.2013, 18:03 **[ТС]**

надо что то там делать чтоб ужалось это дело???)

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

Добавлено через 1 минуту
ну да поджалось в 10 раз где то))))))) но это на первый взгляд, будет пробывать, спасибо всем что помогли)

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	02.07.2013, 17:50	15
	Сообщение от Ko а нет примера?) Какого примера? Берете vector<char> и vector<bool> и заполняете туеву-хучу элементов, замечая сколько съест памяти тот и другой при одинаковом кол-ве элементов. Это если в реализацию не смотреть. 1

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	02.07.2013, 18:01	19
	Сообщение от CheshireCat Только не должна, а может Сообщение от Tulosba Нормальная реализация ключевое слово 0

@Ko 5 / 5 / 2 Регистрация: 23.12.2011 Сообщений: 282
		1
	Есть матрица из [100000][100000] как лучше ее представить в голове компьютера) 02.07.2013, 16:29. Показов 5052. Ответов 45 Метки нет (Все метки) Всем добрый день. Решил коллективно подумать))) есть матрица из [100000][100000] в ней у меня значения 0 или 1 я представил её как char матрицу допустим если 0 это А если 1 это В занимает она в памяти 10 гигов, как сделать более компактней. Ещё осложняет ситуацию что мне к этим значениям нужно обращаться как [x][x]. Может как то можно сделать в битовом представлении такую матрицу и сжать до 8 раз или более? Кто что подскажет? пожалуйста выскажитесь по этому поводу. Добавлено через 14 минут Есть ещё мысль создать таблицу всех вариантов типа [0] = "AAAAAAAAAAAAAAAAAAAA" [1] = "AAAAAAAAAAAAAAAAAAAB" .... 0

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	02.07.2013, 16:35	2
	vector<vector<bool>> для начала. А зачем вообще такая матрица? 1

@~~Ascendancy~~ Заблокирован
	02.07.2013, 16:36	3
	char = 1 байт и следовательно 100000 * 100000 ты меньше чем 10 гигабайт не представишь 0

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	02.07.2013, 16:37	4
	А у тебя все 10000000000 значений будут одновременно присутствовать? Если нет, то прежде всего посмотри в сторону разреженных матриц. И "сжать" в битовое представление тоже можно - нужно будет всего-навсего написать простенький собственный класс и переопределить в нем operator[]. В общем, задача легко решается. Только нужно подумать над теми вариантами использования твоей матрицы, которых в сообщении ничего не сказано.... 1

@Ko 5 / 5 / 2 Регистрация: 23.12.2011 Сообщений: 282
	02.07.2013, 16:51 [ТС]	5
	Сообщение от Tulosba vector<vector<bool>> для начала. А зачем вообще такая матрица? производяться расчёты разово и чтоб из 10000000000 000 раз потом не пересчитывать они сохраняются в матрицу потом я беру из неё значения. Вектор нет смысла применять если большое количество расчёт если это програмулинка которая не загружает одно даже ядро в компе то для удобства очень подходит Добавлено через 1 минуту* Сообщение от CheshireCat А у тебя все 10000000000 значений будут одновременно присутствовать? Если нет, то прежде всего посмотри в сторону разреженных матриц. И "сжать" в битовое представление тоже можно - нужно будет всего-навсего написать простенький собственный класс и переопределить в нем operator[]. В общем, задача легко решается. Только нужно подумать над теми вариантами использования твоей матрицы, которых в сообщении ничего не сказано.... да разряжено это классно, у меня даже компилятор от intela сам создаёт такую матрицу, я беру ему делаю матрицу она должна занимать 5 гигов в памяти он выделяет 700 килобайтов))) Добавлено через 41 секунду Дак я и хотел чтоб мы подумали как сделать этот класс, может у кого то есть в этом опыт Добавлено через 40 секунд давайте сделаем матрицу 128x128 к примеру Добавлено через 5 минут разделить строчку по 8 значений и записать в битовом выражении я в этом направлении думаю 10101010 11111111 00000000 00100101 ну что то в этом хуже как только потом брать значения нужные 0

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	02.07.2013, 17:06	6
	Сообщение от Ko Вектор нет смысла применять если большое количество расчёт если это програмулинка которая не загружает одно даже ядро в компе то для удобства очень подходит У Вас с пунктуацией проблемка. Ничего не понятно. А сравнения проводили, что табличный подход работает быстрее, чем повторное вычисление? 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	02.07.2013, 17:09	7
	Ko, вы орудуете супер-компьютером ЦРУ? Тут дофига операций. Просто оптимизируйте алгоритм решения задачи. 0

@Ko 5 / 5 / 2 Регистрация: 23.12.2011 Сообщений: 282
	02.07.2013, 17:22 [ТС]	8
	Сообщение от Tulosba У Вас с пунктуацией проблемка. Ничего не понятно. А сравнения проводили, что табличный подход работает быстрее, чем повторное вычисление? ) да разница 4-5 раз дольше по этому жертвуем оперативной памятью Добавлено через 4 минуты Сообщение от Dani Ko, вы орудуете супер-компьютером ЦРУ? Тут дофига операций. Просто оптимизируйте алгоритм решения задачи. Если бы алгоритм не был оптимизирован задача не могла быть решена пока компьютер находится в этом материально-физическом мире. И пожалуйста в моей ветке не надо употреблять любых названий не связанных с с++) Добавлено через 5 минут Всё таки может кто поможет написать класс с битами? 0

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	02.07.2013, 17:29	9
	Сообщение от Ko Всё таки может кто поможет написать класс с битами? Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит. 2

@Ko 5 / 5 / 2 Регистрация: 23.12.2011 Сообщений: 282
	02.07.2013, 17:31 [ТС]	10
	Сообщение от Tulosba Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит. интересно как это bool мне поможет и сделает один бит, может 1 байт?) 0

	02.07.2013, 18:03

~~Dr_Quake~~ Заблокирован
	02.07.2013, 17:36	11
	10 гигов это немного, но если нету - банальная запись на диск и чтение, запись такого типа - чтобы чтение было линейным и дело в шляпе, всё от алгоритма зависит. 0

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	02.07.2013, 17:37	12
	Ko, ознакомьтесь http://www.cplusplus.com/refer... ctor-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. 2

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	02.07.2013, 17:43	13
	Tulosba, а может и не сопимизить. Пусть проверит. Если нет, то с битами написать не так уж тяжело. 0

@Ko 5 / 5 / 2 Регистрация: 23.12.2011 Сообщений: 282
	02.07.2013, 17:46 [ТС]	14
	Сообщение от Tulosba Ko, ознакомьтесь http://www.cplusplus.com/refer... ctor-bool/ заинтригован))) спасибо) а нет примера?) 0

@Ko 5 / 5 / 2 Регистрация: 23.12.2011 Сообщений: 282
	02.07.2013, 17:55 [ТС]	16
	я выделяю память а не вектора завожу)))) 0

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	02.07.2013, 17:55	17
	Сообщение от Tulosba Я про vector<bool> не просто так сказал. Нормальная реализация должна использовать для хранения элемента как раз один бит. Только не должна, а может (23.3.7/3) - "A space-optimized representation of bits is *recommended*". 1

@Ko 5 / 5 / 2 Регистрация: 23.12.2011 Сообщений: 282
	02.07.2013, 18:03 [ТС]	20
	надо что то там делать чтоб ужалось это дело???) Добавлено через 24 секунды нормальная реализация, а что там может быть не реально? Добавлено через 1 минуту ну да поджалось в 10 раз где то))))))) но это на первый взгляд, будет пробывать, спасибо всем что помогли) 0