Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Парсинг XML

Автор: T0ohtik 15.5.2009, 21:43

Надо распарсить большую XML порядка 5 метров. Для парсинга использую SAX парсер из libxml. На данный момент не удовлетворяет качество написанного кода, а именно большой свич, который перебирает все возможные теги. Посему возник вопрос, может лучше заменить свич на карту, ключем которой будет имя тэга, а хранимым объектом - вызов функции? Как это скажется на производительность?

Автор: azesmcar 15.5.2009, 21:51

Цитата(T0ohtik @  15.5.2009,  21:43 ) а именно большой свич, который перебирает все возможные теги Каким образом? Я имею ввиду что switch в С++ со строками не работает. Как именно написан switch? Цитата(T0ohtik @  15.5.2009,  21:43 ) ключем которой будет имя тэга, а хранимым объектом - вызов функции? Как это скажется на производительность?  положительно (во всяком случае не отрицательно)  у map -а логаритмический поиск. Хотя вы можете и не заметить если тагов не очень много

Автор: T0ohtik 15.5.2009, 22:12

Вообще то я не С++ использую, а Objective - C. Ну и не совсем свич, а конструкцию else if. Мне кажется вопрос более по технике программирования а не по технологии. Будут ли красивые, высокоуровневые конструкции работать быстрее чем низкоуровневые не красивые?

Автор: azesmcar 15.5.2009, 22:18

Цитата(T0ohtik @  15.5.2009,  22:12 ) Вообще то я не С++ использую, а Objective - C. Ну и не совсем свич, а конструкцию else if. Мне кажется вопрос более по технике программирования а не по технологии else if? тут вообще думать не очем   Цитата(T0ohtik @  15.5.2009,  22:12 ) Будут ли красивые, высокоуровневые конструкции работать быстрее чем низкоуровневые не красивые?  switch - может быть оптимизирован в таблицу переходов, он может работать намного быстрее if если все правильно написать. Но if - это тупое средство проверки. Быстрым его никак не назовешь..он работает так - как написан. Мап - контейнер созданный для быстрого нахождения элемента с логаритмической сложностью поиска. If - для сравнения Код if (a == 1) ... else if (a == 2) ... else if (a == 3) ... else ... имеет линейную сложность, так как если к примеру а == 3, то он пройдет все 3 проверки прежде чем найдет нужное условие. Добавлено через 1 минуту и 37 секунд T0ohtik В случае мапа - единственное что вы потеряете - немного скорости на вызовы функции, но приобретете намного больше на поиске + красота кода. Добавлено через 3 минуты и 47 секунд T0ohtik в некоторых ситуациях - смотря какие теги, можно было бы вообще убрать поиск и сделать его скорость константным..короче тут уже все зависит от конкретной задачи

Автор: T0ohtik 15.5.2009, 22:26

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

Автор: Alexeis 15.5.2009, 22:28

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

Автор: Lazin 15.5.2009, 22:28

Цитата(T0ohtik @  15.5.2009,  22:12 ) Вообще то я не С++ использую, а Objective - C. Ну и не совсем свич, а конструкцию else if. Мне кажется вопрос более по технике программирования а не по технологии. Будут ли красивые, высокоуровневые конструкции работать быстрее чем низкоуровневые не красивые? конструкция if () .. else if () ... else ... - время поиска - O(N), константа небольшая поиск в бинарном дереве, зависит от того, как оно сбалансировано, если оно сбалансировано хорошо, то время поиска O(ln N), константа - больше чем в первом случае поиск в хэш таблице, зависит от количества колизий, в принципе, можно считать, что время поиска постоянно, константа зависит от реализации и она выше чем в первых двух случаях, так как нужно вычислить хэш строки вывод, в случае небольшого количества тэгов можно применить цепочку if else if.. или здоровых switch, в случае если тэгов просто много, то нужно использовать бинарное дерево поиска, если их очень много, то хэш таблицу

Автор: Alexeis 15.5.2009, 22:31

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

Автор: azesmcar 15.5.2009, 22:35

самый примитивный допустим у нас есть теги html body head суммируем их ASCII коды. html=437 body=430 head=402 максимальный 437 Код func_ptr arr[438]; arr[430] = func_body_handler; arr[437] = func_html_handler; arr[402] = func_head_handler; например что-то типа этого, разумеется это не идеальный пример для подражания  просто пример привел в какую сторону можно мыслить. я бы честно говоря много раз подумал прежде чем избрать подобный подход. проблематично для будущего, и память жрет, да и все равно сумму символов считать придется.  тут на мой взгляд лучшее решение - хэш таблица.

Автор: Lazin 15.5.2009, 22:35

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

Автор: T0ohtik 15.5.2009, 22:47

Цитата(Lazin @ 15.5.2009,  22:35) еще один вариант(довольно тупой, но может работать), определить какие тэги встречаются чаще других, если к примеру несколько тэгов встречается намного чаще других(к примеру их доля - 80% от всех используемых тэгов) то можно их разместить в начале цепочки if-ов, а все остальные - в порядки частоты встречаемости правда это будет работать только если в частоте встречаемости тэгов есть закономероность... Уже возникала такая идея...  А каким образом можно посчитать когда оптимально использовать хэш таблицу? В моем случае примерно до 20 тэгов.

Автор: azesmcar 15.5.2009, 22:50

Цитата(T0ohtik @  15.5.2009,  22:47 ) Уже возникала такая идея...smile  А каким образом можно посчитать когда оптимально использовать хэш таблицу? В моем случае примерно до 20 тэгов.  вам скорость нужна или красота кода? т.е. чем вы недовольны на данный момент?

Автор: math64 16.5.2009, 00:24

Можно для конкретного случая подобрать hash-функцию, которая будет выдавать разные значения для разных элементов, но неправильные элементы тоже будут выдавать совпадающие коды, нужно использовать добавочную проверку. Код enum { html = 't', head = 'e', body = 'o', }; int hash(const char*key) { return key[1]; } ... switch(hash(key)) {   case html:  if(strcmp(key,"html")==0) ...; break;   case head: if(strcmp(key,"head")==0) ...; break;   case body: if(strcmp(key,"body")==0) ...; break;   default: }

Автор: Andrey44 18.5.2009, 07:51

T0ohtik, можно еще использовать IXMLDOMDocument, IXMLDOMNode, IXMLDOM........ В общем их много и довольно просты в использовании. А если применять к тому-же xPath, то все вообще становится довольно просто. Это сугубо мое личное мнение.

Автор: Lazin 18.5.2009, 08:05

Цитата(Andrey44 @  18.5.2009,  07:51 ) T0ohtik, можно еще использовать IXMLDOMDocument, IXMLDOMNode, IXMLDOM........ В общем их много и довольно просты в использовании. А если применять к тому-же xPath, то все вообще становится довольно просто. Это сугубо мое личное мнение.  да уж... Цитата(T0ohtik @  15.5.2009,  21:43 ) Надо распарсить большую XML порядка 5 метров. Для парсинга использую SAX парсер из libxml. очевидно, что ТС хочет обрабатывать документ по частям не загружая его в память целиком...

Автор: Andrey44 18.5.2009, 09:05

Цитата(Lazin @  18.5.2009,  08:05 ) очевидно, что ТС хочет обрабатывать документ по частям не загружая его в память целиком... По моему 5 метров памяти в наше время - это скажем не много

Автор: Lazin 18.5.2009, 09:20

5Mb xml файл, это очень много

Автор: Andrey44 18.5.2009, 09:33

Цитата(Lazin @  18.5.2009,  09:20 ) 5Mb xml файл, это очень много  Да, не знал, извиняюсь. Цитата Для работы с объёмными XML документами надо использовать инструменты не использующие DOM.

Автор: Alexeis 18.5.2009, 09:36

5 Мб это много для проца, а не для ОЗУ. Нужно создать огромное количество мелких объектов и выделить память под кучу строк. Сама операция создание маленького объекта или строки весьма медленная.

Автор: xvr 18.5.2009, 16:16

Можно сделать trie дерево на switch'ах. Скорость будет максимальная, но вручную это писать - проще сразу застрелится

Автор: T0ohtik 18.5.2009, 21:40

Цитата(azesmcar @ 15.5.2009,  22:50) Цитата(T0ohtik @  15.5.2009,  22:47 ) Уже возникала такая идея...smile  А каким образом можно посчитать когда оптимально использовать хэш таблицу? В моем случае примерно до 20 тэгов.  вам скорость нужна или красота кода? т.е. чем вы недовольны на данный момент? Ранее был не доволен скоростью, да и в принципе и красотой. Но "ларчик то просто открывался" В тестовом примере я использовал 2мб XML на компе MAC OS она распрасивалась за 2 минуты, при этом очень сильно нагружая проц. Далее было решено использовать NSDictionary - это аналог std::map, реализован он путем хэш функции. Время парсинга уменьшился примерное на 10 сек. Но перед уходом, я решил немного почистить код и убрал функцию логирования в консоль распрасеных строк и о чудо, XML'ка начала парсится примерно за 10 секунд Вот такая оптимизация вышла. И код красивый и поиск быстрый. Всем спасибо кто ответил.

Автор: nikitos1980 10.7.2009, 12:40

T0ohtik, Скажи пожалуйста, где ты качал исходники (проект) для компиляции libxml? Я скачал дистрибутив, но не могу скомпилить,файлов не хватает: ustring.h, config.h... ustring нашел а дальше все посыпалось... Если можешь, кинь мне проект для libxml или пни ссылкой Спасибо

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)