2
\$\begingroup\$

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...

\$\endgroup\$
6
\$\begingroup\$

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
  x.report('cascading create:') {index = QuickIndex.new(floats)}
  x.report('cascading access:') do
    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------
NUMBER OF FLOATS    CASCADING       FLAT     CASCADING    FLAT
    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------
NUMBER OF FLOATS    CASCADING       FLAT     CASCADING    FLAT
    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          
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Nat Jan 9 '14 at 10:33
  • \$\begingroup\$ @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. \$\endgroup\$ – Wayne Conrad Jan 9 '14 at 12:12
  • \$\begingroup\$ @Nat, Please see above for memory benchmarks. \$\endgroup\$ – Wayne Conrad Jan 9 '14 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.