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