XML 파서 / 유효성 검사기의 알고리즘 복잡성

StackOverflow https://stackoverflow.com/questions/31826

  •  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 모델에서 문서의 메모리 공간에 비례해야 함). 서로 다른 색상은 서로 다른 종류의 문서에 해당합니다. 척도는 로그 / 로그입니다. 검은 색 선이 파란색 점에 가장 잘 맞습니다. 모든 종류의 문서에서 바이트 크기와 노드 크기 사이의 관계는 선형 적이지만 비례 계수는 매우 다를 수 있습니다.

benchmarks-bytes_vs_nodes

도움이 되었습니까?

해결책

내가 그 문제에 직면했고 Google에서 아무것도 찾을 수 없다면 아마도 내가 직접 시도 할 것입니다.

어디로 가는지에 대한 느낌을 얻을 수있는 일부 "이전 뒤편"항목입니다.그러나 XML 파서를 수행하는 방법에 대한 아이디어가 필요합니다. 비 알고리즘 벤치 마크의 경우 여기를 참조하세요.

다른 팁

많은 가정을하지 않는 한 단순한 복잡성 측정 항목을 만들기에는 너무 많은 변수가 관련되어 있다고 생각합니다.

간단한 SAX 스타일 파서는 문서 크기 측면에서 선형이어야하고 메모리 측면에서 평평해야합니다.

XPath 표현의 복잡성이 큰 역할을하기 때문에 XPath와 같은 것은 입력 문서의 관점에서 설명하기가 불가능합니다.

스키마 유효성 검사와 마찬가지로 크고 단순한 스키마는 선형적일 수있는 반면 훨씬 복잡한 구조를 가진 작은 스키마는 더 나쁜 런타임 성능을 보여줍니다.

대부분의 성능 질문과 마찬가지로 정확한 답을 얻는 유일한 방법은 측정하고 어떤 일이 발생하는지 확인하는 것입니다.

Rob Walker의 말이 맞습니다. 문제가 충분히 상세하게 지정되지 않았습니다.파서 만 고려하면 (그리고 유효성 검사를 수행하는지에 대한 질문을 무시하고) 두 가지 주요 특징이 있습니다. 트리 기반 (DOM을 생각하고 스트리밍 / 이벤트 기반)은 SAX (푸시) 및 StAX (당기기).매우 일반적으로 말하면 트리 기반 접근 방식은 더 많은 메모리를 사용하고 더 느립니다 (전체 문서 구문 분석을 완료해야하기 때문에). 반면 스트리밍 / 이벤트 기반 접근 방식은 메모리를 덜 사용하고 더 빠릅니다.트리 기반 파서는 일반적으로 사용하기 더 쉬운 것으로 간주되지만 StAX는 SAX에 비해 (사용 편의성 측면에서) 크게 개선 된 것으로 알려졌습니다.

내 응용 프로그램에 매우 큰 XML 파일을로드 할 계획이었습니다.Stack Overflow에 대한 질문 : 가능한 가장 빠른 XML매우 큰 문서 처리 .

그렇습니다. 파싱 부분이 병목 현상이었습니다.

결국 XML 파서를 전혀 사용하지 않았습니다.대신 속도 최적화를 위해 가능한 한 효율적으로 문자를 하나씩 구문 분석했습니다.그 결과 3GHz Windows PC에서 내부 데이터 구조의 읽기, 구문 분석 및로드를 위해 초당 40MB의 속도가 발생했습니다.

다양한 XML 파싱 모드가 이것과 어떻게 비교되는지 듣고 싶습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top