java에서 백만 단어 목록에있는 하위 문자열 수를 얻으려고합니다. 이전 값에 다음 값이 포함되어 있는지 확인하기 위해 각 문자열을 루핑하여 성능에 큰 문제가있는 것 같습니다. 적은 수의 단어로도 잘 작동하지만 백만 단어의 거대한 목록이 포함될 때 카운트를 되 찾는 데는 시간이 걸립니다. 누군가가 나에게 이것에 대한 가장 빠른 접근법을 말할 수 있습니까?백만 단어 목록에서 부분 문자열 수 얻기
2N 시간에 얻을 수 있다고 생각합니다.
이것은 간단합니다. 하지만 어쩌면 누군가가 나아질 수 있습니다. 나는 호기심으로 기다리고있다.
순진한 해결책은 Set에 모든 하위 문자열을 삽입 한 다음 해당 세트의 크기를 확인하는 것입니다.
너무 느리거나 너무 많은 메모리를 소비하는 경우 맞춤형 데이터 유형 (예 : 균형 잡힌 문자 트리)이 더 빠를 수 있습니다.
약 1 억 개의 하위 문자열이있는 트리가 32 비트 jvm에 저장할 수 있습니다.
보다 큰 데이터 세트의 경우 해시 체질 알고리즘이 메모리 솔루션에 대해 조금 더 나아갈 수 있습니다.
괜찮은 데이터베이스 또는 데이터 저장소를 사용하여 하위 문자열을 인덱싱하고 저장할 수 있습니다. 당신이 유닉스 또는 리눅스를 사용하는 경우
은, 모든 문자열을 생성하는 프로그램을 작성하기 위해 충분하다, 사실 .. 또한
몇 개의 파일과 전혀 거의 메모리를 사용하는 모든 문자열을 정렬 할 수 있습니다 external sort algorithms 있습니다 sort -q 및 wc을 통해 파이프하면 아마 더 빨리 그리고 거의 코딩 할 필요없이 대답을 얻을 수 있습니다. 하지만 그것이 내가 생각한 실험실을 통과하지 못하게 할 것입니다.
찾고있는 것을 보여줄 수 있습니까? 성능 문제를 나타내는 코드도 함께 제시하십시오. – Behe
'이전 값에 다음 값이 들어있는 경우 '예제를 제공하십시오 –
이 부분 문자열이 입력에 주어 졌는가 또는 아마도 문자열의 공통 부분을, 아마도 세트에서 찾은 것 같습니까? – Cromax