0
어떻게 cstring이 함수보다 빠릅니까? C와 비슷한 소스인가?string :: find()에 의해 사용 된 문자열 검색 알고리즘 C++
A
답변
3
C++ 표준 라이브러리의 표준 구현은 없지만 컴파일러와 함께 제공되는 구현을 살펴보고 어떻게 작동하는지 직접 확인할 수 있어야합니다.
일반적으로 대부분의 STL 기능은 C 코드보다 빠르지 않습니다. 일반적으로 더 안전하고, 일반화되고, 범용 C 범용보다 훨씬 더 넓은 범위의 상황을 수용하도록 설계되었습니다.
+3
펑터를 사용하는 STL 함수는 일반적으로 함수 포인터를 사용하는 C보다 빠릅니다. 예를 들어'std :: sort'와'std :: binary_search'는 C의 표준 라이브러리에 포함 된'qsort'와'bsearch'보다 상당히 빠릅니다. –
+2
STL의 "close-source binary"버전은 없습니다. 아무도 수출 가능한 템플릿을 구현하지 않았습니다. 누구나 STL 구현을위한 소스 코드를 제공해야합니다. Dinkumware 포함. –
+0
잘 알고 있습니다. 그에 따라 답변을 편집했습니다. Comeau C++에는 내보낼 수있는 템플릿이 있습니까? 나는 그것을 실제로 구현 한 유일한 컴파일러라고 생각했다. –
1
모든 문자열 클래스의 표준 최적화는 문자열 길이와 함께 문자열 길이를 저장하는 것입니다. 어떤 문자열 작업을 O (n) 대신 O (1), strlen()이 분명하다는 것을 알고 문자열 길이가 필요합니다.
문자열을 복사하면 실제 복사본에는 아무런 효과가 없지만 복사본이 O (1) 개가되기 전에 할당 할 메모리 양을 알아낼 수 있습니다. 전체 알고리즘은 여전히 O (n)입니다. 기본 작업은 여전히 동일하며, 셔블 바이트는 모든 언어 에서처럼 오래 걸립니다.
문자열 클래스는 안전하고 (발을 쏠 어렵게) 사용하기 쉽고 (명시 적 코드가 덜 필요하기 때문에) 유용합니다. 그들은 느리게되지 않았기 때문에 대중적으로 널리 사용되었습니다.
0
문자열 클래스는 C 문자열에서보다 훨씬 많은 문자열 데이터를 저장합니다. 길이가 좋은 예입니다. 여분의 메모리 사용에 대한 절충안으로, 여분의 CPU 사이클을 확보하게됩니다.
편집 : 그러나 근본적으로 동일한 작업을 수행 할 것이므로 하나가 다른 것보다 상당히 느리지는 않습니다. MSDN은 string :: find()가 Functor 기반 시스템을 사용하지 않기 때문에 최적화를하지 않을 것이라고 제안합니다.
0
찾기 문자열 기술을 구현하는 방법에는 여러 가지가 있습니다. 가장 쉬운 방법은 검색 문자열이 있으면 대상 문자열의 모든 위치를 확인하는 것입니다. 그렇게 빨리 코딩 할 수 있지만 가능한 가장 느린 코드입니다. (O (m * n), m = 길이 검색 문자열, n = 길이 대상 문자열)
위키 피 디아 페이지 http://en.wikipedia.org/wiki/String_searching_algorithm을 살펴보면 다른 옵션이 제시됩니다. 가장 빠른 방법은 유한 상태 컴퓨터를 만드는 것입니다. 그런 다음 뒤로 이동하지 않고 문자열을 삽입 할 수 있습니다. 그렇다면 단지 O (n).
STL이 실제로 사용하는 알고리즘은 무엇인지 모르겠습니다. 그러나 소스 코드를 검색하여 알고리즘과 비교할 수 있습니다.
관련 문제
- 1. Java에서 문자열 검색 알고리즘
- 2. 문자열 검색 알고리즘
- 3. 전체 텍스트 검색 알고리즘 C#
- 4. XML 검색 알고리즘 C++
- 5. C++ 문자열 유형 독립 알고리즘
- 6. lucene에서 사용하는 문자열 일치 알고리즘
- 7. DICOM 파일 검색 알고리즘 C#
- 8. LINQ, 쿼리에서 string [] 사용
- 9. C# 기본 변수 메서드에 의해 사용 된 멤버 변수 재정의
- 10. C#에서 문자열 비교를위한보다 빠른 알고리즘
- 11. 부분 문자열 알고리즘
- 12. C++ std :: string and string
- 13. 게임에서 알고리즘 검색?
- 14. <string> 및 STL이없는 C++ 문자열
- 15. 문자열 일치 알고리즘
- 16. Runtime.exec (String)에 의해 전달 된 환경 변수
- 17. 대용량 파일 검색 알고리즘
- 18. C# 용 가역 문자열 diff (기록) 알고리즘?
- 19. 문자열 발생 알고리즘 계산
- 20. objective-c string, string-formatter
- 21. 그래프 검색 알고리즘
- 22. 자바 단어 검색 알고리즘
- 23. 단어 검색 알고리즘
- 24. ActiveRecord :: Base # find에 해당하는 proxy_reflection은 무엇입니까?
- 25. 점프는 검색 알고리즘
- 26. 마샬링 문자열, C++ C 번호에 '변환이 라이브러리에 의해 지원되지 않습니다'
- 27. 다중 기준 검색 알고리즘
- 28. 하위 문자열 검색 문자열
- 29. C# : PNG 압축 알고리즘/라이브러리 검색
- 30. 즉석 검색 알고리즘
왜 더 빨리 생각하십니까? –
상대 속도를 측정하는 데 사용한 코드를 게시 할 수 있습니까? 실제로 테스트 프레임 워크에서 차이점을 보았을 수도 있고 기본 코드에서 차이점을 볼 수도 있습니다. –
C 및 C++ 라이브러리 (각각) 및 C++ 및 C 컴파일러 (각각)의 구현을 논의하지 않고도 속도에 관해 논의 할 수 없습니다. C89, C99, C++ 0x 등은 언어 구현 방법을 정의하는 표준입니다. "C"나 "C++"에 대해 이야기 할 때, 그는 일반적으로 언어를 언급하고 있으며 특정 구현은 언급하지 않습니다. 귀하의 _ 플랫폼에 대한 언급이 없으므로 귀하의 질문에 대한 답변을 시작할 수 없습니까? –