LINUX.ORG.RU

понятно ли написана функция(и)?

 , , ,


0

1

Эта функция принимает список и корневой узел и формирует binary search tree, каждый раз - разное.


def create_lists(dic, ls, node):   #creates left and right lists for a node & updates a dict
    ind=ls.index(node.data)
    ls1=(ls[:ind]) # can be empty, no index error
    ls2=ls[ind+1:]  # can be empty, no index error

    dic[node]=(ls1, ls2)
    return dic


def create_childs (dic, node):   #creates left and right childs for a parent & updates a dict
    import random

    if dic[node][0]:
        intL=random.choice(dic[node][0])
        node.left=Node(intL)
        dic=create_lists(dic, dic[node][0], node.left)



    if dic[node][1]:
        intR=random.choice(dic[node][1])
        node.right=Node(intR)
        dic=create_lists(dic, dic[node][1], node.right)


    del dic[node]

    return dic


def bin_srch_tr(ls, root):
    # ls must be sorted in increased order!
    print(root)

    import random

    dic=dict()
    dic=create_lists(dic, ls, root)
    dic = create_childs(dic, root)

    while dic:
        dic2=dic.copy()
        for node in dic:
            print('node' , node.data, dic) # current node & all node objects with left & right lists per node in a dic
            dic2 = create_childs(dic2, node)
        dic=dic2

    return root


ls=[1,2,3,4,5,6,7]
root=Node(4)  # root where data is int, left & right are None  

print(bin_srch_tr(ls, root))

С PEP познакомься.

anonymous ()

понятно ли написана функция(и)

Нет.

vvn_black ★★★★ ()

Это шок

ls=[1,2,3,4,5,6,7]

ls = list(range(1,8,1))
anonymous ()
Ответ на: комментарий от anonymous

А вот это, не шок?

dic=dict()  # sic! словарь
dic=create_lists(dic, ls, root)
dic = create_childs(dic, root)  # sic! список
vvn_black ★★★★ ()

Говнокод. Но как для гвидобейсикокодера - норм.

anonymous ()

Понятно, но знак присваивания отделяй пробелами, это не баш.

Deleted ()

Я в ваших BFS не понимаю, но генерацию случайного дерева по ключам, сделал бы так, может оно и не сильно понятнее, но нет загадочного переопределения словарей и списков.

3.7:

from dataclasses import dataclass
import random


@dataclass
class Node:
    key: int
    data: dict
    left: int = None
    right: int = None

    def __str__(self):
        return (
            f'Node(key: {self.key}, left: {self.left}, right: {self.right})')


def random_branch(root, keys):
    if len(keys) == 0:
        return None
    elif len(keys) == 1:
        return Node(keys[0], {})
    else:
        return random_tree(keys)


def random_tree(keys):
    index = random.randint(0, len(keys) - 1)
    root = Node(keys[index], {})

    root.left = random_branch(root, keys[: index])
    root.right = random_branch(root, keys[index + 1:])

    return root


keys = [*range(10), ]  # любой список, для примера 0..9
keys.sort()            # упорядочиваем

root = random_tree(keys)
print(root)

Node(key: 5, left: Node(key: 4, left: Node(key: 1, left: Node(key: 0, left: None, right: None), right: Node(key: 3, left: Node(key: 2, left: None, right: None), right: None)), right: None), right: Node(key: 6, left: None, right: Node(key: 8, left: Node(key: 7, left: None, right: None), right: Node(key: 9, left: None, right: None))))

Ну и если приложить форматирование:

Node(key: 5,
     left: Node(key: 4,
                left: Node(key: 1,
                           left: Node(key: 0,
                                      left: None,
                                      right: None),
                           right: Node(key: 3,
                                        left: Node(key: 2,
                                                   left: None,
                                                   right: None),
                                        right: None)),
                right: None),
     right: Node(key: 6,
                 left: None,
                 right: Node(key: 8,
                             left: Node(key: 7,
                                        left: None,
                                        right: None),
                             right: Node(key: 9,
                                         left: None,
                                         right: None))))


      _5_
    /     \
   4       6
  /         \
  1          8
 / \        / \
0   3      7   9
   /
  2  

vvn_black ★★★★ ()
Ответ на: комментарий от vvn_black

Ну мне понятно. Может, у тебя и профессиональнее с декоратором и прочими изысками, но это же


    def random_branch(root, keys):
        ....
        ....
        ....

        return random_tree(keys) 
    def random_tree(keys):

        ....
        root.left = random_branch(root, keys[: index])
        root.right = random_branch(root, keys[index + 1:])

вроде рекурсия?

Мне без рекурсии хотелось. Если keys = [*range(100), ]? Можно измерить время выполнения ради интереса.

hibiscusM ()
Ответ на: комментарий от hibiscusM

Можно измерить время выполнения ради интереса.

А, смысл? Вот циферки, real 0m0,086s и real 0m0,456s, во втором 100 тыс. индексов.

И, рекурсия она не про скорость выполнения, а про глубину вложенности и хватит ли на неё памяти в пике. А во-вторых, насколько я понимаю BFS совсем не про единовременное создание самого дерева.

vvn_black ★★★★ ()
Ответ на: комментарий от hibiscusM

с декоратором и прочими изысками

Да, не в «декораторе» дело, Node может быть каким угодно другим классом или структурой, реализующей узел.

Вот от такого, если без надобности, дискомфорт сразу возникает

dic=dict()
dic=create_lists(dic, ls, root)
dic = create_childs(dic, root)

как вариант

dic = create_childs(create_lists({}, ls, root), root)

vvn_black ★★★★ ()
Ответ на: комментарий от vvn_black

vvn_black

dic = create_childs(create_lists({}, ls, root), root)  

А можно какой-нибудь пример вашего питоновского кода, где вы в качестве параметра передаете функции словарь в таком виде { }, и потом используете его этой функции?

@ xDShot,
в этой теме я прошу высказаться специалистов в программировании, а не случайных людей. Неужели это не очевидно?

hibiscusM ()
Ответ на: комментарий от hibiscusM

«Каждый дурак может написать код, понятный компьютеру. Хорошие программисты пишут код, понятный людям.»

xDShot ★★★★★ ()
Ответ на: комментарий от hibiscusM

где вы в качестве параметра передаете функции словарь в таком виде { }

Если только в functools.reduce, а в данном случае, надо словарь определять внутри create_lists.

vvn_black ★★★★ ()
Ответ на: комментарий от vvn_black

ну в целом ваш вариант

 dic = create_childs(create_lists({}, ls, root), root) 
меня, мягко говоря, заставил призадуматься (еще и root 2 раза в одной строке, очень странная запись). Те варианты, что мне выкладывают здесь, я мельком просматриваю, не проверяю, не тестирую. Вроде на первый взгляд выглядит правдоподобно для питона, ну и ладно.

hibiscusM ()
Ограничение на отправку комментариев: только для зарегистрированных пользователей