Dealing with large amounts of strings

[Narks]

I've got, say, a thousand strings. There are no duplicate strings.

I've got two functions.

Function A:
Search all the strings for an exact match to the string entered in chat, and return the result.

Function B:
Search all the strings for a partial match to the string entered in chat, and copy the results to an array.


If I use an array, I suspect:
- it will be very slow
- I will be very close or will be hitting the operations limit (which I can try to avoid by using .execute, which I will be doing, but I'd rather not use up so much processing power)

But if I use a hashtable:
- I cannot retrieve the key of a hashtable for partial matching

Any ideas as to what I should do in this scenario?

 

[DarkRevenant]

Arrays, being in the memory, are actually pretty fast. Also, arrays don't count toward the operations limit. Seriously, with only a thousand strings, it's not much of a big deal. I would suggest writing a prototype in C to test the speed, and then multiply the time by some large number (10x or more) for the time it will take using the WC3 VM.

Also, be advised that JASS NG is still just JASS, meaning any library functions you use will be slower than if you just coded it yourself to begin with.

 

[tooltiperror]

Use a linked list.

1) O(1) removal of strings (big deal for 500+ strings that need to change spots)
2) O(1) addition of strings (big deal for 500+ strings that need to change spots)
3) You can cache strings as they are used noticeably.
4) You get tremendous power over changing your code with little modifications.
5) Do you need a fifth reason?

Other notes:

1) You may want to use a hashtable instead of an array. The downside of this is that you lose some speed, but the good news would be that you would be able to have more than 8190 strings stored. If you really want, you could wait for say 8170 strings (give yourself some breathing room) and then get rid of those.
2) Reserve the first two characters of your string for a token. <symbol><anynumber> to store player who said it and then a symbol for the state it was said in or something. then filter out the first two substrings if you have to. Useful if you want to parse it later, but overkill depending on what exactly you are doing.
3) Perhaps you should make use of [ljass]//! novjass[/ljass] to stop JASSHelper from over complicating things like DarkRevenant said.

Are strings and integers of equal speed? I'd think converting strings to integers in ASCII values or something then converting to like, base 27 might be slower than using strings, but Blizzard has a habit of weird things (H2I, I2C/C2I, invalid typecasting in Blizzard.j, IsUnitType failure)

 

[Weep]

Function A:
Search all the strings for an exact match to the string entered in chat, and return the result.

Save a true boolean in a hashtable keyed to StringHash(string) for each of your strings, then just see if there's a true boolean at the StringHash key of the entered chat string.

Function B:
Search all the strings for a partial match to the string entered in chat, and copy the results to an array.

Do you mean that the entered chat is a substring of the pre-defined string, or that the entered chat string contains the pre-defined string and more? If the former, I don't know. If the latter, initialize a thousand triggers each with [ljass]call TriggerRegisterPlayerChatEvent(whichPlayer, whichPlayer, whichString, false)[/ljass]. That should consume little resources and should initialize in much less than a second, though may need some operation-limit-evasion.

 

[chobibo]

You could sort and search, [del]but using the hashtable is the most optimal solution.[/del]

Wait... Function B stores strings on which array? a different one? if so is it a temporary one?