Standard container like C+ STL

[yxdragon]

now numba has list and dic, Is there a plan to implement stack, queue, linkedlist, heap... just like C+ STL container?

[esc]

now numba has list and dic, Is there a plan to implement stack, queue, linkedlist, heap... just like C+ STL container?

Currently the only plan is to implement typed.Set but as of yet not selected for implementation, so no ETA.

[yxdragon]

So I will try to implement a simple stl in numba's python level. I will report my progress and the problems encountered here, and I kindly request your assistance.

now numba has list and dic, Is there a plan to implement stack, queue, linkedlist, heap... just like C+ STL container?

Currently the only plan is to implement typed.Set but as of yet not selected for implementation, so no ETA.

[yxdragon]

first of all, I test the typed List container.

from numba import njit, typeof, from_dtype
from numba.typed import List
import numpy as np

t_point = np.dtype([('x', np.float32), ('y', np.float32)])

@njit
def foo(l):
    l.append(np.void((1,0), dtype=t_point))

# not work
lst = List[typeof(t_point)]()

lst = List.empty_list(from_dtype(t_point))
lst.append(np.void((1,0), dtype=t_point)) # works

foo(lst) # not work, it seems that njit not support np.void

1. the official document's demo is for int, and push the first one (to infer the type), then the jit function works.

I want to set the type in init. and I found Listtype not works. But List.empty_list works.

2. I instance a List of numpy struct. t_point = np.dtype([('x', np.float32), ('y', np.float32)]), and use np.void to alloc it. but njit not support np.void. (I know it works for jitclass object, but I think numpy struct is a good choice, for it is simple, and can treat as nparray). So how to insert an np struct in jit function?

[yxdragon]

open a repo: https://github.com/Image-Py/nbstl
now has implemented Stack, Queue, Deque, Heap.

here is a convexhull demo implemented by PointStack:
we can use TypedStack(dtype) to build a TypedStack,
then use push(x, y) and pop() to got an x,y record.

import numpy as np
import numba as nb
import nbstl

# build Point dtype and PointStack
t_point = np.dtype([('x', np.float32), ('y', np.float32)])
PointStack = nbstl.TypedStack(t_point)

# push to stack one by one, if not turn right, pop
@nb.njit
def convex_line(pts, idx):
    hull = PointStack(128)
    for i in idx:
        p2 = pts[i]
        while hull.size>1:
            p1 = hull.top(0)
            p0 = hull.top(1)
            s = p0.x*p1.y - p0.y*p1.x
            s += p1.x*p2.y - p1.y*p2.x
            s += p2.x*p0.y - p2.y*p0.x
            if s<-1e-6: break
            hull.pop()
        hull.push(p2.x, p2.y)
    return hull.body[:hull.size]

# get up line and down line, then concat the hull
@nb.njit
def convexhull(pts):
    idx = np.argsort(pts['x'])
    up = convex_line(pts, idx)
    down = convex_line(pts, idx[::-1])
    return np.concatenate((up, down[1:]))

if __name__ == '__main__':
    from time import time
    # use randn to make 102400 random points
    pts = np.random.randn(102400, 2).astype(np.float32)
    pts = pts.ravel().view(t_point)

    hull = convexhull(pts)
    start = time()
    hull = convexhull(pts)
    print('convex hull of 102400 point cost:', time()-start)

when the points's count is 1024000, it run 5 times faster than shapely!