Shulou(Shulou.com)06/03 Report--

This article mainly introduces "how to use an integer to represent a list". In daily operation, I believe many people have doubts about how to use an integer to represent a list. Xiaobian consulted all kinds of materials and sorted out simple and easy operation methods. I hope to help you answer the doubts of "how to use an integer to represent a list"! Next, please follow the small series to learn together!

summary

Unlike C, Rust, and Go, Python's default int has an arbitrary size. [Note 1],[Note 2]

This means that an integer can store an infinite number of values as long as there is enough memory.

For example, you can open Python 3 and run the following command:

>>> import math

>>> math.factorial(2020)

[number omitted] # Python cat Note: This is the factorial of 2020, the result is a long string of numbers, so omitted

>>> math.log2(math.factorial(2020))

19272.453841606068

>>> type(math.factorial(2020))

That is, in Python, the commonly used int can easily hold a C-style fixed-size unsigned int that takes up 19273 bits. In a language like Python, convenience trumps speed and memory efficiency, which is really useful.

This infinite precision also means that we can store any amount of information in a single int. An entire book, an entire database, or even anything can be stored in a single Python int, provided it is coded correctly.

(Python cat note: this article, in-depth analysis of Python integer does not overflow the implementation principle, can be read in association)

Thus, we can imagine a Python dialect that has only integers and requires int to represent all other types (dictionary, list, etc.). We also have special functions and methods that can treat int as a list, dict, and so on.

This will be a fun and entertaining exercise, and that's what this article is about.

There is an obvious way to do this: all data structures are just bit-arrays in memory. In the worst case, it is a set of related bit arrays (e.g., like each node in a linked list or tree), and their collection is just a bit array. Bit arrays can be interpreted as binary numbers. So we can certainly do that. But it's kind of boring.

In this post and subsequent posts in this series, I'll show you some ways to represent complex data structures with int. They are not necessarily the most compact, rational, or efficient; the common goal is to find interesting representations of these data structures. [Note 3]

Introduction to Gödel Numbering

The first data structure we want to represent is a list. We will use Gödel numbers named after the logician Kurt Gödel. For convenience, we deal only with lists of unsigned integers (i.e., natural numbers).

The principle of Gödel numbers is that every natural number greater than 1 is represented by a unique prime decomposition. It is based on the fundamental theorem of arithmetic.

(Python cat note: prime factorization, also translated as prime factorization, prime factorization, etc., refers to writing each number in the form of prime multiplication)

Here are some examples:

A number can be uniquely identified by a list of exponents of its prime factors (up to its highest non-zero exponent). So we can use 126 to represent the list [1, 2, 0, 1]. The first number in the list is the exponent of 2 when 126 is factored into primes, the second number is the exponent of 3, and so on.

A few more examples:

What if there is a zero at the end of the list? Well, based on the code, that's not going to happen.

In our prime factorization, there can be an infinite number of prime numbers with exponent 0, so we need to stop somewhere. [Note 4] We chose to stop at the last non-zero exponent.

This representation also uses very large numbers when the list contains large numbers. That's because the numbers in the list represent exponents, so the size of int grows exponentially with them. For example,[50, 1000, 250] needs to be represented by a number of 2266 bits.

On the other hand, long lists containing a very large number of small integers, especially large sparse lists (i.e., most of the values are zero), have a very compact representation compared to other int-encoded lists.

Mind you, encoding list as int is not a good programming practice, just a fun experiment.

Python implementation

Let's look at Python's implementation. Here are a few caveats:

We will use the function with yield because it simplifies the operation greatly. [Note 5]

You'll see a lot of while loops. This is because list generatives, ranges, and most of the things you intend to use in a for loop are forbidden in int-only dialects. All of these are replaced by while loops.

prime number generator

The first function we'll write is an iterator that will generate primes sequentially. It's critical from start to finish. The implementation here is the simplest possible version.

I'll probably write a full article on algorithms for generating prime numbers soon, because it's a cool topic and an old field of research in itself. The best-known algorithm is the Sieve of Erathosthenes, but this is only the tip of the iceberg. [Note 6]

Here, a very childish realization suffices:

def primes(starting: int = 2):

"""Yield the primes in order.

Args:

starting: sets the minimum number to consider.

Note: `starting` can be used to get all prime numbers

_larger_ than some number. By default it doesn't skip

any candidate primes.

"""

candidate_prime = starting

while True:

candidate_factor = 2

is_prime = True

# We'll try all the numbers between 2 and

# candidate_prime / 2. If any of them divide

# our candidate_prime, then it's not a prime!

while candidate_factor int:

"""Create a new empty list. """

# 1 is the empty list. It isn't divisible by any prime.

return 1 Traversing elements def iter_list(l: int):

"""Yields elements in the list, from first to last. """

# We go through each prime in order. The next value of

# the list is equal to the number of times the list is

# divisible by the prime.

for p in primes():

# We decided we will have no trailing 0s, so when

# the list is 1, it's over.

if l int:

"""Return i-th element of l. """

# First we iterate over all primes until we get to the

# ith prime.

j = 0

for p in primes():

if j == i:

ith_prime = p

break

j += 1

# Now we divide the list by the ith-prime until we

# cant divide it no more.

num_divisions = 0

while l % ith_prime == 0:

num_divisions += 1

l = l // ith_prime

return num_divisions def append(l: int, elem: int) -> int:

# The first step is finding the largest prime factor.

# We look at all primes until l.

# The next prime after the last prime factor is going

# to be the base we need to use to append.

# E.g. if the list if 18 -> 2**1 * 3**2 -> [1, 2]

# then the largest prime factor is 3, and we will

# multiply by the _next_ prime factor to some power to

# append to the list.

last_prime_factor = 1 # Just a placeholder

for p in primes():

if p > l:

break

if l % p == 0:

last_prime_factor = p

# Now get the _next_ prime after the last in the list.

for p in primes(starting=last_prime_factor + 1):

next_prime = p

break

# Now finally we append an item by multiplying the list

# by the next prime to the `elem` power.

return l * next_prime ** elem Try these functions.

You can open a Python, iPython or bPython session and try these functions!

It is recommended that list elements use numbers from 1 to 10. Append and access can take a long time if you use a large number.

To some extent, using Gödel numbers to represent lists is impractical, although the range of available values can be greatly expanded by optimizing prime generation and decomposition algorithms.

In [16]: l = empty_list()

In [17]: l = append(l, 2)

In [18]: l = append(l, 5)

In [19]: list(iter_list(l))

Out[19]: [2, 5]

In [20]: access(l, 0)

Out[20]: 2

In [21]: access(l, 1)

Out[21]: 5

In [22]: l

Out[22]: 972 # Python Cat Note: 2^2*3^5=972 Other int codes

We saw a way to represent lists of natural numbers as int. There are other, more practical methods that rely on subdividing the binary form of numbers into blocks of varying sizes. I am sure you can make such a suggestion.

I may write other articles later on about better algorithms for generating and factoring prime numbers, and int representations of other complex data structures.

At this point, the study of "how to use an integer to represent a list" is over, hoping to solve everyone's doubts. Theory and practice can better match to help everyone learn, go and try it! If you want to continue learning more relevant knowledge, please continue to pay attention to the website, Xiaobian will continue to strive to bring more practical articles for everyone!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.