develop

Python code for the sequence partition problem (using NumPy)

Imagine we have an array of numbers [9, 8, 7, 1, 2, 3, 4, 5, 6]. What’s the best solution to split it into 3 partitions with the most “average sum”, which means they have minimum differences for their sums. (Remember that we can’t change the order of this array)

For example, we can split this array into three partitions like this [9, 8, 7] [1, 2, 3, 4] [5, 6]. Then the sums of the three partitions are 24, 10, 11. This solution is not the best since the sums have big differences.

The algorithm and source code for this problem is in the book “The Algorithm Design Manual“. And below is the python code of my implementation:

# Find the most average way for partitions
import numpy as np
def maximum_partition(sequence, M, nr_partitions, sum_array):
    for n in range(2, len(sequence) + 1):
        for k in range(2, nr_partitions + 1):
            array = []
            for i in range(1, n + 1):
                select = max(M[i][k - 1], sum_array[n - 1] - sum_array[i - 1])
                array.append(select)
            M[n][k] = min(array)
    return M[len(sequence)][nr_partitions]
def init_matrix(sequence, nr_partitions, M, sum_array):
    for index in range(len(sequence)):
        sum_array.append(sum(sequence[: index + 1]))
    for k in range(1, nr_partitions + 1):
        M[1][k] = sequence[0]
    for n in range(1, len(sequence) + 1):
        M[n][1] = sum(sequence[:n])
if __name__ == "__main__":
    # The sequence and the number of partitions
    sequence = [9, 8, 7, 1, 2, 3, 4, 5, 6]
    partitions = 3
    # init
    M = np.zeros((len(sequence) + 1, partitions + 1), dtype=int)
    sum_array = []
    init_matrix(sequence, partitions, M, sum_array)
    # call the main function
    range_sum_max = maximum_partition(sequence, M, partitions, sum_array)
    print("Sum of the maximum range:", range_sum_max)
    # split the sequence by using maximum sum of one range
    current_sum = 0
    for index in range(len(sequence)):
        if (current_sum + sequence[index]) > range_sum_max:
            print("| ", end="")
            current_sum = 0
        current_sum += sequence[index]
        print(sequence[index], end=" ")
    print("\r")

The code is unbelievable simple (just less than 50 lines). And this is the power and charm of dynamic programming.

Python code for the n-queens problem (using NumPy)

I am reading the second edition of “The Algorithm Design Manual” recently. Reaching the chapter about backtracking, I realized that this method could solve many problems, even complicated problems, quickly and efficiently. Therefore I plan to write a solution to the n-queens problem by using backtracking.

Here is my Python code (Github):

# Using backtracking to resolve n-queues problem
import numpy as np
max_columns = 8
max_rows = max_columns
def print_chess(problem):
    head = "_" * (len(problem) + 2)
    tail = "-" * (len(problem) + 2)
    print(head)
    for row in problem:
        row_str = "|"
        for item in row:
            row_str += str(item)
        row_str += "|"
        print(row_str)
    print(tail + "\n")
def remove_diagonal(problem, occupied_coordinate, max_cols, candidates):
    row, col = occupied_coordinate
    step = max_cols - col - 1
    # remove right-down
    if (row + step) < len(problem) and (row + step) in candidates:
        candidates.remove(row + step)
    # remove right-up
    if (row - step) >= 0 and (row - step) in candidates:
        candidates.remove(row - step)
def construct_candidates(problem, k) -> int:
    if k <= 0:  # for first column
        return [0]  # return 'first row' if it is a 1x1 chess
    else:
        # find empty rows
        candidates = set(range(len(problem)))
        for col in range(k):
            for row in range(max_rows):
                if problem[row][col] > 0:
                    # remove queens in the same row or same column
                    if row in candidates:
                        candidates.remove(row)
                    # remove queens in the same diagonal
                    remove_diagonal(problem, (row, col), k, candidates)
        return list(candidates)
# check all rows to make sure they all have queues ('1')
def is_solution(problem, k):
    result = True
    for index in range(min(k, len(problem))):
        if sum(problem[index]) <= 0:
            result = False
    return result
def construct_solution(problem, candidate, k):
    new_problem = problem.copy()
    new_problem[candidate][k - 1] = 1
    return new_problem
def solve(problem, k):
    if is_solution(problem, k):
        print_chess(problem)
        return 1
    else:
        count = 0
        candidates = construct_candidates(problem, k)
        for candidate in candidates:
            new_problem = construct_solution(problem, candidate, k)
            count += solve(new_problem, k + 1)
        return count
if __name__ == "__main__":
    # try to resolve a max_rows x max_columns chess matrix
    initial_problem = np.zeros((max_rows, max_columns), dtype=int)
    count = solve(initial_problem, 1)
    print("Number of solutions: ", count)

I use NumPy for operations of the “chessboard” (matrix) as it’s extremely efficient.

The previous time I wrote code for the n-queens problem was in 2001, which was 20 years ago. The data centre of my school just gave us some old Intel 486 machines for practice, since we were not students of the computer science department (they keep the newest machines for their own students). The eight-queues problem cost about a half-hour to run at that time. But now it will only cost half a second on my laptop:

See how Moore’s law works in the recent 20 years.

Encrypt and decrypt a string in shell

When using a container in Kubernetes, I prefer to use a shell command to complete the task instead of writing a python script since the shell commands are usually much simpler and intuitive.

If I want to encrypt a string “helloworld”, it could be accomplished by:

echo helloworld | openssl aes-256-cbc -a -salt -pbkdf2 -pass pass:mypassword

The ‘mypassword’ is the real password for encryption.

To decrypt, I could just use

echo U2FsdGVkX1+SWVzJK6Ji7DJ77r/U9XxyxNqDXrxZ6ck= | openssl aes-256-cbc -d -a -pbkdf2 -pass pass:mypassword

Kubeflow deployment: part 2

Instead of using other strange components of Kubeflow, we can just use Kubeflow Pipelines which is much easier to be deployed and used.

After deployment (less than 20 minutes), I test my first example and it succeeded:

import kfp
from kfp.components import func_to_container_op, InputPath, OutputPath
@func_to_container_op
def do_something(output_csv: OutputPath(str)):
    with open(output_csv, "w") as writer:
        writer.write("name,score\n")
        writer.write("hello,100\n")
        writer.write("world,50\n")
@func_to_container_op
def show_something(input_csv: InputPath()):
    with open(input_csv, "r") as reader:
        for line in reader:
            print(line)
def do_and_show_something():
    csv_data = do_something()
    csv_data.set_memory_limit("1G")
    csv_data.set_cpu_limit("0.5")
    show_op = show_something(csv_data.output)
    show_op.set_memory_limit("1G")
    show_op.set_cpu_limit("0.5")
if __name__ == "__main__":
    kfp.compiler.Compiler().compile(do_and_show_something, __file__ + ".yaml")

To limit the resource (CPU/Memory), we only need to call the function of the op (Operation).

Then python3 xxx.py to convert the python script file to YAML, and upload the YAML file to Kubeflow Pipelines.

That is how easy to use just Pipeline component of Kubeflow!

Some tips in groovy of Jenkins

Groovy could be used as the configuration file for Jenkins workflow. Although I totally don’t make head or tail of Groovy, its syntax is not hard to learn.

How to iterate a list

To export a bunch of tables to CSV format, we could use

[
  "table1",
  "table2",
  "table3",
].each {
  table_name ->
  sh "export ${table_name} to ${table_name}.csv"
}

Get the output of the shell

We could run shell commands in the Groovy file and then get its output.

all_files = sh (
    script: 'ls -lh',
    returnStdout: true
).trim()
echo "All files: ${all_files}"

How to paste in Vim

After I have written the SQL on BigQuery’s UI:

SELECT
  first_column
FROM
  `project.dataset.table`
ORDER BY
  `first_column` ASC
LIMIT
  1000

I tried to copy it to my Vim editor through “Ctrl + c” and “Ctrl + v”. But the result in my Vim looks like irregular steps

SELECT
  *
  FROM
    `project.dataset.table`
    ORDER BY
      `first_column` ASC
      LIMIT
        1000

Even using “Shift + Option + Command + v” to paste code without format couldn’t solve this problem.

Actually, it’s not a problem about system pasting, but about Vim. The correct way is to set Vim to accept “paste” at first

:set paste

then we can get the pasting content correctly.

The “real size” of hex file for AVR microcontroller

Recently I dug out my USBasp tool and a few AVR microcontrollers, for enjoying programming the C language again. Unexpectedly, the old ATTINY2313V and ATmega88V couldn’t work with my USBasp tool (maybe they have already been fused with an external crystal but I don’t have one at hand). The only two pieces that could work are ATmega16A and ATmega16L. At least I could still have some fun with it.

My waterfall-light built from ATmega16A

The code for playing the ATmega16A is at https://github.com/RobinDong/atmega16a.

Later when glancing over the documents of Atmel’s new ATTINY series, I found out that the ATTINY13A only have 1KB space to store program. My example of waterfall light was compiled out to a 2KB hex file. Does that mean I couldn’t put my program into the ATTINY13A? How could I get the real occupation size of flash for the hex file?

Here is one solution by using avr-size

$ avr-size main.hex
   text	   data	    bss	    dec	    hex	filename
      0	    756	      0	    756	    2f4	main.hex

Only 756 bytes (text + data) will be used in flash, so the ATTINY13A should be okay.

Another command for this is more human-readable

$ avr-size --format=avr --mcu=atmega16 main.elf
AVR Memory Usage
----------------
Device: atmega16
Program:     756 bytes (4.6% Full)
(.text + .data + .bootloader)
Data:          6 bytes (0.6% Full)
(.data + .bss + .noinit)

Now, what should I do if I want to reduce the size of the binary file compiled from my code? Here is the guide from Atmel.

First, I change the type of the variable “mode” from “unsigned int” to “unsigned char”, this leads the binary file to 726 bytes. Then change all inner functions to “static” (I guess this removed some unused symbol for external linking), reduce the binary size to 668 bytes.

—— 2021.07.13 ——

Furthermore, when I use “-mrelax” option in gcc-avr for linker relaxation, the binary size shrink to 656 bytes.

Be careful with random generate number

This is the program I have used for a month:

import numpy as np
np.random.seed(202105)
rand = np.random.rand()
# business logic code using 'rand'

Then I add another np.random.rand() in the head of the code, and this time the output data of this code became quite different.

The reason is simple: the “rand” always generates 0.9 in the previous execution, but since it becomes the second rand() call instead of the first one, it generates 0.06 (unfortunately). The 0.06 is far less than 0.9 so the output data is totally different.

I think the solution is also simple: don’t make your program too dependent on the random number, or just keep your generated number under a range (like 0.6~0.9 in my case).

Trace memory error of CUDA program

The program which used CUDA for computing in GPU reported error about memory:

terminate called after throwing an instance of 'std::runtime_error'
  what():  [CUDA] an illegal memory access was encountered LightGBM/src/treelearner/cuda_tree_learner.cpp 239

For common C++ program, we use gdb for debugging. For CUDA program, we should use cuda-gdb. Make sure to compile CUDA code with -g flag and then run:

/usr/local/cuda-11.0/bin/cuda-gdb python3
(cuda-gdb) run test.py

After a while, we could see the exact memory corrupt position of the code:

CUDA Exception: Warp Illegal Address
The exception was triggered at PC 0x1668b2f0 (histogram_16_64_256.cu:182)
Thread 1 "python3" received signal CUDA_EXCEPTION_14, Warp Illegal Address.
[Switching focus to CUDA kernel 0, grid 10, block (2163,0,0), thread (0,0,0), device 0, sm 0, warp 3, lane 0]
0x000000001668b380 in LightGBM::histogram16<<<(7360,1,1),(16,1,1)>>> () at LightGBM/src/treelearner/kernels/histogram_16_64_256.cu:185
185            feature = (feature >> ((ind & 1) << 2)) & 0xf;

Migrate Spark job to BigQuery

I have just finished a work about migrating Spark job to BigQuery, or more precisely: migrate Python code to SQL. It’s a tedious work but improve the performance significantly: from 4 hours runtime of PySpark to half an hour on BigQuery (Honors belongs to the BigQuery!).

There are a few notes for the migration, or just SQL skills:

To create or overwrite a temporary table:

CREATE OR REPLACE TEMP TABLE `my_temp_tbl` AS ...

2. Select all columns from a table except some special ones:

SELECT * EXCEPT(year, month, day) FROM ...

3. To do pivot() on BigQuery: https://hoffa.medium.com/easy-pivot-in-bigquery-one-step-5a1f13c6c710. The key is clause EXECUTE IMMEDIATE which works like eval() in Python: take string as input and run it as SQL snippet.

4. Using clause OFFSET with LIMIT is terribly slow when the table is very big. The best solution for me is that use “bq extract” to export data to GCS as parquet files, and then get each part of these files by a program.

5. The parquet files could use column names that contain a hyphen, like “last-year”, “real-name”. But the BigQuery only support columns with underline, like “last_year”, “real_name”. So the “bq load” will automatically transfer column name “last-year” in the parquet file to “last_year” in the table of BigQuery.