Рекурсивная производительность обработки данных с использованием Java и SQLite

голоса
4

Если у вас есть ответ, который не Java / SQLite связаны, я бы с удовольствием прочитал.

Окружающая среда

Я хранить элементы в базе данных со следующей схемой:

###################
#       Item      #    
###################
#      _id        #    This is the primary key
#    parent_id    #    If set, it the ID of the item containing this item
#      date       #    An ordinary date
#  geocontext_id  #    Foreign key to a pair of named coordinates
###################

###################
#   Geocontext    #    
###################
#       _id       #    This is the primary key
#       name      #    Way for the user to label a pair of coordinates (e.g : home, work)
#         x       #    One of the coordinate
#         y       #    The other one
###################

Проблема

Я должен фильтровать элементы в соответствии с geocontext и датой. Было бы легкой работой, если элементы были на том же уровне, но хитрость заключается в том, что это рекурсивная. EG:

root
      |_item 1
      |_item 2 
      |      |_item 4
      |      |_item 5
      |             |_item 6
      |_item 3
      |      |_item 8
      |             |_item 10
      |_item 11
      |       |_item 12
      |_item 7

Там нет явного предела рекурсивной глубины.

Теперь, если мы находимся в каком - либо узле и фильтра с датой «1 апреля», мы должны видеть не только те элементы , непосредственно содержащиеся в узле , который соответствует дате, но мы должны увидеть элементы , которые содержат элементы , соответствующие даты , а также ,

EG: Мы находимся в «пунктах 2», если «пункт 6» соответствует дате, то мы считаем «пункт 5» соответствует дате тоже, и мы должны сохранить его. Если мы в корне, то пункт 2 должен быть отображен.

То же самое относится и к geocontext, но это еще сложнее, потому что:

  • Она хранится в другой таблице.
  • Совпадение контекста является дорогостоящим математическим вычислением.

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

Примечание: мне не нужно , чтобы отобразить дерево . Отобразить список отфильтрованных данных из дерева. Мы должны видеть только плоский список из элементов. Задача состоит в том, чтобы решить , следует ли отображать каждый элемент или нет, по всем детям иерархии.

Как я пытался решить

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

###################
# Geocontex_cache #    
###################
#     item_id     #     I can Join the items table on this field
#     child_id    #     I can delete / update a child, and so delete / update the cache
#  geocontext_id  #     I can delete / update a geocontext, and so delete / update the cache
#        x        #      Here, I can brute force :-)
#        y        # 
###################

###################
#    Date_cache   #    
###################
#     item_id     #     
#     child_id    #    
#       date      #    
###################

Это кажется разумным, но я не пробовал еще. Тем не менее, он должен следующие недостатки:

  • Я переместил дорогостоящий процесс к получить / установить / создать / удалить методы, которые должны управлять кэшированной датой. Это будет трудный код писать и поддерживать. Элемент уровня пять глубины будет Тригер процесса, который ударит рекурсивно пять родителей.

  • Размер Ot база данных может стать огромной. Пять-де-глубина на уровне элементов хранения кэшированных данных для пяти родителей. Не знаю, если это уместно, так как это аа приложения моно-пользователь с ручным вводом. Я не думаю, что кто-то будет вставлять более thatn 1000 пунктов с более чем 10 уровнем глубины.

Теперь хорошая новость заключается в переходе от основания пирамиды к вершине, а не другому способу, так что это не имеет ужасно, как кажется. Когда я буду иметь дело с удалением родительского элемента, то это будет еще одна приятная головная боль, но я сохраняю его на другой вопрос ;-).

Теперь мой вопрос

Как бы вы храните данные и обрабатывать фильтрации Int наиболее оптимальным образом?

Необязательный :

Должен ли я определить явный рекурсивный предел глубины? Должен ли я выполнять фильтрацию с помощью SQL или Java? SQL, безусловно, будет быстрее, но соответствуя geocontext гораздо проще сделать в Java.

Как я работаю на Android платформы, у меня есть следующие ограничения:

  • Java является единственным языком в наличии, а не со всем стандартным Lib.

  • SQLite является единственным СУБД доступны.

  • Производительность и память являются важными вопросами. В случае, если у вас есть выбор, срок службы батареи и, следовательно, производительность является приоритетом.

  • Экзотика внешний ЛИЭС не может быть использовано.

PS: Я порылся в SO и найти некоторые интересные фрагменты информации (espacially Что является наиболее эффективным / элегантным способом разбора плоской таблицы в дерево? ). Это намек, но не решает проблемы.

Задан 04/04/2009 в 11:18
источник пользователем
На других языках...                            


4 ответов

голоса
5

1) Во- первых, давайте посмотрим на просто положить все в памяти. Это простое, гибкое, и , прежде всего, быстрое, решение. Недостатки включают тот факт , что вы должны прочитать все в память при запуске (дают пользователю красивой полосу загрузки , и они даже не заметят), и , возможно , придется сделать небольшую дополнительную работу , чтобы гарантировать , что все отражаются на диск , когда пользователь думает , что это, так что данные не будут потеряны.

В этом анализе я делаю некоторые общие предположения о Android / Dalvik Я действительно не знаю, что многое о, так что надеюсь, это несколько точным :) Помните, что G1 имеет 192MB оперативной памяти. Кроме того, ваше предположение выше было максимум около 1000 пунктов.

Object superclass ~ 8 bytes
parent/child pointer ~ 4 bytes
date (long) ~ 8 bytes
name (non interned string avg 32 chars) ~ 64 bytes
x point (int) ~ 4 bytes
y point (int) ~ 4 bytes

Total = 92 bytes + possible memory alignment + fudge factor = 128 bytes
1000 items = 125kB
10000 items = 1.22MB

Примечание: Я понимаю, что в то время как ребенок может иметь только один указатель, родитель может иметь несколько детей. Тем не менее, количество детей> родительский, указатели (элементы - 1), так что средняя стоимость> указатель родительской, ребенок это (элементы - 1) / элементы ~ 1 элемент или 4 байта. Это предполагает ребенок структуру, которая не выделяет неиспользуемую память, такие как LinkedList (в отличие от ArrayList)

2) Ботаник во мне говорит , что это было бы забавное место , профилировать B + дерево, но я думаю , что это слишком для того, что вы хотите в данный момент :) Однако, независимо от решения вы в конечном итоге принятия, если вы не держите все в память, вы наверняка хотите , чтобы кэшировать как можно больше верхних уровней дерева в памяти , как вы можете. Это может сократить количество дисковых операций резко.

3) Если вы не хотите идти всю память, другое возможное решение может быть следующим. Билл Karwin предлагает довольно элегантную структуру RDBMS называется Closure Таблица для оптимизации дерева на основе читает, делая записи более сложным. В сочетании с кэшем верхнего уровня может дать вам выигрыш в производительности, хотя я бы проверить это , прежде чем принимать мои слова на нем:

При оценке зрения, использовать то, что у вас есть в памяти, чтобы оценить, как много детей, как вы можете. Для тех детей, которые не соответствуют, используйте SQL соединение между таблицей закрытия и плоской таблицей с подходящим где положением, чтобы узнать, есть ли какие-либо согласующие дети. Если да, то вы будете указывать этот узел в списке результатов.

Надеюсь, что все это имеет смысл, и кажется, что он будет работать на то, что вам нужно.

Ответил 07/04/2009 в 16:56
источник пользователем

голоса
2

Я слушал Soonil и дал попробовать в «закрытия стола». Я добавил следующую таблицу:

################
#   Closure    #
################
# ancestor_id  #
#   item_id    #
################

Если, как я никогда не использовал эту модель раньше, она работает таким образом:

Вы добавляете строку для каждого прямого или косвенного отношения в иерархии. Если C является потомком B, а B ребенок А, у вас есть:

ancestor    item
   B         C
   A         B
   A         C      # you add the indirect relationship   
   A         A
   B         B
   C         C      # don't forget any item is in relation with himself 

Тем не менее, с этой схемой, вы упускаете важную информацию: каковы прямые отношения? Что делать, если вы хотите только прямые потомки элемента?

Для этого, вы можете добавить столбец is_directс BOOL в таблице закрытия, или вы можете просто держать столбец parent_idв itemтаблице. То , что я сделал , потому что это мешает мне переписывать много моего предыдущего кода.

Хорошая часть, что теперь я могу проверить, если элемент соответствует дате или geocontext в одном запросе.

EG, если я просматриваю все элементы, содержащиеся в пункте № 4 и хочу получить только те, соответствующие или содержащие ребенок, соответствующих даты D:

SELECT ti.parent_id, ti.id, ti.title 
FROM item AS di                                  # item to filter with the date
              JOIN closure AS c                  # closure table
                  ON (di.id = c.item_id) 
              JOIN item AS ti 
                  ON (c.ancestor_id = ti.id)     # top item to display
WHERE di.date = D                                # here you filter by date   
AND ti.parent_id = 4                             # here you ensure you got only the top items

Так что я могу выбросить все мои *_cacheтаблицы. У меня еще есть много работы , чтобы сделать одну UPDATE / DELETE / CREATE , но все централизовано и большинство из них является процедурным, не рекурсивным. Довольно круто.

Единственная боль, что я должен рекурсивно добавить элемент для всех его предка. Но получение предков выстрел один запрос, так что это действительно разумно. И, конечно, таблица закрытия занимает много места, но в моем случае я просто не волнует. Не забудьте индексироваться, если вы ищете perfs ...

Любовь это SQL трюк, спасибо большое, ребята! Это немного сложно получить, на первый взгляд, но так очевидно, как только вы сделали это.

Ответил 17/04/2009 в 16:58
источник пользователем

голоса
1

Это может быть оффтоп, но .. вы рассматривали использование сериализации?

Google протокол буфера могут быть использованы для упорядочивания данных в очень эффективной манере (время и пространство), вы должны были бы затем создать подходящую структуру дерева (смотреть в любой книге CS), чтобы помочь с поиском.

Я упомянул буфера протокола, потому что быть библиотекой Google они могут быть доступны на Android.

Просто мысль.

Ответил 04/04/2009 в 11:28
источник пользователем

голоса
-1

AFAICT вы можете использовать иерархические запросы (Google для «CONNECT BY» «СТАРТ С») в SQLite ...

Ответил 04/04/2009 в 17:35
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more