[ новости /+++ | форум | теги | ]

<< Предыдущая ИНДЕКС Поиск в статьях src Установить закладку Перейти на закладку Следующая >>

Ключевые слова: perl, struct, hash,  (найти похожие документы)

From: jkeks <[email protected]>
Newsgroups: email
Date: Mon, 16 Dec 2003 14:31:37 +0000 (UTC)
Subject: сравнение сложных структур данных в Perl


сравнение сложных структур данных

  Задача стояла следующая, необходимо написать универсальную блоговую модель, на
  основе которой можно хранить любые данные любой сложности. Особенность таких
  данных в том, что есть корневые элементы данных, от которых отраставют любые
  структуры. Впринципе придумать что-то другое сложно, да и к тому же меня эта
  модель вполне устраивает.

  Сам алгоритм работы уже был построен так что в модуле (написанном на Perl)
  существовало 2 функции получить данные, и записать данные.
  Вот тут я и задумался, что этими функциями я не отделаюсь, во первых нужна
  возможность удаления, изменения записей и наконец основой основ должен быть
  ПОИСК.

  Когда я писал ret WebOS data.pm (http://jkeks.far.ru/ret) я подошел к этому
  грубо говоря НИКАК.

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

  Что я подразумеваю под словом сложный.

  Если вы сталкивались с Perl , то наверняка знаете внутренее устройство сложных
  структур. Мягко говоря - она до ужаса мне нравится. Все построено на ссылках.
  Двухмерный массив мы получим когда каждому элементу массива мы ассоциируем
  ссылку на отедльный массив. Таким образом мы легко можем создавать Х-мерные
  массивы. кроме того какие-то элементы могу ссылаться на простые строки
  (скаляры) данных, а некоторые на хэши.

  В популярной книге Кристиансена Perl CookBook описаны лишь базовые возможности
  ссылок. Например Хэши массивов или массивы хэшей. Нас же интересуют ЛЮБЫЕ. А
  точнее массив  чего-то!
  например Массив хэшей массивов скаляров.
  Стрктуру определяет программист. Интерфейс для работы с данными предоставляет
  сам Perl (немного сложный, однако вполне претенддующий на роль УНИВЕРСАЛЬНОГО)

  Итак.. ПОИСК.

  О условиях.

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

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

  Я 3 дня не мог приехать к решению, а может и больше уже наверно.. пока не
  пошел в бблиотеку и не посидел там рядом с девченками 8)
  И вот что получилось:
  Алгоритм представляет из себя 4 блока, 3 из них почти одинаковые и работают с
  разными типами данных SCALAR HASH ARRAY. четвертый выполняет повторяющиеся
  функции.

 Рассмотрим самый простой блок обработки скаляров:

 Блок этот выполнен в виде функции _Scalar
 В его задачи входит проверка на соответствие однородность типов скаляров.
 Далье Если скаляр является ссылкой , тогда в массив накопления ссылок из
 соответствующих элементов массивов кладутся значения.
 Иначе проверяются сами данные на совпадение.

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

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

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

 Ну и теперь хочу привести простой пример отходя от которого можно развить идею,
 В начале определимся, что в массиве

 a@  находится оригинальный массив с шаблоном от пользователя.
 @b  очередная запись считанная из базы
 @a_ - рабочий простой массив, получаемый после опреации:
 @a_=@a; (понятно что копируется в него не все, а только начальный массив, без
 данных от ссылок.
 @b_ - аналогично!

 sub _Array
 {
 for ($i=0;$i<#$;$i++)
     {
     if (ref($b[i]) ne ref($a_[i])) {} # не совпадает структура
     if (ref($a_[i]) {push (@link, $a_[i]); push (@link, $b_[i])}
     else
         {
         if ($a_[i] ne $b_[i])     # не совпадают элементы массива
            {}
         }
     
     }
 
 _All();
 }
 

 sub _All
 {
 if ( #$link > 0 )
    {
    $b = pop @link;
    $a = pop @link;
    if (ref($a) ne ref($b) {} # не совпадает структура опять. Одно из правил о
			      # несовпадении структуры лишее.
    if (ref($a) eq 'SCALAR') {$a_=$$a; $b_=$$b; _Scalar()}
    if (ref($a) eq 'ARRAY') {@a_=$@a; @b_=$@b; _Array()}
    if (ref($a) eq 'HASH') {%a_=$%a; %b_=$%b; _Hash()}
    }
 else
 {} # данные совпали!!!
 }



 Ну вот..
 а по принципу функции _Array() надо написать функцию _Hash и _Scalar.

 Вот и вся сложность сравнения стрктур данных любой сложности.
 А на этом я все..
 Чтоб у вас не было таких проблемм.

 Ну и сами вы сможете оценить полноценный код (который однозначно скоро появится
 на http://jkeks.far.ru/ret , ну и хуже того на базе этого будет работать проект
 http://revda.biz
 Так что заходите в гости.

<< Предыдущая ИНДЕКС Поиск в статьях src Установить закладку Перейти на закладку Следующая >>

Партнёры:

Хостинг: