| Author |
Message |
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
 Posted: 21 Nov 2004 12:09:44 pm Post subject: |
|
|
As you may have noticed in the other topic, I've written a talking eliza-like program. However, it's slow.
In my opinion, the slowness is concentrated in a particular function.
chekfind(test,plate)
test, plate are lists of strings. This is supposed to check if test fits the format specified in plate and if so, return what's in ellipses using a matrix. Example:
test = {"I", "THINK", "I", "CAN", "!"}
plate = {"...", "THINK", "..."}
should return the matrix [ [1,1] [3,5] ] because the subset of test from 1 to 1 is what goes in the first ellipsis, and the subset of test from 3 to 5 goes in the second. If test doesn't fit, chekfind returns 0.
I know this is a poor explanation, if you have questions ask.
If I were unable to make this, I would of course leave programming in shame and ignominy. I did; however, my version of the function takes a bit of time that adds up. I want to make it as fast as possible, in particular to make it figure out that test doesn't fit (if it doesn't) as fast as possible.
Help please? |
|
| Back to top |
|
|
Arcane Wizard
`semi-hippie`
Super Elite (Last Title)
Joined: 02 Jun 2003
Posts: 8993
|
| Posted: 21 Nov 2004 01:56:20 pm Post subject: |
|
|
| What's your curent code? |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 21 Nov 2004 05:47:30 pm Post subject: |
|
|
Oops, forgot to post that. Here it is, in Ti-89 basic:
Code:
chekfind(sentence,pattern)
Func
Local unmat, i, j, newrow, count, s, p
dim(sentence)+1->s
dim(pattern)+1->p
""->sentence[s]
""->pattern[p]
{}->unmat
true->newrow
1->j
For i,1,s
If pattern[j]="..." Then
If newrow Then
false->newrow
1->unmat[dim(unmat)+1]
0->count
EndIf
If sentence[i]=pattern[j+1] Then
count->unmat[dim(unmat)+1]
true->newrow
j+2->j
Else
count+1->count
EndIf
Else
If sentence[i]!=pattern[j]
Return 0
j+1->j
EndIf
EndFor
If j<=p
Return 0
Return seq({unmat[i],unmat[i+1]},i,1,dim(unmat),2)
EndFunc
|
|
| Back to top |
|
|
NETWizz
Byte by bit
Bandwidth Hog
Joined: 20 May 2003
Posts: 2369
|
| Posted: 21 Nov 2004 07:27:08 pm Post subject: |
|
|
| Eliza sucks compared to Alice. |
|
| Back to top |
|
|
Arcane Wizard
`semi-hippie`
Super Elite (Last Title)
Joined: 02 Jun 2003
Posts: 8993
|
| Posted: 22 Nov 2004 03:25:36 am Post subject: |
|
|
JBirk, I think Sir Robin wouold appreciate it if you kept that debate to the other topic, this one is specifically about optimiznig this routine, not chatterbots in general. : )
Sir Robin, tell me if this would work correctly so I know I've got the idea..
1->a
While a<dim(PATTERN) and PATTERN[a]="..."
a+1->a
EndWhile
If PATTERN[a]=SENTENCE[a]
return { {1, a-1} {a+1,dim(SENTENCE)} } //don't know if this is possible
return 0 |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 22 Nov 2004 06:23:26 pm Post subject: |
|
|
I assume you mean PATTERN[a] != "..."
this would work. but! your routine assumes there is only one word other than ...'s in the pattern. It wouldn't work correctly with something like
{"...","IF","...","THEN","..."}
for a pattern. I know I forgot to mention this tiny detail before,now I have... |
|
| Back to top |
|
|
Arcane Wizard
`semi-hippie`
Super Elite (Last Title)
Joined: 02 Jun 2003
Posts: 8993
|
| Posted: 23 Nov 2004 11:11:13 am Post subject: |
|
|
Code:
{ }->POS
{ }->RETURN
For a,1,dim(SENTENCE)
If PATTERN!="..." //if keyword found
Then
If SENTENCE[a]=PATTERN[a] //check if it's matched
Then
a->POS[dim(POS)+1] //if it is, store position of it to POS
Else //not matched by SENTENCE
dim(SENTENCE)->a //end loop
o->r //return 0
EndIf
EndIf
EndFor
If not(r) //if not everything was matched we won't want to format the return value
Return 0
1->c //subset
1->b //from b to POS[a]-1
For a,1,dim(POS)
If POS[a]!=a //need to find room for a subset first
Then
b->RETURN[c][1] //from b..
POS[a]-1->RETURN[c][2] //to POS[a]-1
EndIf
c+1->c //next subset
EndFor
Return RETURN
Last edited by Guest on 23 Nov 2004 11:49:56 am; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 23 Nov 2004 05:04:47 pm Post subject: |
|
|
Quote: If SENTENCE[a]=PATTERN[a] I might be wrong but wouldn't this not help if a word in the sentence happened to be in a different position in the pattern?
Edit: a teacher person from my robotics club that I asked about this, suggested tokenizing words in the patterns, because the lists on the 89 can be mixed string/number. I am going to try this, see how it works.
a nice tokenizery thing:
"1:WHAT2:WHY3:HELLO3:HI4:SALAD" -> tokens
//this is saved data
Code:
inString(tokens,":"&word) -> find
If find Then
expr(mid(tokens,find-1,1)) -> sentence[i]
Else
word -> sentence[i]
EndIf
notice that if I have HELLO and HI both tokenize to 3 then the program will understand them both to mean the same thing. 
Last edited by Guest on 23 Nov 2004 05:12:35 pm; edited 1 time in total |
|
| Back to top |
|
|
Arcane Wizard
`semi-hippie`
Super Elite (Last Title)
Joined: 02 Jun 2003
Posts: 8993
|
| Posted: 24 Nov 2004 08:57:40 am Post subject: |
|
|
Sir Robin wrote: Quote: If SENTENCE[a]=PATTERN[a] I might be wrong but wouldn't this not help if a word in the sentence happened to be in a different position in the pattern?
Isn't it the whole point that in such a case the sentence wouldn't match the pattern? |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 24 Nov 2004 04:32:50 pm Post subject: |
|
|
No.
Each ... can match any number of words. Something like
... YOU ... ARE ...
should be able to match
I KNOW THAT YOU ARE CHEATING SOMEHOW. THERE IS A HUMAN HIDING INSIDE! |
|
| Back to top |
|
|
Darth Android
DragonOS Dev Team
Bandwidth Hog
Joined: 31 May 2003
Posts: 2104
|
| Posted: 01 Dec 2004 12:04:46 am Post subject: |
|
|
I am not sure what is "fast" and what is not, considering that all i have is an 84+se.
never the less i made a program that does what you said, just convert it to 89 basic and tell me if it is faster or slower. works as such:
input:
cant have 2 ...'s in a row
... is the wildcard
determines words based on spaces
Str0 is wildcarded string (the one with ...'s)
Str9 is text string to be matched
destroys Str1-Str3,L1,L2,A-F,W-(theta)
output:
W=1 means match, W=0 means no match
L2: format {start word, end word, start word 2, end word 2,...}
I didn't bother with the matrices output that you requested because that is not hard to add and was unneeded for this program's purpose
example:
input:
Str9: "THIS IS A TEST STRING FOR THE PROGRAM"
Str0: "... IS A ... FOR ..."
output:
L2: {1,1,4,5,7,8}
prgmTOK is a token parser, Str2 is the token, Str1 is input. A=0 for total number of tokens, or A>0 for Ath token into Str3. Nothing more than a subroutine, above inputs/outputs apply to main program below prgmTOK
(anything after //'s are comments, "->" means Store, "(th)" means theta, also note that this was made today, havent had time to optimise)
prgmTOK:
Code:
If not(inString(Str1,Str2 //Is token in string?
Then
If A>1 //No
Then //Token is not in string
Delvar BDelvar Str3
Else
Str1->Str3
1->B
End
Else //But of course it is!
Delvar L1 //Reset variables
0->dim(L1
2->D
1->C
If Str2=sub(Str1,1,1 //remove beginning and ending token separaters
sub(Str1,2,length(Str1)-1->Str1
If Str2=sub(Str1,length(Str1),1
sub(Str1,1,length(Str1)-1->Str1
While inString(Str1,Str2,C //loop though, marking beginning character of each token
1+inString(Str1,Str2,C->C
C-1->L1(D
D+1->D
End
If A //Total or Token?
Then
1+length(Str1->L1(D
1+L1(A->E
sub(Str1,E,L1(A)+1)-E->Str3
End
dim(L1->B //Return total no matter what :lol:
End
heres the main program:
prgmWILDCARD
Code:
1->dim(L2 //reset vars
Str0->Str1
DelVar A"(1 space)->Str2
prgmTOK //get total words in stings
B->(th)
Str9->Str1
prgmTOK
B->Z //reset some more vars
1->Y
1->X
1->W
For(F,1,(th) //loop for all words in wildcarded string, all have to match something
F->A
Str0->Str1
prgmTOK //get current word
If Str3="... //wildcard?
Then
Y->L2(X //mark as begining of wildcard strand and update vars
X+1->X
F+1->F
F->A
If F>(th) //is the wildcard the last word?
Then
Z->L2(X //yes, simply add the # of words in the text string to the end
Return
End
prgmTOK //current word that we are searching for in text string changed, so update
End
Str3->Str0
Str9->Str1 //shift so we can use prgmTOK with text string
Repeat Str3=Str8 or Y>Z //loop until we find the current word from the wildcard
Y->A //string in the text string or until we have reached then end of the text string
prgmTOK
Y+1->Y
End
If Y>Z+1 //did we match the wildcard or hit end of text string
Then
DelVar W //end of text string, no match
Return
End
Y-2->L2(X //match, set end of widlcard
X+1->X
End
should work fine, if it doesnt let me know, i probably mistyped something while typing this whole thing in in the fast reply box
Last edited by Guest on 01 Dec 2004 12:48:43 am; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 02 Dec 2004 07:59:31 pm Post subject: |
|
|
Thanks, I'll convert it to 89 Basic as soon as I get me some free time.
Edit: oh and please don't spend your time optimizing the 83+ code as it will likely have to be optimized differently for the 89.
Last edited by Guest on 02 Dec 2004 09:05:10 pm; edited 1 time in total |
|
| Back to top |
|
|
|
68k Calculator Basic => TI-BASIC
