I was using the vtkIntArray::LookupValue on an array with repetitive values, similar to this:
import vtk
values = [ 2, 2, 3, 3, 3, 8, 7, 8, 7, 8, 7, 6, 9, 6, 9, 6, 9]
array = vtk.vtkIntArray()
for v in values:
array.InsertNextValue(v)
for v in [ 2,3,6,7,8,9 ] :
print(f"{v} : {array.LookupValue(v)}" )
This yields the following - to me somewhat surprising - output:
2 : 1
3 : 2
6 : 15
7 : 8
8 : 9
9 : 12
I sort of expected that lookupValue would return the first index, but clearly it doesn’t. This is due, I suppose, to vtkGenericDataArrayLookupHelper::UpdateLookup() using unstable algorithms std::partition and std::sort.
I think it may be useful to have a stable implementation of the lookup, but not if the user pays by a performance degradation. Since VTK now supports C++11, we could consider to change the implementation by using an std::unordered_map of values containing vectors of indices. This avoids the partitioning and sorting and greatly simplifies looking up values and lists of values.To see if this approach would perform well enough to justify the change I made a (simplified) index lookup.
I implemented the index lookup in three different ways:
- unstable: vector of index-value pairs with unstable partitioning for nan and unstable sorting;
- stable: vector of index-value pairs with stable partitioning for nan and stable sorting;
- mapped: unordered_map of vectors of indices
These are tested with a vector of 1000000 ints populated by random numbers, sorted numbers and unsorted numbers. Each of these population approaches are done with
- 10 unique numbers
- 100000 unique numbers
The tests show the timings for lookup of
- first: the first lookup (invoking the construction of auxiliary data structures);
- single: cumulative time for looking up a single index for each entry of the vector;
- all: cumulative time for looking up all indices for each entry of the vector;
map_of_vectors.cpp (10.6 KB).
These are the results build with g++ - O3 (GCC) 6.3.1 20170216 (Red Hat 6.3.1-3)
unstable random 1 | first: 9.644e-02 single: 4.119e-02 all: 3.341e+02
stable random 1 | first: 7.332e-02 single: 3.865e-02 all: 3.329e+02
mapped random 1 | first: 2.063e-02 single: 1.174e-02 all: 3.201e+02
unstable random 2 | first: 1.051e-01 single: 2.048e-01 all: 3.323e-01
stable random 2 | first: 1.109e-01 single: 2.047e-01 all: 3.278e-01
mapped random 2 | first: 8.999e-02 single: 5.380e-02 all: 1.614e-01
unstable sorted 1 | first: 3.880e-02 single: 2.570e-02 all: 2.065e+02
stable sorted 1 | first: 5.930e-02 single: 2.630e-02 all: 2.079e+02
mapped sorted 1 | first: 1.340e-02 single: 1.205e-02 all: 2.071e+02
unstable sorted 2 | first: 3.290e-02 single: 3.362e-02 all: 5.553e-02
stable sorted 2 | first: 4.705e-02 single: 3.471e-02 all: 5.593e-02
mapped sorted 2 | first: 2.599e-02 single: 1.410e-02 all: 3.283e-02
unstable reverse 1 | first: 3.013e-02 single: 3.411e-02 all: 5.482e-02
stable reverse 1 | first: 3.904e-02 single: 3.387e-02 all: 5.505e-02
mapped reverse 1 | first: 2.528e-02 single: 1.449e-02 all: 3.362e-02
unstable reverse 2 | first: 8.932e-02 single: 2.535e-02 all: 2.077e+02
stable reverse 2 | first: 4.755e-02 single: 2.538e-02 all: 2.082e+02
mapped reverse 2 | first: 1.345e-02 single: 1.208e-02 all: 2.070e+02
From this it appears that the mapped implementation performs better or equal in all cases.
Are there any objections against modifying the current implementation?