Qbasicnews.com
September 17, 2019, 05:39:24 AM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1]
  Print  
Author Topic: create a function...  (Read 3086 times)
Agamemnus
x/ \z
*****
Posts: 3491



« on: October 12, 2005, 12:15:13 PM »

Create a function with the following specifications:

*It checks for the existence of any of a set of strings inside one position of a string.
*It takes this form:

INSTRMULTI%(startlocation%, stringarray$(), stringtosearch$)

1) startlocation% is the starting search location inside stringtosearch$.
2) stringarray$() are the strings to search.
3) Two values result:
INSTRMULTI%, the search location.
stringindexfound%, the index position of the first string found. Strings should be sorted alphabetically, A-Z, and on size, smallest first.

Optional:
Make stringindexfound%() an array, so that if there is more than one string found at the first location, the array gives all the index values of all the strings found.

*********
Important
*********

This wouldn't be much of a challenge if you only used INSTR and compared the results inside the function. That's inefficient. The function should not search the same character in a string twice or more!

*******
Prizes
*******

Satisfaction that you created a good time-saving function...
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Antoni Gual
Na_th_an
*****
Posts: 1434



WWW
« Reply #1 on: October 13, 2005, 07:20:54 AM »

It's a FB challenge, is'nt?
For QB, the trivial case takes less than 1/18th second in my pc...In QB all the  strings must fit into the 64K of DGROUP and can't have more than 32700 chars.
Code:

'by Antoni , for 1500 strings searched in a 31000 chars buffer
DECLARE FUNCTION instrmulti% (startloc%, ss() AS STRING, bigs$, strindxfnd%)
randomize timer
CONST bigslen = 31000
const arrsz=1500
dim i%,a%,b%,bigs$
bigs$ = SPACE$(bigslen)
REDIM ss(1 to arrsz) AS STRING

FOR i = 1 TO bigslen
MID$(bigs$, i, 1) = CHR$(RND * 96+32)
NEXT
PRINT "string built"
a% = bigslen - 10
FOR i% = 1 TO arrsz
   ss(i%) = MID$(bigs$, RND * a%, rnd*15+4)
NEXT
PRINT "search strings built"

t!=timer
a% = instrmulti%(1, ss$(), bigs$, b%)
IF a% > 0 THEN
  PRINT "First match found at index ";a%;" for string nr ";b%," : " ; ss(b%);" = "; MID$(bigs$, a%,LEN(ss$(b%)))
else
  print "Search string not found"
eND IF
print "in"; timer-t!;"seconds"
sleep
END

FUNCTION instrmulti% (startloc%, ss() AS STRING, bigs$, strindxfnd%)
 dim i%,a%,b%,a1%
 a% = LEN(bigs$)
 FOR i% = LBOUND(ss, 1) TO UBOUND(ss, 1)
   a1% = INSTR(bigs$,ss(i%))
   IF (a1% > 0) AND (a1% < a%) THEN a% = a1% :strindxfnd% = i%:
   'print i%,a1%,a%
 NEXT
 IF a% = LEN(bigs$) THEN a% = 0
 instrmulti% = a%
END FUNCTION

Logged

Antoni
Antoni Gual
Na_th_an
*****
Posts: 1434



WWW
« Reply #2 on: October 13, 2005, 08:50:58 AM »

Second finding:
Bruteforce in FB is fast too. A 3,1 Mb string, searching for 1500 strings of  2000 to 2200 chars requires 1,4 seconds.  FB implements INSTR using Boyer-Moore search...

Can someone do it faster? :Huh:

Code:

DECLARE FUNCTION instrmulti% (startloc%, ss() AS STRING, bigs$, strindxfnd%)
randomize timer
CONST bigslen = 3100000
const arrsz=1500
dim i%,a%,b%,bigs$
bigs$ = SPACE$(bigslen)
REDIM ss(1 to arrsz) AS STRING

FOR i = 1 TO bigslen
MID$(bigs$, i, 1) = CHR$(RND * 96+32)
NEXT
PRINT "string built"
a% = bigslen - 10
FOR i% = 1 TO arrsz
   a%=rnd*200+2000
   ss(i%) = MID$(bigs$, RND*(bigslen-a%), a%)
NEXT
PRINT "search strings built"

t!=timer
a% = instrmulti%(1, ss$(), bigs$, b%)
IF a% > 0 THEN
  PRINT "First match found at index ";a%;" for string nr ";b%," : " ; ss(b%);" = "; MID$(bigs$, a%,LEN(ss$(b%)))
else
  print "Search string not found"
eND IF
print "in"; timer-t!;"seconds"
sleep
END

FUNCTION instrmulti% (startloc%, ss() AS STRING, bigs$, strindxfnd%)
 dim i%,a%,b%,a1%
 a% = LEN(bigs$)
 FOR i% = LBOUND(ss, 1) TO UBOUND(ss, 1)
   a1% = INSTR(bigs$,ss(i%))
   IF (a1% > 0) AND (a1% < a%) THEN a% = a1% :strindxfnd% = i%:
   'print i%,a1%,a%
 NEXT
 IF a% = LEN(bigs$) THEN a% = 0
 instrmulti% = a%
END FUNCTION
Logged

Antoni
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #3 on: October 13, 2005, 03:22:15 PM »

Yeah, an FB test would work better. Consider that you might want to search each string several times..

Brute force is ok, but I had in mind this:
Change the strings like so:
apple
pear
mud

apm
peu
pad
pr
l
e

Now search for the Nth character of the big string inside each of these new strings. N starts at 1. If you find anything, add N and search with the next string. Keep doing this until you reach the end of one of them. Abort if string positions are switched mid-way. (ie, you find mud but not the "app" part of apple)

Considerations:
*Input strings must be sorted biggest or smallest first, and alphabetically as well. It needs to be alphabetically sorted because of problems with false aborts, I think. (may not be the case, would need to be tested)
*The new string would need to be preserved somehow.
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Antoni Gual
Na_th_an
*****
Posts: 1434



WWW
« Reply #4 on: October 13, 2005, 04:37:57 PM »

You provided all the ideas...where is the challenge?  Cheesy
Logged

Antoni
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #5 on: October 13, 2005, 06:07:57 PM »

Making it work.

 :normal:
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!