beethoven97's blog

By beethoven97, history, 2 months ago, In English

I write this blog to talk about arrays in python . As we know python lists is slow and a memory consumption because it can't assign uniform data type unlike other low languages like c and c++ ,you can read more about that in this documentation.

but there is an efficient way to make arrays like c++ ,it's the array module ,I will discuss about it and its powerful differences in terms of time and memory between it and lists.

  1. what is python array ?

python array is an array module implemented in c language unlike lists which is a cpython implementation ,it must determine a datatype like c arrays.

you can import it by the following line :

from array import array

it contains most of c datatypes like 32 bit integer :'i' ,64 bit integer :'q' , double values :'d', chars:'u'. but it doesn't contains string datatype.

  1. How to use it?

it's very similar to python lists in usage and contains most of lists functions like insert , append , count,... but the difference is that you must define array data type first . you can see this for more understanding.

But array doesn't contain sort function but you can do the following for sorting:

from array import array
#'i' means integer 32 bit datatype
a=array('i',sorted([2,3,4,1])) 
  1. examples

Here some codes to show the time and memory consumptions: — dp problem: array vs list

-graph problem 717ms using list vs 514ms using array module

Notice that not only array is faster than list but it's also less than list in terms of memory space, as you can see in the previous dp problem lists uses 77500 KB but array uses 30800 KB which is less than half of lists memory usage.

finally ,I think that array module is really useful in python competitive programming unlike lists.

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by beethoven97 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by beethoven97 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by beethoven97 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by beethoven97 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by beethoven97 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by beethoven97 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks it is really helpful.

»
2 months ago, # |
  Vote: I like it +17 Vote: I do not like it

What I think actually happened here is that you found some kind of bug in PyPy.

The list.count in your code for some reason runs extremely slow. The code using list.count TLEs on tc8 156990689.

If you implement the .count manually then tc8 takes around 200 ms 157280198.