Find which set of numbers (range) a given number belongs to, without using loops

Question

I'm confused to decide which or what kind of algorithm to find an object based on the following criteria: There are 2 classes: 'TileSets' and 'Tile'. TileSet have 2 int attributes: firstTileId and lastTileId, while Tile has a single int attribute: id, like that:

struct TileSet { int firstTileId, lastTileId; } 

struct Tile { int id; }

The application is supposed to have no more than 10 TileSets (normally 3-5) and 10.000+ Tiles. Speed is extremely crucial to determine which TileSet a Tile with a given id belongs to. The first and last id attributes don't change after a tileset is added to the vector and they don't overlap each other, for example: {{1, 25}, {26, 125}, {126, 781}, {782, 789}...}. There are no holes either in the tile range, as we can see. Tiles vector is not ordered nor it can be. My current implementation (kind of pseudo short code) is:

Vector t = 10.000+ tiles
Vector ts = tilesets with a size of a number of a power of 2 number bigger than 6, at least
for tileIndex = 0; tileIndex < t.size; tileIndex++, do:
   for tilesetIndex = 0; tilesetIndex < ts.size; tilesetIndex++, do:
      if (ts[tilesetIndex].firstTileId >= t[tileIndex].id && t[tileIndex].id <= ts[tilesetIndex].lastTileId) 
         // tile t[tileIndex] belongs to the tileset ts[tilesetIndex]! Done!

What kind of algorithm could I use for this kind of situation? Are there any formulas to this?

Answer 1

You'd use an interval container that uses optimized storage and algorithms.

In this example using Boost ICL, I have made some "arbitrary" choices to generate nice disjunct TileSets:

using TileSets = icl::split_interval_set<int>;

struct TileSet : TileSets::interval_type::type {
    TileSet(int b, int e) : TileSets::interval_type(closed(b, e)) {}
};

struct Tile : TileSets::interval_type::type {
    Tile(int id) : TileSets::interval_type(closed(id, id)) {}
};

The beauty is the high-level coding:

Live On Coliru

TileSets gen_tiles   (size_t n = 100000);
TileSets gen_tilesets(size_t n = (2ull << 8) + 1);

#include <iostream>

int main() {
    auto const tiles = gen_tiles   (10);
    auto const ts    = gen_tilesets(30);

    std::cout << ts << "\n----\n";

    for (auto hit : tiles & ts) {
        std::cout << hit.lower() << " hits in tileset " << *ts.find(hit) << "\n";
    }
}

Prints

{[8,71)[71,133)[133,206)[206,231)[231,465)[465,467)[467,565](565,581)[581,651](651,907)[907,1000)[1000,1395](1395,1429)[1429,1560](1560,1706)[1706,1819)[1819,1835)[1835,1997)[1997,2124](2124,2328)[2328,2913)[2913,2922)[2922,3043)[3043,3338)[3338,3664](3664,3825](3825,3999)[3999,4320](4320,4506](4506,4561](4561,4593](4593,4668)[4668,5143)[5143,5248](5248,5633)[5633,5925](5925,6012](6012,6076)[6076,6117](6117,6119](6119,6175](6175,6184)[6184,6509)[6509,6804](6804,7081](7081,7220)[7220,7852](7852,8325)[8325,8600](8600,8662](8662,9386](9386,9423)[9423,9489](9489,9657](9657,9700](9700,9738](9738,9833](9833,9923]}
----
1561 hits in tileset (1560,1706)
1835 hits in tileset [1835,1997)
3746 hits in tileset (3664,3825]
4459 hits in tileset (4320,4506]
5969 hits in tileset (5925,6012]
5987 hits in tileset (5925,6012]
7320 hits in tileset [7220,7852]
7797 hits in tileset [7220,7852]
7966 hits in tileset (7852,8325)
9508 hits in tileset (9489,9657]

PERFORMANCE

When run with the default sizes (100000 tiles in 2^8+1 tilesets) it takes 0.034s on my box

$ time ./test | tee >(echo "total lines: $(wc -l)") | tail
9987 hits in tileset (9984,9990]
9988 hits in tileset (9984,9990]
9989 hits in tileset (9984,9990]
9990 hits in tileset (9984,9990]
9991 hits in tileset (9990,9995]
9992 hits in tileset (9990,9995]
9993 hits in tileset (9990,9995]
9994 hits in tileset (9990,9995]
9995 hits in tileset (9990,9995]
total lines: 9988

real    0m0.034s
user    0m0.029s
sys 0m0.008s

Live On Coliru that runs in 0.064s. That includes the time taken for output, which does redundant lookups (ts.find(hit))!

UPDATE - Higher Volumes

More performance testing with higher volumes and more specific timing output:

Live On Coliru

#include <boost/icl/interval_set.hpp>
#include <boost/icl/split_interval_set.hpp>

namespace icl = boost::icl;

using TileSets = icl::split_interval_set<int>;

struct TileSet : TileSets::interval_type::type {
    TileSet(int b, int e) : TileSets::interval_type(closed(b, e)) {}
};

struct Tile : TileSets::interval_type::type {
    Tile(int id) : TileSets::interval_type(id) {}
};

TileSets gen_tiles   (size_t n = (1ull << 22));
TileSets gen_tilesets(size_t n = (1ull << 12));

#include <iostream>
#include <iomanip>
#include <boost/chrono/chrono_io.hpp>

template <typename F>
auto timed(char const* task, F&& f) {
    using namespace boost::chrono;
    struct _ {
        high_resolution_clock::time_point s;
        const char* task;
        ~_() { std::cout << " -- (" << task << " completed in " << duration_cast<milliseconds>(high_resolution_clock::now() - s) << ")\n"; }
    } timing { high_resolution_clock::now(), task };

    return f();
}

int main() {
    auto const tiles = timed("Generate tiles", [] { return gen_tiles(); });
    auto const ts    = timed("Generate tile sets", [] { return gen_tilesets(); });

    //std::cout << ts << "\n----\n";

    std::cout << "Random tiles generated:    " << tiles.iterative_size() << " across a domain of " << std::setprecision(2) << static_cast<double>(tiles.size()) << "\n";
    std::cout << "Tilesets to match against: " << ts.iterative_size()    << " across a domain of " << std::setprecision(2) << static_cast<double>(tiles.size()) << "\n";

    timed("Query intersection", [&] { std::cout << "Total number of hits: "   << (tiles & ts).iterative_size() << "\n"; });
    timed("Query difference",   [&] { std::cout << "Total number of misses: " << (tiles - ts).iterative_size() << "\n"; });

    //for (auto hit : tiles & ts) {
        //std::cout << hit.lower() << " hits in tileset " << *ts.find(hit) << "\n";
    //}
}

#include <random>

static auto gen_tile_id = [prng=std::mt19937{42}, dist=std::uniform_int_distribution<>()] () mutable 
    { return dist(prng); };

TileSets gen_tiles(size_t n) {
    TileSets r;
    std::generate_n(icl::inserter(r, r.end()), n, [] () -> Tile { return gen_tile_id(); });
    return r;
}

TileSets gen_tilesets(size_t n) {
    TileSets r;
    std::generate_n(icl::inserter(r, r.end()), n, [] () -> TileSet {
                auto b = gen_tile_id(), e = gen_tile_id();
                return { std::min(b,e), std::max(b,e) };
            });
    return r;
}

Prints (on my box):

 -- (Generate tiles completed in 3773 milliseconds)
 -- (Generate tile sets completed in 152 milliseconds)
Random tiles generated:    4190133 across a domain of 4.2e+06
Tilesets to match against: 8191 across a domain of 4.2e+06
Total number of hits: 4187624
 -- (Query intersection completed in 1068 milliseconds)
Total number of misses: 2509
 -- (Query difference completed in 533 milliseconds)

Answer 2

As your tile sets do not change, then the best strategy is to do some precalculation that will allow for a faster lookup. I can see several good approaches to this.

Lookup table

If tile ids are integers and not big enough, you can just create a lookup table. For each id you just record the number of tileset this id belongs to. Something like this

for set in tilesets
    for id=set.first to set.last
        setLookup[id] = set.number

Now to find a set by a tile id, you just look up

setLookup[tile.id]

Binary search

A second approach works if your tile ids are not integers or can be so big that the lookup table becomes impractical. Then you sort all your tilesets in advance so that their firsts increase (or lasts increase, which is equivalent as the sets do not overlap), and then use binary search to find the tileset given a tile id. However, if you have really a few of tilesets, this might be not faster than a sequential lookup, you'll have to test it.

Static association

Finally, if your tile ids do not change either, then I do not see why you can not associate tiles with tile sets completely in advance. Just have an additional field in your Tile class that stores the TileSet number (or reference or whatever).

---

Note that by saying "do not change" I mean "change not too often". If changes are allowed, but are quite rare, than you can implement any solution which assumes that it does not change, and do a complete recalculation each time something changes.

Answer 3

To this problem I would use optimized binary tree search, taking into account sizes of intervals. If tile ids has uniform distribution it may have sense to minimize the count of comparisons required to determine the TileSet for TileSet with bigger interval. This idea reminds Huffman coding algorithm where binary tree gets built the way that encoding of more frequent symbols the path in tree is minimized

Consider the following example.

Given TileSets:

[0,2), [2,9), [9,34), [34,39), [39,48), [48,148), [148,153), [153,154)

then sizes of intervals are:

2,7,25,5,9,100,5,1

Total interval length (sum of intervals) is:

length = 154 

Let's estimate number of comparisons for following approaches

1. One-by-one comparison (like implemented in your question) If Tile belongs to first TileSet, then to find first TileSet required one comparison; If Tile belongs to second TileSet, two comparisons required, If Tile belongs to third TileSet, three comparisons required, and so on:

   C1 = (2*1 + 7*2 + 25*3 + 5*4 + 9*5 + 100*6 + 5*7 + 1*8)/length = 799/154 = 4.84
   

2. Binary tree.

           / \
         /     \
       /         \
      / \       /  \
     /   \     /    \
    /\   /\   /\    /\
   2  7 25 5 9 100 5  1
   

   Every path takes 3 comparisons, so:

   C2 = 3
   

3. Weighted tree.

            /  \
          /      \
        / \        \
      /\   \       / \
    /\  \   /\    /  /\
   2  7 25 5  9 100 5  1
   

   Comparisons estimation:

   C3 = (2*4+7*4+25*3+5*3+9*3+100*2+5*3+1*3)/154 = 2.41
   

As seen third approach requires less comparisons than others.

Tree gets built the following way: split TileSets into two parts such way that difference between sum of weights of the left part and the right part is minimized. For given example:

[2,7,25,5,9,100,5,1] => [2,7,25,5,9],[100,5,1]

Perform split on left and right parts until tree is built.

This approach is profitable when some TileSets are much wider than others.

Answer 4

10x faster? Here is how you can make your code run about 10 times (or more) faster. We want to remove branches, and vectorize our inner loop with the help of gcc.

We want to remove the condition inside the loop:

for (int i=0; i<10000; ++i) {
  for (int j=0; j<8; j++) {
    if ((tiles[i] >= lowerBounds[j]) &&
        (tiles[i] <= upperBounds[j])) {
      ids[i] = j;
    }
  }
}

This is a quick solution which you can probably improve:

for (int i=0; i<10000; ++i) {
  for (int j=0; j<8; ++j) {
    short int ld = range[j] - tiles[i] + lowerBounds2[j];
    ld = ld<0?0:ld;
    ld = ld>(range[j]-1)?0:ld;
    ld = ld>1?1:ld;
    ids2[i] += j*ld;
  }
}

The second solution is about 10 times faster on an i5-4200U if you ask g++ to optimize the code as we don't have the time for the AVX intrinsics and etc.:

g++ -std=c++11 -O3 -march=native

The timings for 10,000 tiles, and 8 tile-ranges, while the cpu speed is fixed at its base frequency:

Trivial: 0.147607 ms
Optimized: 0.014068 ms

The timing while the cpu is allowed to throttle to its highest frequency:

Trivial: 0.043876 ms
Optimized: 0.004328 ms

Here is the (quick & dirty) code, and I think you get the idea and can improve it:

#include <iostream>
#include <random>
#include <chrono>
#include <cstring>

using namespace std;
using namespace std::chrono;

int main() {
  short int lowerBounds [8] = {0, 2,  9, 34, 39,  48, 148, 153};
  short int upperBounds [8] = {1, 8, 33, 38, 47, 147, 152, 154};
  short int range       [8] = {3, 8, 26,  6, 10, 101,   6,   3};
  short int lowerBounds2[8] = {-1, 1, 8, 33, 38,  47, 147, 152};
  short int tiles [10000];
  short int ids [10000] = {0};
  short int ids2 [10000] = {0};

  // 10,000 random tiles
  default_random_engine gen;
  uniform_int_distribution<short int> dist(0, 154);
  for (int i=0; i<10000; ++i) {
    tiles[i] = dist(gen);
  }

  // *** trivial solution
  double bestTime = 1.0;
  for (int r=0; r<100; r++) {
    auto t1 = high_resolution_clock::now();
    for (int i=0; i<10000; ++i) {
      for (int j=0; j<8; j++) {
        if ((tiles[i] >= lowerBounds[j]) &&
            (tiles[i] <= upperBounds[j])) {
          ids[i] = j;
        }
      }
    }
    auto t2 = high_resolution_clock::now();
    auto elapsed = duration_cast<duration<double>>(t2 - t1).count();
    if (elapsed < bestTime)
      bestTime = elapsed;
  }
  cout<<"Trivial: "<<bestTime*1000<<" ms"<<endl;

  // *** optimized solution
  bestTime = 1.0;
  for (int r=0; r<100; r++) {
    // ids should be zero for this method
    memset(ids2, 0, 10000*sizeof(short int));
    auto t1 = high_resolution_clock::now();
    for (int i=0; i<10000; ++i) {
      for (int j=0; j<8; ++j) {
        short int ld = range[j] - tiles[i] + lowerBounds2[j];
        ld = ld<0?0:ld;
        ld = ld>(range[j]-1)?0:ld;
        ld = ld>1?1:ld;
        ids2[i] += j*ld;
      }
    }
    auto t2 = high_resolution_clock::now();
    auto elapsed = duration_cast<duration<double>>(t2 - t1).count();
    if (elapsed < bestTime)
      bestTime = elapsed;
  }
  cout<<"Optimized: "<<bestTime*1000<<" ms"<<endl;

  // validate
  for (int i=0; i<10000; i++)
    if ((ids[i] - ids2[i]) != 0) {
      cout<<"The results didn't match!"<<endl;
      break;
    }
}

You could also use multi-threading to gain a bit more speedup. That I supposed is easy for you to implement.

NB: If you don't set those optimization flags, the method I suggest will be just slightly faster or possibly even slower than the trivial method.

Answer 5

First of all, I'd sort the tile sets. E.g. first by firstTileId and then by lastTileId. Then you can use a binary search (untested code, please beware):

auto findTileSetIndex(const Vector& sets,
                      size_t start, size_t end,
                      const Tile& value)
-> signed int {
    if(start == end) return -1;
    size_t mid = start + (end-start)/2;
    if(sets[mid].firstTileId <= t[tileIndex].id &&
       sets[mid].lastTileId > t[tileIndex].id)
        return mid;
    if(sets[mid].firstTileId > t[tileIndex].id)
        return findTileSetIndex(sets, start, mid, value);
    return findTileSetIndex(sets, mid, end, value);
}

for(auto& tile : t) {
    auto tileSetIndex = findTileSetIndex(ts, 0, ts.size(), t);
    if(tileSetIndex > 0) {
       // t belongst to ts[tileSetIndex]
    }
}