XML 파서 / 유효성 검사기의 알고리즘 복잡성
-
09-06-2019 - |
문제
입력 문서의 크기와 복잡성이 다양한 XML 도구 (파서, 유효성 검사기, XPath 표현식 평가 기 등)의 성능에 어떤 영향을 미치는지 알아야합니다. CPU 시간과 메모리 사용량이 어떻게 영향을 받는지 문서화 한 리소스가 있습니까? 문서 크기 (바이트)? 노드 수? 그리고 관계가 선형, 다항식 또는 더 나쁜가요?
업데이트
2008 년 9 월 IEEE Computer Magazine, vol 41 nr 9의 기사에서 저자는 4 개의 인기있는 XML 구문 분석 모델 (DOM, SAX, StAX 및 VTD)을 조사했습니다. 그들은 입력 파일의 크기가 1-15KB에서 1-15MB로 또는 약 1000 배 더 커질 때 DOM 파서의 처리량이 절반으로 줄어드는 매우 기본적인 성능 테스트를 실행합니다. 다른 모델의 처리량은 크게 영향을받지 않습니다.
안타깝게도 노드 수 / 크기에 따른 처리량 / 메모리 사용량과 같은 자세한 연구는 수행하지 않았습니다.
기사는 여기 입니다.
업데이트
이 문제에 대한 공식적인 치료법을 찾을 수 없었습니다. 그만한 가치가있는 것은 문서 크기 (바이트)의 함수로 XML 문서의 노드 수를 측정하는 몇 가지 실험을 수행했습니다. 저는 창고 관리 시스템에서 일하고 있으며 XML 문서는 일반적인 창고 문서입니다. 사전 배송 통지 등
아래 그래프는 바이트 단위의 크기와 노드 수 사이의 관계를 보여줍니다 (DOM 모델에서 문서의 메모리 공간에 비례해야 함). 서로 다른 색상은 서로 다른 종류의 문서에 해당합니다. 척도는 로그 / 로그입니다. 검은 색 선이 파란색 점에 가장 잘 맞습니다. 모든 종류의 문서에서 바이트 크기와 노드 크기 사이의 관계는 선형 적이지만 비례 계수는 매우 다를 수 있습니다.
해결책
내가 그 문제에 직면했고 Google에서 아무것도 찾을 수 없다면 아마도 내가 직접 시도 할 것입니다.
어디로 가는지에 대한 느낌을 얻을 수있는 일부 "이전 뒤편"항목입니다.그러나 XML 파서를 수행하는 방법에 대한 아이디어가 필요합니다. 비 알고리즘 벤치 마크의 경우 여기를 참조하세요.
다른 팁
많은 가정을하지 않는 한 단순한 복잡성 측정 항목을 만들기에는 너무 많은 변수가 관련되어 있다고 생각합니다.
간단한 SAX 스타일 파서는 문서 크기 측면에서 선형이어야하고 메모리 측면에서 평평해야합니다.
XPath 표현의 복잡성이 큰 역할을하기 때문에 XPath와 같은 것은 입력 문서의 관점에서 설명하기가 불가능합니다.
스키마 유효성 검사와 마찬가지로 크고 단순한 스키마는 선형적일 수있는 반면 훨씬 복잡한 구조를 가진 작은 스키마는 더 나쁜 런타임 성능을 보여줍니다.
대부분의 성능 질문과 마찬가지로 정확한 답을 얻는 유일한 방법은 측정하고 어떤 일이 발생하는지 확인하는 것입니다.
Rob Walker의 말이 맞습니다. 문제가 충분히 상세하게 지정되지 않았습니다.파서 만 고려하면 (그리고 유효성 검사를 수행하는지에 대한 질문을 무시하고) 두 가지 주요 특징이 있습니다. 트리 기반 (DOM을 생각하고 스트리밍 / 이벤트 기반)은 SAX (푸시) 및 StAX (당기기).매우 일반적으로 말하면 트리 기반 접근 방식은 더 많은 메모리를 사용하고 더 느립니다 (전체 문서 구문 분석을 완료해야하기 때문에). 반면 스트리밍 / 이벤트 기반 접근 방식은 메모리를 덜 사용하고 더 빠릅니다.트리 기반 파서는 일반적으로 사용하기 더 쉬운 것으로 간주되지만 StAX는 SAX에 비해 (사용 편의성 측면에서) 크게 개선 된 것으로 알려졌습니다.
내 응용 프로그램에 매우 큰 XML 파일을로드 할 계획이었습니다.Stack Overflow에 대한 질문 : 가능한 가장 빠른 XML매우 큰 문서 처리 .
그렇습니다. 파싱 부분이 병목 현상이었습니다.
결국 XML 파서를 전혀 사용하지 않았습니다.대신 속도 최적화를 위해 가능한 한 효율적으로 문자를 하나씩 구문 분석했습니다.그 결과 3GHz Windows PC에서 내부 데이터 구조의 읽기, 구문 분석 및로드를 위해 초당 40MB의 속도가 발생했습니다.
다양한 XML 파싱 모드가 이것과 어떻게 비교되는지 듣고 싶습니다.