cocuh's note

type(あうとぷっと) -> 駄文

Cythonで連結リスト(linked list)をつくってみる

Python

CのライブラリのPythonバインディングを書こうと思い、Cythonでやろうと練習を兼ねてlinked listを作ってみました。(Python C APIはつらかったので…)
わりと旬を逃した感はありますが気にせずやっていきます。


調べると実装する方法は2つあるようで、

ということで両方やってみました

やりたいこと


1.Cを使わないでCython上で実装

cythonlinkedlist.pyx
from libc.stdlib cimport malloc # malloc関数をcからimport

ctypedef struct _LinkedListStruct:
    # C上の構造体として宣言(Python側からは見えない)
    int data
    _LinkedListStruct*next

cdef class LinkedList:
    # Python側から見えるclass
    
    cdef _LinkedListStruct*_head
    # Pythonから見えずCythonから見えるcdef

    def __cinit__(self):

        self._head = NULL

    cpdef add(self, int data): # cpdef void add(~~~は不可
        # CからもPythonからも読み込めるcpdef

        # mallocする
        # <_LinkedListStruct*>がないとコンパイルでエラる
        cdef _LinkedListStruct*obj = <_LinkedListStruct*> malloc(sizeof(_LinkedListStruct))
        if not obj:
            raise MemoryError()

        # データを入れる
        obj.data = data
        obj.next = NULL # 初期化を忘れるとセグフォる
        
        # 最後尾探索
        cdef _LinkedListStruct*ptr = self._head # if文ないで宣言出来ない
        if self._head is NULL:
            # 地味に使えるis
            # Noneは使えない
            self._head = obj
            return
        else:
            while ptr.next is not NULL:
                ptr = ptr.next
            ptr.next = obj

    cpdef count(self, int data): # cpdef int count(~~~~は可
        cdef _LinkedListStruct*ptr = self._head
        cdef int c = 0
        while ptr is not NULL:
            if ptr.data == data:
                c += 1
            ptr = ptr.next
        return c
    
    def __iter__(self):
        # こっちはdefを使う
        # 特殊メソッドはdefっぽい…?(自信はない)
        cdef _LinkedListStruct*ptr = self._head
        while ptr is not NULL:
            yield ptr.data
            ptr = ptr.next
            
        # # 次の書き方も通った
        # l = []
        # while ptr is not NULL:
        #     l.append(ptr.data)
        #     ptr = ptr.next
        # return iter(l)

setup.py

CとかでいうMakefileにあたるものになる

from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

setup(
    cmdclass = {'build_ext':build_ext},
    ext_modules = [Extension('cythonlinkedlist', ['cythonlinkedlist.pyx'])]
)
試す
$ python setup.py build_ext -i
   // python setup.py build_ext --inplace でも可
   // Cythonのビルドしてる
running build_ext
cythoning cythonlinkedlist.pyx to cythonlinkedlist.c
build 'pythonlinkedlist' extention
gcc (略)
$ python
Python 3.3.4 (default, Feb 11 2014, 15:56:08) 
[GCC 4.8.2 20140206 (prerelease)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import cythonlinkedlist
>>> ll = cythonlinkedlist.LinkedList()
>>> ll.add(1)
>>> ll.add(2)
>>> ll.add(3)
>>> ll.add(1)
>>> ll.add(2)
>>> ll.add(1)
>>> ll.count(1)
3
>>> ll.count(2)
2
>>> ll.count(3)
1
>>> [x for x in ll]
[1, 2, 3, 1, 2, 1]


(∩´∀｀)∩わーいできた


2.Cで実装しPythonのインターフェイスをCythonでかく

linkedlist.c

タブン一般的な実装方法
【ちゃんと作るときはfreeしましょう】

#include <stdlib.h>
#include <stdio.h>

typedef struct LinkedListStruct{
    int data;
    struct LinkedListStruct *next;
}LinkedListStruct;

LinkedListStruct* add(LinkedListStruct* head, int data)
{
    // 普通にmalloc
    LinkedListStruct *obj = (LinkedListStruct *)malloc(sizeof(LinkedListStruct));
    if(obj == NULL){
        fprintf(stderr,"malloc failed\n");
        exit(1);
    }
    
    // データ格納
    obj->next = NULL;
    obj->data = data;
    
    
    // 最後尾探索
    if(head == NULL){
        return obj;
    }else{
        LinkedListStruct *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = obj;
        return head;
    }
}

int count(LinkedListStruct *ptr, int data)
{
    int c = 0;
    while(ptr != NULL){
        if(ptr->data == data){
            c += 1;
        }
        ptr = ptr->next;
    }
    return c;
}


int main(void){
    // テスト用
    LinkedListStruct*head = NULL;
    
    head = add(head,1);
    head = add(head,2);
    head = add(head,3);
    head = add(head,1);
    head = add(head,2);
    head = add(head,1);
    
    printf("1:%d\n",count(head,1));
    printf("2:%d\n",count(head,2));
    printf("3:%d\n",count(head,3));
    
    printf("\n");
    LinkedListStruct*ptr = head;
    while(ptr != NULL){
        printf("%d, ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

cyrhonlinkedlist.pxd

cでいう.hと同じようなものらしい
これを使わずにpyx上にかいてもできるけれど、名前空間的にごちゃごちゃして読みにくいので個人的に分けてます

cdef extern from "linkedlist.c":
    cdef struct LinkedListStruct:
        int data # pyxで参照しているものを宣言
        LinkedListStruct *next
    int count(LinkedListStruct* head, int data)
    LinkedListStruct* add(LinkedListStruct* head, int data)

cyrhonlinkedlist.pyx
cimport cythonlinkedlist as cll # 地味に使えるas

cdef class LinkedList:
    cdef cll.LinkedListStruct *_head
    
    def __cinit__(self):
        # __init__ではされないことがあるらしい
        # http://docs.cython.org/src/userguide/special_methods.html
        self._head = NULL
    
    cpdef add(self, int data): # cpdef void add(~~~~はだめ
        self._head = cll.add(self._head, data)
        if self._head is NULL:
            raise MemoryError()

    cpdef count(self, int data): # cpdef int count(~~~~でもよいっぽい
        return cll.count(self._head, data)
    
    def __iter__(self):
        # やっぱりこっちの特殊メソッドもdef
        # cpdefにするとエラー
        
        cdef cll.LinkedListStruct*ptr = self._head
        while ptr is not NULL:
            yield ptr.data # CのintからPythonのintに暗黙の型変換
            ptr = ptr.next

setup.py

1番めとおなじ

from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

setup(
    cmdclass = {'build_ext':build_ext},
    ext_modules = [Extension('cythonlinkedlist', ['cythonlinkedlist.pyx'])]
)


Trial【不可算名詞】ためす
$ python setup.py build_ext -i
running build_ext
cythoning cythonlinkedlist.pyx to cythonlinkedlist.c
building 'cythonlinkedlist' extension
gcc -pthread -Wno-unused-result -DDYNAMIC_ANNOTATIONS_ENABLED=1 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -march=x86-64 -mtune=generic -O2 -pipe -fstack-protector --param=ssp-buffer-size=4 -fPIC -I/usr/include/python3.3m -c cythonlinkedlist.c -o build/temp.linux-x86_64-3.3/cythonlinkedlist.o
In file included from cythonlinkedlist.c:343:0:
linkedlist.c: In function ‘main’:
linkedlist.c:71:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
gcc (略)なにかwarningでてるけど通る
$ python
Python 3.3.4 (default, Feb 11 2014, 15:56:08) 
[GCC 4.8.2 20140206 (prerelease)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import cythonlinkedlist
>>> ll = cythonlinkedlist.LinkedList()
>>> ll.add(1)
>>> ll.add(2)
>>> ll.add(3)
>>> ll.add(1)
>>> ll.add(2)
>>> ll.add(1)
>>> ll.count(1)
3
>>> ll.count(2)
2
>>> ll.count(3)
1
>>> [x for x in ll]
[1, 2, 3, 1, 2, 1]
>>>


٩( 'ω' )وよっしゃ


まとめ

意外と癖がありますがCythonいいなとおもいました。
いろいろな書き方ができるのがPythonicじゃない気もするけれどそこはZENを貫く方針で。

(自分の理解ミスじゃなく)挙動がおかしいと思ったことはなかったのでわりとしっかりできているように感じました。
ちょっとデバッグが非常にめんどくさいのとかCの知識がそこそこいることとかあるのでそこが注意要りそうですがPython C API叩くより断然楽です。

pyoggあたりとaudioあたりのPythonのメンテがうごいてなかったりしてるので勉強しつつ自分でwrapしようかなと思ってたり(希望的観測)


めも

gcc -lglutみたいにコンパイル時にライブラリ*1を読み込ませたいときはkwargsにlistで入れてあげるといけるのでメモです。

from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

setup(
    cmdclass = {'build_ext':build_ext},
    ext_modules = [Extension('pyopenal', ['pyopenal.pyx'],
                             libraries=['openal']
                             )]
)
注意書き

この記事はお酒飲んで書いてしまたのでなにか間違いに気づきましたらコメントいただけるとありがたいです。

*1:Cは詳しくないので用語あってる自信ないです