Re: [Cython] FW: cython and hash tables / dictionary

[Robert Bradshaw]

Thanks for the implementation. I noticed that your compare was only comparing pointers, so if you had two equal strings at different memory addresses it wouldn't find them (which may or may not be what you'd want) Also, your pointers would go out of scope as soon as test ended (so you couldn't return ht and use it later).

- Robert

I built on what you had to get a float -> float hashtable. Note that this technique only works since the float value fits inside a void*, anything bigger and you'd have to allocate memory manually to stick it into the hashtable.

cy_stl.pyx
Description: Binary data

sage: from cy_stl import *
sage: time time_c_hashtable(10**5)
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
sage: time time_c_hashtable(10**6)
CPU times: user 0.08 s, sys: 0.00 s, total: 0.08 s
Wall time: 0.08 s
sage: time time_c_hashtable(10**7)
CPU times: user 0.75 s, sys: 0.00 s, total: 0.75 s
Wall time: 0.75 s
sage: time time_py_hashtable(10**5)
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
sage: time time_py_hashtable(10**6)
CPU times: user 0.18 s, sys: 0.00 s, total: 0.19 s
Wall time: 0.19 s
sage: time time_py_hashtable(10**7)
CPU times: user 2.01 s, sys: 0.01 s, total: 2.02 s
Wall time: 2.02 s

Not near the speed gains I was expecting...disappointing.

- Robert


On Sep 7, 2009, at 12:28 PM, Sebastien Binet wrote:

hi there,



really just to get started :)

to test:
$ python -c 'import cy_stl as cc; cc.test()'

hth,
sebastien.

attached is a simple cy_stl.pyx file (together with its setup.py companion)

cythonHash.pxd:

cdef extern from "hash-table.h":
    ctypedef struct HashTable
    ctypedef void *HashTableKey
    ctypedef unsigned long HashTableHashFunc(HashTableKey value)
    ctypedef unsigned long HashTableEqualFunc(HashTableKey value)
    HashTable *hash_table_new(HashTableHashFunc hash_func,
HashTableEqualFunc equal_func)

cdef inline unsigned long c_hash_func(HashTableKey value):
    return 1

cdef inline unsigned long c_hash_equal(HashTableKey value):
    return 1


cythonPT.pyx:

cimport cythonHash
from cythonHash cimport HashTable

class MY_Phrase_Table(object):

    def __init__(self):

        pp = HashTable          #error here
      print type(pp), pp


or function identifier.


already declared from .pxd and the original .c file.




-----Original Message-----
From: Stefan Behnel [mailto:stefan...@behnel.de]
Sent: vrijdag 4 september 2009 16:03
To: sa...@kortec.nl
Cc: cython-dev@codespeak.net
Subject: Re: [Cython] FW: cython and hash tables / dictionary

Sanne Korzec wrote:

This yields in the following error: 'HashTable' is not a constant, variable I don't really get how I should reference to Hashtable. I thought it was

In the documentation

http://c-algorithms.sourceforge.net/doc/hash- table_8h.html#e361c4c0256ec6c7

4

1ecfeabef33d891 , I can find:

HashTable* hash_table_new       (       HashTableHashFunc       hash_func,
                HashTableEqualFunc      equal_func
        )

To create a new hash table. But I can't find were the HashTableHashFunc

and

HashTableEqualFunc are declared. The only thing I can find is in the

header

file which state:

typedef unsigned long(* HashTableHashFunc)(HashTableKey value)
typedef unsigned long(* HashTableHashFunc)(HashTableKey value)

Does this mean I have to write these functions myself?

Yes.

In c?

You can write them in Cython:

    cdef unsigned long c_hash(HashTableKey value):
        return huge_calculation_on(value)

And how then do I call them from cython?

You don't. Instead, you pass the function names (i.e. pointers) into
hash_table_new().

My guess:

hashtable.pyx

"hashtable.pxd", I assume?

cdef extern from "hash_table.h":

object HashTable hash_table_new(object hash_func, object equal_func)

the functions as a ctypedef.

Stefan


_______________________________________________
Cython-dev mailing list
Cython-dev@codespeak.net
http://codespeak.net/mailman/listinfo/cython-dev

That won't work. You can't use Python functions as their signature won't match the required signatures. Instead, define HashTable as a struct and

--
#########################################
# Dr. Sebastien Binet
# Laboratoire de l'Accelerateur Lineaire
# Universite Paris-Sud XI
# Batiment 200
# 91898 Orsay

Cython-dev mailing list
Cython-dev@codespeak.net
http://codespeak.net/mailman/listinfo/cython-dev

#########################################<cy_stl.pyx><setup.py>_______ ________________________________________

_______________________________________________
Cython-dev mailing list
Cython-dev@codespeak.net
http://codespeak.net/mailman/listinfo/cython-dev