Оптимизация иерархии в хранилище данных Google Appengine

Question

У меня есть иерархические данные, которые хранятся в хранилище данных с использованием модели, которая выглядит следующим образом:

class ToolCategories(db.Model):  
   name = db.StringProperty()  
   parentKey = db.SelfReferenceProperty(collection_name="parent_category")  
   ...  
   ...  

Я хочу напечатать все имена категорий с сохранением иерархии, скажем, в такой форме:

--Information Gathering  
----OS Fingerprinting  
----DNS  
------dnstool  
----Port Scanning   
------windows  
--------nmap  
----DNS3  
----wireless sniffers  
------Windows  
--------Kismet  

Для выполнения вышесказанного я использовал простую рекурсию, используя возможность обратных ссылок:

class GetAllCategories (webapp.RequestHandler) :


        def RecurseList(self, object, breaks) :
                output = breaks + object.name + "</br>"
                for cat in object.parent_category:
                        output = output + self.RecurseList(cat, breaks + "--")

                return output



        def get (self) :
                output = ""
                allCategories = ToolCategories.all().filter(' parentKey = ', None)
                for category in allCategories :
                        output = output + self.RecurseList(category, "--")

                self.response.out.write(output)

Поскольку я очень новичок в программировании движка приложений (вряд ли 3 дня с тех пор, как я начал писать код), я не уверен, является ли это наиболее оптимизированным способом с точки зрения доступа к Datastore для выполнения желаемой работы.

Это лучший способ? если не то, что есть?

Answer 1

У вас очень разумный подход! Моим основным предупреждением было бы то, что не имеет ничего общего с GAE, а с Python очень много: не собирайте строку из кусочков с + или + = . Скорее вы составляете список кусочков строк (с помощью append или extension или списков и т. Д.), И когда вы все закончите, вы присоединяете его для получения последней строки результат с ''. join (thelist) или тому подобное. Несмотря на то, что последние версии Python стремятся оптимизировать внутреннюю производительность O (N в квадрате) циклов + или + = , в конце концов вы всегда лучше составлять списки строк по пути и ''. join собирая их в самом конце!

Answer 2

Основным недостатком вашего подхода является то, что вы используете " список смежности " способ представления деревьев, вы должны сделать один запрос хранилища данных для каждой ветви дерева. Запросы к хранилищу данных довольно дороги (около 160 мс каждый), поэтому построение дерева, особенно если оно большое, может быть довольно дорогим).

Существует еще один подход, который по сути используется хранилищем данных для представления групп сущностей: вместо простого хранения родительского ключа сохраните весь список предков, используя ListProperty:

class ToolCategories(db.Model):
  name = db.StringProperty()
  parents = db.ListProperty(db.Key)

Затем, чтобы построить дерево, вы можете получить всю вещь в одном запросе:

q = ToolCategories.all().filter('parents =', root_key)