XML Parsing?

[stweet]

Партизан, исходя из ваших мнений: Работая в команде, вам бы сами сотрудники пальцы отбили за гонки xml в виде объекта с данными по всей программе.

[wvxvw]

Даже не знаю, как это еще сказать... для любого алгоритма есть более или менее подходящие структуры данных. Например, для нахождения пути по карте хорошо подходит дерево, но дерево плохо подходит для запоминания истории действий пользователя - для этого лучше подходит стек. Логично для задачи выбирать самую подходящую структуру данных, потому что одной универсальной хорошей для всех - не существует.
Говорю я это к тому, что нельзя сказать ХМЛ плохой или хороший вообще - можно только применитльно к конкретному агоритму, который использует его.
Но, была неоднократно замечена тенденция использовать ХМЛ не по назначению. Типичные примеры - это когда в ХМЛ хранятся не строковые данные, и потом их приходится при работе с ними все время кастовать из одного типа в другой. Или, другой пример - когда алгоритм поиска узла соответствующего условию превращается в експоненциальный или еще хуже - просто потому, что ХМЛ предоставляет готовые методы для того, чтобы такой алгоритм легко реализовать. А, например, реализовать алгоритмы построенные на последовательном увеличении глубины просматриваемого дерва в с использованием ХМЛ - не тривиально.

На досуге, если интересно, можете попробовать с помощью ХМЛя решить игру пятнашки:

[   ] [ 1 ] [ 2 ] [ 3 ]
[ 4 ] [ 5 ] [ 6 ] [ 7 ]
[ 8 ] [ 9 ] [ 10] [ 11]
[ 12] [ 13] [ 14] [ 15]

состояние к которому нужно прийти из любой комбинации. Нужно получить решение вида:
[начальное состояние] -> [следующее состояние] -> ... [последнее состояние]
где состояние состоит из записи расположения фигур на доске и смежных с ними транспозиций.
Например, целевое (последнее состояние) записанное в ХМЛ выглядело бы:

<state a="" b="1" c="2" d="3" e="4" f="5" ... l="15">
  <state  a="1" b="" c="2" d="3" e="4" f="5" ... l="15"/>
  <state  a="4" b="1" c="2" d="3" e="" f="5" ... l="15"/>
  .
  .
  .
  </state/>

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

[Wolsh]

состояние к которому нужно прийти из любой комбинации.

Пятнашки собираются не из любой комбинации. Например, если вручную поменять местами 14 и 15, то собрать обратно правильными ходами не получится.

[Партизан]

Ого... o_O Как все накинулись
Я где-то написал, что ни в коем случае не использовать ничего кроме XML?
Мне кажется или я как-то неправильно доношу мысль или вы не внимательно читаете. Я всего навсего не понимаю для чего переводить XML (!)полностью в Object. Я целиком и полностью за парсинг полученных данных с последующей их типизацией. Например, если мы получаем от некого сервиса список географических объектов то почему не создать отдельный класс с подходящими свойствами для такого типа выбрав соответствующие ноды из XML? Но я опять же повторюсь, я НЕ понимаю зачем все это, а кроме этого в XML могут быть и другие данные, сначала переводить в Object. Я опять же просто не вижу логики в этом. Это не говоря уже о перекрестных данных и namespace... и на вопрос "зачем в Object?" кроме низкой скорости я ни одного ответа еще не прочитал здесь. В общем, я в замешательстве некотором пребываю: все до единого кроме меня постоянно телефонные справочники города Москвы грузят и единым списком со всем этим работают? Для чего нужна эта пресловутая суперскорость доступа к загруженной информации? А время затраченное на перевод всего этого медленного XML в Object похоже никого не смущает?
В общем, как смог попытался объяснить свою позицию.

[stweet]

Для чего нужна эта пресловутая суперскорость доступа к загруженной информации?

Действительно, зачем ложки если есть руки, хм... только лишние движения.

А время затраченное на перевод всего этого медленного XML в Object похоже никого не смущает?

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

[wvxvw]

Сообщение от Wolsh

Пятнашки собираются не из любой комбинации. Например, если вручную поменять местами 14 и 15, то собрать обратно правильными ходами не получится.

Интересное заявление... попробуем проверить

Партизан, Вы просто попробуйте решить задачку - тогда все вопросы про потраченое время на переделывание из одной структуры в другую отпадут.
Просто для ориентации: если решать задачу используя алгоритм поиска "сначала вширину" - то памяти вашего компа не хватит (и даже не важно, ХМЛ вы использовали или нет, но с ХМЛем загнется на один этап раньше, чем без него). Если вы будете решать через "сначала вглубину" - то за счет того, что доступ и проверка узлов ХМЛя занимает пусть и незначительно болше времени, чем у типизированных объектов - там же сумашшедшие цифры получатся. Ну и так далее.
Время потраченное на переделку из ХМЛ в другую структуру может оказаться меньше 0.000001% по сравнению с 1000000% проигрыша от последующих использований ХМЛя.
Но самое главное, что нужно понять - что это не всегда так - это зависит от алгоритма который данные использует!

[Wolsh]

попробуем проверить

http://mathworld.wolfram.com/15Puzzle.html

По поводу задачки... я думаю все таки тема была не настолько абстрактно-универсальна, родилась из конкретного примера скининг/локализация, и само по себе утверждение, что нет необходимости переводить XML в Object подразумевало гораздо более тривиальные задачи. было приведено несколько доводов за Обжект, которые мне лично кажутся не просто неубедительными, а заблуждением.
1. Насчет скорости доступа не было приведено ни одного убедительного теста. Я так же "на своем опыте" могу сказать, что как-то делал проект с XML-списком локаций, у каждой из ~200 локаций было по 6 атрибутов, и поиск тега локации по любому атрибуту с извлечением другого атрибута этой локации занимал время, абсолютно незаметное для глаза, как и перезапись этих атрибутов на лету. Я не испытал ни разу даже мимолетного желания использовать другой формат "базы данных". Да, согласен, это не телефонная книга Москвы. На мой взгляд это как раз средненькая тривиальная задачка. Я именно и предлагаю не подниматься в небесные выси и не рассматривать здесь какие-то запредельные ситуации с гигантскими объемами данных или изначально непригодной структурой. Итак ясно, что эти ситуации требуют особого подхода. В связи с этим они не могут служить доказательством порочности использования XML в обычных повседневных ситуациях вроде скининга и локализации интерфейса сайтика или игрушки. То, что XML не является абсолютно универсальным форматом данных, я думаю любому очевидно. Но в 80% случаев он вполне удовлетворяет.
2. Насчет типизации. Отлично, что в Обжекте свойства типизированы. Но что с того, если формируете этот Обжект Вы из того же (загруженного) XMLя? Сам момент кастинга типа Вам не избежать. Это не довод.
Сюда же добавлю про имена — это в AS2-парсинге вы получали преимущество, когда брали из XML данные по структуре, то есть "пятый чайлд третьего чайлда у шестого чайлда узла документа" и записывали в Обжект с милым именем bodyColor. Сейчас, с XPath/E4X, в этом нет никакого смысла. Если Вы не знаете, что за XML вы загрузили (не представляю, как это) и что вы собираетесь там искать, то это проблема не XML а вашей архитектуры проекта. В описанной stweet ситуации, когда безрукие заказчики реализуют неправильный XML — это проблема не XML, а плохого проекта; и даже не заказчика, которому дали вручную заполнять XML (очевидно небезопасная операция), но не обеспечили контроля (например, с помощью XMLSchema на стороне сервера, если речь идет о CMSке).

[stweet]

Ну .. вероятно я не с той стороны донёс смысл своей мысли.
Я подразумевал не "гонки" XML как "БД" в "ходе" выполнения программы, а во время её написания.
Т.е. берёте вы чей то проект, а там всё в XML-ках, коментов "0", и обмен содержимым так же всё через XMLList-ы, вот как работать над таким проектом? Из моей практики: -Работая над одним проектом несколько человек, будут значительно тормозить развитие-расширение программы если один из них не будит типизировать данные. Иначе, разработчики поседеют коментировать каждый кастинг! Мне приносит удовольствие работать над красивым кодом, а так же не сложно написать тот или иной объект. Таким образом приятно смотреть на архитектуру проекта и/или передавать другому разработчику не боясь что к тебе ночью придут наказать за кривизну рук. Из ваших же фактов выходит: - Написал абстрактный класс, натолкал его XML-какми а там пусть разбираются где, что и зачем?!... Вот сиди и парси.

[wvxvw]

Почитал - интересно. Я когда решал, то выбрал в качестве эвристической функции для поискового алгоритма, как в книжке было написано, сумму расстояний до правильного расположения элементов, но судя по статье можно было бы использовать и количество инверсий (тем более, что если их нечетное количество, то сразу можно было бы выяснить, что задача не решается. Хотя вроде как есть еще какая-то лучшая функция для этого...

А на счет скорости - все очень просто. Когда вам нужно искать что-то а не просто перебрать все значения, то способ которым это делается очень важен. descendants() - это самый простой depth-first search. Т.е. это даже не поиск, а перебор, но в контексте поиска он становится им. Это совсем не оптимальный по времени алгоритм. Оптимальный по времени, если нет эвристической функции - breadth-first search, но он очень затратный по памяти. И есть еще вагон и маленькая тележка промежуточных алгоритмов. Кроме этого алгоритмы поиска делятся на "слепые" и "осведомленные" (т.е. когда есть эвристическая функция). Кроме того, поиск может искать "самого-самого" а может искать конкретный элемент. В задаче может быть исключено посещение тех же узлов дважды, а может быть разрешено. И еще куча всякого разного.

Переводить ХМЛ в типизированные объекты имеет смысл всегда, когда он хранит что-то, что вобщем не должно быть строкой. Например, как в ситуации которую тут обсуждали - хранение логических величин, или чисел, и уж тем более сложных объектов. Т.как сериализовать / десериализовать их каждый раз при чтении-записи явно лишнее.

[Wolsh]

Т.е. это даже не поиск, а перебор

Опять же, на своем опыте (его — практического — немного, но все же на чём еще я могу строить свою позицию?) ситуации, когда поиск и должен быть перебором, то есть сама работа программы основана на списках-выборках, а не получении единственного значения уникального атрибута — не так уж и редки. В частности упомянутый мной проект карты игрового мира с локациями работал именно списками. Изначально я и подразумевал создание специального класса, представляющего "локацию", и даже написал его — но так и не воспользовался)) Потому как наворачивать какие-то вектора/массивы локаций, производить по ним выборки (все тем же полным перебором, да по все тем же свойствам элементов, а не по самим элементам), потом возиться и с этими массивами — показалось(?) мне нелепым усложнением и запутыванием простого и красивого кода с использованием XMLList. Ситуации разные бывают. XML прожорлив, когда нужен уникальный элемент, возможно этим объясняется разница в скорости при локализации, где элементы действительно уникальны и поиск превращается в бессмысленный перебор всего документа.