Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
0 / 0 / 0
Регистрация: 29.10.2016
Сообщений: 6
1

Экономия памяти

26.03.2018, 20:55. Показов 652. Ответов 20
Метки нет (Все метки)

Здравствуйте, уважаемые программисты!
Как разместить информацию о числах из массива, используя как можно меньше памяти?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.03.2018, 20:55
Ответы с готовыми решениями:

Экономия памяти
Скажите, будет ли второй вариант кода занимать меньше памяти? 1ый вариант: float a; f(a); ...

Экономия памяти при упаковке данных
Здравствуйте, уважаемые программисты! Есть такая задача: Задан упорядоченный целочисленный...

Скорость или экономия памяти - что бы выбрали Вы?
...

Экономия памяти или борьба с точками. (что-то типа массива ссылок хотелось бы иметь)
У меня есть объект Point. И есть Объект Grup. В объекте Grup я выделил динамически память под...

20
1122 / 851 / 394
Регистрация: 30.10.2017
Сообщений: 2,382
26.03.2018, 23:24 2
Подробнее опишите проблему.
0
Модератор
1623 / 1078 / 485
Регистрация: 17.07.2012
Сообщений: 5,308
27.03.2018, 04:58 3
Цитата Сообщение от olivia11 Посмотреть сообщение
Как разместить информацию о числах из массива
Какую информацию? Какую задачу вы решаете(т.е что вы хотите сделать)?
0
0 / 0 / 0
Регистрация: 29.10.2016
Сообщений: 6
27.03.2018, 05:38  [ТС] 4
Задан упорядоченный массив целых чисел длины N>>1000. Значения элементов массива находятся в числовом интервале [0, 17].
Нужно написать функцию, которая размещает информацию о числах из массива, используя как можно меньше памяти.
0
1122 / 851 / 394
Регистрация: 30.10.2017
Сообщений: 2,382
27.03.2018, 12:15 5
olivia11, что такое >> ?
0
3331 / 2704 / 733
Регистрация: 25.03.2012
Сообщений: 9,785
Записей в блоге: 1
27.03.2018, 12:45 6
QuakerRUS, много больше, блин! Что непонятного?
А по теме Сожми по хаффману.
0
Эксперт C
25592 / 15962 / 3418
Регистрация: 24.12.2010
Сообщений: 34,914
27.03.2018, 12:50 7
Если массив упорядочен, то его можно представить массивом целых x[18]
x[0] - Количество чисел равных 0
x[1] - Количество чисел равных 1
и так далее до 17 ....
0
1122 / 851 / 394
Регистрация: 30.10.2017
Сообщений: 2,382
27.03.2018, 13:00 8
Kuzia domovenok, у меня было подозрение, но в C++ этот знак используется для других целей, поэтому решил уточнить.
0
0 / 0 / 0
Регистрация: 29.10.2016
Сообщений: 6
27.03.2018, 13:59  [ТС] 9
Я не совсем поняла, как это сделать, если заранее количество чисел неизвестно.
Просто, мне кажется, такая упаковка данных займёт куда больше памяти (целых 18 массивов), вместо 1 динамического.
0
2857 / 1725 / 353
Регистрация: 09.09.2017
Сообщений: 7,271
27.03.2018, 14:27 10
Байт, это не сохранит порядок
olivia11, мы не знаем какую информацию вы хотите потом из сжатого массива получить. А то можно просто упаковать в структуры
C
1
2
3
4
5
6
struct elems{
  int e1:5;
  int e2:5;
  int e3:5;
};
struct elems arr[];
это даст экономию в 1,3 раза без потери информации. Правда разархивировать будет чуть сложнее.
0
0 / 0 / 0
Регистрация: 29.10.2016
Сообщений: 6
27.03.2018, 14:31  [ТС] 11
Потом мне нужно будет распаковать данные из массива, то есть т.е. по информации, полученной в этом задании, восстанавить исходное состояние массива.
0
1122 / 851 / 394
Регистрация: 30.10.2017
Сообщений: 2,382
27.03.2018, 14:34 12
COKPOWEHEU, только занимать в памяти будет такая структура число байтов, равное разрядности int. Надо тогда уж 10 значений по 5 бит использовать при 32-разрядном int.

Немного оптимальнее по размеру в восемнадцатеричной системе хранить данные в блоках по 36 байт (при 32-разрядном int), но их будет сложнее извлекать и записывать, чем используя битовые поля.
0
2857 / 1725 / 353
Регистрация: 09.09.2017
Сообщений: 7,271
27.03.2018, 15:00 13
C
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <stdint.h>
 
struct elems{
  uint16_t e1:5;
  uint16_t e2:5;
  uint16_t e3:5;
};
struct elems arr[10];
int main(){
  printf("%i\n", sizeof(arr));
}
говорит 20 байт, то есть по 2 байта на элемент. Значит все-таки в 1.5 раза экономия места
0
Эксперт C
25592 / 15962 / 3418
Регистрация: 24.12.2010
Сообщений: 34,914
27.03.2018, 15:40 14
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Байт, это не сохранит порядок
Не понял, о каком порядке речь.
Вот задание
Цитата Сообщение от olivia11 Посмотреть сообщение
Задан упорядоченный массив целых чисел длины N. Значения элементов массива находятся в числовом интервале [0, 17].
Я понял так, что массив представляет что-то в этом роде: 0 0 0 1 1 3 4 5 5 17 17
Упаковывается по моему предложению он так: 3 2 0 1 1 2 0 0 0 ... 0 2
Восстановить исходный массив не составит труда
3 нолика, 2 единички, 1 тройку ...
Может быть условие надо читать как-то иначе, но мне на это ума не хватает
2
QuakerRUS
27.03.2018, 15:52
  #15

Не по теме:

:D Байт оказался самым внимательным из нас. А мы тут уже почти ракету построили, а надо было молоток.

0
302 / 214 / 74
Регистрация: 23.05.2011
Сообщений: 970
27.03.2018, 15:59 16
Тут нужно применить подход из sparse matrix в scipy.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Индекс — значение, значение — кол-во таких
size_t index_ranges[18] = {};
 
// Получаем оригинальное значение из нашего
int get_val(const size_t index)
{
   int ind = 0;
   size_t offset = 0;
   while(offset+index_ranges[ind]<=index)
   {
       offset+=index_ranges[ind++];
       if(ind>=18)
          throw "Error";
   }
   return ind;
}
Добавлено через 1 минуту
Кстати, такой упаковкой мы ещё добились константной вставки в массив!
0
0 / 0 / 0
Регистрация: 29.10.2016
Сообщений: 6
27.03.2018, 16:05  [ТС] 17
Извините, я не понимаю, как такая упаковка займёт меньше места.. Ведь так получается целых 18 массивов, вместо одного динамического.

Добавлено через 52 секунды
А можно где-то подробнее об этом почитать? Не совсем пока понимаю, что тут у вас происходит.
0
1122 / 851 / 394
Регистрация: 30.10.2017
Сообщений: 2,382
27.03.2018, 16:05 18
olivia11, у вас упорядоченный массив. Вам нужен один массив со счетчиками на 18 элементов. Смотрите сообщение от Байт.
0
Эксперт C
25592 / 15962 / 3418
Регистрация: 24.12.2010
Сообщений: 34,914
27.03.2018, 16:13 19
Цитата Сообщение от olivia11 Посмотреть сообщение
Ведь так получается целых 18 массивов,
Где это, интересно, вы увидели 18 массивов Есть просто 18 чисел и больше ничего. Эти числа - счетчики. И опять же - больше ничего.
Посмотрите внимательно на пост 14. Там приведен правильный пример массива? Если нет, то вы неправильно сформулировали задачу.

Не по теме:

Цитата Сообщение от olivia11 Посмотреть сообщение
А можно где-то подробнее об этом почитать?
Чего тут читать-то? Позовите ежика - он поймет:)

0
302 / 214 / 74
Регистрация: 23.05.2011
Сообщений: 970
27.03.2018, 16:16 20
И даже более навороченный вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template<int lower_bound = 0, int upper_bound = 18>
class SparceList
{
private:
    constexpr static size_t RANGE_SIZE = upper_bound-lower_bound;
    // Индекс — значение, значение — кол-во таких
    size_t value_sizes[RANGE_SIZE] = {};
public:
    // Получаем оригинальное значение из нашего
    int get_val(const size_t index)
    {
       size_t ind = 0;
       size_t offset = 0;
       while(offset+value_sizes[ind]<=index)
       {
           offset+=value_sizes[ind++];
           if(ind>=RANGE_SIZE)
              throw "Error";
       }
       return (int)ind+lower_bound;
    }
    void add(const int val)
    {
        if (val>=upper_bound || val<lower_bound)
            throw "Error";
        value_sizes[val-lower_bound]++;
    }
};
Цитата Сообщение от olivia11 Посмотреть сообщение
Ведь так получается целых 18 массивов, вместо одного динамического.
Нет, получается 1 массив с 18 элементами вместо 1 массива с огромным количеством.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.03.2018, 16:16

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Экономия по времени
Приветствую всех! Как сделать данную программу максимально быстрой, для прохождения теста в...

Экономия трафика при передачи последовательности изображений в сети за счет эффективного кодирования
Всем добрый день! Есть такая задачка: мы берем последовательность изображений и передаем в сеть как...

Выделить в памяти 1024 ячейки по 8 байт и вывести их адреса(МИНИ менеджер памяти))
Вот тут появилась такая интересная задача: требуется сделать программу которая управляет 1024...

Можно ли разместить переменную в нужную ячейку памяти и реально ли хранить данные, разбросанными по памяти?
Добрый день. Не могу найти информацию по двум вопросам : 1) могу ли я разместить переменную в...

Резервирование памяти/освобождение памяти для трехмерного массива
Необходимо создать трехмерный массив (A), в котором элементы вдоль направления Z выли бы выровнены...

Разработка программы обмена местами двух целочисленных ячеек памяти без использования дополнительной памяти
Разработка программы обмена местами двух целочисленных ячеек памяти без использования...


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

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

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