Блог

Я написал программу для составления списка простых чисел от 2 до заданного пользователем числа как на python, так и на C. Я запустил обе программы, ищущие простые числа с точностью до одного и того же числа, и посмотрел на их соответствующие процессы в activity monitor. Я обнаружил, что реализация python использовала ровно в 9 раз больше памяти, чем реализация C. Почему python требует намного больше памяти и почему это конкретное значение multiple для хранения одного и того же массива целых чисел? Здесь представлены обе реализации программы:

Версия Python:

 import math
import sys

top = int(input('Please enter the highest number you would like to have checked: '))
num = 3
prime_list = [2]
while num <= top:
    n = 0
    prime = True
    while int(prime_list[n]) <= math.sqrt(num):
        if num % prime_list[n] == 0:
            prime = False
            n = 0
            break
        n = n   1
    if prime == True:
        prime_list.append(num)
        prime = False
    num = num   1
print("I found ", len(prime_list), " primes")
print("The largest prime I found was ", prime_list[-1])
  

Версия C:

 #include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/types.h>
#include <unistd.h>

int main(){
    int N;
    int arraySize = 1;
    int *primes = malloc(100*sizeof(int));
    int isPrime = 1;
    primes[0] = 2;
    int timesRealloc = 0;
    int availableSlots = 100;

    printf("Please enter the largest number you want checked: n");
    scanf("%d", amp;N);

    int j = 0;
    int i;
    for (i = 3; i <= N; i =2){
        j = 0;
        isPrime = 1;
        while (primes[j] <= sqrt(i)) {
            if (i%primes[j] == 0) {
                isPrime = 0;
                break;
            }
            j  ;
        }
        if (isPrime == 1){
            primes[arraySize] = i;
            arraySize  ;
        }
        if (availableSlots == arraySize){
            timesRealloc  ;
            availableSlots  = 100;
            primes = realloc(primes, availableSlots*sizeof(int));
        }
    }

    printf("I found %d primesn", arraySize);
    printf("Memory was reallocated %d timesn", timesRealloc);
    printf("The largest prime I found was %dn", primes[(arraySize-1)]);


    return 0;
}
  

 >>> import sys
>>> sys.getsizeof(123456)
28
  

Это в 7 раз больше размера C int . В Python 3 целых числа являются экземплярами struct _longobject a.k.a PyLong :

 struct _longobject {
    PyVarObject ob_base;
    digit ob_digit[1];
};
  

где PyVarObject находится

 typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size;
} PyVarObject;
  

и PyObject является

 typedef struct _object {
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;
  

Из этого мы получаем следующее использование памяти для этого объекта 123456 в 64-разрядной сборке Python:

• 8 байт для счетчика ссылок ( Py_ssize_t )
• 8 байт для указателя на объект типа amp;PyLong_Type (типа PyTypeObject *
• 8 байт для подсчета количества байт в части объекта переменной длины; (типа Py_ssize_t )
• 4 байта на каждые 30 бит цифр в целом числе.

Поскольку 123456 умещается в первые 30 бит, это в сумме равно 28, или 7 * sizeof (int)

Это в дополнение к тому факту, что каждый элемент в Python list является PyObject * , который указывает на фактический объект; каждый из этих указателей имеет 64 бита в 64-разрядных сборках Python; что означает, что каждая ссылка на элемент списка сама по себе потребляет в два раза больше памяти, чем C int .

Сложите 7 и 2, и вы получите 9.

Для более эффективного хранения кода вы можете использовать массивы; с типом code 'i' потребление памяти должно быть довольно близко к версии C. у array s есть append метод, благодаря которому увеличение массива должно быть даже проще, чем в C / with realloc .