1. Language enhancement
- Posted by Joe Otto <jotto at NETZERO.NET>
Jul 08, 1999
-
Last edited Jul 09, 1999
Robert,
I think a very useful addition to Euphoria would be a function similar to
find () as follows:
i = find_sorted (x, s)
This function would assume that "s" is sorted and perform a binary search.
I haven't done any benchmarking on this, but as I understand it, find ()
only does a linear search because it does not take a sorted sequence.
Correct?
Joe
________________________________________________________
NetZero - We believe in a FREE Internet. Shouldn't you?
Get your FREE Internet Access and Email at
http://www.netzero.net/download/index.html
2. Re: Language enhancement
>Robert,
>
>I think a very useful addition to Euphoria would be a function similar to
>find () as follows:
>
> i = find_sorted (x, s)
>
>This function would assume that "s" is sorted and perform a binary search.
> I haven't done any benchmarking on this, but as I understand it, find ()
>only does a linear search because it does not take a sorted sequence.
> Correct?
That's correct. A binary search might actually be a nice addition; it should
on average be much faster for large sequences. Maybe it could be put in the
misc.e file, or possibly sort.e.
In the meantime, this function (in case you needed one) should do the trick:
-- BEGIN CODE --
function sfind (object x, sequence s)
integer min, max, pos, comp
min = 1
max = length (s)
while (min <= max) do
pos = min + floor ((max - min) / 2)
comp = compare (s[pos], x)
if (comp = 0) then
return pos
elsif (comp < 0) then
min = pos + 1
else
max = pos - 1
end if
end while
return 0
end function
-- END CODE --
Hope this helps,
Rod Jackson
3. Re: Language enhancement
- Posted by Joe Otto <jotto at NETZERO.NET>
Jul 09, 1999
-
Last edited Jul 10, 1999
Thanks for the code Rod - I've already written a Euphoria version though.
:)
What I'd like to see is the binary search algorithm implemented by Robert
*internally* like find () is. That would give us access to VERY fast
searches.
Joe
-----Original Message-----
From: Roderick Jackson [SMTP:rjackson at CSIWEB.COM]
Sent: Friday, July 09, 1999 11:33 AM
To: EUPHORIA at LISTSERV.MUOHIO.EDU
Subject: Re: Language enhancement
>Robert,
>
>I think a very useful addition to Euphoria would be a function similar to
>find () as follows:
>
> i = find_sorted (x, s)
>
>This function would assume that "s" is sorted and perform a binary search.
> I haven't done any benchmarking on this, but as I understand it, find ()
>only does a linear search because it does not take a sorted sequence.
> Correct?
That's correct. A binary search might actually be a nice addition; it
should
on average be much faster for large sequences. Maybe it could be put in the
misc.e file, or possibly sort.e.
In the meantime, this function (in case you needed one) should do the
trick:
-- BEGIN CODE --
function sfind (object x, sequence s)
integer min, max, pos, comp
min = 1
max = length (s)
while (min <= max) do
pos = min + floor ((max - min) / 2)
comp = compare (s[pos], x)
if (comp = 0) then
return pos
elsif (comp < 0) then
min = pos + 1
else
max = pos - 1
end if
end while
return 0
end function
-- END CODE --
Hope this helps,
Rod Jackson
________________________________________________________
NetZero - We believe in a FREE Internet. Shouldn't you?
Get your FREE Internet Access and Email at
http://www.netzero.net/download/index.html
