Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
1 / 1 / 0
Регистрация: 02.10.2023
Сообщений: 39

Уменьшить объем памяти

01.12.2023, 17:46. Показов 1028. Ответов 13
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Дано первое число a, задающее последовтальеность. a1 = (a0 * x + y) % 2^15. То есть каждый следующий рекурсивно задается предыдыщуим. Надо вывести наименьшие P из первых M ее элементов. То есть если M = 20, P = 10. То из первых 20 элементов последовательности надо вывести наименьшие 10.
Я реализовал такой код через множества. Ограничение по памяти 4 мегабайта. Как мой код можно уменьшить или убыстритьь?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <set>
#include <cmath>
using namespace std;
int main() {
    int amount_of_elements, first_n_elements;
    long long first_element, x, y;
    cin >> amount_of_elements >> first_n_elements >> first_element >> x >> y;
    int mod = pow(2, 15);
    multiset <int> result;
    for (int i = 0; i < amount_of_elements; i++) {
        long long temp = (first_element * x + y) % mod;
        result.insert(temp);
        first_element = temp;
    }
    int count = 0;
    auto end = result.end();
    for (auto i = result.begin(); i != end; i++) {
        if (count == first_n_elements) break;
        cout << *i << ' ';
        count++;
    }
}
Через множество. Однако ограничение по памяти всего 4 мегабайта. Как можно уменьшить обьем занимаемой памяти
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
01.12.2023, 17:46
Ответы с готовыми решениями:

Ошибка: Объем переменной «m» можно уменьшить
Codacy выводит предупреждение &quot;The scope of the variable 'm' can be reduced.&quot; для кода: int a, m, b; int count = 0; if...

Как уменьшить объем программы упростить код
Здравствуйте, вопрос такой, можно ли как то упростить данный код программы cделать меньшим по объему , суть её заключается в том что...

Как уменьшить размер выделенной памяти
Доброе утро! пишет: переопределение формального параметра &quot;text&quot; :( подскажите пожалуйста как уменьшить размер выделенной памяти под...

13
7804 / 6568 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
01.12.2023, 17:54
Какой там диапазон для M, что не хватает 4 мегабайта?
0
1 / 1 / 0
Регистрация: 02.10.2023
Сообщений: 39
01.12.2023, 18:43  [ТС]
Для М не больше 10^7, для Р не больше 1000
0
7804 / 6568 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
01.12.2023, 19:04
Лучший ответ Сообщение было отмечено efewfedd как решение

Решение

В multiset добавляешь не больше P элементов. Когда заполнится, сравниваешь очередной с максимальным и если подходит, заменяешь.
1
1 / 1 / 0
Регистрация: 02.10.2023
Сообщений: 39
01.12.2023, 20:21  [ТС]
а как это сделать? Как удалит последний элемент и вообще: как его узнать и сравнить с чем-то
0
фрилансер
 Аватар для Алексей1153
6442 / 5636 / 1127
Регистрация: 11.10.2019
Сообщений: 14,984
01.12.2023, 20:23
Цитата Сообщение от efewfedd Посмотреть сообщение
multiset
std::multiset можно заменить на std::vector (с соответствующими упражнениями по поддержанию отсортированности)

будет намного меньше памяти лопать
0
7804 / 6568 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
01.12.2023, 22:20
Цитата Сообщение от efewfedd Посмотреть сообщение
Как удалит последний элемент и вообще: как его узнать и сравнить с чем-то
Ну через итератор - rbegin(), удялять через erase(). Документацию открой.
0
фрилансер
 Аватар для Алексей1153
6442 / 5636 / 1127
Регистрация: 11.10.2019
Сообщений: 14,984
02.12.2023, 09:08
Цитата Сообщение от efewfedd Посмотреть сообщение
То есть если M = 20, P = 10. То из первых 20 элементов последовательности надо вывести наименьшие 10.
я не очень понял, зачем тут задаётся два значения, ведь из них нужно только меньшее. Я же правильно понимаю?

Тогда примерно так (ввод закомментирован, переменные инициализированы)
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
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
 
int main()
{
    size_t amount_of_elements=100, first_n_elements=10;
    //std::cin >> amount_of_elements >> first_n_elements;
    
    long long first_element=3, x=5, y=6;
    //std::cin >> first_element >> x >> y;
    
    std::vector<int> v;
    v.reserve(amount_of_elements);
    for (size_t i = 0; i < amount_of_elements; i++)
    {
        long long temp = (first_element * x + y) % (2<<15);
        v.push_back(temp);
        first_element = temp;
    }
 
    if(first_n_elements<v.size())    
    {
        std::partial_sort(v.begin(), v.begin()+first_n_elements, v.end());
 
        for (size_t i=0; i<first_n_elements; i++)
        {
            std::cout << v[i] << ' ';
        }
    }
}
0
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,266
02.12.2023, 10:03
Цитата Сообщение от Алексей1153 Посмотреть сообщение
std::multiset можно заменить на std::vector (с соответствующими упражнениями по поддержанию отсортированности)
Сортировать вектор придётся многа раз - каждый раз, когда формула выдаст число меньше максимального в векторе. ТОгда заменяем последнее число в векторе на новое - и сортировка. Или какой-то "ручной" алгоритм по вставке нового числа на "своё" место в векторе + соответственно удаление последнего (максимального) элемента вектора. Зато памяти будет занимать мало: размер вектора = 1000х4 байта (для int).
0
фрилансер
 Аватар для Алексей1153
6442 / 5636 / 1127
Регистрация: 11.10.2019
Сообщений: 14,984
02.12.2023, 10:08
Цитата Сообщение от alexu_007 Посмотреть сообщение
Сортировать вектор придётся многа раз
нет, просто нужно искать место вставки при помощи std::lower_bound

а в моём последнем посте сортировка делается один раз, и то частично. Так мне показалось даже лучше
0
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,266
02.12.2023, 10:23
И ещё. 215 = 32768. Формула (линейная конгруэнтная функция) a1 = (a0 * x + y) % 32768 даст неповторяющуюся последовательность не более 32767 чисел - это в идеале, на самом деле скорее всего намного хуже (зависит от значений x и y). Так что продлевать цикл до максимальных 107 не имеет смысла: никаких новых чисел мы из этой формулы не получим.

Добавлено через 9 минут
Цитата Сообщение от Алексей1153 Посмотреть сообщение
нет, просто нужно искать место вставки при помощи std::lower_bound
Ну место то мы найдем, но нужно ещё вставить число в это место где-то в середине вектора. Не потребует ли поиск места и вставка времени больше, чем сортировка?
0
фрилансер
 Аватар для Алексей1153
6442 / 5636 / 1127
Регистрация: 11.10.2019
Сообщений: 14,984
02.12.2023, 10:32
alexu_007, искаться будет не дольше, чем в std::multiset - я бы даже поставил на то, что быстрее. А вот вставка будет подольше. Именно поэтому я не стал сортировать каждый раз, а сортирую частично в самом конце

Добавлено через 1 минуту
Цитата Сообщение от Алексей1153 Посмотреть сообщение
А вот вставка будет подольше.
хотя, тоже вопрос. Для сета - выделение памяти, а для вектора будет memcpy
0
1 / 1 / 0
Регистрация: 02.10.2023
Сообщений: 39
02.12.2023, 11:41  [ТС]
Два занчения нужны, так как мы берем остаток. То есть может быть так, что последовательность первых 20 элементов будет выглядеть как-то так:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 1, 1, 1, 1, 1, 1.
Если вывести просто 10 элементов, то они не будут наименьшими.
0
7804 / 6568 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
02.12.2023, 13:38
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
34
35
36
37
#include <iostream>
#include <set>
 
using namespace std;
 
int main()
{
    int amount_of_elements, first_n_elements;
    long long first_element, x, y;
    int mod = 2 << 15;
    
    cin >> amount_of_elements >> first_n_elements >> first_element >> x >> y;
    
    multiset <int, std::greater<int>> result;
    
    for (int i = 0; i < first_n_elements; i++) {
        long long temp = (first_element * x + y) % mod;
        result.insert(temp);
        first_element = temp;
    }
    
    for (int i = first_n_elements; i < amount_of_elements; i++)
    {
        long long temp = (first_element * x + y) % mod;
        multiset<int>::iterator it = result.begin();
        if (*it > temp) { result.erase(it); result.insert(temp); }
        first_element = temp;
    }
    
    int count = 0;
    auto rend = result.rend();
    for (auto i = result.rbegin(); i != rend; i++) {
        if (count == first_n_elements) break;
        cout << *i << ' ';
        count++;
    }
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
02.12.2023, 13:38
Помогаю со студенческими работами здесь

[Сортировка слиянием] Уменьшить количество требуемой памяти для сортировки
Добрый, на момент написания, день всем. Изучаю алгоритмы данных, дошёл до сортировки слиянием (Merge Sort). Прочитал, что для...

Проверить объем доступной памяти
Нужно проверить объем доступной памяти до и после выполнения программы. Как это можно сделать?

Объём памяти доступный процессу
В книге Джеффри Рихтера сказано &quot;Каждому процессу выделяется собственное виртуальное адресное пространство. Для 32-разрядных процессов...

Map STL - максимальный объем памяти
Пишу модуль для программы - что-то вроде переводчика. Есть словарь синонимов (40+мб). Загружаю его в map, но после 740000+ ключа,...

Как уменьшить размер потребляемой памяти?
Доброго времени суток)не подскажите как уменьшить размер потребляемой памяти приложением? К примеру моя программа вести почти 2...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru