问题类型
性能问题
你是否在 TF nightly 中复现了这个 bug?
是的
问题来源
二进制文件
Tensorflow 版本
v2.11.0-rc2-17-gd5b57ca93e5 2.11.0
自定义代码
无
OS 平台和发行版
操作系统平台:Linux-4.19.0-23-cloud-amd64-x86_64-with-debian-10.13 Linux 发行版:('debian', '10.13', '')
移动设备
无响应
Python 版本
Python 版本:3.7.12
Bazel 版本
无响应
GCC/编译器版本
无响应
CUDA/cuDNN 版本
NVIDIA-SMI 460.32.03 Driver Version: 460.32.03 CUDA Version: 11.2
GPU 型号和内存大小
无响应
当前行为?
String/IntegerLookup 层下使用了静态哈希表。我注意到随着词汇表大小的增加,性能会降低,因为我假设它基本上是一个具有 O(1) 查找时间的哈希表,但这不应该是这样。我的时间复杂度假设有误吗?
重现问题的独立代码
test = tf.keras.layers.StringLookup(name=f"{100000}_string_lookup", vocabulary = list(map(str, range(100000))))
%timeit test("23")
>> 75.3 ms ± 430 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
test_100 = tf.keras.layers.StringLookup(name=f"{100}_string_lookup", vocabulary = list(map(str, range(100))))
%timeit test_10("23")
>> 610 µs ± 21.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
testi = tf.keras.layers.IntegerLookup(name=f"{100000}_int_lookup", vocabulary = list(range(100000)))
testi_100 = tf.keras.layers.IntegerLookup(name=f"{100}_string_lookup", vocabulary = list(range(100)))
%timeit testi(23)
%timeit testi_100(23)
>>75.9 ms ± 421 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
>>816 µs ± 21.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
相关日志输出
75.3 ms ± 430 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
610 µs ± 21.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
75.9 ms ± 421 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
816 µs ± 21.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
9条答案
按热度按时间ojsjcaue1#
这本应该是一个性能问题,我认为我已经将其标记为如此。
yi0zb3m42#
$x_{1e0f1}^{x}$
c3frrgcw3#
看起来是针对Keras的
许多Python调用随大小而缩放。
qq24tv8q4#
@sboshin,对于延迟的道歉。我能够在Colab中使用Tensorflow 2.11、2.12和tf-nightly复现这个问题。请查看gist中的相同2.11、2.12和tf-nightly(2.13.0.dev20230418)。
这似乎是一个Keras问题。请在keras-team/keras repo.上发布此问题。
了解更多请查看;
https://discuss.tensorflow.org/t/keras-project-moved-to-new-repository-in-https-github-com-keras-team-keras/1999。谢谢!
nimxete25#
我能够直接通过静态哈希表复现这个问题,所以我认为这不是一个Keras问题。
我会使用静态哈希运算符直接更新Colab。
oipij1gg6#
你好,@sboshin 。
在
vocabulary_size
上增加会导致哈希表变大,最坏情况下时间复杂度可能会增加,对吗?根据 source ,我可以看到最坏情况下的时间复杂度也可以是 O(n)。此外,我们在这里比较了两种不同大小的哈希表的时间复杂度。我认为,通常我们会比较同一表上不同操作的时间复杂度。例如,我已经用三种不同的搜索操作测试了每种哈希表,每种哈希表的时间几乎相同,第一种表大约为每循环70毫秒,第二种表大约为每循环850微秒。
请参考附件 gist 。
2fjabf4q7#
我感到困惑。哈希表的查找应该是O(1)的时间复杂度,如果我们假设最坏的情况,那么我们不应该每次都遇到最坏的情况。你基本上证明了TF哈希表每次都会遇到最坏的情况。
mlmc2os58#
在这里,我们比较了两种不同大小的哈希表的时间复杂度。在我看来,通常我们会比较同一表上不同操作的时间复杂度。例如,我用3种不同的搜索操作测试了每种哈希表,每种哈希表的时间几乎相同。第一种表大约为70毫秒/循环,第二种表大约为850微秒/循环。
除此之外,您还有其他方法来检查哈希表的大小吗?
@synandi 这是我的观点吗?
TF哈希表查找操作是否总是O(n)?根据“来源”,我们还可以看到平均情况应该是O(1),您如何告诉我这是平均情况?最坏的情况应该很少发生,而不是一直发生。
当发生常数碰撞时,最坏的情况就会发生,因为哈希函数很糟糕,所以您要么认为TF哈希函数很糟糕,要么仍然存在一个导致其时间复杂度为O(n)的错误。
查找是将键进行哈希以找到其位置,这是一个常数时间复杂度的操作,它不应该随着词汇量的大小而变化。
3duebb1j9#
使用字典。