Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Парсинг XML 
:(
    Опции темы
T0ohtik
Дата 15.5.2009, 21:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 115
Регистрация: 9.2.2008

Репутация: нет
Всего: 1



Надо распарсить большую XML порядка 5 метров. Для парсинга использую SAX парсер из libxml. На данный момент не удовлетворяет качество написанного кода, а именно большой свич, который перебирает все возможные теги. Посему возник вопрос, может лучше заменить свич на карту, ключем которой будет имя тэга, а хранимым объектом - вызов функции? Как это скажется на производительность?
PM MAIL   Вверх
azesmcar
Дата 15.5.2009, 21:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211



Цитата(T0ohtik @  15.5.2009,  21:43 Найти цитируемый пост)
а именно большой свич, который перебирает все возможные теги

Каким образом? Я имею ввиду что switch в С++ со строками не работает. Как именно написан switch?

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

положительно (во всяком случае не отрицательно) smile у map -а логаритмический поиск. Хотя вы можете и не заметить если тагов не очень много

Это сообщение отредактировал(а) azesmcar - 15.5.2009, 21:55
PM   Вверх
T0ohtik
Дата 15.5.2009, 22:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 115
Регистрация: 9.2.2008

Репутация: нет
Всего: 1



Вообще то я не С++ использую, а Objective - C. Ну и не совсем свич, а конструкцию else if. Мне кажется вопрос более по технике программирования а не по технологии. Будут ли красивые, высокоуровневые конструкции работать быстрее чем низкоуровневые не красивые?
PM MAIL   Вверх
azesmcar
Дата 15.5.2009, 22:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211



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

else if? тут вообще думать не очем smile 

Цитата(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

в некоторых ситуациях - смотря какие теги, можно было бы вообще убрать поиск и сделать его скорость константным..короче тут уже все зависит от конкретной задачи
PM   Вверх
T0ohtik
Дата 15.5.2009, 22:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 115
Регистрация: 9.2.2008

Репутация: нет
Всего: 1



Цитата

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


с этого примера поподробнее. Хочу пример!
PM MAIL   Вверх
Alexeis
Дата 15.5.2009, 22:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 12
Всего: 459



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


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
Lazin
Дата 15.5.2009, 22:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154



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

конструкция if () .. else if () ... else ... - время поиска - O(N), константа небольшая
поиск в бинарном дереве, зависит от того, как оно сбалансировано, если оно сбалансировано хорошо, то время поиска O(ln N), константа - больше чем в первом случае
поиск в хэш таблице, зависит от количества колизий, в принципе, можно считать, что время поиска постоянно, константа зависит от реализации и она выше чем в первых двух случаях, так как нужно вычислить хэш строки

вывод, в случае небольшого количества тэгов можно применить цепочку if else if.. или здоровых switch, в случае если тэгов просто много, то нужно использовать бинарное дерево поиска, если их очень много, то хэш таблицу
PM MAIL Skype GTalk   Вверх
Alexeis
Дата 15.5.2009, 22:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 12
Всего: 459



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


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
azesmcar
Дата 15.5.2009, 22:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211



самый примитивный
допустим у нас есть теги
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;

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

тут на мой взгляд лучшее решение - хэш таблица.

Это сообщение отредактировал(а) azesmcar - 15.5.2009, 22:36
PM   Вверх
Lazin
Дата 15.5.2009, 22:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154



еще один вариант(довольно тупой, но может работать), определить какие тэги встречаются чаще других, если к примеру несколько тэгов встречается намного чаще других(к примеру их доля - 80% от всех используемых тэгов) то можно их разместить в начале цепочки if-ов, а все остальные - в порядки частоты встречаемости
правда это будет работать только если в частоте встречаемости тэгов есть закономероность...
PM MAIL Skype GTalk   Вверх
T0ohtik
Дата 15.5.2009, 22:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 115
Регистрация: 9.2.2008

Репутация: нет
Всего: 1



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

Уже возникала такая идея...smile 
А каким образом можно посчитать когда оптимально использовать хэш таблицу? В моем случае примерно до 20 тэгов.
PM MAIL   Вверх
azesmcar
Дата 15.5.2009, 22:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211



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

вам скорость нужна или красота кода? т.е. чем вы недовольны на данный момент?

Это сообщение отредактировал(а) azesmcar - 15.5.2009, 22:50
PM   Вверх
math64
Дата 16.5.2009, 00:24 (ссылка)  | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72



Можно для конкретного случая подобрать 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:
}

PM   Вверх
Andrey44
Дата 18.5.2009, 07:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1501
Регистрация: 4.12.2006
Где: На работе

Репутация: 2
Всего: 26



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


--------------------
????? ??, ??????? ?????.  smile 
PM MAIL WWW ICQ   Вверх
Lazin
Дата 18.5.2009, 08:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154



Цитата(Andrey44 @  18.5.2009,  07:51 Найти цитируемый пост)
T0ohtik, можно еще использовать IXMLDOMDocument, IXMLDOMNode, IXMLDOM........
В общем их много и довольно просты в использовании.
А если применять к тому-же xPath, то все вообще становится довольно просто.
Это сугубо мое личное мнение. 

да уж...
Цитата(T0ohtik @  15.5.2009,  21:43 Найти цитируемый пост)
Надо распарсить большую XML порядка 5 метров. Для парсинга использую SAX парсер из libxml.

очевидно, что ТС хочет обрабатывать документ по частям не загружая его в память целиком... 
PM MAIL Skype GTalk   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »


 




[ Время генерации скрипта: 0.0969 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.