[REBOL] Series comparison techniques
From: atruter::labyrinth::net::au at: 14-Aug-2003 13:56
Given the following code:
<code>
search-series: func [series [series!] operator [string!] value] [
clear rowids
switch operator [
"=" [operator: :equal?]
"<>" [operator: :not-equal?]
"<" [operator: :lesser?]
">" [operator: :greater?]
"<=" [operator: :lesser-or-equal?]
">=" [operator: :greater-or-equal?]
"like" [operator: :find]
]
start: now/time/precise
repeat pos length? series [
if operator series/:pos value [insert tail rowids pos]
]
print now/time/precise - start
rowids
]
max-rows: 100000
;max-rows: 1000000
;max-rows: 10000000
rowids: make block! max-rows
block: make block! max-rows
loop max-rows [insert tail block random 1000]
</code>
I was reasonably happy with the time taken to evaluate:
search-series block "=" 1
for 100,000 1,000,000 and 10,000,000 values respectively (taking .14, 1.375
and 14 seconds on my Win2000 AMD1800XP 256Mb system). Increasing the data
volumes by a factor of 10 increased the time taken by a similar amount.
Since tests for equality are important, I added the following function to
do this:
<code>
find-value: func [series [series!] value] [
clear rowids
start: now/time/precise
while [not none? series: find series value][
insert tail rowids index? series
series: next series
]
print now/time/precise - start
rowids
]
</code>
and was [pleasantly] surprised to see that:
find-value block 1
returned results in .015, .063 and .59 seconds respectively. Which got me
thinking about *how* REBOL could do this given:
1) The series is not sorted
2) Values are not unique
3) Runtime increases at a lesser rate than data volume
I am now wondering what other "clever" techniques / algorithms are
available to handle other operators (eg. <>, <, >, etc)
Thoughts?
Regards,
Ashley
