# Improvements on tree index class

I developed a QuickIndex class which serves to index arrays of stringafiable objects using a tree structure. The purpose is to then primarily to allow for fast index or include? method calls directed to the quick_index object as a proxy for the original array, as the index tree can be traversed much more efficiently than a linear array.

There is a gist containing the whole class, but the main functionality comes from the two methods included below.

class QuickIndex
def initialize ary, stop_char = "!"
@stop_char = stop_char
@size = ary.size
@index = Hash.new
ary.each_with_index do |num, i|
num = num.to_s.split("") << @stop_char
index = @index
until num.empty?
n = num.shift
index = index[n] ||= (n == @stop_char ? [] : {})
end
index << i
end
end

def index item
index = @index
(item.to_s.split("") << @stop_char).each { |n| next unless index = (index[n] or nil rescue nil) }
index
end
end


The stop_char is a single character which serves to indicate the end of a string in the index.

The class is specifically intended for locating specific values in very large (NArray) arrays of ints or floats, but it's nice for it to work with other objects too.

It works reasonably well, but I'd like to know of any optimisations or alternative strategies to this problem which would make the class quicker at either building or querying the index and/or reduce the memory footprint. Or if there's some standard library alternative I've overlooked...

You can build it faster and use it faster if you use a flat hash instead of cascading hashes.

Here's a simple implementation using a "flat" hash:

class QuickerIndex

def initialize(array)
@index = {}
array.each_with_index do |item, i|
(@index[item.to_s] ||= []) << i
end
end

def index(item)
@index[item.to_s]
end

end


and a benchmark to compare the two:

require 'benchmark'
floats = 10_000.times.map{rand}
Benchmark.benchmark('', 20) do |x|
index = nil
floats.each do |float|
index.index(float)
end
end
x.report('flat create:') {index = QuickerIndex.new(floats)}
x.report('flat access:')  do
floats.each do |float|
index.index(float)
end
end
end


# CPU

## No duplicate items

Without duplicate items, the CPU time needed to create and access various sizes of indices were:

                    ------CREATE--------     -----ACCESS------
10,000             0.27         0.05          0.20    0.03
100,000             3.98         0.45          2.42    0.43
1,000,000           140.75        14.13         69.72    4.84


With no duplicate items, flat hash scales a little better than cascading hash in create, but much better in access. Flat hash is faster for create and access.

## Duplicate items

Now, what about repeated items? You indicate that there is some likelihood that two items will share the same key (that is, have the same #to_s). Let's assume that each number is duplicated 10 times. That is, in a list of 10,000 floats, there are really 1,000 unique floats; in a list of 100,000 floats, there are 10,000 unique floats:

                    ------CREATE--------     -----ACCESS------
10,000              0.23        0.02       0.20       0.02
100,000              2.20        0.26       2.12       0.21
1,000,000             27.70        3.56      26.29       2.62
10,000,000            364.14       25.16     341.66      23.44


Both flat and cascading hash perform better with duplicate items than without. Flat hash still scales better, and is always faster.

# Memory

Unless compiled with the right switch, Ruby lacks an effective way to tell how much memory is in use by its objects. As a proxy, we can use "ps", which reports the total process size in kilobytes. It's an imperfect proxy, but it's the best we have.

Here are the numbers for various numbers of floats. The number of unique floats was always kept at 1/10th the total number of floats. The memory size reported is the amount that memory usage went up after creating the instance of the index class:

NUMBER OF FLOATS    CASCADING        FLAT
10,000             2,048k         52k
100,000            32,952k      1,664k
1,000,000           232,868k     28,596k
10,000,000         2,232,568K    229,512k

• Linear scaling is apparently an improvement, but do I understand correctly that this assumes every float is unique? and that it'll use as at least as much memory as the original array? As I failed to mention in the question, my application involves at least 100 typed arrays (so smaller memory footprint than native ruby arrays) of ints or floats, some of them being millions of items long, hence the need to index, without using too much memory. The domain is vertices and faces of 3D meshes. – Nat Jan 9 '14 at 10:33
• @Nat, You're right, I missed that you are storing multiple indices per key. Still, if this code is modified to do that, I think it will use less memory than the code in question. The code in question creates, worst case, N * D hash tables (N being the number of unique string keys, and D being the key length). I didn't benchmark memory, but will when I get a chance. BTW, the link to the gist is bad. – Wayne Conrad Jan 9 '14 at 12:12
• @Nat, Please see above for memory benchmarks. – Wayne Conrad Jan 9 '14 at 14:21