Searching arrays...
BlitzMax Forums/BlitzMax Beginners Area/Searching arrays...
| ||
Continuing with my "how many questions can a beginner ask in a day" routine- I'm trying to search through an array and find if it holds a value. How can this be done, or is there something more suited than a standard array? Thanks! |
| ||
Simple examplesLocal array:Int[] = [1 , 2 , 3 , 4 , 5 , 6] 'Does it contain '4'? For Local i:Int = 0 Until array.length ' the method allows to know how many items the array contains If array[i] = 4 Print "YES" End If Next ' iterate with EACHIN For Local ai:Int = EachIn array ' ask to the array until the array is empty If ai = 4 Print "YES" End If Next And now how to complicate your life... Type atype Field value:Int End Type Local mytype:atype = New atype mytype.value=152 Local array2:Object[] ' it's a array of GENERIC object... array2 = array2[..3] 'create an array of 3 elements array2[0] = String("Uno") ' the first is a STRING array2[1] = String(10) ' the second should be an Integer...but you need to convert it to a |
| ||
Excellent! Thanks... I'll have much array studying to do tomorrow :) |
| ||
what about binary search? |
| ||
I haven't yet looked into a binary search. I'm storing numbers as the program runs, and then hoping to check afterwards if the're in the list that's been created. Would that work? |
| ||
Hello. If your array are ordered you can look at mid point. If the object searched is minor than this object look at midpoint of low segment otherwise look at high segment. This reduce the number of comparisons. The efficiency is O(log(n)) vs O(n) offered by the other version. The problem is that the array must be ordered and this take a time. Bye, Paposo |
| ||
Thanks Paposo, that's interesting. I'm actually doing the opposite of searching for something- I'm searching through an array to find if a value isn't already in it. When I do need to search for something though I'll looking into ordering the array. |
| ||
Use TMaps. |
| ||
If the array to be searched is insanely large (say, in tens of thousands), it would probably be best to move to hash tables. The performance is always O(1), meaning the size of the array doesn't matter. There are couple of examples in the code archives for hash maps. |
| ||
Thanks guys. While I'm here... are there any Tmap examples? |
| ||
hash maps are the best solution for a large number of elements. i don't know how tMaps handle collisions... you can also use binary trees to mantain O(log n) for search. |
| ||
AFAIK, TMap does use balanced binary tree. |
| ||
yep, you're right... i did'nt know it. so are not TMaps hashTables? |
| ||
johnny: hashtables are nothing else than arrays where you map a given key onto the allowed set of indices. Its not a tree or the like, it is pure arithmetic (key -> integer). That mapping thouch can lead to collisions especially when TMaps have no collisions. TMap are AVL / Black-Red Dictionary tree -> a balanced binary tree. Always log(n) on anything. a TMap can also be seen as key based array / associative array, as you can adress your value with the key instead of an index. Would actually be great if BM allowed that: local myArray:object[""] = new object[""] myArray["Day 1"] = TestObject :) |
| ||
tnx... i know what hash tables and AVLs are. I didn't know what TMap implements. Now i think would be fine to have HMap... |
| ||
http://www.blitzbasic.com/codearcs/codearcs.php?code=1717 http://www.blitzbasic.com/codearcs/codearcs.php?code=1907 A couple of hash map implementations. |