java - 如何提高大量的字符串比较速度

Answer 1

아이디어 쓰기

으아악

귀하의 데이터는 실제로 매우 고유하므로 여기에서 간소화할 수 있습니다.
모든 문자열의 길이는 20자이고 ATCG 4자로 구성되어 있기 때문입니다. 그런 다음 비교를 위해 정수로 변환할 수 있습니다.
바이너리 표현은 다음과 같습니다

으아악

문자열의 길이는 고정되어 있고 각 문자는 2비트로 표현될 수 있으므로 각 문자열은 40비트 정수로 표현될 수 있습니다. 32+8 형태로 표현할 수도 있고, 64 비트 쉐이핑을 직접 사용할 수도 있습니다. 이를 위해서는 C 언어를 사용하는 것이 좋습니다.

비교에 대해 이야기해보겠습니다.
每一个candidate在bg_db中与之差异小于等于4的所有记录을 찾아야 하기 때문에 두 정수에 대해 ^ 비트 XOR 연산을 수행하는 한 결과 二进制中1不超过8个,且这不超过8个1最多只能分为4个组는 요구 사항(00^11 =11)을 충족할 수 있습니다. ,10^01=11).
결과의 40 비트를 20개의 그룹으로 나눕니다. 즉, 세 가지 값을 가진 그룹은 최대 4개 ​​b01 b10 b11이고 나머지는 모두 b00 .
그러면 비교 알고리즘을 작성하기 쉽습니다.
각 바이트(4개 그룹)에 대해 0이 아닌 3개의 값으로 구성된 여러 그룹을 얻어서 전체 비교 결과를 간략하게 얻을 수 있습니다.
각 바이트에 대해 256개의 가능한 값 ​​만 있고, 3^4=81종류의 한정된 값 ​​만 있기 때문에 결과를 먼저 저장한 다음 검색할 수 있습니다.
결과에 0이 아닌 그룹이 몇 개 있는지 구하는 함수는 다음과 같습니다.

으아악

Answer 2

우선, 예상 시간이 완전히 틀렸습니다. 이런 종류의 대규모 데이터 처리는 수만 개의 항목을 실행하고 10초 이상 지속되어야 총 시간을 계산하는 곱셈에 사용될 수 있습니다. 항목 하나만 계산하면 이 시간은 중요한 IO 및 CPU 오버헤드가 아닌 거의 초기화 프로세스의 오버헤드입니다

다음 본문

ACTG의 4가지 가능성은 2비트에 해당합니다. 하나의 문자를 사용하여 하나의 유전자 위치를 나타내기에는 너무 낭비입니다.

아무 알고리즘도 사용하지 않고 유전자 20개만 바이너리 형식으로 작성해도 시간을 5배 절약할 수 있습니다

그리고 20번 반복한 결과 CPU 명령어 개수는 20*n이고, n은 최소 3개 이상으로 추정됩니다. 하지만 바이너리의 경우 비교를 위한 XOR 연산은 바로 CPU 명령어이고, 지시사항은 1입니다

Answer 3

알고리즘에 대해 잘 모르지만, 경험상 복잡한 알고리즘은 이 단순하고 투박한 알고리즘만큼 시간도 오래 걸리고 빠르지도 않습니다

데이터 처리를 위해 멀티스레딩과 클러스터링을 고려할 수 있습니다

그런데 해밍 거리도 계산이 가능한 것 같습니다

Answer 4

또한 알고리즘이 사용되지 않으며 C로 작성된 무차별 솔루션입니다

내 컴퓨터(CPU: Core 2 Duo E7500, RAM: 4G, OS: Fedora 19)에서 테스트 결과

으아악

대상의 24코어 CPU로 전환하면 성능이 20배 향상되고, 48대를 추가해 함께 작동하면 5000W 연산에 15초가 걸리며, 시간은
10000000 * 1000000000이 됩니다. / 500 / 1000000 * 15 / 20 / 48 / 3600 / 24 = 3.616898일

으아악

매개변수 컴파일 및 실행

으아악

멀티스레딩으로 변경하면 속도가 빨라집니다. 제 컴퓨터에서는 2 스레드로 변경하고 간단히 500条candidates를 사용하여 9040257微秒로 속도를 높일 수 있습니다. 스레드 수를 4으로 늘리면 성능이 크게 향상되지는 않지만 최신 CPU에는 하이퍼스레딩 기술이 적용되어 속도가 더 좋아질 것으로 예상됩니다. . .

으아악

컴파일 및 테스트

으아악

Answer 5

죄송합니다. 오늘 다른 분이 답글을 다는 걸 봤어요.
질문을 자세히 살펴보니 그냥 일치하는 줄로만 알았습니다.
그래서 저는 AC자동기계를 사용하자고 제안했습니다.

그러나 질문의 ​​목적은 시퀀스의 차이점을 찾는 것입니다.
둘 사이의 편집 거리를 찾는 것입니다.
위키: 거리 편집
위키: Ravenstein 거리

저는 OJ를 브러싱할 때 DP(동적 프로그래밍)를 사용하여 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 횟수를 찾았습니다.

으아악

예:

으아악

str2가 str1로 변환됩니다

b 삽입 한 번 계산
d 삭제 한 번 계산
f 수정 한 번 계산

피험자의 ATCG 유전자 서열은 변형된 것만 찾으면 되나요?
그런데
ATCGATCG
TCGATCGA
는 어떻게 계산해야 할까요?

수정 사항만 찾은 경우 str1[i]와 str2[i]를 직접 비교하세요.

으아악

@rockford에서 영감을 받았습니다.
원시 데이터를 전처리할 수 있습니다.

후보 문자열
GGGAGCAGGCAAGGACTCTG
A5 T2 C4 G9

A5 T2 C4 G9 처리 후 추가 데이터

bg_db의 문자열
CTGCTGACGGGTGACACCCA
A4 T3 C7 G6

A4 T3 C7 G6 처리 후 추가 데이터

A5 -> A4는 -1로 기록됩니다.
T2 -> T3은 +1로 기록됩니다.
C4 -> C7은 +3으로 기록됩니다.
G9 -> -3

분명히 A는 수정된 경우에만 TCG가 될 수 있습니다.
마찬가지로 모두 + 또는 모두 -
만 계산하면 최소한 얼마나 많은 차이가 있는지 알 수 있습니다.
4보다 큰 것은 비교할 필요가 없습니다.

먼저 전처리된 추가 데이터를 비교한 후 단일 비교 알고리즘을 통해 비교를 수행합니다.
(토요일 야근, 퇴근 후 글쓰기)

Answer 6

개별 작업이 결정됩니다. 이러한 작업을 작업자에게 보내는 것은 단일 프로세스에서 동시에 수행되지 않습니다.
사실, 비교하기 위해 [a, b]와 [c, d]를 갖는 것과 같습니다. 귀하의 작업은

1. [a, c]

2. [a, d]

3. [b, c]

4. [b, d]

동기식 직렬인 경우 필요한 시간은 4 * 단일 시간
4개의 CPU 또는 4개의 머신이 병렬인 경우 필요한 시간은 거의 단일 시간입니다.

그래서 게놈과 같은 계산은 기본적으로 대규모 머신에서 멀티 코어 병렬 작업을 사용하여 수행됩니다. 기본적으로 참조 원리는 Google MapReduce 논문의 원리입니다.

Answer 7

나는 알고리즘을 잘 모르지만, 당신처럼 많은 양의 데이터를 가지고 있어서 한 대의 컴퓨터와 비교하는 것은 절대 불가능합니다. 즉, map-reduce 모델을 사용하여 계산합니다.
map은 먼저 각 후보를 bg_db에 하나씩 매핑하여 다음과 같은 데이터 구조를 형성합니다(candidates,bg_db)
대기열에 넣은 다음 이를 다른 서버에 전달합니다. 각 서버는 여러 프로세스를 사용하여 계산합니다. 이것이 유일한 방법이지만 데이터 양이 너무 크므로 작업을 할당하고 병렬로 계산하는 방법을 찾으십시오. ,

Answer 8

사전 트리를 사용하여 모든 문자열을 저장할 수 있습니다. 그런 다음 쿼리할 때 사전 트리를 순회하는 방법을 사용할 수 있습니다.
트리를 순회할 때 현재 노드의 시퀀스를 유지할 수 있습니다. 이 시퀀스는 현재 순회하는 노드와 해당 노드 간의 불일치 수를 저장합니다.
다음 노드를 순회할 때 현재 시퀀스의 모든 노드를 아래로 내려가 새로운 노드 시퀀스를 형성해 보세요.
많은 문자열의 현재 비트를 함께 비교할 수 있어 시간을 절약할 수 있다는 장점이 있습니다. 각 위치별로 선택의 여지가 많지 않고 불일치도 크지 않기 때문에 현재 노드 시퀀스를 과도하게 확장해서는 안 됩니다. (추측입니다..너무 꼼꼼히 확인은 안해봤습니다...)

으아악

위 코드는 대략적인 아이디어입니다. C++로 작성하면 훨씬 빠릅니다.
전체 프로세스는 분산 컴퓨팅용 클러스터를 사용하여 수행할 수 있습니다.

Answer 9

질문자는 시각적으로 계산할 수 있는 여러 대의 기계를 가지고 있지 않습니다.
각 문자열의 알파벳 숫자의 합(A:0,T:1,C:2,G:)을 계산하는 간단한 아이디어가 있습니다. 3) 먼저 두 문자열의 순서합의 차이를 계산합니다. 최대값은 12를 초과할 수 없습니다. 4개의 A가 4개의 G가 됩니다. 차이가 12보다 작으면
은 대략적인 생각입니다. 추가 설정을 사용하면 이론적으로 훨씬 더 빨라질 수 있습니다.
문자열 편집 거리(한 문자열을 다른 문자열에 추가, 삭제, 수정하는 최소 편집 횟수)를 계산하는 또 다른 알고리즘이 있습니다. 현재로서는 직접 확인할 수 없습니다.

Answer 10

나는 blastn-short를 사용한다

:)