Binary Search Method

[STxAxTIC]

As predicted, it's not apples-to-apples.

Gotta replace my hash function which uses a cosine, and then a completely separate recursive string function just to remove the decimal point. The ReplaceSubString function should be gone from the hash function - use Lukes suggestion instead.

Also your wordlist of 400k+ entries exceeded the value of the hash table size of 300007. You wired it for collisions in other words. Not sure if you noticed or if that's an accidental straw man.

This isn't worth beans until you get an honest comparison.

EDIT

LOL and I just noticed you're using the hash table wrong. Why on earth are you storing the index (as a collision) next to the word? This is a speed test - trim that fat!

... And once we see where this test finally goes, let's push the record limit to the maximum and see how each one does with like, a billion words.

[Pete]

Bill, you made my point about the problems with hashing. With my methods and Steve's method, you don't need a complicated pre-plan, which may need to be overhauled or adjusted someday. Just alphabetize the list, which a one-time never change it algorithm.

I do love the hashing method and it is a damn clever fast and efficient way to set up a list to be searched and indexed. I suppose the merits in any of these methods depends on the use. For instance, indexing doesn't mean squat in a spell check routine, so I need that feature like a fish needs a bicycle. That's one reason why even my quick and dirty QB64 instr() method is appealing to me. So while you keep searching for the Holly Grail of hash, Steve and I just grab a couple of Dixie cups and drink up.

In any event, good luck with your hash refinements and thank you for starting this awesome topic for discussion, originally in the, "Dictionizer" thread, and to Steve for continuing it here. Guys, we need more critical thinking threads like these around here.

Pete

[SMcNeill]

As predicted, it's not apples-to-apples.

Gotta replace my hash function which uses a cosine, and then a completely separate recursive string function just to remove the decimal point. The ReplaceSubString function should be gone from the hash function - use Lukes suggestion instead.

Also your wordlist of 400k+ entries exceeded the value of the hash table size of 300007. You wired it for collisions in other words. Not sure if you noticed or if that's an accidental straw man.

This isn't worth beans until you get an honest comparison.

I told you you were comparing apples to peanut butter...

The Binary Search is a "search and done" method for data retrieval.  The Hash Table is an "instant jump to a spot in memory and then parse a much smaller data set" method for data retrieval.  As long as you're going to have collisions and need to search for those, you have to take that search time into consideration.

Using your suggestions of "Luke's method" + "Table Larger Than List", we end up with the following code:

Code: QB64: [Select]

1. DIM SHARED HashTableSize AS LONG
2. HashTableSize = 611953 ' Best to use a big prime number. Bigger examples are 611953 and 1014729.
3.  
4. DIM SHARED LB AS STRING ' Make sure that bcracketing sequences do not appear in the data source, otherwise use (a) special character(s).
5. DIM SHARED RB AS STRING
6. LB = "{"
7. RB = "}"
8.  
9. DIM SHARED EnglishDictionary(HashTableSize) AS STRING ' Hash table size does not need to equal the size of the source dictionary itself.
10.  
11. OPEN "466544 Word List.txt" FOR BINARY AS #1
12.  
13. DIM SHARED WordList(466545) AS STRING
14. PRINT "Loading library"
15. DO UNTIL EOF(1)
16.     count = count + 1
17.     LINE INPUT #1, WordList(count)
18. LOOP
19. CLOSE #1
20.  
21. Sort WordList()
22.  
23. i = 0
24. FOR i = 1 TO 466545
25.     b$ = WordList(i) 'the word to store
26.     c$ = LTRIM$(RTRIM$(STR$(i))) 'to store the index
27.     d = HashFunc(b$) ' Calculate the hash value (array address) of the word on hand.
28.     EnglishDictionary(d) = EnglishDictionary(d) + LB + b$ + RB + LB + c$ + RB
29. NEXT
30. CLOSE #1
31. PRINT "Done creating Hash Table."
32.  
33. ' Done developing fast lookup tool. Now time for an application.
34.  
35. PRINT "Looking up"
36. DIM RandomWords(50000) AS STRING
37. FOR i = 1 TO 50000
38.     c = INT(RND * 466544) + 1
39.     RandomWords(i) = WordList(c)
40. NEXT
41.  
42. t# = TIMER
43. FOR i = 1 TO 50000
44.     'PRINT "Searching for: "; RandomWords(i),
45.     l$ = Lookup$(RandomWords(i))
46.     'IF l$ <> "" THEN
47.     'l = INSTR(l$, " ")
48.     'word$ = LEFT$(l$, l - 1)
49.     'index = VAL(MID$(l$, l + 1))
50.     'PRINT WordList(index) 'to show that we got the index back successfully
51.     'ELSE
52.     'PRINT "NOT FOUND!"
53.     'END IF
54. NEXT
55. PRINT USING "###.### seconds lookup using Hash Table"; TIMER - t#
56.  
57. t# = TIMER
58. FOR i = 1 TO 50000
59.     index = FindIndex(RandomWords(i))
60.     'PRINT "Searching for: "; RandomWords(i),
61.     'IF index THEN 'to show that we got the index back successfully
62.     '    PRINT WordList(index)
63.     'ELSE
64.     '    PRINT "NOT FOUND!"
65.     'END IF
66. NEXT
67. PRINT USING "###.### seconds lookup using Binary Search"; TIMER - t#
68.  
69. PRINT
70. PRINT "And just to compare results -- the first 15 words:"
71. FOR i = 1 TO 10
72.     'PRINT "Searching for: "; RandomWords(i),
73.     l$ = Lookup$(RandomWords(i))
74.     IF l$ <> "" THEN
75.         l = INSTR(l$, " ")
76.         word$ = LEFT$(l$, l - 1)
77.         index = VAL(MID$(l$, l + 1))
78.         PRINT WordList(index), 'to show that we got the index back successfully
79.     ELSE
80.         PRINT "NOT FOUND!",
81.     END IF
82.     index = FindIndex(RandomWords(i))
83.     'PRINT "Searching for: "; RandomWords(i),
84.     IF index THEN 'to show that we got the index back successfully
85.         PRINT WordList(index)
86.     ELSE
87.         PRINT "NOT FOUND!"
88.     END IF
89. NEXT
90.  
91.  
92.  
93.  
94. FUNCTION Lookup$ (a AS STRING)
95.     r$ = ""
96.     b$ = EnglishDictionary(HashFunc(a))
97.     c$ = ""
98.     d$ = ""
99.     IF b$ <> "" THEN
100.         DO WHILE c$ <> a
101.             c$ = ReturnBetween(b$, LB, RB)
102.             IF c$ = "" THEN EXIT DO
103.             b$ = RIGHT$(b$, LEN(b$) - LEN(LB + c$ + RB))
104.             d$ = ReturnBetween(b$, LB, RB)
105.         LOOP
106.     END IF
107.     r$ = a + "  " + d$
108.     Lookup$ = r$
109. END FUNCTION
110.  
111. FUNCTION ReturnBetween$ (a AS STRING, b AS STRING, c AS STRING) ' input string, left bracket, right bracket
112.     i = INSTR(a, b)
113.     j = INSTR(a, c)
114.     f = LEN(c)
115.     ReturnBetween$ = MID$(a, i + f, j - (i + f))
116. END FUNCTION
117.  
118. FUNCTION HashFunc (s$)
119.     DIM hash~&, i
120.     hash~& = 5381
121.     FOR i = 1 TO LEN(s$)
122.         hash~& = ((hash~& * 33) XOR ASC(s$, i)) MOD 611953
123.     NEXT i
124.     HashFunc = hash~&
125. END FUNCTION
126.  
127.  
128. FUNCTION ReplaceSubString$ (a AS STRING, b AS STRING, c AS STRING)
129.     j = INSTR(a, b)
130.     IF j > 0 THEN
131.         r$ = LEFT$(a, j - 1) + c + ReplaceSubString$(RIGHT$(a, LEN(a) - j + 1 - LEN(b)), b, c)
132.     ELSE
133.         r$ = a
134.     END IF
135.     ReplaceSubString$ = r$
136. END FUNCTION
137.  
138.  
139. SUB Sort (Array() AS STRING)
140.     'The dice sorting routine, optimized to use _MEM and a comb sort algorithm.
141.     'It's more than fast enough for our needs here I th ink.  ;)
142.     gap = UBOUND(array)
143.     DO
144.         gap = 10 * gap \ 13
145.         IF gap < 1 THEN gap = 1
146.         i = 0
147.         swapped = 0
148.         DO
149.             IF _STRCMP(Array(i), Array(i + gap)) > 0 THEN
150.                 SWAP Array(i), Array(i + gap)
151.                 swapped = -1
152.             END IF
153.             i = i + 1
154.         LOOP UNTIL i + gap > UBOUND(Array)
155.     LOOP UNTIL swapped = 0 AND gap = 1
156. END SUB
157.  
158. FUNCTION FindIndex (search$)
159.     SHARED SearchTimes, LastIndex
160.     SearchTimes = 0
161.     min = 1 'lbound(wordlist)
162.     max = 466544 'ubound(wordlist)
163.  
164.     DO UNTIL found
165.         SearchTimes = SearchTimes + 1
166.         gap = (max + min) \ 2
167.         compare = _STRCMP(search$, WordList(gap))
168.         IF compare > 0 THEN
169.             min = gap
170.         ELSEIF compare < 0 THEN
171.             max = gap
172.         ELSE
173.             FindIndex = gap
174.             found = -1
175.             EXIT FUNCTION
176.         END IF
177.         IF max - min < 1 THEN LastIndex = gap: found = -1 'it's not in the list
178.         ' PRINT min, max, search$, WordList(gap), compare
179.         ' SLEEP
180.     LOOP
181. END FUNCTION
182.  
183.  

Faster than previously by about half, but still about twice as slow as the  binary search method...

Regardless; I think the results speak to show that when your data is already sorted, doing a binary search of it is rather quite efficient. 

Anyway, I think I've did as you asked:

I think the burden's on you to do the speed test m8 (for a large data set with lots of performance demand).

If it's *wrong* at this point, I think the burden's on you to show us where and how.

[STxAxTIC]

Nah, I don't need to prove shit to you guys again on this. Fun talk though. Someone who takes the time to sift through this convo, and the way Steve split it among two threads, will get a real chuckle.

If you really want a *win* on this Steve, adjust it for a dataset size typical of a respectable database. A few billion if you can. There's the bait. You might even be right. Try a billion or so.

EDIT:

shit car's been running. lemme fix this up later

[Pete]

Check your refrigerator. If it's running too, the chances are it's having an affair with your car. You'll probably be back soon, because history proves frigid relationships don't last too long.

Seriously Bill, billions of data entries and a hash algorithm to accommodate that project?  What, thousands of collisions that need to be sorted? I would think at that level, you would at least need to combine our methods to get adequate results.

Pete

[SMcNeill]

...adjust it for a dataset size typical of a respectable database. A few billion if you can. There's the bait. You might even be right. Try a billion or so.

Here's you a list with 10 million "words" in it, but it'll easily scale to whatever size you want (as long as you have the memory limits to run it):

Code: QB64: [Select]

1. DEFLNG A-Z
2. DIM SHARED HashTableSize AS LONG
3. HashTableSize = 10000019 ' Best to use a big prime number. Bigger examples are 611953 and 1014729.
4.  
5. DIM SHARED LB AS STRING ' Make sure that bcracketing sequences do not appear in the data source, otherwise use (a) special character(s).
6. DIM SHARED RB AS STRING
7. LB = "{"
8. RB = "}"
9.  
10. PRINT "Reserving memory for Hashtable..."
11. DIM SHARED EnglishDictionary(HashTableSize) AS STRING ' Hash table size does not need to equal the size of the source dictionary itself.
12.  
13.  
14. CONST limit = 10000000
15. DIM SHARED WordList(limit) AS STRING
16.  
17. PRINT "Generating List..."
18. FOR i = 1 TO limit
19.     WordList(i) = STR$(i) 'generate a list of "words"
20. NEXT
21.  
22. PRINT "Sorting list to alphabeticlize it..."
23. Sort WordList() 'to put it in alphabetic order and not numeric
24.  
25. PRINT "Creating Hash Table..."
26. FOR i = 1 TO limit
27.     b$ = WordList(i) 'the word to store
28.     d = HashFunc(b$) ' Calculate the hash value (array address) of the word on hand.
29.     EnglishDictionary(d) = EnglishDictionary(d) + LB + b$ + RB
30. NEXT
31. PRINT "Done creating Hash Table."
32.  
33. ' Done developing fast lookup tool. Now time for an application.
34.  
35. PRINT "Generating search list..."
36. DIM RandomWords(limit) AS STRING
37. RandomWords() = WordList() 'lets just look up all the damn words
38.  
39.  
40. PRINT "Searching using Hash Table"
41. t# = TIMER
42. FOR i = 1 TO limit
43.     l$ = Lookup$(RandomWords(i))
44. NEXT
45. PRINT USING "###.### seconds lookup using Hash Table"; TIMER - t#
46.  
47. PRINT "Searching using Binary Search"
48. t# = TIMER
49. FOR i = 1 TO limit
50.     index = FindIndex(RandomWords(i))
51.     'PRINT i, index, "?"; RandomWords(index)
52.     'SLEEP
53. NEXT
54. PRINT USING "###.### seconds lookup using Binary Search"; TIMER - t#
55.  
56.  
57. FUNCTION Lookup$ (a AS STRING)
58.     r$ = ""
59.     b$ = EnglishDictionary(HashFunc(a))
60.     c$ = ""
61.     d$ = ""
62.     IF b$ <> "" THEN
63.         DO WHILE c$ <> a
64.             c$ = ReturnBetween(b$, LB, RB)
65.             IF c$ = "" THEN EXIT DO
66.             b$ = RIGHT$(b$, LEN(b$) - LEN(LB + c$ + RB))
67.             'd$ = ReturnBetween(b$, LB, RB)
68.         LOOP
69.     END IF
70.     r$ = a '+ "  " + d$
71.     Lookup$ = r$
72. END FUNCTION
73.  
74. FUNCTION ReturnBetween$ (a AS STRING, b AS STRING, c AS STRING) ' input string, left bracket, right bracket
75.     i = INSTR(a, b)
76.     j = INSTR(a, c)
77.     f = LEN(c)
78.     ReturnBetween$ = MID$(a, i + f, j - (i + f))
79. END FUNCTION
80.  
81. FUNCTION HashFunc (s$)
82.     DIM hash~&, i
83.     hash~& = 5381
84.     FOR i = 1 TO LEN(s$)
85.         hash~& = ((hash~& * 33) XOR ASC(s$, i)) MOD HashTableSize
86.     NEXT i
87.     HashFunc = hash~&
88. END FUNCTION
89.  
90.  
91. FUNCTION ReplaceSubString$ (a AS STRING, b AS STRING, c AS STRING)
92.     j = INSTR(a, b)
93.     IF j > 0 THEN
94.         r$ = LEFT$(a, j - 1) + c + ReplaceSubString$(RIGHT$(a, LEN(a) - j + 1 - LEN(b)), b, c)
95.     ELSE
96.         r$ = a
97.     END IF
98.     ReplaceSubString$ = r$
99. END FUNCTION
100.  
101.  
102. SUB Sort (Array() AS STRING)
103.     'The dice sorting routine, optimized to use _MEM and a comb sort algorithm.
104.     'It's more than fast enough for our needs here I th ink.  ;)
105.     gap = UBOUND(array)
106.     DO
107.         gap = 10 * gap \ 13
108.         IF gap < 1 THEN gap = 1
109.         i = 0
110.         swapped = 0
111.         DO
112.             IF _STRCMP(Array(i), Array(i + gap)) > 0 THEN
113.                 SWAP Array(i), Array(i + gap)
114.                 swapped = -1
115.             END IF
116.             i = i + 1
117.         LOOP UNTIL i + gap > UBOUND(Array)
118.     LOOP UNTIL swapped = 0 AND gap = 1
119. END SUB
120.  
121. FUNCTION FindIndex (search$)
122.     SHARED SearchTimes, LastIndex
123.     SearchTimes = 0
124.     min = 1 'lbound(wordlist)
125.     max = limit + 1
126.  
127.     DO UNTIL found
128.         SearchTimes = SearchTimes + 1
129.         gap = (max + min) \ 2
130.         compare = _STRCMP(search$, WordList(gap))
131.         IF compare > 0 THEN
132.             min = gap
133.         ELSEIF compare < 0 THEN
134.             max = gap
135.         ELSE
136.             FindIndex = gap
137.             found = -1
138.             EXIT FUNCTION
139.         END IF
140.         IF max - min < 1 THEN LastIndex = gap: found = -1 'it's not in the list
141.         'PRINT min, max, search$, WordList(gap), compare
142.         'SLEEP
143.     LOOP
144. END FUNCTION
145.  

One word of caution though:  This won't run in QB64x32...

You wanted a hash table size larger than the data set ("Also your wordlist of 400k+ entries exceeded the value of the hash table size of 300007. You wired it for collisions in other words."), and simply reserving space for it in memory takes up about 2.6GB of RAM, as you can see just from the snippet below:

Code: QB64: [Select]

1. DEFLNG A-Z
2. DIM SHARED HashTableSize AS LONG
3. HashTableSize = 10000019 ' Best to use a big prime number. Bigger examples are 611953 and 1014729.
4.  
5. DIM SHARED LB AS STRING ' Make sure that bcracketing sequences do not appear in the data source, otherwise use (a) special character(s).
6. DIM SHARED RB AS STRING
7. LB = "{"
8. RB = "}"
9.  
10. PRINT "Reserving memory for Hashtable..."
11. DIM SHARED EnglishDictionary(HashTableSize) AS STRING ' Hash table size does not need to equal the size of the source dictionary itself.

Once the data is all filled and in memory, it requires 3,418.6MB to run without  crashing.

(And, for what it's worth, the binary search still beats the hash table for speed, on my PC, with one taking 6 seconds, the other taking 4.5.)

[_vince]

Steve, the big-O notation is designed to specifically not compare apples to oranges. Dicscrete calculus will be a lesson for another time... I just cant right now, my facepalm hurts.

Dicscrete calculus, Bill? I think you'd better chose a search method and get that spell checker up and working for craps sake.

If you mean discrete calculus, is that one of those math courses offered at night for active singles? If so, what is the probably of completing the course without contracting a nasty case of standard deviations?

Pete :D

Either way, the dic will secrete

[Pete]

They say comedy is contagious, but I'm not sure anyone wants to catch it that way.

Pete :D

[Ed Davis]

Well, I thought I would give this a try.

I took the original code, and tried to make it "apples to apples" as much as possible.

Note that for the hash function proper, no need to do a mod on each iteration.  One at the end is enough.  Also, I redid the hash lookup, as it was doing lots of extra work.

On my machine, hashing wins: .109 vs .219.  About twice as fast.

Code: QB64: [Select]

1. DIM SHARED HashTableSize AS LONG
2. HashTableSize = 500009' Best to use a big prime number. Bigger examples are 611953 and 1014729.
3.  
4. DIM SHARED LB AS STRING ' Make sure that bcracketing sequences do not appear in the data source, otherwise use (a) special character(s).
5. DIM SHARED RB AS STRING
6. LB = "{"
7. RB = "}"
8.  
9. DIM SHARED EnglishDictionary(HashTableSize) AS STRING ' Hash table size does not need to equal the size of the source dictionary itself.
10.  
11. OPEN "466544 Word List.txt" FOR BINARY AS #1
12.  
13. DIM SHARED WordList(466545) AS STRING
14. PRINT "Loading library"
15. DO UNTIL EOF(1)
16.     count = count + 1
17.     LINE INPUT #1, WordList(count)
18. LOOP
19. CLOSE #1
20.  
21. print "Sorting wordlist"
22. Sort WordList()
23.  
24. print "Creating Hash Table"
25. i = 0
26. FOR i = 1 TO ubound(wordlist)
27.     b$ = WordList(i) 'the word to store
28.     d = HashFunc(b$) ' Calculate the hash value (array address) of the word on hand.
29.     if d < 0 then
30.         print "hash out of range"
31.         end
32.     end if
33.     EnglishDictionary(d) = EnglishDictionary(d) + LB + b$ + RB
34. NEXT
35. CLOSE #1
36.  
37. ' Done developing fast lookup tool. Now time for an application.
38.  
39. const ITER = 75000
40.  
41. PRINT "Creating "; ITER; " random word lookup table"
42. DIM RandomWords(ITER) AS STRING
43. FOR i = 1 TO ITER
44.     c = INT(RND * 466544) + 1
45.     RandomWords(i) = WordList(c)
46. NEXT
47.  
48. Print "Search via Hashing...       ";
49. t# = TIMER
50. FOR i = 1 TO ITER
51.     l$ = Lookup$(RandomWords(i))
52.     if l$ <> RandomWords(i) then
53.         print "HashTable error - searched: ", RandomWords(i), " found: ", l$
54.         end
55.     end if
56. NEXT
57. PRINT USING "###.### seconds lookup using Hash Table"; TIMER - t#
58.  
59. Print "search via Binary Search... ";
60. t# = TIMER
61. FOR i = 1 TO ITER
62.     index = FindIndex(RandomWords(i))
63.     if WordList(index) <> RandomWords(i) then
64.         print "BinarySearch error - searched: ", RandomWords(i), " found: ", WordList(index)
65.     end if
66. NEXT
67. PRINT USING "###.### seconds lookup using Binary Search"; TIMER - t#
68.  
69. PRINT
70. PRINT "And just to compare results -- the first 10 words:"
71. FOR i = 1 TO 10
72.     'PRINT "Searching for: "; RandomWords(i),
73.     l$ = Lookup$(RandomWords(i))
74.     IF l$ <> "" THEN
75.         l = INSTR(l$, " ")
76.         word$ = LEFT$(l$, l - 1)
77.         index = VAL(MID$(l$, l + 1))
78.         PRINT WordList(index), 'to show that we got the index back successfully
79.     ELSE
80.         PRINT "NOT FOUND!",
81.     END IF
82.     index = FindIndex(RandomWords(i))
83.     'PRINT "Searching for: "; RandomWords(i),
84.     IF index THEN 'to show that we got the index back successfully
85.         PRINT WordList(index)
86.     ELSE
87.         PRINT "NOT FOUND!"
88.     END IF
89. NEXT
90.  
91. FUNCTION Lookup$ (s AS STRING)
92.     haystack$ = EnglishDictionary(HashFunc(s))
93.     needle$ = LB + s + RB
94.     p = instr(haystack$, needle$)
95.     if p = 0 then
96.         Lookup$ = ""
97.     else
98.         Lookup$ = mid$(haystack$, p + 1, LEN(needle$) - 2)
99.     end if
100. END FUNCTION
101.  
102. FUNCTION HashFunc (s AS STRING) ' input string
103.     DIM hash~&, i
104.  
105.     hash~& = 5381
106.  
107.     FOR i = 1 TO LEN(s$)
108.         hash~& = ((hash~& * 33) XOR ASC(s$, i))
109.     NEXT i
110.  
111.     HashFunc = hash~& mod HashTableSize
112. END FUNCTION
113.  
114. SUB Sort (Array() AS STRING)
115.     'The dice sorting routine, optimized to use _MEM and a comb sort algorithm.
116.     'It's more than fast enough for our needs here I think.  ;)
117.     gap = UBOUND(array)
118.     DO
119.         gap = 10 * gap \ 13
120.         IF gap < 1 THEN gap = 1
121.         i = 0
122.         swapped = 0
123.         DO
124.             IF _STRCMP(Array(i), Array(i + gap)) > 0 THEN
125.                 SWAP Array(i), Array(i + gap)
126.                 swapped = -1
127.             END IF
128.             i = i + 1
129.         LOOP UNTIL i + gap > UBOUND(Array)
130.     LOOP UNTIL swapped = 0 AND gap = 1
131. END SUB
132.  
133. FUNCTION FindIndex (search$)
134.     SHARED SearchTimes, LastIndex
135.     SearchTimes = 0
136.     min = lbound(wordlist)
137.     max = ubound(wordlist)
138.  
139.     DO UNTIL found
140.         SearchTimes = SearchTimes + 1
141.         gap = (max + min) \ 2
142.         compare = _STRCMP(search$, WordList(gap))
143.         IF compare > 0 THEN
144.             min = gap
145.         ELSEIF compare < 0 THEN
146.             max = gap
147.         ELSE
148.             FindIndex = gap
149.             found = -1
150.             EXIT FUNCTION
151.         END IF
152.         IF max - min < 1 THEN LastIndex = gap: found = -1 'it's not in the list
153.         ' PRINT min, max, search$, WordList(gap), compare
154.         ' SLEEP
155.     LOOP
156. END FUNCTION
157.  
158.  

Many years ago (1990 to be precise), when I was needing something like this for a project I was doing in C, I ran extensive tests on different search functions - avltree, binarytree, binary search, hashing (I tested 135 different hash functions), custom lists tuned to the data, and a few more.

I reran some of those tests this morning.

In C at least, with my code (e.g., a custom binary search, instead of the built-in bsearch), hashing is about 2 times faster than binary searching.  So pretty much what I found for the code above.

Per the literature, it is even faster to use a power of 2 for the table size, rather than a prime for the table size, and then and off the appropriate bits instead of doing the mod at the end of the hash function.  In my tests with C, I did find this to be true, although it was just slightly faster, not strikingly so.  But of course, when you have potentially many millions of lookups, then every bit of speed counts.  Also note that the power of 2 table size assumes a high quality hash function.  Otherwise, it is best to stick with a prime number as the table size.

Anyway, cool topic!  Thanks to everyone who shared something on this!

[SMcNeill]

I’m getting perfectly equal time tests on my PC, with both taking 0.164 seconds to run.  Either way, both methods are generally fast enough to hold up and work in most situations.

The biggest advantage to the hash list is that you dont need sorted data, whereas a binary search has lower memory requirements.  My advice is to choose whichever you prefer; either will usually work in most cases.

[SMcNeill]

Taking Ed's improvements, I played around and tweaked the hash routine even further, making it a  much faster program:

Code: QB64: [Select]

1. DIM SHARED HashTableSize AS LONG
2. HashTableSize = 500009 ' Best to use a big prime number. Bigger examples are 611953 and 1014729.
3.  
4. DIM SHARED EnglishDictionary(HashTableSize) AS STRING ' Hash table size does not need to equal the size of the source dictionary itself.
5.  
6. OPEN "466544 Word List.txt" FOR BINARY AS #1
7.  
8. DIM SHARED WordList(466545) AS STRING
9. PRINT "Loading library"
10. DO UNTIL EOF(1)
11.     count = count + 1
12.     LINE INPUT #1, WordList(count)
13. LOOP
14. CLOSE #1
15.  
16. PRINT "Creating Hash Table"
17. i = 0
18. FOR i = 1 TO UBOUND(wordlist)
19.     b$ = WordList(i) 'the word to store
20.     d = HashFunc(b$) ' Calculate the hash value (array address) of the word on hand.
21.     IF d < 0 THEN
22.         PRINT "hash out of range"
23.         END
24.     END IF
25.     EnglishDictionary(d) = EnglishDictionary(d) + CHR$(LEN(b$)) + b$
26. NEXT
27. CLOSE #1
28.  
29. ' Done developing fast lookup tool. Now time for an application.
30.  
31.  
32.  
33. CONST ITER = 75000
34.  
35. PRINT "Creating "; ITER; " random word lookup table"
36. DIM RandomWords(ITER) AS STRING
37. FOR i = 1 TO ITER
38.     c = INT(RND * 466544) + 1
39.     RandomWords(i) = WordList(c)
40. NEXT
41.  
42. PRINT "Search via Hashing...       ";
43. t# = TIMER
44. FOR i = 1 TO ITER
45.     l$ = Lookup$(RandomWords(i))
46.     IF l$ <> RandomWords(i) THEN
47.         PRINT "HashTable error - searched: ", RandomWords(i), " found: ", l$
48.         END
49.     END IF
50. NEXT
51. PRINT USING "###.### seconds lookup using Hash Table"; TIMER - t#
52.  
53. FUNCTION Lookup$ (s AS STRING)
54.     haystack$ = EnglishDictionary(HashFunc(s))
55.     size = 1: l = 1
56.     DO UNTIL needle$ = s OR size = 0
57.         size = ASC(haystack$, l)
58.         needle$ = MID$(haystack$, l + 1, size)
59.         l = l + size + 1
60.     LOOP
61.     IF size > 0 THEN Lookup$ = needle$
62. END FUNCTION
63.  
64. FUNCTION HashFunc (s AS STRING) ' input string
65.     DIM hash~&, i
66.     hash~& = 5381
67.     FOR i = 1 TO LEN(s$)
68.         hash~& = ((hash~& * 33) XOR ASC(s$, i))
69.     NEXT i
70.     HashFunc = hash~& MOD HashTableSize
71. END FUNCTION

What's the main difference here?

EnglishDictionary(d) = EnglishDictionary(d) + CHR$(LEN(b$)) + b$

We're not storing our data separated by delimiters.  Instead, we're manually recording the size of each entry and using it to directly retrieve our information.  (Side note: This is a simple implementation of those dreaded "linked lists" which STx is so obsessive over.  It's hard to believe he didn't implement one from the start, since he's the resident guru on the subject for us!)

By going this route, we don't need to rely on INSTR to search for the various entries for us, giving us two distinct advantages:

1) It's much faster to "jump" from word to word, than it is to search byte by byte for a match.

2) It's less likely to generate any false positives, as we're retrieving the exact string from memory and comparing.  _INSTR("dogfood", "dog") is a match -- there's a "dog" in "dogfood", but "dog" <> "dogfood" if we compare directly.

Like most code, when it comes to speed, the devil's in the details.

[Pete]

I've already pointed out INSTR requires use of a delimiter like a comma.

dog - dogfood is easily solved that way...

wordlist$ = ",bill,cat,dog,dogfood,pete,steve,"
a = INSTR(wordlist$,",dog,")

dogfood would not be returned, just dog. Besides... dog food is two words. :P

Hey, did you try my INSTR search and frequency sample? It's dog gone fast!
https://www.qb64.org/forum/index.php?topic=1001.msg102017#msg102017

Pete

[SMcNeill]

I've already pointed out INSTR requires use of a delimiter like a comma.

dog - dogfood is easily solved that way...

wordlist$ = ",bill,cat,dog,dogfood,pete,steve,"
a = INSTR(wordlist$,",dog,")

dogfood would not be returned, just dog. Besides... dog food is two words. :P

Hey, did you try my INSTR search and frequency sample? It's dog gone fast!
https://www.qb64.org/forum/index.php?topic=1001.msg102017#msg102017

Pete

That's the point I was making with the previous post -- instead of using INSTR at all, which requires you to SEARCH the string for your words, store the length in front of each entry instead.

wordlist$ = "4bill3cat3dog7dogfood4pete5steve"

here you read 4, then get 4 characters for a string -- "bill"
then read 3, get 3 characters for "cat"...
then read 3, get 4 characters for "dog" -- MATCH!

Your method works like this:

wordlist$ = ",bill,cat,dog,dogfood,pete,steve,"
a = INSTR(wordlist$,",dog,")

byte 1 -- ",bill" <> ",dog"
byte 2 -- "bill," <> ",dog,"
byte 3 -- "ill,c" <> ",dog,"
byte 4 -- "ll,ca" <> ",dog,"
... and on byte by byte until ",dog," = ",dog,"

That's a 33 character string, and ",dog," is 5 characters, so there's up to 28 checks that the computer is doing behind the scene to look for the first occurrence of your string...

compared to a max of 6 comparisons if we simple read each word all at once. 

When dealing with a process which may be repeated in multiple loops, over and over, it ends up making a difference in performance.  ;)

[Pete]

But that's what seed in INSTR() is for, so you skip from delimiter to delimiter.

See the same post and the second code box, which uses seed% to deal with lookup frequency within a random word list.

Pete

[SMcNeill]

But that's what seed in INSTR() is for, so you skip from delimiter to delimiter.

See the same post and the second code box, which uses seed% to deal with lookup frequency within a random word list.

Pete

Seed gives you a starting point, but you still check byte by byte for a match...

a$ = “,1,2,3,4,5,3,7,8,”

seed = INSTR(seed + 1, a$, “,3,”)

Run first, it does a compare at byte 1, then byte 2, then 3... at byte 5 it finds “,3,” — 5 comparisons.

Then you have:

seed = seed + LEN(“,3,”)  ‘5 + 3
seed = INSTR(seed, a$, “,3,”)

Now you start at byte 8 and search byte by byte until you get to byte 11... 5 more comparisons.

INSTR by its nature is a byte by byte compare routine (it has to be, or else how would it know where the search string appears at?  A random guess?)


wordlist$ = "4bill3cat3dog7dogfood4pete5steve0”

Placing the size first lets you advance by words, not by bytes. 

See the difference, and why one is faster than the other?