Challenge 7을 사용해 주신 분들께 감사드립니다. 기회가 없더라도 토론을 지켜봐 주시기 바랍니다. 이 문제를 어떻게 해결할 수 있습니까? 개념적으로 가장 간단한 접근 방식은 단일 문자 중복을 찾은 다음 두 문자 중복, 세 문자 등을 찾아 중복이 없을 때까지 한 문자씩 증가하는 것입니다. 주어진 길이에 대해 가능한 모든 문자열을 순진하게 검사하는 것은 하위 문자열 길이에 따라 점점 더 많은 시간이 소요됩니다. 약 30,000자 길이의 Covid-19 게놈의 경우, 4개만 있는 7자 하위 문자열 중복이 보장되지만 7 = 16,384 고유 조합, 6889개만 발생(42%). 그리고 하위 문자열이 길어짐에 따라 가능한 중복 수가 급격히 증가함에 따라 중복 수가 줄어듭니다. 이 접근 방식이 작동하려면 중복 항목을 식별하는 효율적인 방법을 찾아야 합니다. 이 문제를 해결하기 위한 다른 방법을 검토한 후 이에 대해 다시 설명하겠습니다.
모든 복제본을 찾는 것에 대해 걱정할 필요 없이 가장 긴 복제본을 찾는 데 집중합시다. 간단한 접근 방식은 하나가 있어야 하므로 7개의 문자 중복으로 첫 번째 문자에서 하위 문자열을 시작하는 것입니다. 그런 다음 중복이 없을 때까지 한 번에 한 문자씩 성장시킵니다. 다음 문자 및 더 긴 중복 하위 문자열로 이동합니다. 복제가 불가능할 정도로 검색 문자열의 끝에 충분히 가까워질 때까지 이 작업을 계속합니다. Covid-19 게놈에서 8자 하위 문자열 앗타아그 첫 번째 문자부터 빌드할 수 있습니다. 두 번째 문자로 이동, 11자 문자열 따아아그따 위치 2를 응시하면 위치 20063에 복제본이 있습니다. 위치 3에서 시작하여 11자 이상의 중복 문자가 없으므로 위치 4로 이동합니다. 등등. 아래 코드는 가장 긴 중복 문자열, 두 개의 32자 중복 문자열을 찾는 데 약 5초가 걸립니다 ㅏ 에스. 아래 코드에서 이미 발견된 가장 긴 하위 문자열과 동일한 길이의 하위 문자열에 대해 중복이 존재하는 경우, 하는 동안 종료하기 전에 적어도 한 번 더 반복합니다. 이러한 상황에서 다음렌 1씩 줄여야 합니다.
findLongestDupe = Function({inString,charSet},{parts,nextLen,nextPos=1,longestDupes={""}},
parts = Items(inString,"");
nextLen = Floor(Log(Length(inString))/Log(N Items(charSet)));
While(nextPos <= Length(inString)-nextLen+1,
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
While(Contains(inString,nextWord,nextPos+1),
nextLen++;
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
);
nextPos++;
If(Length(nextWord)>Length(longestDupes[1]),
nextLen--; //nextLen will be one more than longest length when Pat Match fails
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
If(Length(nextWord)==Length(longestDupes[1])+1,
Insert Into(longestDupes,nextWord),
longestDupes = Eval List({nextWord})
);
);
nextChar++;
);
longestDupes;
);
와 같은 @Craige_Hales ' 이전 블로그 항목에 게시된 코드에서 패턴 매칭을 사용하여 위의 접근 방식을 구현해 보았습니다. 놀랍게도 결과는 5~6배 더 오래 걸렸습니다. 정확한 이유는 모르겠지만 내 직감은 (지난번에 설명했듯이) 포함 하위 문자열 복제가 덜 자주 발생하면 훨씬 빠릅니다.
JMP에 내장된 중복 검색기인 요약 테이블 플랫폼. 이 접근 방식의 장점은 모든 하위 문자열 길이로 시작할 수 있다는 것입니다. 하위 문자열을 어떻게 구축해야 합니까? 지난 달의 블로그 게시물에서 두 가지 솔루션을 찾을 수 있습니다. 첫 번째는 입력 문자열을 원자화하고 반복합니다.
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
For(i=1,i<=nInds,i++,
Insert Into(stringList,Concat Items(parts[i::(i + subStringLen - 1)],""))
);
어디 inString 입력 문자열이고 subStringLen 빌드 중인 하위 문자열의 길이입니다. 반복적이지 않은 접근 방식은 표현식을 사용하여 구현할 수 있습니다.
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
i=1;
stringList[1::nInds] = Expr(Concat Items(parts[i::(i++ + subStringLen - 1)],""));
stringList = Eval List(stringList);
또는 패턴 매칭
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
각 접근 방식의 속도를 테스트하기 위해 임의로 생성된 4개의 문자로 구성된 1,000,000자 길이의 입력 문자열에 크기 4, 9, 15 및 21의 하위 문자열을 구축했습니다. 각 길이에서 10번의 반복이 실행되었습니다. 아래 결과는 패턴 매칭의 우월성을 보여줍니다. 전체 결과는 다음에서 찾을 수 있습니다. 테스트 빌드 하위 문자열.JMP .
연산
|
문자열 길이 구성 시간(초)
|
4
|
9
|
15
|
21
|
표현
|
6.91
|
7.35
|
8.19
|
9.01
|
고리
|
2.56
|
2.98
|
3.62
|
4.26
|
패턴 매칭
|
1.09
|
1.12
|
1.10
|
1.11
|
알고리즘, 문자열 길이 및 알고리즘 x 문자열 길이 상호 작용에 대한 통계적 차이(p << 0.001)를 보여주는 ANOVA를 수행했습니다. Tukey의 HSD를 사용한 사후 테스트는 패턴 일치 알고리즘의 문자열 길이 수준 간에 통계적 차이가 없음을 나타냅니다. 더 큰 문자 집합에서 이 방법이 어떻게 수행되는지 확인하기 위해 무작위로 선택된 26자로 구성된 1,000,000자 길이의 문자열로 테스트를 실행했습니다. 위와 동일한 하위 문자열 길이와 2자 및 40자 하위 문자열에서 20회 반복이 실행되었습니다. 통계적 차이가 있었지만 실질적인 차이는 작았습니다.
하위 문자열
길이
|
시간(초)
|
2
|
1.11
|
4
|
1.08
|
9
|
1.09
|
15
|
1.11
|
24
|
1.13
|
40
|
1.53
|
하위 문자열 구성과 중복 찾기를 함께 사용하면 아래 코드와 같이 보일 수 있습니다. 중복과 관련된 행을 알면 문자열에서 해당 행의 위치를 식별할 수 있습니다. 이것은 나중에 우리에게 유리하게 작용할 것입니다. 테이블을 비공개로 설정하면 작업 속도가 약간 빨라집니다.
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
tmpTbl = New Table("tmp",New Column("tmp",Character,Values(stringList)),Private);
sumTbl = tmpTbl << Summary(Group(:tmp),Private);
dupeLocs = sumTbl << Get Rows Where(:N Rows > 1);
dupes = Column(sumTbl,1)[dupeLocs];
Close(tmpTbl,No Save);
아래 표는 Covid-19와 1,000,000개의 문자열을 사용한 10회 실행을 기준으로 단일 반복의 평균 실행 시간을 제공합니다. 결과를 보면 문자열과 부분 문자열이 커짐에 따라 하위 문자열 크기 최적화 없이 이 접근 방식을 독점적으로 사용하는 것이 문제가 된다는 것을 쉽게 알 수 있습니다.
하위 문자열
길이
|
코로나 19
|
1M
|
2
|
0.0517
|
1.68
|
4
|
0.0504
|
4.25
|
9
|
0.1837
|
8.29
|
15
|
0.2226
|
8.63
|
21
|
0.2209
|
8.85
|
40
|
0.2957
|
12시 30분
|
하위 문자열 크기 최적화를 시작하더라도 입력 데이터의 구조가 얼마나 많거나 적을지 예측할 수 없습니다. 더 나은 접근 방식은 하이브리드 전략을 사용하는 것입니다. 사용 요약 주어진 크기의 복제본을 식별한 다음 이러한 복제본만 사용하여 구축할 수 있는 가장 긴 복제본을 찾습니다. 가장 긴 복제본의 하위 문자열이 더 짧은 하위 문자열 길이에서 생성된 복제 집합에 나타나야 하기 때문에 작동합니다. 몇 가지 가능한 접근 방식이 있습니다. 논의할 최종 방법과 유사하지만 다른 접근 방식을 선택합니다. 솔직히 말해서, 나는 이 접근법을 생각해 내기 전에 마지막 방법을 보았고 의심할 여지 없이 그것에 의해 큰 영향을 받았습니다. 내가 선택한 접근 방식의 문제는 원래 부분 문자열 위치를 추적하는 데이터 구조를 만드는 것이었습니다. 코드는 넉넉한 간격으로 약 50줄로 놀라울 정도로 짧습니다. Covid-19 데이터에서 모든 중복 항목을 찾는 데 약 0.32초가 걸리고 1,000,000자 문자열의 경우 13초가 걸립니다. 코드는 다음에서 찾을 수 있습니다. findLongestDupe(요약).JSL .
요약 각 반복에서 중복을 찾는 데 사용됩니다. 큰 테이블의 경우 속도가 느리지만 이전 단계의 복제본 수만큼 큰 테이블만 빌드하면 됩니다. 중복을 보장하기 위해 최소 길이보다 한 문자 더 많은 하위 문자열 길이로 시작하면 총 중복 수가 즉시는 아니더라도 매우 빠르게 감소할 가능성이 있습니다. 몇 번의 반복에서 행 수가 너무 크지 않은 경우 더 긴 하위 문자열로 시작하는 등 추가 최적화 없이 이 방법을 사용할 수 있습니다. 이 방법의 장점은 이러한 상황에서 추가 최적화를 사용할 수 있다는 것입니다. 초기 문자열 위치를 추적하는 데 사용되는 인덱싱은 논의할 마지막 방법에서 사용되는 연관 배열과 함께 사용되는 방식으로 작동합니다. 초기 길이의 중복 문자열 위치를 찾아서 임시 배열에 저장하십시오. 이러한 위치에서 시작하여 한 문자 더 긴 문자열을 빌드하여 입력 문자열의 범위를 초과하는 모든 문자열을 제거하십시오. 이 목록에서 중복 문자열의 위치를 찾으십시오. 인덱스가 있는 요소만 유지하면서 이전에 저장된 배열에 대한 인덱스로 사용하여 이러한 새 인덱스를 원래 위치에 다시 연결할 수 있습니다. 이전 어레이를 이 어레이로 교체하십시오. 이전 어레이에 가장 긴 복제 위치가 포함되는 시점에 복제가 남아 있지 않을 때까지 계속합니다.
위에서 언급했듯이 최종 방법은 이전 방법과 맛이 비슷합니다. 이 접근법에 대한 아이디어는 @brady_brady . 몇 가지 중요한 차이점이 있습니다. 먼저 한 문자부터 모든 하위 문자열을 만듭니다. 이것은 비효율적으로 들리지만 연관 배열을 사용하고 행렬을 사용하여 개별 문자열 문자를 인덱싱하면 문자열을 직접 검색하지 않고 존재하지 않는 문자 조합을 피할 수 있습니다. 일반적으로 문자 집합과 입력 문자열이 커지면 이전 방법보다 성능이 우수합니다. 다양한 입력 문자열 크기(50K – 2.5M) 및 문자 세트(4 – 72)에 대해 10회 실행하여 두 가지 접근 방식을 비교했습니다. 요약 방법(1)과 연관 배열 방법(2)에 대한 평균 실행 시간이 아래에 나와 있습니다. 전체 결과는 가장 빠른 방법 비교.JMP에서 찾을 수 있습니다.
|
50K
|
10만
|
50만
|
1M
|
2.5M
|
문자 세트 크기
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
4
|
0.5087
|
0.5814
|
0.9081
|
1.2664
|
5.421
|
6.813
|
13.412
|
13.778
|
32.23
|
35.67
|
10
|
0.2724
|
0.4117
|
0.6251
|
0.9207
|
2.850
|
4.509
|
6.998
|
9.503
|
13.61
|
24.70
|
26
|
0.3098
|
0.3748
|
0.6786
|
0.7441
|
3.625
|
3.981
|
7.363
|
8.537
|
21.68
|
19.58
|
52
|
0.4247
|
0.3265
|
1.0617
|
0.7682
|
4.246
|
4.046
|
9.522
|
7.395
|
30.67
|
18.08
|
72
|
0.3186
|
0.3309
|
0.7308
|
0.7079
|
3.533
|
4.236
|
7.192
|
8.917
|
20.14
|
18.97
|
Summary 메서드와 마찬가지로 이 접근 방식은 입력 문자열을 단일 문자로 바꾸는 것으로 시작합니다. 그러나 문자로 직접 작업하는 대신 문자 집합에 나타나는 숫자 위치가 사용됩니다. 이를 통해 문자열 연산보다 빠른 경향이 있는 행렬 연산을 사용하여 하위 문자열 빌드가 발생할 수 있습니다. 특히, 첫 번째 반복은 연관 배열에 대한 키(예: G의 경우 [3])로 각 문자 집합 위치의 행렬 표현을 취하고 입력 문자열에서 해당 위치의 벡터를 해당 값으로 사용합니다. 각각의 후속 반복은 입력 문자열의 마지막 요소를 넘지 않도록 주의하면서 이전 배열의 모든 키에 대한 벡터 값을 더한 1의 입력 문자열 값을 찾아 새로운 연관 배열을 작성하는 것으로 시작됩니다. 증분 벡터의 첫 번째 요소에 해당하는 값은 나머지 증분 벡터 값에서 중복 항목을 검색하는 데 사용됩니다. 존재하는 경우 연관된 위치가 새 배열 요소의 값에 사용됩니다. 이 요소에 대한 키는 복제된 요소의 문자 집합 값을 원래 키에 연결하여 작성되므로 문자열을 쉽게 다시 만들 수 있습니다. 검색 값과 중복 항목이 있는 경우 벡터에서 제거되고 값이 남지 않을 때까지 검색이 계속됩니다. 이 구축 프로세스는 이전 배열의 각 요소에 대해 발생합니다. 완료되면 새 연관 어레이가 이전 어레이를 대체하고 다음 반복이 시작됩니다. 이것은 이전 배열을 대체할 새 키가 없을 때까지 계속됩니다. 이전 배열에는 가장 긴 복제본이 포함되어 있습니다.
Brady의 코드는 다음에서 찾을 수 있습니다. findLongestDupe(AA).JSL . 다른 문자 집합을 사용할 수 있도록 약간 조정했습니다.
다음 시간에는 문자열에서 목록으로 이동할 것입니다. 이전 블로그에서 언급한 바와 같이, 반복 방지는 관련된 두 개의 최근 커뮤니티 게시물의 주제였습니다. 숫자 요소를 문자로 변환 그리고 목록 인덱싱 . 다음에 도전할 두 가지. 링크된 게시물에 올라온 질문을 기반으로 합니다. 두 경우 모두. 숫자 값을 문자열로 변환하고 있습니다.
- 목록을 변환하는 함수를 작성하십시오. N 목록(각각 중 나 숫자). 가정하지 마십시오 중 나 모든 목록에 대해 동일합니다.
- 항목 1의 목록을 바꿀 수 있는 함수를 작성하세요. 다음은 작은 예입니다.
inputList = {{12, 11, 16, 1, 15, ., 23, 8, 16, 17}, {1, 10, ., 4, 25, ., 19, 21, ., 3}, {11, 21,
22, 7, 3, ., 24, 10, 21, 20}, {., ., ., ., ., ., ., ., ., .}, {11, ., 3, ., 9, ., 23,
., 3, 16}};
outputList = {{12, 1, 11, ., 11}, {11, 10, 21, ., .}, {16, ., 22, ., 3}, {1, 4, 7, ., .}, {15, 25,
3, ., 9}, {., ., ., ., .}, {23, 19, 24, ., 23}, {8, 21, 10, ., .}, {16, ., 21, ., 3},
{17, 3, 20, ., 16}}
행운을 빌어요!
도전에 대처하는 한 가지 방법이 있습니다. 나는 "가정하지 마십시오 미 is same for all list"는 전체 목록을 누락된 값으로 채워야 할 수도 있음을 의미합니다. 반복({.},10)은 {.,.,.,.,.,.,.,.,.,.}를 생성합니다. Insert()는 목록이 아닌 목록의 항목을 추가합니다(참조 목록을 다른 목록에 삽입하는 방법 .)
inputList = {
{12, 11, 16, 1, 15, ., 23, 8, 16, 17},
{1, 10, ., 4, 25, ., 19, 21, ., 3},
{11, 21, 22, 7, 3, ., 24, 10, 21, 20},
{1}, // odd across-list
{., ., ., ., ., ., ., ., ., .},
{11, ., 3, ., 9, ., 23, ., 3, 16}};
// find rows and max cols of input:
nrows = N Items( inputList );
ncols = 0;
For( irow = 1, irow <= nrows, irow += 1,
ncols = Max( ncols, N Items( inputList[irow] ) )
);
// if the across-lists are not all the same size, add missing values
For( irow = 1, irow <= nrows, irow += 1,
If( ncols > N Items( inputList[irow] ),
Insert Into( inputList[irow], Repeat( {.}, ncols - N Items( inputList[irow] ), . ) )
)
);
// make a table of numbers from the lists
dt = New Table( "temp", invisible, Add Rows( nrows ), <<ADD multiple="" columns=""></ADD>이 JSL은 목록의 숫자 값을 보유하기에 충분한 행과 숫자 열이 있는 모두 누락된 데이터 테이블을 생성합니다. 데이터 테이블 첨자는 길이가 일정하지 않은 행에 만족하지 않으며 할당 중에 숫자를 문자로 변환하는 데 만족하지 않습니다. 변환은 SetDataType 메시지를 열 목록으로 전송하여 거의 끝 부분에서 수행됩니다(명시적인 JSL 루프 방지). 이전된 숫자 목록은 그 직전에 캡처됩니다.
데이터 테이블 첨자는 열이 모두 숫자일 때 숫자 행렬을 통해 가져오고 설정하려고 하지만 숫자 목록에서 행복하게 설정할 것입니다. get은 행렬을 반환하지만 문제 요구 사항은 전치된 숫자 목록을 반환하는 것이므로 AsList()는 행렬(데이터 테이블에서)을 다시 목록으로 변환하는 작업을 수행합니다.
