Dictionizer: Useful utility and study of Hashing

[bplus]

The question there, Pete, is what spot does the word contain in your list?  If just knowing it’s there is good enough, that might work, but if you need the word index, it’s insufficient.  ;)

Steve you had nothing to worry about.

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2.  
3. OPEN "466544 Word List.txt" FOR BINARY AS #1
4. DIM SHARED WordList(1 TO 466544) AS STRING
5. DO UNTIL EOF(1)
6.     count = count + 1
7.     LINE INPUT #1, WordList(count)
8. LOOP
9. CLOSE #1
10. DIM RandomWords(50000) AS STRING
11. FOR i = 1 TO 50000
12.     c = INT(RND * 466544) + 1
13.     RandomWords(i) = WordList(c)
14. NEXT
15. PRINT "Steve's 50000 word lookup with binary search"
16. t# = TIMER
17. FOR i = 1 TO 50000
18.     index = FindIndex(RandomWords(i))
19. NEXT
20. PRINT USING "###.### seconds lookup"; TIMER - t#
21.  
22.  
23. 'pete's method
24. OPEN "466544 Word List.txt" FOR BINARY AS #1
25. word$ = SPACE$(LOF(1))
26. GET #1, , word$
27. CLOSE #1
28. PRINT "Pete's 50000 word lookup using INSTR to get position in string of word."
29. t# = TIMER
30. FOR i = 1 TO 50000
31.     place = INSTR(word$, RandomWords(i) + CHR$(13) + CHR$(10))
32. NEXT
33. PRINT USING "###.### seconds lookup"; TIMER - t#
34.  
35. END
36.  
37.  
38.  
39.  
40. DO
41.     _KEYCLEAR
42.     INPUT "Give me any word"; search$
43.     search$ = LTRIM$(RTRIM$(search$))
44.     PRINT "Searching for "; search$
45.     IF search$ = "" THEN END
46.     index = FindIndex(search$)
47.     IF index THEN
48.         PRINT "Word was found at position "; index; " in "; SearchTimes; "passes."
49.     ELSE
50.         PRINT "Word was not in list."
51.         PRINT "Previous word was ==> "; WordList(LastIndex - 1)
52.         PRINT "Next word was ======> "; WordList(LastIndex + 1)
53.         PRINT "Search took"; SearchTimes; "passes."
54.     END IF
55.     PRINT
56. LOOP
57.  
58.  
59.  
60. FUNCTION FindIndex (search$)
61.     SHARED SearchTimes, LastIndex
62.     SearchTimes = 0
63.     min = 1 'lbound(wordlist)
64.     max = 370099 'ubound(wordlist)
65.     DO UNTIL found
66.         SearchTimes = SearchTimes + 1
67.         gap = (min + max) \ 2
68.         compare = _STRICMP(search$, WordList(gap))
69.         IF compare > 0 THEN
70.             min = gap + 1
71.         ELSEIF compare < 0 THEN
72.             max = gap - 1
73.         ELSE
74.             FindIndex = gap
75.             found = -1
76.         END IF
77.         IF max - min <= 1 THEN LastIndex = gap: found = -1 'it's not in the list
78.         ' PRINT min, max, search$, WordList(gap), compare
79.         ' SLEEP
80.     LOOP
81. END FUNCTION
82.  
83.  

Ha, ha, ha, had me fooled too! ;-))

Though the INSTR method would find a word in collisions fast enough, I imagine.

[SMcNeill]

Makes sense when you think about what INSTR does:  compares character by character until it finds a match....

PRINT INSTR (“1234567890”, “0”)  <—- this would need to start at position 1 and compare each byte in the string to where “0” appears first — if it appears at all.

So take 466544 words of average length 5, and you have a string with 2 million bytes in it...  That’s up to 2 million comparisons to find a match...

To be honest, I’m surprised all it took was 2.5 minutes or so to finish. 

[Pete]

For my needs, INSTR() works great. Actually, I have used my method to pare words out of very large html page. I just don't look up words 50,000 times! So to find just one word in a 50,000 word list with an average of 6 letters per word would be nearly instantaneous...

Code: QB64: [Select]

1. x$ = ","
2. DO
3.     x$ = x$ + CHR$(RND * 26 + 65)
4.     IF INT(RND * 8) = 5 THEN x$ = x$ + ","
5.     IF LEN(x$) > 150000 AND flag = 0 THEN flag = 1: PRINT "Half finished...": x$ = x$ + ",ATE,"
6. LOOP UNTIL LEN(x$) > 300000
7.  
8. PRINT x$
9. PRINT
10. PRINT " Press any key to run speed test..."
11.  
12. SLEEP: PRINT
13.  
14. t# = TIMER
15. PRINT "ATE is at position:"; INSTR(x$, ",ATE,") + 1
16. PRINT USING "###.### seconds lookup"; TIMER - t#

What does take a minute is putting the 300000+ character string together.

Parsing out frequency would require seeding the instr() function but with seeding, it is also very fast.

It's a quick and dirty low tech solution if you don't mind clogging up a lot of memory to use it.

Edit: Wow, frequency tests are lightening fast, too.

Code: QB64: [Select]

1. x$ = ","
2. DO
3.     x$ = x$ + CHR$(RND * 26 + 65)
4.     IF INT(RND * 500) = 25 THEN x$ = x$ + ",ATE,"
5. LOOP UNTIL LEN(x$) > 300000
6.  
7. PRINT x$
8. PRINT
9. PRINT " Press any key to run speed test..."
10.  
11. SLEEP: PRINT
12.  
13. t# = TIMER
14. DO
15.     ii = ii + 1
16.     seed& = INSTR(seed&, x$, ",ATE,")
17.     IF seed& = 0 THEN EXIT DO
18.     PRINT ii; seed&; MID$(x$, seed& + 1, LEN("ATE"))
19.     seed& = seed& + LEN(",ATE,")
20. LOOP
21. PRINT USING "###.### seconds lookup"; TIMER - t#

Pete

[_vince]

Pete the Builder

I believe QB64 actually uses hash tables.  I remember when that was a giant milestone for galleon in improving compilation time - hashing for variable (sub, function, array, etc) names though I am not familiar with exactly how it was done. Here's a reasonable list of applications that even mentions programming language interpreters/compilers: https://en.wikipedia.org/wiki/Hash_table#Uses. Maybe Steve can further increase compilation time by replacing it with his binary search?

@STx the dictionary example may be a poor example of practical hash table use unless Steve is just totally messing with you with this one-upping you with the binary search, who knows. The best and simplest example would be "associative arrays (arrays whose indices are arbitrary strings or other complicated objects), especially in interpreted programming languages like Perl, Ruby, Python, and PHP" (from the wiki).  Here's an example:

there's an array called "cat":

cat$(0) = "Benedict"
cat$(1) = "maine coon"
cat$(2) = "rats"
cat$(3) = "35 kg"

It's a little confusing to remember that I'd have to call cat$(1) to get it's breed type, a better representation is:

cat_hash$("name") = "Benedict"
cat_hash$("breed") = "maine coon"
cat_hash$("food") = "rats"
cat_hash$("mass") = "35 kg"

now all you need is a hashing function to resolve the following:

"name" -> 0
"breed" -> 1
"food" -> 2
"mass" -> 3

as you can imagine, this is extremely useful in tables and databases.  Shame on Steve for spamming this otherwise informative thread with unrelated and misleading nonsense.

[Pete]

"Yes he can!"

Just don't get on his bad side... Angry Pete

https://thumbs.gfycat.com/ReasonableEmbellishedHalcyon-size_restricted.gif

[SMcNeill]

@STx the dictionary example may be a poor example of practical hash table use unless Steve is just totally messing with you...

Now we all know I wouldn’t do anything like that.  :P

[_vince]

Edited above

[_vince]

Perhaps a dictionary implementation is as follows:

hashing function:

"apple" -> 3
"africa" -> 1
"xylophone" -> 2
"zebra" -> 0

then you simply store your dictionary as follows

dict$(0) = "horse-like animal"
dict$(1) = "continent"
dict$(2) = "musical instrument"
dict$(3) = "type of fruit"

obviously it does not have to be in order at all, and words can resolve to arbitrary numbers which are just more conveniences of hash tables