Нужно предложение для эффективного управления памятью в C ++?

Question

Я написал небольшую программу, чтобы найти число, которое является и простым, и множителем определенного числа n.Я получаю число n из файла и печатаю его в другом.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <iostream>
#include <fstream>

using namespace std;
bool PrimeFactor(int );
int countSize(int);


char * p_str = "";//store result of prime factor
int size = 0;//length of p_str

int main(int argc, char** argv) {
std::ifstream fin;
fin.open("input.txt");

std::ofstream fout;
fout.open("output.txt", std::ios::app);

int N;//number to factor

while (fin >> N){   
    //Find prime factor
    PrimeFactor(N);
    fout << p_str;// print string storing result
    fout << endl;
}

fin.close();
fout.close();

return 0;
}

bool PrimeFactor( int n ){
int count = 0;// count divisors

for (int i = 2 ; i < n; i++){
    if ( n % i == 0 ){
        // convert integer to string
        char * tmpstr = new char[ countSize(i) ]  ;// allocate according to size of integer (not waste memory)
        sprintf( tmpstr, "%d ", i); // NOTE : if not have the blank after %d -> no space

        // condition : prime and not duplicate existing number in global string
        if ( PrimeFactor(i) && !strstr( p_str, tmpstr ) ){

            char * new_p = new char [ size + countSize(i) ];
            strcpy( new_p, p_str );// copy the global string to new place
            strcat( new_p, tmpstr );// append new integer value
            p_str = new_p ; // let glocal string be renewed with appending new result
            size = size + countSize(i);
            cout << size << endl;
        }
        count ++;
    }
}

if (count > 0)//not prime
    return false;
return true;
}

//counting the number of digit of an integer
int countSize(int n){
    int count = 0;
    if (n < 10)
        return 1;
    while ( n >= 10 ){
        count++;
        n = n/10;
    }
    return count + 1;
}

При таком подходе результат может быть дублирован, если я не сохраню найденные числа в C-строке и проверим,следующий номер уже номер в строке.Я выбираю C-строку, так как она сложнее, чем std :: string.Таким образом, вопрос заключается в манипулировании строкой, чтобы минимизировать использование памяти.Я должен использовать глобальный указатель на символ (так как не нужно определять размер массива символа).Кажется, что func CountSize (), хотя и возвращает то, что нужно (длина числа в строке), строка все равно тратит часть памяти, а переменная размера - это не то, что я имел в виду.Также я не могу получить размер с помощью sizeof () с указателем на символ.Кто-нибудь может мне помочь?

Answer 1

ОК, так что вы хотите использовать строки char *, предположительно, чтобы справиться с ними на будущее.Это замечательно.Но сначала вам понадобится ускоренный курс в заповеди управления c-string ...

Вы должны соединиться каждые new с delete

Ваша цель - попытаться минимизировать использование памяти, верно?Ну, каждый раз, когда вы создаете строку с new, но затем не удаляете ее, вы теряете эту память.Это плохая практика в целом, но и определенная потеря памяти.В вашем случае вы выделяете new [] для создания массива, а вызовы new [] должны быть сопряжены с delete [].Итак, в вашей функции PrimeFactor:

strcpy( new_p, p_str );// copy the global string to new place
strcat( new_p, tmpstr );// append new integer value
// delete original contents of p_str
delete [] p_str;
p_str = new_p ; // let glocal string be renewed with appending new result

Вам также понадобится delete [] в самом конце вашей программы, чтобы очистить память p_str перед ее выходом.

Ты всегда будешь освобождать место для нулевого терминатора

Когда компьютер читает к-струну, он не знает заранее, как долго это будет продолжаться.Если у вас есть символ [100], инициализированный содержимым «Привет», как компьютер, как известно, останавливается после «i», а не «H» или символа 5 после «i»?C-строки недопустимы, если они не заканчиваются нулевым терминатором, записанным как '\ 0'.Нуль-терминатор указывает компьютеру: «Хорошо, мы закончили».Строка окончена.Это довольно изящно, но могут возникнуть проблемы, потому что нулевой терминатор занимает место в массиве символов.Для сохранения «Привет» требуется char [3]; - char[0] - это «H», char[1] - это «i», а char[2] - «\ 0».Таким образом, ваш новый код выделения строк должен выглядеть следующим образом:

    char * tmpstr = new char[ countSize(i) + 1 ]  ;// allocate according to size of integer (not waste memory)
    ...
        char * new_p = new char [ size + countSize(i) + 1 ];

Обратите внимание на + 1 s.Это необходимо для того, чтобы в ваших строках оставалось место для нулевого терминатора.

Вы должны использовать функции, безопасные для строк

sprintf, strcpy и strcat (и другие) устарели в пользу новых функций sprintf_s, strcpy_s и strcat_s._S означает «безопасный».Эти функции принимают дополнительный параметр для размера изменяемой строки и гарантируют, что ограничение размера не нарушено.Все функции строкового модификатора гарантируют, что вышеупомянутый нулевой терминатор прикреплен, но в вашем коде вы не дали им достаточно места для этого.Таким образом, функции, не являющиеся безопасными для строк, записывали один символ, вставляя вашу объявленную память в неизвестную память - плохо - очень плохо.Строково-безопасные версии этих функций вместо этого могли бы привести к сбою вашей программы с ошибкой, предупреждающей вас о том, что что-то не так и нужно исправить.Строковая безопасная реализация ваших функций будет выглядеть так:

    int tmpstrSize = countSize( i ); // calculate tmpstrSize once
    char * tmpstr = new char[ tmpstrSize + 1 ]  ;// allocate according to size of integer (not waste memory)
    sprintf_s( tmpstr, tmpstrSize + 1, "%d ", i); // NOTE : if not have the blank after %d -> no space
    ...
        int new_pSize = size + tmpstrSize; // calculate new_pSize once
        char * new_p = new char [ new_pSize + 1 ];
        strcpy_s( new_p, new_pSize, p_str );// copy the global string to new place
        strcat_s( new_p, new_pSize, tmpstr );// append new integer value

Теперь вы в порядке и в безопасности, и если что-то пойдет не так, вы будете знать .

Вы должны написать код C ++ на языке C ++

По правде говоря, программа, которую вы написали выше, на самом деле не C ++, а C. Конечно, она будет нормально работать всреда C ++, но метод полностью основан на C.Программы на C ++ используют std::string s для строк и std::vector s для списков целых чисел.Так что, эй, я понимаю, что вы хотите изучить материал низкого уровня для этого испытания, я сам там был.Но как только вы знаете, как это сделать, функциональность C ++, которая делает практически все, что я описал выше, неуместной для обработки строк, становится находкой , и вы никогда не захотите возвращаться назад.

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

Answer 2

Строка не совсем подходящая структура данных для того, что вы пытаетесь сделать. Вы, кажется, обеспокоены потреблением памяти, но почему? У вас действительно не хватает памяти с вашей программой? Использование строки для этой задачи накладывает много ненужной работы: выделение памяти, копирование строки для добавления нового числа, поиск в строке существующего числа, преобразование целых чисел в строки, подсчет числа цифр в целом числе больше раз, чем необходимо , и так далее. Использование строк C также упрощает ввод ошибок: строки, которые не заканчиваются нулем, переполнения буфера и т. Д. Например, при преобразовании целого числа в строку вы не выделяете байт для нулевого терминатора, поэтому sprintf переполняет ваш буфер.

Более подходящей структурой данных будет набор целых чисел. Набор может хранить значение один раз и только один раз. Вы можете использовать метод find, чтобы увидеть, существует ли элемент в наборе. Использование набора, вероятно, потребует немного больше памяти, но ваша программа будет намного, намного, намного быстрее, потому что вы замените много операций O (N) операциями O (1) и O (log n).

Вы не можете использовать sizeof, чтобы получить размер выделенного массива. Это потому, что sizeof возвращает размер типа, поэтому, когда вы используете sizeof для строки C, вы получаете размер указателя, а не размер массива. Вы должны отслеживать размер массива самостоятельно.

Вы упоминаете об использовании C-строк вместо std :: string, потому что это сложнее. Я благодарю вас за то, что вы пытаетесь бросать вызов, потому что это отличный способ расширить ваши возможности и узнать что-то новое. Если я могу сделать предложение: сделайте простейшую вещь, которая может сработать первой. Напишите тесты, чтобы убедиться, что он делает то, что, как вы думаете, он делает. Имея работающую программу и проверочный тест, вы можете начать оптимизировать потребление памяти, производительность или сложные структуры данных для развлечения. Тест позволяет вам убедиться, что ваши оптимизации не привели к ошибкам при оптимизации.

Answer 3

Храните целые числа в виде строк, и вы спрашиваете об эффективном управлении памятью?