2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3  След.
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 11:32 
Аватара пользователя
Zealint в сообщении #541492 писал(а):
(едва ли когда-нибудь long с языке C станет больше 4 байт).
Увы! На 64-разрядном хосте, при компиляции gcc, long оказался 8-ми байтовым. Намучился я с ним изрядно. Дело в том, что данные в файлах были рассчитаны на 4-х байтовый long

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 12:59 
Zealint в сообщении #541492 писал(а):
На самом деле в случае с char может получиться ерунда. Вообще-то он однобайтовый. Но он на то и символьный, что может однажды стать двухбайтовым, как int из 2 байт однажды стал 4...

Есть тип __int8 и он уж точно не станет 16-битным (для этого ему надо потеснить __int16). А вообще это свойство процессора - работать с данными порциями по 8 бит, так что байту до появления первых квантовых компьютеров ничего не грозит.

Цитата:
...А ещё для решения указанной задачи можно забить на решето и решать по-другому.

Есть много задач, когда в массивы записываются только 0 и 1. Например получить пару миллиардов неповторяющихся случайных чисел. Работа с битами - уменьшение требуемой памяти в 8 раз - может оказаться неплохим решением.

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 13:10 
Alexu007 в сообщении #541521 писал(а):
А вообще это свойство процессора - работать с данными порциями по 8 бит
Ну, уже лет 20 как его свойство работать с данными порциями по 32 бита...

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 13:52 
nestoklon в сообщении #541524 писал(а):
Ну, уже лет 20 как его свойство работать с данными порциями по 32 бита...

Может я неправильно сформулировал? Минимальная порция данных - 8 бит = 1 байт. Процессор не может переписать выборочно 1 или 2 бита, он может переписать только весь байт целиком. Возможно это и не лучшее решение, но оно было принято, и поменять его сегдня = выбросить на помойку весь имеющийся софт.

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 15:23 
Аватара пользователя
pika в сообщении #540319 писал(а):
нужно уменьшить размер массива в 8 раз, я понимаю, что нужно обращаться к битам, но не могу реализовать.
А кто вам мешает уменьшить размер массива не в 8, а в 30 раз?
После 30 простые числа дают остаток от деления на 30 - 1, 7, 11, 13, 17, 19, 23, 29. - ровно 8 штук, вот ведь везуха! Ну и рассматривать числа "тридцатками" На каждую тридцатку - 8 битов = 1 байт

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 15:46 
Zealint в сообщении #541492 писал(а):
(едва ли когда-нибудь long с языке C станет больше 4 байт).
Уже.
В 64-битном режиме часто 64-битным делают именно long, а int оставляют 32 бита.

-- Ср фев 22, 2012 07:52:18 --

Alexu007 в сообщении #541533 писал(а):
nestoklon в сообщении #541524 писал(а):
Ну, уже лет 20 как его свойство работать с данными порциями по 32 бита...

Может я неправильно сформулировал? Минимальная порция данных - 8 бит = 1 байт. Процессор не может переписать выборочно 1 или 2 бита, он может переписать только весь байт целиком.
В зависимости от того, что вы имеете в виду под "переписать выборочно", пентиумы либо могут переписать выборочно 1 бит, либо не могут переписать выборочно 1 байт.
Есть команды для оперирования с битами прямо в памяти (с битовой адресацией), правда при этом физически читается и пишется больше бита, но с другой стороны порция физического чтения больше также и байта.

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 18:22 
Day в сообщении #541498 писал(а):
Zealint в сообщении #541492 писал(а):
(едва ли когда-нибудь long с языке C станет больше 4 байт).
Увы! На 64-разрядном хосте, при компиляции gcc, long оказался 8-ми байтовым. Намучился я с ним изрядно. Дело в том, что данные в файлах были рассчитаны на 4-х байтовый long
venco в сообщении #541577 писал(а):
Уже.
В 64-битном режиме часто 64-битным делают именно long, а int оставляют 32 бита.

Да, неожиданно. Но идея моя в том, чтобы найти такой тип, который точно не поменяется. Вот мне подсказывают __int8, но он не везде есть. Лучше определить свой тип MyInt32 и потом подставлять в него именно то, что будет гарантированно 32 битовым. А вообще нарушение совместимости немного раздражает, поэтому я во многих важных программах всегда определяю свои типы данных. При переносе программы просто меняю преамбулу файла.

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 18:43 
venco в сообщении #541577 писал(а):
В зависимости от того, что вы имеете в виду под "переписать выборочно", пентиумы либо могут переписать выборочно 1 бит, либо не могут переписать выборочно 1 байт.
Есть команды для оперирования с битами прямо в памяти (с битовой адресацией), правда при этом физически читается и пишется больше бита, но с другой стороны порция физического чтения больше также и байта.

Процессор может загрузить из памяти в регистр 1 байт, проделать с ним некие действия, и записать байт из регистра в память. Чтобы поменять 1 бит в памяти, нужно всё равно переписывать весь байт.

Какие там у вас команды для оперирования битами прямо в памяти? И как адресация осуществляется? Может я отстал от жизни?

-- Ср фев 22, 2012 19:52:18 --

Zealint в сообщении #541628 писал(а):
...Лучше определить свой тип MyInt32 и потом подставлять в него именно то, что будет гарантированно 32 битовым. А вообще нарушение совместимости немного раздражает, поэтому я во многих важных программах всегда определяю свои типы данных. При переносе программы просто меняю преамбулу файла.

Круто! А хоть арифметические операции для своего типа работать будут, или нужно будет самому вручную переписывать всё, начиная с А + В?

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 18:53 
Alexu007 в сообщении #541635 писал(а):
Процессор может загрузить из памяти в регистр 1 байт, проделать с ним некие действия, и записать байт из регистра в память. Чтобы поменять 1 бит в памяти, нужно всё равно переписывать весь байт.

Какие там у вас команды для оперирования битами прямо в памяти? И как адресация осуществляется? Может я отстал от жизни?
Чтобы поменять байт в памяти, современный процессор читает 64-байтовую строку кеша, а потом пишет её целиком назад. Полная аналогия с модификацией одного бита. А для битов и команды есть в i386: bt, btc, bts, btr.

-- Ср фев 22, 2012 11:03:16 --

Alexu007 в сообщении #541635 писал(а):
Круто! А хоть арифметические операции для своего типа работать будут, или нужно будет самому вручную переписывать всё, начиная с А + В?
Под определением своего типа Zealint, скорее всего, имел в виду typedef - синоним существующего типа вместе со всеми его функциями и операторами.

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 20:00 
venco в сообщении #541638 писал(а):
Под определением своего типа Zealint, скорее всего, имел в виду typedef - синоним существующего типа вместе со всеми его функциями и операторами.

Да, именно так имело в виду здесь.

Хотя в самом общем случае и не обязательно. Когда говорят, определить тип, а потом сообщают, что меняется только преамбула файла, то очевидно, что каким-то образом все нужные операторы тоже меняются или работают автоматически (если они вообще нужны, что не обязательно). При этом делается это как-то легко, раз успешно применяется на практике. Детали уже зависят от конкретного случая.

-- Ср фев 22, 2012 20:05:08 --

Вот пример заготовки, которая меня последние несколько лет полностью устраивает. Слово signed добавил лишь из эстетического чувства, заставшего меня в момент написания кода.

Код:
   typedef signed char      int8;
   typedef signed short int int16;
   typedef signed int       int32;
#if defined(__GNUC__)
   typedef signed long long int64; 
#else
   typedef signed __int64   int64; 
#endif

   typedef unsigned char      int8u;
   typedef unsigned short int int16u;
   typedef unsigned int       int32u;
#if defined(__GNUC__)                 
   typedef unsigned long long int64u;
#else
   typedef unsigned __int64   int64u;
#endif


 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 20:20 
Day в сообщении #541566 писал(а):
pika в сообщении #540319 писал(а):
нужно уменьшить размер массива в 8 раз, я понимаю, что нужно обращаться к битам, но не могу реализовать.
А кто вам мешает уменьшить размер массива не в 8, а в 30 раз?
После 30 простые числа дают остаток от деления на 30 - 1, 7, 11, 13, 17, 19, 23, 29. - ровно 8 штук, вот ведь везуха! Ну и рассматривать числа "тридцатками" На каждую тридцатку - 8 битов = 1 байт

Как это прикрутить к обсуждаемому алгоритму? Там элементы таблицы последовательно перемножаются, а тут остатки от деления... что на что умножать?

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 20:22 
Zealint в сообщении #541675 писал(а):
Слово signed добавил лишь из эстетического чувства, заставшего меня в момент написания кода.
На всякий случай: в случае с "signed char" это важно, "signed char" и "char" - разные типы.

-- Ср фев 22, 2012 12:24:50 --

Alexu007 в сообщении #541681 писал(а):
Day в сообщении #541566 писал(а):
pika в сообщении #540319 писал(а):
нужно уменьшить размер массива в 8 раз, я понимаю, что нужно обращаться к битам, но не могу реализовать.
А кто вам мешает уменьшить размер массива не в 8, а в 30 раз?
После 30 простые числа дают остаток от деления на 30 - 1, 7, 11, 13, 17, 19, 23, 29. - ровно 8 штук, вот ведь везуха! Ну и рассматривать числа "тридцатками" На каждую тридцатку - 8 битов = 1 байт

Как это прикрутить к обсуждаемому алгоритму? Там элементы таблицы последовательно перемножаются, а тут остатки от деления... что на что умножать?
Это нетривиальная оптимизация, но экономит не только память, но и рантайм из-за лучшей работы кеша.

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 22:19 
Аватара пользователя
Alexu007 в сообщении #541681 писал(а):
Как это прикрутить к обсуждаемому алгоритму? Там элементы таблицы последовательно перемножаются, а тут остатки от деления... что на что умножать?
Обещаю, покажу. Это не слишком сложно, но требует некоторого умственного напряжения. Вот, празднички закончатся, или пауза какая образуется...

Всех с наступающим праздником!

Идея в том, что хранить не все элементы решета, а только те, которые в остатке деления на 30 дают 1, 7 и тд. Ведь не храните же вы четные позиции. Или все-таки храните? Но это, гмм... расточительно. Ведь и ежу понятно, что четные после двойки не будут простыми.

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 23:14 
Day в сообщении #541725 писал(а):
Ведь не храните же вы четные позиции. Или все-таки храните

Храним мы только единицы и нули. А само число - это адрес, смещение относительно начала массива. В адресах простых чисел - нули, остальное единицы.

 
 
 
 Re: С++: Уменьшение памяти в 8 раз
Сообщение22.02.2012, 23:30 
Аватара пользователя
Alexu007 в сообщении #541760 писал(а):
Храним мы только единицы и нули. А само число - это адрес, смещение относительно начала массива. В адресах простых чисел - нули, остальное единицы.
Значит по адресу 20223456 вы тоже что-то храните?
Вы там храните единицу, я знаю. А зачем ее хранить? Если даже я знаю, не протряся еще ничего из этого решета. :-)

-- Чт фев 23, 2012 00:47:27 --

Попробую еще прояснить идею.
Для числа N его признак простоты мы храним не по адресу N, а по адресу вычисленному так
Код:
  A = N/30;
  R = N%30;
  if (R==1) A+=1;
  else if (R==7) A+=2
  else if (R==11) A+=3
  // ......

А остальные значения N нас просто не интересуют, мы априори знаем, что они не просты (простите невольный каламбур)
Все это, конечно, можно оформить и поизящнее, но подождите чуток.

 
 
 [ Сообщений: 34 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group