динамична памет - въпрос - Софтуерен университет

Jovanna 186 Точки

динамична памет - въпрос

Здравейте,

въпросчето е към материала от предишното издание на курса, как могат да се разположат неопределен брой стрингове (примерно броят да се въвежда от конзолата) с различна дължина, на случайни начални позиции, като след четене на всеки стринг да се генерира позиция за него в блок с памет с определена големина, N байта? С една if проверка ще го приключваме когато не съществува свободна позиция вече, но как да проверим дали има още място в новото парче памет?

И разполагането на случайни позиции как става? С new и list ли? Нямам си и представа това случайно разполагане как става в новото парче памет.

Тагове:

07/01/2018 12:24:23 C++ Fundamentals 07/01/2018 12:34:09

MartinBG 4803 Точки

Не съм сигурен, че правилно разбирам въпроса.

Ако питаш как се създава нещо в динамичната памет (heap), то това става с ключовата дума new, но предполагам, че това сте го учили вече?

За подобен проблем (съхраняване на неизвестно количество стрингове с произволен размер), аз бих използвал някой STL контейнер (vector, list, map, stack, queue и т.н.. - според конретните нужди) и string (не се сещам за много практически проблеми, при които бих предпочел да менажирам ръчно стринговете, вместо да ползвам готовата библиотека).

***

Въпросът ти ме навежда на мисълта, че искаш да контролираш как се случват нещата на ниско ниво (заделяне и освобождаване на определено количество памет, проверки за препълване). Това в практиката се налага рядко, а още по-рядко е добра идея да се прави, защото губи време както за писане, така и за поддържане, и води до раздуване на програмата с код, който едва ли е свързан директно с проблема, който програмата трябва да реши.

Често стрещана грешка при начинаещите програмисти е, че оптимизират кода си на ниско ниво (т.н. микро оптимизации) без дори да са открили дали и защо им е бавна програмата (Profiling), вместо да подберат правилен алгоритъм и структури, които наистина ще решат проблемите. Не по-малка е и групата в другата крайност - тези, които още не са се замислили за това как работи кодът, който са написали, и дали не може да се оптимизира решението им. :)

07/01/2018 16:26:14 07/01/2018 16:36:42

Jovanna 186 Точки

Не точно на ниско ниво, но с подобен ефект.

Опитах се да го разпиша нато код, но при положение че стринговете са с неизвестна дължина (по условие) и програмата трябва да приключи 1/ ако динамичната памет се напълни или 2/ потребителят да я приключи преди напълване и с въвеждане на празен стринг (Как се въвежда от конзолата празен стринг?? Аз си дефинирах 0 за == "emptyString", има ли нещо по-добро?)

Въвеждам допълнителен вектор, който е "генератор" на произволни индекси чрез random_device и shuffle, като всеки път erase-вам числото което взимам (ползвам нулевия индекс), за да не се презаписват стринговете от вход, ако се падне същия случаен int от вектора.

Но, не мисля че това е правилното решение, защото трябва да се държи сметка за изчерпването на броя байтове, големината на заделената динамичната памет. N в случая с допълнителния вектор го ползвам като индекси на int-ове, което за системата и Windows е 4 байта x 8 бита, въпросът е какво правим ако стринговете са по-големи? Вероятно трябава да се изчислява свободната динамична памет, всеки път след въвеждане на стринг, което не е проблем. Но, как ще се генерира след това случаен индекс, и, така има опасност някои индекси, генерирани по-напред, да се окажат невалидни.

Иначе, написах не така усложнено решение:

https://pastebin.com/6Sefwdxp

08/01/2018 20:14:33

MartinBG 4803 Точки

Много въпроси :)

Би ли дала пълното условие на задачата или линк към него, за да се ориентирам по-точно в проблема?

Иначе, празен стринг от конзолата се въвежда с натискане на Enter без да има други символи на този ред. В C++ може да го засечеш чрез getline, напр:

std::string line;
std::getline(std::cin, line);

if (line.empty()) // Empty string
{
   // Put your code here
}

09/01/2018 06:49:58

kolioi 641 Точки

Не съм много сигурен каква е целта на това упражнение (не съм вземал никакъв курс по C++ - нито предишния, нито сегашния). Доколкото разбирам, имаш някакво парче памет и го пълниш със стрингове (или заемаш памет с произволни размери в него) докато не се напълни, т.е. няма достатъчно място за следващия стринг (парче памет). Ако първоначалния блок памет е с големина N байта, тогава имаш блок с начален адрес adr до adr+N и трябва да генерираш случайно цяло число в интервала от 0 до N, където да разположиш първия стринг. Ако първия стринг S1 има дължина L1 и начален адрес A1, следващия стринг S2 трябва да се разположи така, че да не се припокрива с S1. Така след като разположиш няколко стринга в един момент няма да има свободно място за следващия, макар и да има по-малки блокчета свободна памет.

Относно въвеждането на празен стринг - в C++ форматирани входни данни се четат с оператора >> на cin, а неформатирани - с getline(). Така че може да използваш нещо такова

string word;
getline(cin, word);
while (word.size()) { ... }

Излизаш от цикъла когато не въведеш нищо, а просто натиснеш Enter.

08/01/2018 23:35:16 09/01/2018 04:23:21

Jovanna 186 Точки

Благодаря ви за поясненията как да се въведе празен стринг и запише в кода.

да, това са проблемите с въвеждане на произволен брой с произволна големина стрингове, и то - на случайни позиции в парче памет с определена големина, това , което ми хрумва е, да направя по същата логика вектор - генератор на случайни позиции но не с int-ове, а с пойнтери към тях и с една пойнтер аритметика и проверка, ако стрингът е по-дълъг от р-ра на int-a + проверка дали има запиасан стринг на следващия пойнтер (ако няма, следващия пойнтер го трия (може да остане малко неизползвано място и никога достъпно, но за друг вариант не се сещам. Така или иначе ако се въвеждат къси стрингове или чар, пак ще е същата ситуация)) Това в цикъл, докато стрингът има място да се запише. Ако на тази случайна позиция не стигне дължината на int и позицията на следващия пойнтер е заета вече, пускам пак генератор на случайна позиция, и така докато се намери място. Ако не се - приключвам програмата. И успоредна проверка за сумата от заетите пойнтери х 4, да не надвишава N байта. Ок ли е това? Ще пробвам да го разпиша

Иначе, ето го условието:

Програма:

- разполагане на въведени от клавиатурата думи с различна дължина на случайни начални позиции в блок с памет

- блокът с памет да е с дължина N байта и размерът му да се задава като параметър от командната линия на програмата

- броят на думите не е предварително известен

- след всяка въведена дума трябва да се генерира позиция за нея

- приключване: или при въвеждане на „празна” дума , или когато не съществува свободна позиция за поредната дума

09/01/2018 11:48:29 09/01/2018 12:03:08

kolioi 641 Точки

По принцип ти трябват само случайни цели числа в интервала от 0 до N. Те представляват отместването от началото на блока където да се задели памет. След това трябва допълнително да направиш проверка дали на този адрес може да се разположи текущия стринг, така че да не се застъпва с вече заетите парчета памет. Най-простия начин да се пази информация за заетите блокове памет е като се използва свързан списък (list). Големия блок памет в който слагаш стринговете може да бъде както в хийпа, така и в стека, трябва ти само началния му адрес и големината му. Един доста добър пример за custom memory manager има тук.

Заделянето на динамична памет в хийпа е "скъп" процес, защото е бавен и затова в много програми предварително се заделя голям блок памет в началото и се работи с него. Така се избягва и изтичането на памет.

09/01/2018 14:50:16

Jovanna 186 Точки

Благодаря! Линкът е много добър!!

09/01/2018 16:23:15