The Diary

Архив

Петък, 26 Януари 2007

Чували ли сте за Quad-Trees. Структура от данни, която по своята същност много напомня 2-d k-d Tree. Това пък за непросветените е балансирано двоично дърво за търсене, което обаче е специално пригодено за многомерни ключове. Тоест примерно ако искате да запазите списък с координати, но се нуждаете бързо да можете за определите дали дадена точка е в списъка или не. Именно тогава идват на помощ тези дървовидни структури. Принципно трика е, че дървото съдържа два вида елементи "хоризонтални" и "вертикални" ако запазим парадигмата, че говорим за координати то "Хоризонталните" елементи делят пространството на ляво и дясно от дадена позиция, вертикалните на горе и долу. Така може с логаритмечен брой стъпки да се провери дали дадена позиция е в дървото. Това дори е полезно ако искате да компресирате картинка с ниска ентропия. ТОест с големи едноцветни области. Защото вместу да представляват отделни точки поддърветата може да са цели области и така ако имате голямо черно петно може да го компресирате в няколко съседни квадратни области. Това дори ви дава една голяма екстра без пари - ако дървото е много голямо и се преточва през бавна среда по слоеве от корена можете да почнете да показвате груб изглед на картината още от рано като при прогресивните jpeg - те дори работят на подобен принцип до колкото знам. Сега да кажа и защо го пиша това. Работата ми сега е да измисля добра структура за пазене на sparse (сори не го знам как е на български) матрици в паметта т.е. такива с много нулеви позиции. Е, мислих доста и засега май това е начина, който мога да измисля с най-добър баланс на всички операции - добавяне, търсене, триене, обхождане по редове и колони. Интересно ми е (макар да не вярвам, че на някой от четящите ще му се мисли въобще, даже тези стигнали до тук да ми се обадят да ги черпя по бира - герои) какви са вашите предложения, темата е интересна, а няма много писано по нея в интернет. Само да предупредя не се касае за матрици 10х10, че да ги пазя като двумерен масив - става дума за милиони редове и стълбове и под 10% ненулеви позиции.

---

Except where otherwise noted the content of this site is licensed under a Creative Commons Attribution License.
Comments, texts and pictures not signed by me are property of their respective owners.
(c) 2003-2005 by Georgi Chorbadzhiyski. Some rights reserved.