Python: расширение сложного дерева DataStructure - PullRequest
Новая
       21

Python: расширение сложного дерева DataStructure

0 голосов
/ 07 ноября 2011

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

Пример. Допустим, я начинаю с Нью-Йорка, который разбивает Бронкс, Кингс, Нью-Йорк, Квинс и Ричмонд в качестве округов, но затем, наконец, каким-то образом они решают обратиться в США.

Я не уверен, что это хороший пример, но просто чтобы прояснить это, есть более четкое объяснение проблемы. 

A (expands to) B,C,D -> B (expands to) K,L,M -> K resolves to Z

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

Я вызываю запрос к базе данных для каждого элемента в расширенной версии, который возвращает список элементов. Идите, пока он не разрешится в один элемент. Без рекурсии я не теряю бурение до последнего элемента, к которому решают другие. Но с рекурсией это не то же самое. Я также новичок в Python, так что, надеюсь, это не плохой вопрос для сайта, подобного этому.

returnCategoryQuery - это метод, который возвращает список элементов путем вызова запроса к базе данных.

Без рекурсии 

#Dictionary to save initial category with the rest of cl_to
baseCategoryTree = {};
#categoryResults = [];

# query get all the categories a category is linked to
categoryQuery = "select cl_to from categorylinks cl left join page p on cl.cl_from = p.page_id where p.page_namespace=14 and p.page_title ='";
cursor = db.cursor(cursors.SSDictCursor);

    for key, value in idTitleDictionary.iteritems():
        for startCategory in value[0]:
            #print startCategory + "End of Query";
            categoryResults = [];
            try:
                categoryRow = "";
                baseCategoryTree[startCategory] = [];
                print categoryQuery + startCategory + "'";
                cursor.execute(categoryQuery + startCategory + "'");
                done = False;
                while not done:
                    categoryRow = cursor.fetchone();
                    if not categoryRow:
                        done = True;
                        continue;
                    categoryResults.append(categoryRow['cl_to']);
                for subCategoryResult in categoryResults:
                    print startCategory.encode('ascii') + " - " +  subCategoryResult;
                    for item in returnCategoryQuery(categoryQuery + subCategoryResult + "'"):
                        print startCategory.encode('ascii') + " - " + subCategoryResult + " - "  + item;
                        for subItem in returnCategoryQuery(categoryQuery + item + "'"):
                            print startCategory.encode('ascii') + " - " + subCategoryResult + " - "  + item + " - " + subItem;
                            for subOfSubItem in returnCategoryQuery(categoryQuery + subItem + "'"):
                                 print startCategory.encode('ascii') + " - " + subCategoryResult + " - "  + item + " - " + subItem + " - " + subOfSubItem;
                                 for sub_1_subOfSubItem in returnCategoryQuery(categoryQuery + subOfSubItem + "'"):
                                      print startCategory.encode('ascii') + " - " + subCategoryResult + " - "  + item + " - " + subItem + " - " + subOfSubItem + " - " + sub_1_subOfSubItem;
                                      for sub_2_subOfSubItem in returnCategoryQuery(categoryQuery + sub_1_subOfSubItem + "'"):
                                          print startCategory.encode('ascii') + " - " + subCategoryResult + " - "  + item + " - " + subItem + " - " + subOfSubItem + " - " + sub_1_subOfSubItem + " - " + sub_2_subOfSubItem;
            except Exception, e:
                traceback.print_exc();

с рекурсией 

def crawlSubCategory(subCategoryList):
    level = 1;
    expandedList = [];
    for eachCategory in subCategoryList:
        level = level + 1
        print "Level  " + str(level) + " " + eachCategory;
        #crawlSubCategory(returnCategoryQuery(categoryQuery + eachCategory + "'"));
        for subOfEachCategory in returnCategoryQuery(categoryQuery + eachCategory + "'"):
            level = level + 1
            print "Level  " + str(level) + " " + subOfEachCategory;
            expandedList.append(crawlSubCategory(returnCategoryQuery(categoryQuery + subOfEachCategory + "'")));
    return expandedList;


#Dictionary to save initial category with the rest of cl_to
baseCategoryTree = {};
#categoryResults = [];

# query get all the categories a category is linked to
categoryQuery = "select cl_to from categorylinks cl left join page p on cl.cl_from = p.page_id where p.page_namespace=14 and p.page_title ='";
cursor = db.cursor(cursors.SSDictCursor);

for key, value in idTitleDictionary.iteritems():
    for startCategory in value[0]:
        #print startCategory + "End of Query";
        categoryResults = [];
        try:
            categoryRow = "";
            baseCategoryTree[startCategory] = [];
            print categoryQuery + startCategory + "'";
            cursor.execute(categoryQuery + startCategory + "'");
            done = False;
            while not done:
                categoryRow = cursor.fetchone();
                if not categoryRow:
                    done = True;
                    continue;
                categoryResults.append(categoryRow['cl_to']);
            #crawlSubCategory(categoryResults);
        except Exception, e:
            traceback.print_exc();
        #baseCategoryTree[startCategory].append(categoryResults);
        baseCategoryTree[startCategory].append(crawlSubCategory(categoryResults));

1 Ответ

0 голосов
/ 07 ноября 2011

Вы пытаетесь найти "королевы" и узнать, что это в США? Вы пытались кодировать свое дерево в XML и использовать lxml.etree для поиска элемента, а затем использовать getpath для возврата пути в формате XPath?

Это будет означать добавление четвертого верхнего уровня к вашему дереву, а именно World, и тогда вы будете искать Queens и узнаете, что путь к Queens равен World/USA/NewYork/Queens. Ответом на ваш вопрос всегда будет второй пункт в XPath.

Конечно, вы всегда можете просто построить дерево из XML и использовать алгоритм поиска по дереву.

...