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

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


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

Это сообщение отредактировал(а) azesmcar - 15.5.2009, 21:55

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

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


switch - может быть оптимизирован в таблицу переходов, он может работать намного быстрее if если все правильно написать. Но if - это тупое средство проверки. Быстрым его никак не назовешь..он работает так - как написан. Мап - контейнер созданный для быстрого нахождения элемента с логаритмической сложностью поиска. If - для сравнения

имеет линейную сложность, так как если к примеру а == 3, то он пройдет все 3 проверки прежде чем найдет нужное условие.

Добавлено через 1 минуту и 37 секунд
T0ohtik

В случае мапа - единственное что вы потеряете - немного скорости на вызовы функции, но приобретете намного больше на поиске + красота кода.

Добавлено через 3 минуты и 47 секунд
T0ohtik

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

с этого примера поподробнее. Хочу пример!

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

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

вывод, в случае небольшого количества тэгов можно применить цепочку if else if.. или здоровых switch, в случае если тэгов просто много, то нужно использовать бинарное дерево поиска, если их очень много, то хэш таблицу

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

самый примитивный
допустим у нас есть теги
html
body
head

суммируем их ASCII коды.

html=437
body=430
head=402

максимальный 437

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

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

Это сообщение отредактировал(а) azesmcar - 15.5.2009, 22:36

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

Уже возникала такая идея... 
А каким образом можно посчитать когда оптимально использовать хэш таблицу? В моем случае примерно до 20 тэгов.

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

Это сообщение отредактировал(а) azesmcar - 15.5.2009, 22:50

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

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

да уж...

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