python - programacion - tablas hash en java

La forma más rápida de generar la función hash de k familia de hash independiente inteligente para k pequeña(<= 5)

Question

Necesito una función hash h[n]:[t] de k familia de hash independiente sabia cuando k es pequeño ( <= 5 ). O necesito n valores hash elegidos uniformemente al azar de [1-t] manera que sean k independientes . Estoy tratando de implementar algunos algoritmos aleatorios donde necesité esto. Estaba generando n números aleatorios de rango [1-t] usando

scipy.stats.randint(0,self._t).rvs(self._n)

pero esto parece ser demasiado lento para mi aplicación. Como no necesito la aleatoriedad completa, sino solo la independencia inteligente, me preguntaba si podría acelerar esto. Sé que puedo usar la familia de hash polinomial para obtener una independencia inteligente, pero ¿es este el mejor? Si es así, ¿hay alguna implementación rápida de esto que pueda enchufar? Si no, ¿cuáles son las formas alternativas (bibliotecas, posiblemente en Python)?

He visto este hilo Obtención de una función hash independiente de K-wise, pero no estoy seguro de lo que significa la respuesta aceptada con esto: " si necesita k hash diferente, simplemente reutilice el mismo algoritmo k veces, con k semillas diferentes " .

Cualquier sugerencia es bienvenida. Gracias.

Answer 1

Puedes intentar usar el jit de numba con random.randint() de random.randint() :

import scipy.stats
import numpy as np
from numba import jit

def randint_scipy(n):
    return scipy.stats.randint(0, 10000).rvs(n)

def randint_numpy(n):
    return np.random.randint(0, 10000, n)

@jit
def randint_numpy_jit(n):
    return np.random.randint(0, 10000, n)

%timeit randint_scipy(5)
%timeit randint_numpy(5)
%timeit randint_numpy_jit(5)

Salida:

1.09 ms ± 10.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
4.63 µs ± 149 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
960 ns ± 50.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Por lo tanto, numpy + numba es 1135 veces más rápido que la implementación de randint() de randint() .