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

Экономия памяти при упаковке данных

11.04.2018, 16:13. Показов 1682. Ответов 13
Метки нет (Все метки)

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

Задан упорядоченный целочисленный массив длины N = 1000.
Значения элементов массива находятся в числовом интервале [0, 15]. Нужно написать

A) функцию, которая «упаковывает» данные, т.е. размещает информацию о числах из массива, используя как можно меньше памяти.
B) функцию, которая «распаковывает» данные, т.е. по информации, полученной при выполнении задания А, восстанавливает исходное состояние массива.

Я написала для задания A, но не понимаю, почему не работает. Идея такая: создать массив [16] и заносить туда количество для каждого числа из заданной последовательности.

Вот функция создания отсортированной последовательности:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int *generateRandomValues(int *array, int size)     
{
    int ch;
    for (int i = 0; i < size; i++)  
    {
        ch = 0 + rand() % 15; 
        array[i] = ch;
    }
 
    qsort(array, size, sizeof(int), compare);       
    
    return array;
}
и непосредственно функция упаковки:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int *inPack(int *array, int size)
{
    int p[16];
    for (int i = 0; i < 16; i++)
        p[i] = 0;
 
    for (int i = 0; i < size; i++) 
    {
        int cnt = 0;
        for (int j = 0; j < 16; j++)
        {
            if (array[i] == array[i - 1])
            {
                cnt++;
                p[j] = cnt;
            }
            else
                cnt = 0;
        }
    }
 
    return p;
}
Добавлено через 58 секунд
Заранее благодарю всех за любые замечания, касающейся темы.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.04.2018, 16:13
Ответы с готовыми решениями:

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

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

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

Реальна ли экономия памяти при использовании генераторов вместо массивов?
Доброго времени суток! Прочитал в книге Котерова, что при использовании генераторов и...

13
2605 / 2195 / 234
Регистрация: 03.07.2012
Сообщений: 7,916
Записей в блоге: 1
11.04.2018, 16:17 2
Предлагаете нам самим разбираться, что значит "не работает"?
0
1 / 1 / 1
Регистрация: 11.04.2018
Сообщений: 45
11.04.2018, 16:19  [ТС] 3
Ну у меня видимо не правильно написала алгоритм, но я не понимаю как сделать по-другому, поэтому прошу помощи.
Или может быть есть какой-то другой вариант экономной по памяти упаковки данных.
0
Велосипедист...
350 / 217 / 73
Регистрация: 15.12.2015
Сообщений: 785
11.04.2018, 16:56 4
1:
Цитата Сообщение от valery7 Посмотреть сообщение
C++
3
int p[16];
Цитата Сообщение от valery7 Посмотреть сообщение
C++
22
return p;
2:
Цитата Сообщение от valery7 Посмотреть сообщение
C++
7
for (int i = 0;
Цитата Сообщение от valery7 Посмотреть сообщение
C++
12
array[i - 1]
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
11.04.2018, 16:57 5
Лучший ответ Сообщение было отмечено valery7 как решение

Решение

Без проверок
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
29
30
31
32
33
#include <algorithm>
#include <array>
#include <iostream>
 
using UnPackedInfo = std::array<int, 1000>;
using PackedInfo   = std::array<size_t, 16>;
 
PackedInfo Pack(const UnPackedInfo &unpInfo)
{
    PackedInfo res {0};
    for (const auto x : unpInfo)
        res[x]++;
    return res;
}
 
UnPackedInfo UnPack(const PackedInfo &pInfo)
{
    UnPackedInfo res {0};
    size_t index = 0;
    for (size_t i = 0; i < pInfo.size(); i++)
        for (size_t j = 0; j < pInfo[i]; j++)
            res[index++] = i;
    return res;
}
 
int main()
{
    UnPackedInfo unpArr = {1, 2, 3, 3, 4, 5, 15};
    std::sort(unpArr.begin(), unpArr.end());
    const PackedInfo pArr = Pack(unpArr);
    const UnPackedInfo unpArr2 = UnPack(pArr);
    std::cout << std::boolalpha << (unpArr == unpArr2);
}
Добавлено через 1 минуту
Цитата Сообщение от valery7 Посмотреть сообщение
Идея такая: создать массив [16] и заносить туда количество для каждого числа из заданной последовательности.
Идея правильная
2
1 / 1 / 1
Регистрация: 11.04.2018
Сообщений: 45
11.04.2018, 17:06  [ТС] 6
Captain Maxee : Что это значит?

Добавлено через 3 минуты
#include <algorithm> - я с этой библиотекой еще не знакома. Мне не понятно, как работает ваша программа..
0
Велосипедист...
350 / 217 / 73
Регистрация: 15.12.2015
Сообщений: 785
11.04.2018, 17:08 7
valery7, насчет 1 — нельзя возвращать указатель на локальный массив; насчет 2 — вместо array[i - 1] на первой итерации, там будет array[ -1 ]. Забудьте. Лучше изучите код от MrGluck.
1
1 / 1 / 1
Регистрация: 11.04.2018
Сообщений: 45
11.04.2018, 17:18  [ТС] 8
MrGluck, могли бы вы написать хотя бы какие-то комментарии к вашему коду?

Добавлено через 6 минут
Я даже ничего не могу вывести, чтобы посмотреть ход работы.
например вывести массив
C++
1
std::cout << unpArr;
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
11.04.2018, 17:40 9
Цитата Сообщение от valery7 Посмотреть сообщение
#include <algorithm> - я с этой библиотекой еще не знакома. Мне не понятно, как работает ваша программа..
Этот заголовочный файл подключается в моём коде исключительно чтобы отсортировать исходную последовательность. Он содержит объявление std::sort, используемуе для сортировки.

Цитата Сообщение от valery7 Посмотреть сообщение
например вывести массив
std::array - это по сути обёртка над массивом фиксированного размера. Вы можете точно так же в цикле выводить содержимое массива, проходясь по индексам.
Или использовать for-each loop
C++
1
2
for (const auto x : arr)
    std::cout << x << " ";
Вместо arr напишите имя массива который хотите вывести. Это, кстати, работает и на обычных массивах.
1
1 / 1 / 1
Регистрация: 11.04.2018
Сообщений: 45
11.04.2018, 18:45  [ТС] 10
Цитата Сообщение от MrGluck Посмотреть сообщение
PackedInfo res {0};
* * for (const auto x : unpInfo)
А что это означает?
Я знаю, что auto - это для переменных сложного типа, но что тут происходит не понятно.

Добавлено через 21 минуту
Цитата Сообщение от MrGluck Посмотреть сообщение
PackedInfo Pack(const UnPackedInfo &unpInfo)
и что тут означает &unpInfo?

Добавлено через 5 минут
Цитата Сообщение от valery7 Посмотреть сообщение
PackedInfo Pack(const UnPackedInfo &unpInfo)
Это я уже поняла, как работает, нашла, но предыдущий вопрос остается.

Добавлено через 21 минуту
все предыдущие вопросы отзываются, я поняла.
сейчас не совсем понимаю, как работает распаковка.
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
11.04.2018, 19:15 11
Лучший ответ Сообщение было отмечено valery7 как решение

Решение

Цитата Сообщение от valery7 Посмотреть сообщение
сейчас не совсем понимаю, как работает распаковка.
Что из себя представляет PackedInfo. Как вы и собирались, это
Цитата Сообщение от valery7 Посмотреть сообщение
массив [16] и заносится туда количество для каждого числа из заданной последовательности.
То есть индекс массива по сути является значением, а значение элементам массива по этому индексу - сколько раз это значение повторяется.
Значит мы просто заводим переменную index, которая будет отвечать за индекс текущего добавляемого элемента в распакованном массиве. И при каждом добавлении смещаем индекс на один (иначе бы записывали по одному и тому же месту).
Проходимся последовательно по всем элементам из запакованной последовательности (16 раз, внешний цикл) и добавляем в результирующую последовательность элемент, равный индексу (таков формат хранения) столько раз сколько записано в запакованном массиве (внутренний цикл).
Всё достаточно тривиально.

Добавлено через 41 секунду
Можете попробовать в отладчике по шагам походить.
1
1 / 1 / 1
Регистрация: 11.04.2018
Сообщений: 45
11.04.2018, 19:29  [ТС] 12
MrGluck, большое вам спасибо, все понятно.

Добавлено через 9 минут
Только с таким представлением данных, не понимаю пока как сгенерировать массив случайных чисел. Написала вот так в main():
C++
1
2
3
4
5
6
7
UnPackedInfo unpArr;
    int ch;
    for (const auto x : unpArr)
    {
        ch = 0 + rand() % 15; // запись случайного числа, которое вернет rand() (от 0 до 15)
        unpArr[x] = ch;
    }
но выдает ошибку.
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
11.04.2018, 19:53 13
Лучший ответ Сообщение было отмечено valery7 как решение

Решение

C++
1
2
3
4
5
6
7
8
9
#include <cstdlib>
#include <ctime>
 
UnPackedInfo unpArr;
srand(time(0));
for (auto &x : unpArr)
    x = rand() % 16; // [0, 15]
std::sort(unpArr.begin(), unpArr.end());
// Pack, Unpack и т.д.
Добавлено через 4 минуты
Или так:
C++
1
2
3
4
5
6
7
#include <random>
 
UnPackedInfo unpArr;
std::default_random_engine gen {std::random_device()() };
std::uniform_int_distribution<> dist(0, std::tuple_size<PackedInfo>() - 1);
std::generate(unpArr.begin(), unpArr.end(), [&dist, &gen] { return dist(gen); });
std::sort(unpArr.begin(), unpArr.end());
1
1 / 1 / 1
Регистрация: 11.04.2018
Сообщений: 45
11.04.2018, 19:57  [ТС] 14
Огромное вам спасибо. Я от вас узнала очень много полезных вещей.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.04.2018, 19:57

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

Экономия памяти
Доброго времени суток, не знаю как надо делать, вот и спросил, допустим есть игра, где шарик просто...

QDir и экономия памяти
Пишу программу под ARM. Вывожу в таблицу содержимое директории расположенной на Flash с помощью...

Экономия памяти и справочные таблицы
Всем привет! Я не так давно работаю в Access и никак не могу уяснить для себя вот какое дело:...

Объявление массивов и передача их по ссылке, экономия памяти
Это кусок спецификации: Не могу понять, почему оба примера выше эквивалентны сначала...


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

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

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