import random
import time
import math
#среднее значение
def average_value(numbers):
return float(sum(numbers) / max(len(numbers)))
class node:
def __init__(self, value = None):
self.value = value
self.left_child= None
self.right_child= None
self.parent= None # указатель на род. узел в дереве
class binary_search_tree:
def __init__(self):
self.root = None
def insert(self, value):
if self.root == None:
self.root = node(value)
else:
self._insert(value, self.root)
def _insert(self, value, cur_node):
if value < cur_node.value:
if cur_node.left_child == None:
cur_node.left_child = node(value)
cur_node.left_child.parent = cur_node # установаливаем род
else:
self._insert(value, cur_node.left_child)
elif value > cur_node.value:
if cur_node.right_child == None:
cur_node.right_child = node(value)
cur_node.right_child.parent = cur_node # установаливаем род
else:
self._insert(value,cur_node.right_child)
# если уже есть данный эл, то не добавляем
def search(self, value):
if self.root != None:
return self._search(value, self.root)
else:
return True
def _search(self, value, cur_node):
if value == cur_node.value:
return True
elif value < cur_node.value and cur_node.left_child != None:
return self._search(value, cur_node.left_child)
elif value > cur_node.value and cur_node.right_child != None:
return self._search(value, cur_node.right_child)
return False
tree = binary_search_tree()
succ = []
fail = []
i = 0
#заполнение дерева
for i in range(10000):
tree.insert(int(random.random() * 10 ** 4))
i += 1
print(i)
#поиск в дереве
for i in range(10 ** 3):
rand = int(random.random() * 10 ** 4)
start_time = time.time()
result = tree.search(rand)
finish_time = time.time() - start_time
if result == True:
succ.append(finish_time)
else:
fail.append(finish_time)
if (len(succ) == 0):
print("Нет успешных результатов поиска!")
else:
min_time = min(succ)
max_time = max(succ)
average_time = average_value(succ)
sum = 0
for i in range(len(succ)):
sum += (succ[i] - average_time) ** 2
deviation_time = math.sqrt((1 / i) * sum) # стандартное отклонение
print("")
print("")
print("min time: " + str(min_time))
print("max time: " + str(max_time))
print("average time: " + str(average_time))
print("deviation time: " + str(deviation_time))
print("")
print("")
if (len(fail) == 0):
print("Нет неудачных результатов поиска!")
else:
average_time = average_value(fail)
sum = 0
for i in range(len(fail)):
sum += (fail[i] - average_time) ** 2
deviation_time = math.sqrt((1 / i) * sum) # стандартное отклонение
print("average time: " + str(average_time))
print("deviation time: " + str(deviation_time))
Добавить комментарий
|
1 ответ
def _insert(self, value, cur_node):
if value cur_node.value:
Что за хитрый if
?
def _search(self, value, cur_node):
if value == cur_node.value:
return True
elif value cur_node.value and cur_node.right_child != None:
Аналогично
Ну и конкретно по вашему вопросу:
def average_value(numbers):
return float(sum(numbers) / max(len(numbers)))
вы передаёте в функцию вот такой список
[0.0, 0.0, 0.0, 0.0, 0.0]
угадайте что происходит :)
надо сделать так:
def average_value(numbers):
return float(sum(numbers) / len(numbers))
Тогда у вас ошибка уже вот тут:
deviation_time = math.sqrt((1 / i) * sum) # стандартное отклонение
Деление на 0
Так что надо проверять еще и i
, например так:
deviation_time = 0 if i == 0 else math.sqrt((1 / i) * sum) # стандартное отклонение
тогда код уже не выдает ошибок и доходит до конца
-
ошибка была в sum(numbers). Я считал, что sum(numbers) - это метод. Оказывается нет.– user4052737 дек 2020 в 5:40