我想创建一个函数,它接受一个字符串并返回0到1之间的数字。该函数应在给定相同字符串时始终返回相同的数字,但除此之外,结果应没有可辨别的模式。任何大量输入字符串的输出数字应遵循均匀分布。
此外,我需要生成多个这样的函数,例如对于字符串“abc”,函数A可能始终返回0.593927,而函数B始终返回0.0162524。我需要它快速(用于数值模拟),并具有合理的统计数据。
我正在使用Python,并将满足以下答案:“这是使用Python库轻松完成的方法”或“这是您可以实现的算法。”如果在Python中没有快速的方法,我会转而使用C语言。
我意识到以下两种方法都可以工作,但它们各自具有缺点,使我希望寻找更优雅的解决方案。
存储字典 我可以每次收到新字符串时计算一个新的随机数,并将其存储在字典中以便再次检索相同的字符串时使用。然而,我的应用程序可能会生成很多仅出现一次的字符串,这最终会导致必须在内存中存储非常大的字典。它还使得重复性更加困难,因为即使我使用相同的种子,如果以不同的顺序接收相同的字符串,我也会生成不同的函数。因此,为了这些原因,更好的方法是在计算随机数时始终保持“即兴表演”。
使用哈希函数 我可以仅对字符串调用哈希函数,然后将结果转换为数字。例如,通过将“种子”字符串附加到每个输入字符串中来解决生成多个函数的问题。但是,那么我将被困在尝试找到具有适当速度和统计数据的哈希函数中。Python内置的哈希很快,但实现依赖于具体实现,而且我不知道统计数据有多好,因为它不是为此类目的而设计的。另一方面,我可以使用诸如md5之类的安全哈希算法,它将具有良好的统计数据,但这对于我的应用程序来说太慢了。针对数据存储应用程序的哈希函数通常比MD5等密码学安全功能要快得多,但它们的设计目的是避免冲突,而不是产生均匀分布的输出,在所有情况下这些目标不一定相同。
哈希函数的进一步说明
为了说明避免冲突和产生均匀结果是不同的事情,请考虑以下示例,其中使用Python内置的哈希函数:
上述输出中没有碰撞,但它们显然不是均匀分布的,因为它们都介于336和351之间,在第三位数字中也有明确的模式。我意识到通过执行(hash("aaa")/HASH_MAX)*1000(假设我可以计算出HASH_MAX的值)可能会得到更好的统计结果,但这应该有助于说明一个好的哈希函数的要求并不同于我所寻找的函数的要求。
关于问题的一些相关信息:
我不知道这个算法将需要处理哪些字符串,因为这些字符串将由模拟程序生成,但以下情况很可能成立:
1. 它们将具有非常受限制的字符集(可能只有4或5个不同的符号)。 2. 有许多唯一或罕见的字符串和少数非常常见的字符串,长度各异。 3. 字符串的长度没有上限,但短字符串很可能比长字符串更常见。我不会惊讶地看到长度超过100个字符的字符串,但我不能确定。其中许多只有一个到三个字符,因此对于短字符串来说,算法快速运行很重要。(但我想我可以为小于某个长度的字符串使用查找表。) 4. 通常,字符串将具有共同的大子字符串——通常两个字符串仅在开头或结尾附加一个单个字符。重要的是,当字符串相似时,算法不倾向于产生类似的输出值。
此外,我需要生成多个这样的函数,例如对于字符串“abc”,函数A可能始终返回0.593927,而函数B始终返回0.0162524。我需要它快速(用于数值模拟),并具有合理的统计数据。
我正在使用Python,并将满足以下答案:“这是使用Python库轻松完成的方法”或“这是您可以实现的算法。”如果在Python中没有快速的方法,我会转而使用C语言。
我意识到以下两种方法都可以工作,但它们各自具有缺点,使我希望寻找更优雅的解决方案。
存储字典 我可以每次收到新字符串时计算一个新的随机数,并将其存储在字典中以便再次检索相同的字符串时使用。然而,我的应用程序可能会生成很多仅出现一次的字符串,这最终会导致必须在内存中存储非常大的字典。它还使得重复性更加困难,因为即使我使用相同的种子,如果以不同的顺序接收相同的字符串,我也会生成不同的函数。因此,为了这些原因,更好的方法是在计算随机数时始终保持“即兴表演”。
使用哈希函数 我可以仅对字符串调用哈希函数,然后将结果转换为数字。例如,通过将“种子”字符串附加到每个输入字符串中来解决生成多个函数的问题。但是,那么我将被困在尝试找到具有适当速度和统计数据的哈希函数中。Python内置的哈希很快,但实现依赖于具体实现,而且我不知道统计数据有多好,因为它不是为此类目的而设计的。另一方面,我可以使用诸如md5之类的安全哈希算法,它将具有良好的统计数据,但这对于我的应用程序来说太慢了。针对数据存储应用程序的哈希函数通常比MD5等密码学安全功能要快得多,但它们的设计目的是避免冲突,而不是产生均匀分布的输出,在所有情况下这些目标不一定相同。
哈希函数的进一步说明
为了说明避免冲突和产生均匀结果是不同的事情,请考虑以下示例,其中使用Python内置的哈希函数:
>>> hash("aaa") % 1000
340
>>> hash("aab") % 1000
343
>>> hash("aac") % 1000
342
>>> hash("aad") % 1000
337
>>> hash("aae") % 1000
336
>>> hash("aaf") % 1000
339
>>> hash("aag") % 1000
338
>>> hash("aah") % 1000
349
>>> hash("aai") % 1000
348
>>> hash("aaj") % 1000
351
>>> hash("aak") % 1000
350
上述输出中没有碰撞,但它们显然不是均匀分布的,因为它们都介于336和351之间,在第三位数字中也有明确的模式。我意识到通过执行(hash("aaa")/HASH_MAX)*1000(假设我可以计算出HASH_MAX的值)可能会得到更好的统计结果,但这应该有助于说明一个好的哈希函数的要求并不同于我所寻找的函数的要求。
关于问题的一些相关信息:
我不知道这个算法将需要处理哪些字符串,因为这些字符串将由模拟程序生成,但以下情况很可能成立:
1. 它们将具有非常受限制的字符集(可能只有4或5个不同的符号)。 2. 有许多唯一或罕见的字符串和少数非常常见的字符串,长度各异。 3. 字符串的长度没有上限,但短字符串很可能比长字符串更常见。我不会惊讶地看到长度超过100个字符的字符串,但我不能确定。其中许多只有一个到三个字符,因此对于短字符串来说,算法快速运行很重要。(但我想我可以为小于某个长度的字符串使用查找表。) 4. 通常,字符串将具有共同的大子字符串——通常两个字符串仅在开头或结尾附加一个单个字符。重要的是,当字符串相似时,算法不倾向于产生类似的输出值。