Sunday, July 11, 2021

Build Catalan Sequence via Python Extension to C++

Notice that Python module 

(.env) [boris@fedora33server CATALAN]$ cat mainCatalan.py

def Catl(n):

    if n == 0: return 1

    s = 0

    for i in range(n):

       s += Catl(i)*Catl(n-1-i)

    return s

def main():

    a = 0

    sequence = []

    a = int(input("Input desired number of Catalan sequence : "))

    for i in range(a):

          sequence.append(Catl(i))

    print(sequence)

if __name__ == "__main__":

    main()

 Actually hangs  ( run for ever)  when value of "a" becomes equal 20. Oops. It exits in 4 min 30 seconds 

***************************************************************

Thus as next exercise test Python Extension to C++ building Catalan list in a second up to value 35 of Catalan Sequence number.

****************************************************************

(.env) [boris@fedora33server CATALAN]$ cat catalan.h

#pragma once

#include <vector>

#include <cstddef>

namespace abc

{

std::vector<long> catalanList(int n) ;

}

(.env) [boris@fedora33server CATALAN]$ cat catalanProc.cpp

#include <iostream>

#include "catalan.h" 

#pragma GCC diagnostic ignored "-Wsign-compare"

namespace abc {

long catan(int n)

{

    long catalan[n + 1];

    catalan[0] = catalan[1] = 1;

    for (int i = 2; i <= n; i++) {

        catalan[i] = 0;

        for (int j = 0; j < i; j++)

            catalan[i] += catalan[j] * catalan[i - j - 1];

    }

    return catalan[n];

};

std::vector<long>  catalanList(int m)

{    

       std::vector<long> result;

       int j;

       for(j=0; j <= m; j++)

       {

           result.push_back(catan(j));

       }

     return result;

};

}  // namespace abc

(.env) [boris@fedora33server CATALAN]$ cat catalanSigma.cpp

#include <Python.h>

#include "catalan.h"

#pragma GCC diagnostic ignored "-Wsign-compare"

extern "C"{}

namespace {

static PyObject *catanList(PyObject* self, PyObject* args)

{

    int m;

    if(!PyArg_ParseTuple(args,"i",&m))

        return NULL;

    std::vector<long> sequence  = abc::catalanList(m);

    PyObject* result = PyList_New(sequence.size());

    for(int i = 0; i < sequence.size(); i++) {

        PyList_SetItem(result, i, PyLong_FromLong(sequence[i]));

    }

    return result;

};

// Our Module's Function Definition structure

// We require this `NULL` to signal the end of our method

// definition

static PyMethodDef myMethodsTable[] = {

    { "catanList",catanList, METH_VARARGS, "Tracking CatanList" },

    { NULL, NULL, 0, NULL }

};

// Our Module Definition struct

static struct PyModuleDef myModule = {

    PyModuleDef_HEAD_INIT,

    "myModule",

    "Test Module",

    -1,

    myMethodsTable

};

// Initializes our module using our above struct

PyMODINIT_FUNC PyInit_myModule(void)

{

    return PyModule_Create(&myModule);

};

} //namespace

(.env) [boris@fedora33server CATALAN]$ cat setup.py

from distutils.core import setup, Extension

import sysconfig

language = 'c++'

std = 'c++20'

default_compile_args = sysconfig.get_config_var('CFLAGS').split()

extra_compile_args = [f"-std={std}", "-Wall", "-Wextra", "-Werror", "-DNDEBUG", "-O3"]

setup(name = 'myModule', version = '1.0',  \

   ext_modules = [Extension('myModule', ['catalanSigma.cpp','catalanProc.cpp'])])

(.env) [boris@fedora33server CATALAN]$ python setup.py install

running install

running build

running build_ext

building 'myModule' extension

creating build

creating build/temp.linux-x86_64-3.9

gcc -pthread -Wno-unused-result -Wsign-compare -DDYNAMIC_ANNOTATIONS_ENABLED=1 -DNDEBUG -O2 -fexceptions -g -grecord-gcc-switches -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -Wp,-D_GLIBCXX_ASSERTIONS -fstack-protector-strong -m64 -mtune=generic -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection -D_GNU_SOURCE -fPIC -fwrapv -O2 -fexceptions -g -grecord-gcc-switches -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -Wp,-D_GLIBCXX_ASSERTIONS -fstack-protector-strong -m64 -mtune=generic -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection -D_GNU_SOURCE -fPIC -fwrapv -O2 -fexceptions -g -grecord-gcc-switches -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -Wp,-D_GLIBCXX_ASSERTIONS -fstack-protector-strong -m64 -mtune=generic -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection -D_GNU_SOURCE -fPIC -fwrapv -fPIC -I/home/boris/CATALAN/.env/include -I/usr/include/python3.9 -c catalanProc.cpp -o build/temp.linux-x86_64-3.9/catalanProc.o

gcc -pthread -Wno-unused-result -Wsign-compare -DDYNAMIC_ANNOTATIONS_ENABLED=1 -DNDEBUG -O2 -fexceptions -g -grecord-gcc-switches -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -Wp,-D_GLIBCXX_ASSERTIONS -fstack-protector-strong -m64 -mtune=generic -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection -D_GNU_SOURCE -fPIC -fwrapv -O2 -fexceptions -g -grecord-gcc-switches -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -Wp,-D_GLIBCXX_ASSERTIONS -fstack-protector-strong -m64 -mtune=generic -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection -D_GNU_SOURCE -fPIC -fwrapv -O2 -fexceptions -g -grecord-gcc-switches -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -Wp,-D_GLIBCXX_ASSERTIONS -fstack-protector-strong -m64 -mtune=generic -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection -D_GNU_SOURCE -fPIC -fwrapv -fPIC -I/home/boris/CATALAN/.env/include -I/usr/include/python3.9 -c catalanSigma.cpp -o build/temp.linux-x86_64-3.9/catalanSigma.o

creating build/lib.linux-x86_64-3.9

g++ -pthread -shared -Wl,-z,relro -Wl,--as-needed -Wl,-z,now -g -Wl,-z,relro -Wl,--as-needed -Wl,-z,now -g build/temp.linux-x86_64-3.9/catalanProc.o build/temp.linux-x86_64-3.9/catalanSigma.o -L/usr/lib64 -o build/lib.linux-x86_64-3.9/myModule.cpython-39-x86_64-linux-gnu.so

running install_lib

copying build/lib.linux-x86_64-3.9/myModule.cpython-39-x86_64-linux-gnu.so -> /home/boris/CATALAN/.env/lib64/python3.9/site-packages

running install_egg_info

Removing /home/boris/CATALAN/.env/lib64/python3.9/site-packages/myModule-1.0-py3.9.egg-info

Writing /home/boris/CATALAN/.env/lib64/python3.9/site-packages/myModule-1.0-py3.9.egg-info


(.env) [boris@fedora33server CATALAN]$ cat  MyCatan.py

import myModule

number = int(input("Inpute desired number in Catalan sequence : " ))

print(myModule.catanList(number))

*****************************************************

This particular case addresses exactly the Yandex Q Question

*****************************************************

(.env) [boris@fedora33server CATALAN]$ python MyCatan.py

Inpute desired number in Catalan sequence : 10

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]

(.env) [boris@fedora33server CATALAN]$ python MyCatan.py

Inpute desired number in Catalan sequence : 20

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 

2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420]

(.env) [boris@fedora33server CATALAN]$ python MyCatan.py

Inpute desired number in Catalan sequence : 30

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 

2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 

24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 

18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304]



















No comments:

Post a Comment