Time performance of np.random.permutation, np.random.choice

I encountered a function with very poor time performance relative to comparable MATLAB code in my pure python graph theory library, so I attempted to profile some operations in this function.

I tracked it to the following result

In [27]: timeit.timeit( 'permutation(138)[:4]', setup='from numpy.random import permutation', number=1000000)
Out[27]: 27.659916877746582

Compared this to the performance in MATLAB

>> tic; for i=1:1000000; randperm(138,4); end; toc
Elapsed time is 4.593305 seconds.

I was able to considerably improve performance by changing this to np.random.choice instead of np.random.permutation as I had originally wrote.

In [42]: timeit.timeit( 'choice(138, 4)', setup='from numpy.random import choice', number=1000000)
Out[42]: 18.9618501663208

But it still doesn't nearly approach the matlab performance.

Is there another way of obtaining this behavior in pure python with time performance approaching the MATLAB time performance?