我用Python写了一棵三叉搜索树,发现当树变得非常深时,试图删除它会导致Python无限期地挂起。以下是产生此行为的代码的简化版本:
import random
import sys
from collections import deque
class Node():
__slots__ = ("char", "count", "lo", "eq", "hi")
def __init__(self, char):
self.char = char
self.count = 0
self.lo = None
self.eq = None
self.hi = None
class TernarySearchTree():
"""Ternary search tree that stores counts for n-grams
and their subsequences.
"""
def __init__(self, splitchar=None):
self.root = None
self.splitchar = splitchar
def insert(self, string):
self.root = self._insert(string, self.root)
def _insert(self, string, node):
"""Insert string at a given node.
"""
if not string:
return node
char, *rest = string
if node is None:
node = Node(char)
if char == node.char:
if not rest:
node.count += 1
return node
else:
if rest[0] == self.splitchar:
node.count += 1
node.eq = self._insert(rest, node.eq)
elif char < node.char:
node.lo = self._insert(string, node.lo)
else:
node.hi = self._insert(string, node.hi)
return node
def random_strings(num_strings):
random.seed(2)
symbols = "abcdefghijklmnopqrstuvwxyz"
for i in range(num_strings):
length = random.randint(5, 15)
yield "".join(random.choices(symbols, k=length))
def train():
tree = TernarySearchTree("#")
grams = deque(maxlen=4)
for token in random_strings(27_000_000):
grams.append(token)
tree.insert("#".join(grams))
sys.stdout.write("This gets printed!\n")
sys.stdout.flush()
def main():
train()
sys.stdout.write("This doesn't get printed\n")
sys.stdout.flush()
if __name__ == "__main__":
main()
这将打印出"This gets printed",但不会打印出"This doesn't get printed"。手动删除对象会产生相同的效果。如果我把插入的字符串数量从2700万减少到2500万,一切都正常 - Python会打印出两个语句,然后立即退出。我尝试运行GDB,这是我得到的回溯:
#0 pymalloc_free.isra.0 (p=0x2ab537a4d580) at /tmp/build/80754af9/python_1546061345851/work/Objects/obmalloc.c:1797
#1 _PyObject_Free (ctx=<optimized out>, p=0x2ab537a4d580)
at /tmp/build/80754af9/python_1546061345851/work/Objects/obmalloc.c:1834
#2 0x0000555555701c18 in subtype_dealloc ()
at /tmp/build/80754af9/python_1546061345851/work/Objects/typeobject.c:1256
#3 0x0000555555738ce6 in _PyTrash_thread_destroy_chain ()
at /tmp/build/80754af9/python_1546061345851/work/Objects/object.c:2212
#4 0x00005555556cd24f in frame_dealloc (f=<optimized out>)
at /tmp/build/80754af9/python_1546061345851/work/Objects/frameobject.c:492
#5 function_code_fastcall (globals=<optimized out>, nargs=<optimized out>, args=<optimized out>, co=<optimized out>)
at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:291
#6 _PyFunction_FastCallKeywords () at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:408
#7 0x00005555557241a6 in call_function (kwnames=0x0, oparg=<optimized out>, pp_stack=<synthetic pointer>)
at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:4616
#8 _PyEval_EvalFrameDefault () at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3124
#9 0x00005555556ccecb in function_code_fastcall (globals=<optimized out>, nargs=0, args=<optimized out>,
co=<optimized out>) at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:283
#10 _PyFunction_FastCallKeywords () at /tmp/build/80754af9/python_1546061345851/work/Objects/call.c:408
#11 0x00005555557241a6 in call_function (kwnames=0x0, oparg=<optimized out>, pp_stack=<synthetic pointer>)
at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:4616
#12 _PyEval_EvalFrameDefault () at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3124
#13 0x00005555556690d9 in _PyEval_EvalCodeWithName ()
at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3930
#14 0x0000555555669fa4 in PyEval_EvalCodeEx () at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:3959
#15 0x0000555555669fcc in PyEval_EvalCode (co=co@entry=0x2aaaaac08300, globals=globals@entry=0x2aaaaaba8168,
locals=locals@entry=0x2aaaaaba8168) at /tmp/build/80754af9/python_1546061345851/work/Python/ceval.c:524
#16 0x0000555555783664 in run_mod () at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:1035
#17 0x000055555578d881 in PyRun_FileExFlags ()
at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:988
#18 0x000055555578da73 in PyRun_SimpleFileExFlags ()
at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:429
#19 0x000055555578db3d in PyRun_AnyFileExFlags ()
at /tmp/build/80754af9/python_1546061345851/work/Python/pythonrun.c:84
#20 0x000055555578eb2f in pymain_run_file (p_cf=0x7fffffffd240, filename=0x5555558c5440 L"minimal.py",
fp=0x5555559059a0) at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:427
#21 pymain_run_filename (cf=0x7fffffffd240, pymain=0x7fffffffd350)
at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:1627
#22 pymain_run_python (pymain=0x7fffffffd350) at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:2876
#23 pymain_main () at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:3037
#24 0x000055555578ec4c in _Py_UnixMain () at /tmp/build/80754af9/python_1546061345851/work/Modules/main.c:3072
#25 0x00002aaaaaf0d3d5 in __libc_start_main () from /lib64/libc.so.6
#26 0x0000555555733982 in _start () at ../sysdeps/x86_64/elf/start.S:103
如果我尝试从那个点开始逐步执行,执行会在obmalloc.c的三行之间循环——GDB说是在1796-98行,但数字似乎有些偏差,回溯中的文件(在/tmp/中)不存在。
这在Python 3.7.3和3.6上都发生过,尽管需要导致挂起的字符串数量不同(对于两个版本都是2700万)。此时所需内存约为80GB,打印第一条语句需要45分钟。我实际使用的版本是用cython编写的,它减少了内存和运行时间,但仍然面临同样的问题。
使用对象的效果与预期相同,即使插入了10亿个字符串。保持对象活动状态(从函数返回它或将其放入全局变量中)将问题推迟到Python退出时——因此至少可以确保在那一点上完成所有工作,但我真的想知道出了什么问题。
编辑:我通过conda(4.6.2)安装了python,并且我在linux服务器节点上。
> uname -a
Linux computingnodeX 3.10.0-862.14.4.el7.x86_64 #1 SMP Wed Sep 26 15:12:11 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
/tmp/build/80754af9/python_1546061345851/work
看起来像是嵌入到可执行文件中的路径 -- 这是 Python 构建时源代码所在的构建服务器的位置和时间。 - ivan_pozdeev