![]() |
Модераторы: Daevaorn |
![]() ![]() ![]() |
|
T0ohtik |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 115 Регистрация: 9.2.2008 Репутация: нет Всего: 1 |
Надо распарсить большую XML порядка 5 метров. Для парсинга использую SAX парсер из libxml. На данный момент не удовлетворяет качество написанного кода, а именно большой свич, который перебирает все возможные теги. Посему возник вопрос, может лучше заменить свич на карту, ключем которой будет имя тэга, а хранимым объектом - вызов функции? Как это скажется на производительность?
|
|||
|
||||
azesmcar |
|
|||
![]() uploading... ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 81 Всего: 211 |
Каким образом? Я имею ввиду что switch в С++ со строками не работает. Как именно написан switch?
положительно (во всяком случае не отрицательно) ![]() Это сообщение отредактировал(а) azesmcar - 15.5.2009, 21:55 |
|||
|
||||
T0ohtik |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 115 Регистрация: 9.2.2008 Репутация: нет Всего: 1 |
Вообще то я не С++ использую, а Objective - C. Ну и не совсем свич, а конструкцию else if. Мне кажется вопрос более по технике программирования а не по технологии. Будут ли красивые, высокоуровневые конструкции работать быстрее чем низкоуровневые не красивые?
|
|||
|
||||
azesmcar |
|
||||||
![]() uploading... ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 81 Всего: 211 |
else if? тут вообще думать не очем ![]()
switch - может быть оптимизирован в таблицу переходов, он может работать намного быстрее if если все правильно написать. Но if - это тупое средство проверки. Быстрым его никак не назовешь..он работает так - как написан. Мап - контейнер созданный для быстрого нахождения элемента с логаритмической сложностью поиска. If - для сравнения
имеет линейную сложность, так как если к примеру а == 3, то он пройдет все 3 проверки прежде чем найдет нужное условие. Добавлено через 1 минуту и 37 секунд T0ohtik В случае мапа - единственное что вы потеряете - немного скорости на вызовы функции, но приобретете намного больше на поиске + красота кода. Добавлено через 3 минуты и 47 секунд T0ohtik в некоторых ситуациях - смотря какие теги, можно было бы вообще убрать поиск и сделать его скорость константным..короче тут уже все зависит от конкретной задачи |
||||||
|
|||||||
T0ohtik |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 115 Регистрация: 9.2.2008 Репутация: нет Всего: 1 |
с этого примера поподробнее. Хочу пример! |
|||
|
||||
Alexeis |
|
|||
![]() Амеба ![]() Профиль Группа: Админ Сообщений: 11743 Регистрация: 12.10.2005 Где: Зеленоград Репутация: 12 Всего: 459 |
Если теги отсортировать в алфавитном порядке, то можно осуществить бинарный поиск, что намного эффективнее.
-------------------- Vit вечная память. Обсуждение действий администрации форума производятся только в этом форуме гениальность идеи состоит в том, что ее невозможно придумать |
|||
|
||||
Lazin |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 3820 Регистрация: 11.12.2006 Где: paranoid oil empi re Репутация: 41 Всего: 154 |
конструкция if () .. else if () ... else ... - время поиска - O(N), константа небольшая поиск в бинарном дереве, зависит от того, как оно сбалансировано, если оно сбалансировано хорошо, то время поиска O(ln N), константа - больше чем в первом случае поиск в хэш таблице, зависит от количества колизий, в принципе, можно считать, что время поиска постоянно, константа зависит от реализации и она выше чем в первых двух случаях, так как нужно вычислить хэш строки вывод, в случае небольшого количества тэгов можно применить цепочку if else if.. или здоровых switch, в случае если тэгов просто много, то нужно использовать бинарное дерево поиска, если их очень много, то хэш таблицу |
|||
|
||||
Alexeis |
|
|||
![]() Амеба ![]() Профиль Группа: Админ Сообщений: 11743 Регистрация: 12.10.2005 Где: Зеленоград Репутация: 12 Всего: 459 |
Сделать массив имен тегов и определять выше или ниже по списку нужный нам тег. Каждый раз "делить" список пополам, как в методе решения уравнения, только функцией будет строка, а аргументом ее индекс в массиве.
-------------------- Vit вечная память. Обсуждение действий администрации форума производятся только в этом форуме гениальность идеи состоит в том, что ее невозможно придумать |
|||
|
||||
azesmcar |
|
|||
![]() uploading... ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 81 Всего: 211 |
самый примитивный
допустим у нас есть теги html body head суммируем их ASCII коды. html=437 body=430 head=402 максимальный 437
например что-то типа этого, разумеется это не идеальный пример для подражания ![]() я бы честно говоря много раз подумал прежде чем избрать подобный подход. проблематично для будущего, и память жрет, да и все равно сумму символов считать придется. тут на мой взгляд лучшее решение - хэш таблица. Это сообщение отредактировал(а) azesmcar - 15.5.2009, 22:36 |
|||
|
||||
Lazin |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 3820 Регистрация: 11.12.2006 Где: paranoid oil empi re Репутация: 41 Всего: 154 |
еще один вариант(довольно тупой, но может работать), определить какие тэги встречаются чаще других, если к примеру несколько тэгов встречается намного чаще других(к примеру их доля - 80% от всех используемых тэгов) то можно их разместить в начале цепочки if-ов, а все остальные - в порядки частоты встречаемости
правда это будет работать только если в частоте встречаемости тэгов есть закономероность... |
|||
|
||||
T0ohtik |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 115 Регистрация: 9.2.2008 Репутация: нет Всего: 1 |
Уже возникала такая идея... ![]() А каким образом можно посчитать когда оптимально использовать хэш таблицу? В моем случае примерно до 20 тэгов. |
|||
|
||||
azesmcar |
|
|||
![]() uploading... ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 81 Всего: 211 |
вам скорость нужна или красота кода? т.е. чем вы недовольны на данный момент? Это сообщение отредактировал(а) azesmcar - 15.5.2009, 22:50 |
|||
|
||||
math64 |
|
|||
Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 2505 Регистрация: 12.4.2007 Репутация: 8 Всего: 72 |
Можно для конкретного случая подобрать hash-функцию, которая будет выдавать разные значения для разных элементов, но неправильные элементы тоже будут выдавать совпадающие коды, нужно использовать добавочную проверку.
|
|||
|
||||
Andrey44 |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1501 Регистрация: 4.12.2006 Где: На работе Репутация: 2 Всего: 26 |
T0ohtik, можно еще использовать IXMLDOMDocument, IXMLDOMNode, IXMLDOM........
В общем их много и довольно просты в использовании. А если применять к тому-же xPath, то все вообще становится довольно просто. Это сугубо мое личное мнение. ![]() -------------------- ????? ??, ??????? ?????. ![]() |
|||
|
||||
Lazin |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 3820 Регистрация: 11.12.2006 Где: paranoid oil empi re Репутация: 41 Всего: 154 |
да уж...
очевидно, что ТС хочет обрабатывать документ по частям не загружая его в память целиком... |
|||
|
||||
![]() ![]() ![]() |
Правила форума "С++:Общие вопросы" | |
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |