Searching arrays...

BlitzMax Forums/BlitzMax Beginners Area/Searching arrays...

Reactor(Posted 2008) [#1]
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!


degac(Posted 2008) [#2]
Simple examples
Local 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 INT STRING
array2[2] = mytype 'the third is an user-type

' using casting to check what it contains
' you could use a FOR...NEXT or FOR..EACHIN
If String(array2[0]) = "Uno" Print "Contains 'Uno'"
If Int(String(array2[1])) = 10 Print "Contains '10'"
If atype(array2[2]) = mytype
	Print "Is an Atype..."
	Print atype(array2[2]).value
End If



Reactor(Posted 2008) [#3]
Excellent! Thanks... I'll have much array studying to do tomorrow :)


johnnyfreak(Posted 2008) [#4]
what about binary search?


Reactor(Posted 2008) [#5]
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?


Paposo(Posted 2008) [#6]
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


Reactor(Posted 2008) [#7]
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.


Beaker(Posted 2008) [#8]
Use TMaps.


Vilu(Posted 2008) [#9]
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.


Reactor(Posted 2008) [#10]
Thanks guys.

While I'm here... are there any Tmap examples?


johnnyfreak(Posted 2008) [#11]
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.


Vilu(Posted 2008) [#12]
AFAIK, TMap does use balanced binary tree.


johnnyfreak(Posted 2008) [#13]
yep, you're right... i did'nt know it.

so are not TMaps hashTables?


Dreamora(Posted 2008) [#14]
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

:)


johnnyfreak(Posted 2008) [#15]
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...


Vilu(Posted 2008) [#16]
http://www.blitzbasic.com/codearcs/codearcs.php?code=1717
http://www.blitzbasic.com/codearcs/codearcs.php?code=1907

A couple of hash map implementations.