프로그래밍 지식에 따르면 순환 프로그래밍 작업을 선형 작업, 즉 벡터화로 전환하면 계산 시간이 향상됩니다. 하지만 이것이 사실입니까? 어떤 조건에서? 얼마만큼? 챌린지 1은 이를 알 수 있는 좋은 기회를 제공했습니다. 네 가지 도전 질문에 답하기 위해 나는 일곱 글자로 구성된 각 세트에 대해 다음과 같이 결정했습니다.
- 각 문자가 사전 단어에 나타나는 횟수를 셉니다. 이를 통해 항목 2, 3, 4에 대한 답을 찾을 수 있었습니다.
- 단어에 7자 세트에 포함되지 않은 문자가 있는지 확인합니다. 이는 항목 1에 필요했습니다.
과제 1 시도 1.JSL은 길이 및 Regex 함수를 기반으로 하는 열 수식을 사용하여 계산을 수행합니다. 코드를 더 쉽게 읽을 수 있도록 몇 가지 추가 열 수식이 사용됩니다. 유일한 반복은 각 문자 집합의 기능을 재평가하는 데 사용됩니다. 실행 시간은 29초 미만입니다(모든 시간은 평균 10번 실행 이상). 나쁘지는 않지만 훌륭하지는 않습니다. 수식의 복잡성 때문입니까, 아니면 열 대신 루프(목록 또는 행렬에 대해)를 사용하여 수식 평가를 수행해야 했기 때문입니까? 저는 test simple.JSL 과 test full.JSL을 사용하여 조사했습니다. 열과 루프를 비교하는 것 외에도 테이블이나 목록에서 직접 입력 값을 읽는 것이 더 빠른지 알아보았습니다. 먼저 테이블의 값을 목록이나 행렬로 읽는 데 시간이 추가됩니까?
아래 결과(초)는 수식이 더욱 복잡해짐에 따라 수식과 루프 간의 차이가 덜 분명해짐을 보여줍니다. 공식을 작성하는 데 사용된 함수는 시간에 훨씬 더 큰 영향을 미쳤습니다. 일반 검색 기능( Regex 및 Loc )은 특정 검색 기능( Contains 및 Substr )보다 훨씬 느렸습니다.
|
기능
|
공식
|
목록 + 목록 액세스
|
목록 + 테이블 액세스
|
|
길이
|
0.0525
|
0.1398
|
0.1311
|
|
장소 + 품목
|
0.4187
|
0.5462
|
0.5383
|
|
Length + 정규식
|
9.3744
|
9.2745
|
9.3911
|
|
루프 + 포함 + 하위 문자열
|
3.3255
|
3.4139
|
3.5444
|
이 지식을 실제로 적용하여 두 개의 새로운 스크립트를 만들었습니다. 과제 1 시도 2.JSL은 하나의 수식 내부에 루프가 있는 수식을 사용하여 문자 수를 계산합니다. 과제 2 시도해 보세요. 3.JSL은 수식 대신 목록을 사용합니다. 또한 항목 1, 2, 3을 충족하는 단어의 경우 7개의 문자 집합 문자를 모두 적어도 한 번 포함해야 한다는 조건을 활용합니다. 실행 시간은 각각 15.50초와 10.40초였습니다. 이 경우 평가할 함수가 적기 때문에 루핑이 더 빨라질 가능성이 높습니다. 개선 사항은 초기 시도보다 훨씬 낫지만 여전히 가장 빠르지는 않습니다. 개선 사항은 더 빠른 함수, 더 적은 루프/함수 평가 또는 도전 질문에 답하기 위한 다른 방법을 통해 이루어져야 합니다. 처음 두 가지 접근 방식은 결실을 맺을 가능성이 적어 보였기 때문에 다른 방법이 모색되었습니다.
Challenge 1 Pattern Matching.JSL 스크립트는 @Craige_Hales 에서 가져온 것입니다. Craige는 최근 JMP Development에서 은퇴했지만 여전히 커뮤니티에서 활발하게 활동하고 있습니다. 그는 JMP 의 패턴 일치 및 정규식 기능을 담당했습니다. Craige의 솔루션은 먼저 사전 목록을 긴 문자열로 변환한 다음 패턴 일치를 적용하여 단어를 솔루션 버킷으로 구문 분석하여 문제를 벡터화합니다. 3.71초 만에 실행되며 패턴 일치의 폭과 유연성을 보여주는 훌륭한 예를 제공합니다. 2.76초가 소요되는 가장 빠른 솔루션은 @brady_brady 에서 나온 것입니다. 그는 사전에 있는 단어에 설정된 각 문자를 적용하는 대신 각 사전 단어에 포함된 모든 알파벳 문자의 발생 횟수를 세는 것부터 시작합니다. 처음에는 문자 비교 횟수가 7개에서 26개로 늘어나지만 한 번만 수행하면 되므로 각각의 새 문자 세트에 대한 재평가를 피할 수 있습니다. 초기 알파벳 행렬에서 적절한 열을 추출하여 답안을 찾게 되므로 훨씬 빠른 해결이 가능합니다. 1146자로 가장 짧은 스크립트이기도 합니다.
첫 번째 챌린지 이후의 순위표는 다음과 같습니다.
5월 1일에 출시되는 챌린지 2를 기대해 주세요!
@MathStatChem 문자 수를 세기 전에 주석과 공백을 제거합니다. 귀하의 새 스크립트는 현재 상태의 내 컴퓨터에서 약 3.6초 안에 실행됩니다. Brady보다 느리지만 Craige보다 빠릅니다. 몇 가지 작은 변화로 꽤 드라마틱한 차이가 납니다! 하지만 일부 항목은 올바르게 답변되지 않았습니다. 아래는 제가 답변과 함께 사용한 문자 세트입니다.
//acehlot
1. {"acacatechol"}
2. {"scientificophilosophical"}
3. {"hypercivilization"}
4. {"macracanthrorhynchiasis", "pancreaticoduodenostomy", "pericardiomediastinitis"}
//ilosuvx
1. {"lixivious"}
2.{"subclavioaxillary"}
3.{"excitovascular"}
4. {"formaldehydesulphoxylate"}
//mnoruwy
1.{"unwormy"}
2.{"countrywoman", "journeywoman", "laundrywoman"}
3.{"jurywoman"}
4.{"formaldehydesulphoxylate"}
새 스크립트와 이전 스크립트의 길이는 각각 2461과 2469였습니다.
그래서 저는 기본적으로 다음과 같은 논리를 사용했습니다. @brady_brady , 그러나 내 초기 문자 계산 코드는 더 많은 루프와 목록 호출을 사용하여 매우 비효율적이었습니다.나는 그의 접근 방식을 대체했고 내 스크립트는 약 3초 만에 실행되었습니다.아주 멋지다!
items() 함수가 이것의 핵심입니다.나는 그것이 이것을 할 것이라는 것을 깨닫지 못했습니다.문자열을 개별 문자 목록(순서대로, 목록의 별도 항목으로 반복되는 문자 포함)으로 변환합니다.
항목(문자열);
따라서 items("easypeasy","")는 {"e", "a", "s", "y", "p", "e", "a", "s", "y"}를 반환합니다.
그런 다음 포함을 사용하여 알파벳 문자의 색인을 참조하는 것도 정말 좋은 트릭이었습니다.
포함("abcedfghijklmnopqrstuvwxyz","a")는 1을 반환합니다.
포함("abcedfghijklmnopqrstuvwxyz","b")는 2를 반환합니다.
코드를 좀 더 장황하게 로그에 출력하도록 만들었으나 문자 수를 세기 전에 주석을 제거했는지는 확실하지 않습니다.
내 코드는 다음과 같습니다(더 빠른 접근 방식으로 개선됨).
startTime = Time Of Day( Today() );
letterSetList = {"apouter", "abdcefl", "acouter", "rstlneo", "efghijk"};
alphabet = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x",
"y", "z"};
abet="abcedfghijklmnopqrstuvwxyz";
_dt = Current Data Table();
numwords = N Rows( _dt );
_c = Column( _dt, "Words" );
wordlist = _c << get values;
// get lengths of each word in word list
// also create a matrix indicating how many times each letter in the alphabet is used in each word
wordlengths = J( numwords, 1, 0 );
alphacounts = J( numwords, 26, 0 );
For( ii = 1, ii <= numwords, ii++,
its=items(wordlist[ii],"");
wordlengths[ii] = Length( wordlist[ii] );
for(jj=1, jj<=nitems(its), jj++, alphacounts[ii,contains(abet,its[jj])]++);
);
// also create a matrix indicating if a letter in the alphabet is used in each word
alphaindex = alphacounts > 0;
For( ll = 1, ll <= N Items( letterSetList ), ll++,
str = letterSetList[ll];
// create an indicator vector for the letters in the string
str_alphaindex = J( 1, 26, 0 );
For( jj = 1, jj <= 26, jj++,
For( kk = 1, kk <= Length( str ), kk++,
str_alphaindex[1, jj] = str_alphaindex[1, jj] + (Substr( str, kk, 1 ) == alphabet[jj])
)
);
// 1 The longest word using all seven letters and only those seven letters. Letters may be used more than once.
// words that meet this criteria will have a "zero distance" from their letter indicator row and the string letter indicator vector
pickrow1 = Distance( alphaindex, str_alphaindex ) == 0;
// now find the word that has the longest length
pickrow1 = pickrow1 & (wordlengths == Max( wordlengths[Loc( pickrow1 )] ));
Print( "1. Find longest word(s) that uses only the letters <" || str || "> (item " || Char( ll ) || " from itemSetList)" );
If( Dim( Loc( pickrow1 ) )[1],
Print( wordlist[Loc( pickrow1 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow1 & (wordlengths == Max( wordlengths[Loc( pickrow1 )] )) ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
// 2 The longest word using all seven letters and any other letters.
// words that meet this condition, the sum of their letter indictor rows for the letters in the string should equal 7
pickrow2 = (V Sum( alphaindex[0, Loc( str_alphaindex )]` )` == 7);
// now find the word that has the longest length
pickrow2 = pickrow2 & (wordlengths == Max( wordlengths[Loc( pickrow2 )] ));
Print(
"2. Find longest word(s) that use all letters <" || str || "> (item " || Char( ll ) ||
" from itemSetList) and/or any other letters"
);
If( Dim( Loc( pickrow2 ) )[1],
Print( wordlist[Loc( pickrow2 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow2 ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
// 3 The longest word using all seven letters and any other letters where no letter
// from the set of seven is used more than once.
// words that meet this condition, meet the condition for the 2nd rule but also the sum of their letter counts for
// the letters in the string has to be equal to 7
pickrow3 = (V Sum( alphaindex[0, Loc( str_alphaindex )]` )` == 7) & (V Sum( alphacounts[0, Loc( str_alphaindex )]` )` == 7);
// now find the word that has the longest length
pickrow3 = pickrow3 & (wordlengths == Max( wordlengths[Loc( pickrow3 )] ));
Print(
"3. Find longest word(s) that use all letters <" || str || "> (item " || Char( ll ) ||
" from itemSetList) only once and/or any other letters "
);
If( Dim( Loc( pickrow3 ) )[1],
Print( wordlist[Loc( pickrow3 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow3 ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
// 4 The longest word in which 5 of the 7 letters appears.
// Any letter including those outside of the 7 may appear once or more
// except the two unused letters from the list of 7, which may not appear at all.
// words that meet this condition have the sum of their letter indicators (for the letters in the string) equal to 5
pickrow4 = (V Sum( alphaindex[0, Loc( str_alphaindex )]` )` == 5);
// now find the word that has the longest length
pickrow4 = pickrow4 & (wordlengths == Max( wordlengths[Loc( pickrow4 )] ));
Print(
"4. Find longest word(s) that uses only 5 of the 7 letters <" || str || "> (item " || Char( ll ) ||
" from itemSetList) and/or any other letters"
);
If( Dim( Loc( pickrow4 ) )[1],
Print( wordlist[Loc( pickrow4 )] );
Print( "which is in the following row(s) from the Word List table " );
Print( Loc( pickrow4 ) );
,
Print( "no word(s) found" )
);
Print( "-------------------" );
);
endTime = Time Of Day( Today() );
Print( endTime - startTime );
