From: jkeks <jkeks@mail.ru>
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
Так что заходите в гости.
1172 Прочтений • [сравнение сложных структур данных в Perl (perl struct hash)] [08.05.2012] [Комментариев: 0]
Vova
