Press "Enter" to skip to content

Posts published in “Desgin”

Python中的整型占多少个字节?

说到计算机中的整型,相信很多人都会联想到32位整型(或者int),是程序员日常生活中用的最多的一种类型。32位整型顾名思义,占用32个位也就是4个字节,取值范围−2,147,483,648~ 2,147,483,647 。C/C++中是4个字节,Java中也是4个字节,但是Python中呢?

我们知道Python中也有int类,而且非常好用,原生支持高精度计算。但是Python中的一个整型到底占用多少字节呢?我相信绝大多数的Python程序员从未想过这一点,越是习以为常的东西越是不会在意它的存在

在Python中,如果想要知道一个对象所占用的内存大小,只需要使用sys.getsizeof这个API就可以了。那就让我们来试一下不同的整数

从上面的小实验可以看出,一个整型最少要占24字节(0),1开始就要占用28个字节,到了2的30次方开始要占用32个字节,而2的128次方则要占用44个字节。我们可以得到两点规律,1. 字节数随着数字增大而增大。2. 每次的增量是4个字节。 好像至此已经回答了我们的题目中的问题:Python中的整型占多少个字节?答案是:变长的(相对于int32的定长),而且最少24个字节。

你以为本文到这里就结束了吗?那你就图样图森破了。一个整型数2,居然要占用28个字节!这完全了颠覆了我的认知,我一定搞清楚为什么。 在哥们的帮助下,我找到了Python的源码。 https://github.com/python/cpython

Python的官方实现是C语言,所以叫cpython。这也就意味着只要Python还在,C就会不消失。其他实现还有jython(Java), IronPython (.Net), PyPy (Python)。

第一件事情要搞清楚的是Python中int类型在cpython的名字是什么?看了半天,在 longobject.h 中发现了一个叫 PyLongObject 的结构体。然而它只是一个马甲,是 _longobject的别名。在longintrepr.h中找到了 _longobject 的定义如下:

在文件的开头就看到了typedef uint32_t digit;digit就是unit32_t, 每个元素占4个字节。但PyObject_VAR_HEAD又是什么鬼?在object.h中发现了它是个宏,上面的注释倒是挺有意思的。

等一下,PyVarObject又是什么?还好定义就在下面。

又一层嵌套,是不是已经晕了,继续查看PyObject的定义,这次反而在上面了。

有完没完啊?_PyObject_HEAD_EXTRA又是什么?看了一下发现它只在debug build中有定义,这里就不展开了。Py_ssize_t等于ssize_t如果有定义的话, ssize_t在64位的机器上就是long_typeobject又是什么?感觉应该非常大,不然就不会用指针了。不过话说回来,既然用了指针,我又何必去关心它是什么呢?反正就是8个字节而已,指向一个内存地址。至此真相大了一个白,如果我们把structs flatten, PyLongObject 定义如下:

ob_refcnt引用计数 8个字节,ob_type类型信息 8个字节(指针),ob_size变长部分元素的个数,8个字节。ob_digit变长的数据部分,字节数为4*abs(ob_size),ob_size可以为0,所以最少8+8+8=24字节,每次增量都是4 (unsigned int) 的倍数。这和我们之前观察到的实验结果吻合。

以上都是基于64位的Python,对于32位的版本,定义如下:

32位就要比64位小很多了,最少12个字节,增量为2个字节。

好了,今天就写到这里。相信你对整型数或者Python有了一个新的认识。下面一篇我们会将会介绍整型数在Python中的表示和计算。

花花酱 LeetCode 895. Maximum Frequency Stack

Problem

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

  • push(int x), which pushes an integer x onto the stack.
  • pop(), which removes and returns the most frequent element in the stack.
    • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Example 1:

Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

  • Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
  • It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
  • The total number of FreqStack.push calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

 

Solution 1: Buckets

We have n  stacks. The i-th stack has the of elements with freq i when pushed.

We keep tracking the freq of each element.

push(x): stacks[++freq(x)].push(x)  # inc x’s freq and push it onto freq-th stack

pop(): x = stacks[max_freq].pop(), –freq(x); # pop element x from the max_freq stack and dec it’s freq.

Time complexity: O(1) push / pop

Space complexity: O(n)

C++

Solution2: Priority Queue

Use a max heap with key: (freq, seq), the max freq and closest to the top of stack element will be extracted first.

Time complexity: O(logn)

Space complexity: O(n)

C++

Related Problems

花花酱 LeetCode 872. Implement Rand10() Using Rand7()

Problem

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

  1. rand7 is predefined.
  2. Each testcase has one argument: n, the number of times that rand10 is called.

Solution: Math

Time complexity: O(49/40) = O(1)

Time complexity: O(7/6 + 7 / 5) = O(1)