프로그래밍 지혜에 따르면 순환 프로그래밍 작업을 선형 작업인 벡터화로 전환하면 계산 시간이 향상됩니다. 그러나 이것이 사실입니까? 어떤 조건에서? 얼마나? 챌린지 1은 알아낼 수 있는 좋은 기회를 제공했습니다. 네 가지 도전적인 질문에 답하기 위해 각 7개의 문자 세트에 대해 다음과 같이 결정했습니다.
- 각 문자가 사전 단어에 나오는 횟수를 세십시오. 이를 통해 항목 2, 3, 4에 대한 답을 찾을 수 있었습니다.
- 단어에 7글자 세트에 없는 문자가 있는지 확인합니다. 이것은 항목 1에 필요했습니다.
도전 1도전 1.JSL 에 기반한 열 수식을 사용하여 계산을 수행합니다. 길이 그리고 정규식 기능. 코드를 더 쉽게 읽을 수 있도록 몇 가지 추가 열 수식이 사용됩니다. 유일한 루핑은 각 문자 집합에 대한 기능을 재평가하는 데 사용됩니다. 실행 시간은 29초 미만입니다(모든 시간은 10회 실행에 대한 평균입니다). 나쁘지는 않지만 좋지는 않습니다. 수식의 복잡성 때문입니까, 아니면 열 대신 루프(목록 또는 행렬에 대해)를 사용하여 수식 평가를 수행해야 했기 때문입니까? 나는 사용 간단한 테스트 .JSL 그리고 전체 테스트.JSL 조사하다. 열과 루프를 비교하는 것 외에도 테이블이나 목록에서 직접 입력 값을 읽는 것이 더 빠른지 확인했습니다. 테이블의 값을 목록이나 행렬로 처음 읽는 데 시간이 추가됩니까?
아래 결과(초 단위)는 수식이 더 복잡해짐에 따라 수식과 루프의 차이가 덜 명확하다는 것을 보여줍니다. 수식을 작성하는 데 사용되는 함수는 시간에 훨씬 더 큰 영향을 미쳤습니다. 일반 검색 기능( 정규식 그리고 위치 )이 특정 검색 기능( 포함 그리고 Substr ).
기능
|
공식
|
목록 + 목록 액세스
|
목록 + 테이블 액세스
|
길이
|
0.0525
|
0.1398
|
0.1311
|
위치 + 항목
|
0.4187
|
0.5462
|
0.5383
|
길이 + 정규식
|
9.3744
|
9.2745
|
9.3911
|
루프 + 포함 + Substr
|
3.3255
|
3.4139
|
3.5444
|
이 지식을 실천에 옮겨 두 개의 새 스크립트를 만들었습니다. 도전 1도전 2.JSL 하나의 수식 안에 루프가 있는 수식을 사용하여 문자를 계산합니다. 챌린지 2 3.JSL 시도 수식이 아닌 목록을 사용합니다. 또한 항목 1, 2 및 3을 만족하는 단어가 적어도 한 번은 7개의 문자 세트 문자를 모두 포함해야 한다는 조건을 이용합니다. 실행 시간은 각각 15.50초와 10.40초였습니다. 이 경우 평가할 함수가 적기 때문에 루핑이 더 빠를 가능성이 높습니다. 두 개선 모두 내 초기 시도보다 훨씬 낫지만 여전히 가장 빠르지는 않습니다. 개선 사항은 더 빠른 함수, 더 적은 루프/함수 평가 또는 챌린지 질문에 답하는 다른 방법에서 나와야 합니다. 처음 두 가지 접근 방식은 결실을 맺을 가능성이 적기 때문에 다른 방법을 모색했습니다.
그만큼 도전과제 1 패턴매칭.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 );
