챌린지 7을 시도해 주신 분들께 감사드립니다. 기회가 없더라도 토론을 따라오셨기를 바랍니다. 이 문제를 어떻게 해결할 수 있습니까? 개념적으로 가장 간단한 접근 방식은 단일 문자 중복을 찾은 다음 두 문자 중복, 세 문자 등을 찾아 중복이 없을 때까지 한 문자씩 증가하는 것입니다. 주어진 길이에 대해 가능한 모든 문자열을 순진하게 검사하는 것은 하위 문자열 길이에 따라 점점 더 많은 시간을 소모하게 됩니다. 대략 30,000자 길이의 코로나19 게놈의 경우, 4자만 포함하는 7자 하위 문자열 중복이 보장됨에도 불구하고 7 = 16,384개의 고유한 조합 중 6,889개만 발생합니다(42%). 그리고 하위 문자열이 길어짐에 따라 가능한 중복 수량이 급격히 증가함에 따라 중복 수는 감소합니다. 이 접근 방식이 작동하려면 중복을 식별하는 효율적인 방법을 찾아야 합니다. 이 문제를 해결하기 위한 다른 방법을 검토한 후 이에 대해 다시 설명하겠습니다.
중복 항목을 모두 찾을 필요 없이 가장 긴 중복 항목만 찾는 데 집중해 보겠습니다. 간단한 접근 방식은 7자 중복이 있어야 하기 때문에 첫 번째 문자에서 하위 문자열을 시작하는 것입니다. 그런 다음 중복이 없을 때까지 한 번에 한 문자씩 늘립니다. 다음 문자 및 더 긴 중복 하위 문자열로 이동합니다. 중복이 불가능할 정도로 검색 문자열의 끝에 충분히 가까워질 때까지 이 작업을 계속하세요. 코로나19 게놈에서는 8자리 하위 문자열이 ATTAAAGG 첫 번째 문자부터 만들 수 있습니다. 두 번째 문자인 11자 문자열로 이동 따아아아아아아아아아아아아아 위치 2를 쳐다보면 위치 20063에 중복이 있습니다. 3번 위치부터 중복된 11자 이상이 없으므로 4번 위치로 이동합니다. 등등. 아래 코드는 가장 긴 중복 문자열을 찾는 데 약 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)],""))
);
어디 문자열 입력 문자열이고 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);
아래 표는 코로나19와 1,000,000개의 문자열을 사용한 10회 실행을 기준으로 단일 반복에 대한 평균 실행 시간을 제공합니다. 결과를 보면, 부분 문자열 크기 최적화 없이 이 접근 방식을 독점적으로 사용하는 것은 문자열과 부분 문자열이 커질 때 문제가 된다는 것을 쉽게 알 수 있습니다.
하위 문자열
길이
|
코로나 19
|
100만
|
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줄 정도로 놀라울 정도로 짧습니다. 코로나19 데이터에서 중복 항목을 모두 찾는 데는 약 0.32초가 소요되고, 100만자 문자열의 경우 13초가 소요된다. 코드는 다음에서 찾을 수 있습니다. findLongestDupe(요약).JSL .
요약 각 반복에서 중복 항목을 찾는 데 사용됩니다. 큰 테이블의 경우 속도가 느리지만 이전 단계의 중복 수만큼 큰 테이블만 빌드하면 됩니다. 중복을 보장하기 위해 최소 길이보다 한 문자 더 긴 부분 문자열 길이로 시작하면 총 중복 수는 즉시는 아니더라도 매우 빠르게 감소할 가능성이 높습니다. 몇 번의 반복에서 행 수가 너무 크지 않으면 더 긴 부분 문자열로 시작하는 등 추가 최적화 없이 이 방법을 사용할 수 있습니다. 이 방법의 장점은 이러한 상황에서 추가 최적화를 사용할 수 있다는 것입니다. 초기 문자열 위치를 추적하는 데 사용되는 인덱싱은 연관 배열에서 사용할 수 있는 방식으로 작동하며, 이는 논의할 최종 방법에서 사용되는 것입니다. 초기 길이의 중복 문자열 위치를 찾아 임시 배열에 저장하는 것부터 시작하세요. 이 위치에서 시작하여 한 문자 더 긴 문자열을 작성하고 입력 문자열의 경계를 초과하는 문자열을 제거하십시오. 이 목록에서 중복 문자열의 위치를 찾으세요. 인덱스가 있는 요소만 유지하면서 이전에 저장된 배열에 대한 인덱스로 사용하여 이러한 새 인덱스를 원래 위치에 다시 연결할 수 있습니다. 이전 어레이를 이 어레이로 교체하십시오. 이전 배열에 가장 긴 복제본의 위치가 포함되는 복제본이 더 이상 남지 않을 때까지 계속합니다.
위에서 언급했듯이 최종 방법은 이전 방법과 맛이 비슷합니다. 이 접근 방식의 아이디어는 다음과 같습니다. @brady_brady . 몇 가지 중요한 차이점이 있습니다. 먼저, 한 문자부터 모든 하위 문자열을 작성합니다. 비효율적으로 들리지만 연관 배열을 사용하고 행렬을 사용하여 개별 문자열 문자를 인덱싱하면 문자열을 직접 검색할 필요가 없고 존재하지 않는 문자 조합을 피할 수 있습니다. 일반적으로 문자 집합과 입력 문자열이 커지면 이전 방법보다 성능이 좋습니다. 두 가지 접근 방식을 비교하기 위해 다양한 입력 문자열 크기(50K~2.5M) 및 문자 집합(4~72)에 대해 10번의 실행이 이루어졌습니다. 요약 방법(1) 및 연관 배열 방법(2)에 대한 평균 실행 시간은 아래와 같습니다. 전체 결과는 가장 빠른 방법 비교.JMP에서 확인할 수 있습니다.
|
50K
|
100K
|
500K
|
100만
|
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}}
행운을 빌어요!
이 문제를 해결하는 한 가지 방법이 있습니다. 나는 "가정하지 마세요"라고 결정했습니다. 미 모든 목록에 대해 동일합니다."는 전체 목록을 누락된 값으로 채워야 할 수도 있음을 의미합니다. Repeat({.},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()는 데이터 테이블의 행렬을 다시 목록으로 변환하는 작업을 수행합니다.
