hirola 0.3.0

选择最大大小

与Python的set和dict不同，Hirola默认情况下不会自动管理其大小（尽管它可以重新配置）。为了防止浪费性的大小调整（这是Python在底层所做的），您可以完全控制并负责表使用多少空间。显然，表的大小必须足够大，以容纳其中的所有键。此外，当哈希表接近满载时，它会变得非常慢。根据您对速度和内存的重视程度，您应该添加20-50%的额外空间。如果您打算查找大量相同的小值集，则如果将最大值增加到最小值的2-3倍，它可以继续运行得更快。

结构化键数据类型

要表示数组轴应被视为单个键，请使用NumPy的结构化dtype。在以下示例中，数据类型(points.dtype, 3)表示一个三维点（三个浮点数的组合）应被视为一个对象。有关指定dtypes的更多信息，请参阅help(HashTable.dtype)。只有最后一个轴或最后几个轴可以被视为单个键。对于其他设置，请首先使用numpy.transpose()进行转换。

import numpy as np
from hirola import HashTable

# Create a cloud of 3D points with duplicates. This is 3000 points in total,
# with up to 1000 unique points.
points = np.random.uniform(-30, 30, (1000, 3))[np.random.choice(1000, 3000)]

# Create an empty hash table.
# In practice, you generally don't know how many unique elements there are
# so we'll pretend we don't either an assume the worst case of all 3000 are
# unique. We'll also give 25% padding for speed.
table = HashTable(len(points) * 1.25, (points.dtype, 3))

# Add all points to the table.
ids = table.add(points)

可以通过table.keys访问无重复内容

>>> table.keys  # <--- These are `points` but with no duplicates.
array([[  3.47736554, -15.17112511,  -9.51454466],
       [ -6.46948046,  23.64504329, -16.25743105],
       [-27.02527253, -16.1967225 , -10.11544157],
       ...,
       [  3.75972597,   1.24130412,  -8.14337206],
       [-13.62256791,  11.76551455, -13.31312988],
       [  0.19851678,   4.06221179, -22.69006592]])
>>> table.keys.shape
(954, 3)

table.add()返回每个点在table.keys中的位置，类似于numpy.unique(..., return_args=True)。

>>> ids  # <--- These are the indices in `table.keys` of each point in `points`.
array([  0,   1,   2, ..., 290, 242, 669])
>>> np.array_equal(table.keys[ids], points)
True

使用table.get()查找点索引，而无需添加它们。

处理几乎满的哈希表

当HashTable几乎满载时，它会变得非常慢。从v0.3.0版本开始，如果表超出90%的容量，将发出效率警告。此警告可以被重新配置为错误、静音或自动调整表大小以腾出空间。以下示例构造函数演示了这些方法

# The default: Issue a warning when the table is 90% full.
HashTable(..., almost_full=(0.9, "warn"))

# Disable all "almost full" behaviours.
HashTable(..., almost_full=None)

# To consider a table exceeding 80% full as an error use:
HashTable(..., almost_full=(0.8, "raise"))

# To automatically triple in size whenever the table exceeds 80% full use:
HashTable(..., almost_full=(0.8, 3.0))

调整表的大小很慢，这就是为什么默认情况下不启用它。除非您真的不知道表需要多大，否则应避免调整大小。

将HashTable用作dict

字典需要一个用于值的第二个数组。应该将HashTable.add()和HashTable.get()的输出用作values的索引。

import numpy as np
from hirola import HashTable

# The `keys` - will be populated with names of African countries.
countries = HashTable(40, (str, 20))
# The `values` - will be populated with the names of each country's capital city.
capitals = np.empty(countries.max, (str, 20))

使用模式values[table.add(key)] = value添加或设置项。

capitals[countries.add("Algeria")] = "Al Jaza'ir"

或批量操作

new_keys = ["Angola", "Botswana", "Burkina Faso"]
new_values = ["Luanda", "Gaborone", "Ouagadougou"]
capitals[countries.add(new_keys)] = new_values

与Python字典一样，覆盖值与写入值完全相同。

使用values[table[key]]检索值。

>>> capitals[countries["Botswana"]]
'Gaborone'
>>> capitals[countries["Botswana", "Algeria"]]
array(['Gaborone', "Al Jaza'ir"], dtype='<U20')

使用table.keys和values[:len(table)]查看所有键和值。由于HashTable会记住键首次添加的顺序，因此这个字典自动是排序字典。

# keys
>>> countries.keys
array(['Algeria', 'Angola', 'Botswana', 'Burkina Faso'], dtype='<U20')
# values
>>> capitals[:len(countries)]
array(["Al Jaza'ir", 'Luanda', 'Gaborone', 'Ouagadougou'], dtype='<U20')

根据使用场景，可能需要或不需要dict.items()的等效功能。如果您需要等效功能，请使用numpy.rec.fromarrays([table.keys, values[:len(table)]])，可能还需要添加一个names=选项。

>>> np.rec.fromarrays([countries.keys, capitals[:len(countries)]],
...                   names="countries,capitals")
rec.array([('Algeria', "Al Jaza'ir"), ('Angola', 'Luanda'),
           ('Botswana', 'Gaborone'), ('Burkina Faso', 'Ouagadougou')],
          dtype=[('countries', '<U20'), ('capitals', '<U20')])

如果键和值具有相同的dtype，则numpy.c_也适用。

>>> np.c_[countries.keys, capitals[:len(countries)]]
array([['Algeria', "Al Jaza'ir"],
       ['Angola', 'Luanda'],
       ['Botswana', 'Gaborone'],
       ['Burkina Faso', 'Ouagadougou']], dtype='<U20')

将HashTable用作set

要从HashTable中获得类似于集合的功能，利用contains()方法。在这些示例中，我们将尝试3和7的整数倍。

import numpy as np

of_3s = np.arange(0, 100, 3)
of_7s = np.arange(0, 100, 7)

我们只需要将一个数组转换为散列表。另一个可以保持为数组。如果两者都是散列表，只需使用一个表的keys属性作为数组即可。

from hirola import HashTable

table_of_3s = HashTable(len(of_3s) * 1.25, of_3s.dtype)
table_of_3s.add(of_3s)

使用table.contains()作为in的矢量化版本。

>>> table_of_3s.contains(of_7s)
array([ True, False, False,  True, False, False,  True, False, False,
        True, False, False,  True, False, False])

从上面的例子中，可以使用以下方法推导出常见的集合操作

• set.intersection() - 数组和集合中的值

>>> of_7s[table_of_3s.contains(of_7s)]
array([ 0, 21, 42, 63, 84])

• 集合减法 - 数组中不在集合中的值

>>> of_7s[~table_of_3s.contains(of_7s)]
array([ 7, 14, 28, 35, 49, 56, 70, 77, 91, 98])

• set.union() - 表或测试数组中的值（无重复）

>>> np.concatenate([table_of_3s.keys, of_7s[~table_of_3s.contains(of_7s)]], axis=0)
array([ 0,  3,  6,  9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48,
       51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99,
        7, 14, 28, 35, 49, 56, 70, 77, 91, 98])

将HashTable用作collections.Counter

对于这个例子，让我们做一些更实质性的工作。统计莎士比亚的《哈姆雷特》剧本中的单词频率是collections.Counter的流行例子，我们也将使用它。

from urllib.request import urlopen
import re
import numpy as np

hamlet = urlopen("https://gist.githubusercontent.com/provpup/2fc41686eab7400b796b/raw/b575bd01a58494dfddc1d6429ef0167e709abf9b/hamlet.txt").read()
words = np.array(re.findall(rb"([\w']+)", hamlet))

计数器只是一个具有整数值的字典，而字典只是一个具有单独值数组的散列表。

from hirola import HashTable

word_table = HashTable(len(words), words.dtype)
counts = np.zeros(word_table.max, dtype=int)

在将散列表用作字典中未定义的唯一新功能是计数键作为它们添加的能力。要计数新元素，请使用相当奇怪的行np.add(counts, table.add(keys), 1)。

np.add.at(counts, word_table.add(words), 1)

该行执行您可能期望的counts[word_table.add(words)] += 1操作，但由于NumPy的工作方式，如果words包含重复项，则后者形式无法将每个计数增加超过一次。

使用NumPy的间接排序函数获取最常或最不常用的键。

# Get the most common word.
>>> word_table.keys[counts[:len(word_table)].argmax()]
b'the'

# Get the top 10 most common words. Note that these are unsorted.
>>> word_table.keys[counts[:len(word_table)].argpartition(-10)[-10:]]
array([b'it', b'and', b'my', b'of', b'in', b'a', b'to', b'the', b'I',
       b'you'], dtype='|S14')

# Get all words in ascending order of commonness.
>>> word_table.keys[counts[:len(word_table)].argsort()]
array([b'END', b'whereat', b"griev'd", ..., b'to', b'and', b'the'],
      dtype='|S14')