Можно ли ускорить реализацию моего набора? ⇐ Python

[Anonymous]

Я пытаюсь создать быструю и эффективную реализацию набора для 64-битных беззнаковых целых чисел. Я не хочу использовать set(), поскольку он преобразует все в целые числа Python, которые занимают гораздо больше места, чем 8 байтов на целое число. Вот мои усилия:

Код: Выделить всё

import numpy as np
from numba import njit

class HashSet:
def __init__(self, capacity=1024):
self.capacity = capacity
self.size = 0
self.EMPTY = np.uint64(0xFFFFFFFFFFFFFFFF)  # 2^64 - 1
self.DELETED = np.uint64(0xFFFFFFFFFFFFFFFE)  # 2^64 - 2
self.table = np.full(capacity, self.EMPTY)  # Initialize with a special value indicating empty

def insert(self, key):
if self.size >= self.capacity:
raise RuntimeError("Hash table is full")
if not self._insert(self.table, key, self.capacity, self.EMPTY, self.DELETED, self._hash):
print(f"Key already exists: {key}")
else:
self.size += 1

def contains(self, key):
return self._contains(self.table, key, self.capacity, self.EMPTY, self.DELETED, self._hash)

def remove(self, key):
if self._remove(self.table, key, self.capacity, self.EMPTY, self.DELETED, self._hash):
self.size -= 1

def __len__(self):
return self.size

@staticmethod
@njit
def _hash(key, capacity):
return key % capacity

@staticmethod
@njit
def _insert(table, key, capacity, EMPTY, DELETED, hash_func):
index = hash_func(key, capacity)
while table[index] != EMPTY and table[index] != DELETED and table[index] != key:
index = (index + 1) % capacity

if table[index] == key:
return False  # Key already exists

table[index] = key
return True

@staticmethod
@njit
def _contains(table, key, capacity, EMPTY, DELETED, hash_func):
index = hash_func(key, capacity)
while table[index] != EMPTY:
if table[index] == key:
return True
index = (index + 1) % capacity
return False

@staticmethod
@njit
def _remove(table, key, capacity, EMPTY, DELETED, hash_func):
index = hash_func(key, capacity)
while table[index] != EMPTY:
if table[index] == key:
table[index] = DELETED
return True
index = (index + 1) % capacity
return False

Я использую цифру везде, где могу, чтобы ускорить процесс, но это все равно не очень быстро. Например:

Код: Выделить всё

hash_set = HashSet(capacity=204800)
keys = np.random.randint(0, 2**64, size=100000, dtype=np.uint64)
def insert_and_remove(hash_set, key):
hash_set.insert(np.uint64(key))
hash_set.remove(key)
%timeit insert_and_remove(hash_set, keys[0])

Это дает:

Код: Выделить всё

16.9 μs ± 407 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

Основная причина — это код, который, я думаю, мне не удалось обернуть с помощью numba.
Как это можно ускорить?

Подробнее здесь: https://stackoverflow.com/questions/792 ... ementation