查找给定数字所属的数字集(范围)，而不使用循环

Question

基于以下标准，我很难决定使用哪种或哪种算法来查找对象:有两个类：“TileSets”和“Tile”。TileSet有两个int属性: firstTileId和lastTileId，而Tile只有一个int属性: id，如下所示：

struct TileSet { int firstTileId, lastTileId; } 

struct Tile { int id; }

应用程序应该有不超过10个TileSets (通常为3-5个)和10.000+磁贴。速度对于确定具有给定id的磁贴属于哪个TileSet至关重要。将平铺集添加到向量后，第一个和最后一个id属性不会更改，并且它们不会相互重叠，例如：{{1，25}，{26,125}，{126,781}，{782,789}...}。正如我们所看到的，在瓦片范围内也没有洞。Tiles向量没有排序，也不可能排序。我目前的实现(一种伪短码)是：

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!

对于这种情况，我可以使用哪种算法？对此有什么公式吗？

Answer 1

由于您的磁贴集不会更改，因此最好的策略是进行一些预计算，以便进行更快的查找。我可以看到几种很好的方法来解决这个问题。

查找表

如果磁贴ids是整数并且不够大，您可以只创建一个查找表。对于每个id，您只需记录此id所属的平铺集的数量。像这样的东西

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

现在，要通过磁贴id找到一个集合，只需查找

setLookup[tile.id]

二分搜索

如果您的tile不是整数，或者可能太大以至于查找表变得不切实际，则第二种方法有效。然后，提前对所有的平铺集进行排序，使它们的first增加(或last增加，这相当于集合不重叠)，然后使用二进制搜索来查找给定的平铺id的平铺集。但是，如果您确实有几个平铺集，这可能不会比顺序查找快，您必须对其进行测试。

静态关联

最后，如果您的磁贴if也没有更改，那么我不明白为什么您不能提前将磁贴与磁贴集完全关联起来。只需在您的Tile类中有一个额外的字段来存储TileSet号(或引用或其他任何值)。

请注意，我说“不要改变”的意思是“不要太频繁地改变”。如果允许更改，但非常少见，那么您可以实现任何假定不更改的解决方案，并在每次更改时进行完整的重新计算。

Answer 2

对于这个问题，我会使用优化的二叉树搜索，并考虑到间隔的大小。如果磁贴If具有均匀分布，则将确定具有较大间隔的TileSet的TileSet所需的比较计数最小化可能有意义。这个想法提醒了Huffman编码算法，其中二叉树的构建方式是对树中路径越频繁的符号进行编码，从而最小化树中的路径

考虑下面的例子。

给定TileSets：

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

那么间隔的大小是：

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

总间隔长度(间隔总和)为：

length = 154 

让我们估计一下以下方法的比较次数

如果属于first TileSet，则需要进行一次比较；如果Tile属于second TileSet，则需要进行两次比较；如果Tile属于third TileSet，则需要进行三次比较，依此类推：

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

• 二叉树。

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

每条路径进行3次比较，因此：

C2 =3

• 加权树。

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

比较估计：

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

如图所示，第三种方法比其他方法需要更少的比较。

树的构建方式如下:将TileSets一分为二，这样就可以最小化左右两部分的权值之和。对于给定的示例：

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

对左侧和右侧部分执行拆分，直到构建好树。

当一些TileSets比其他的宽得多时，这种方法是有利可图的。

Answer 3

快10倍？这里是如何让你的代码运行快10倍(或更多)。我们想要删除分支，并在gcc的帮助下向量化我们的内循环。

我们想要删除循环中的条件：

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;
    }
  }
}

这是一个可以改进的快速解决方案：

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;
  }
}

第二个解决方案在i5-4200U上大约快10倍，如果你要求g++优化代码，因为我们没有时间做AVX的内部函数等等：

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

10,000个磁贴和8个磁贴范围的计时，而cpu速度固定在其基本频率：

Trivial: 0.147607 ms
Optimized: 0.014068 ms

允许cpu调节到其最高频率时的定时：

Trivial: 0.043876 ms
Optimized: 0.004328 ms

下面是(快速和肮脏的)代码，我想你已经明白了，并且可以改进它：

#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;
    }
}

您还可以使用多线程来获得更多的加速。我想这对你来说很容易实现。

NB:如果你不设置这些优化标志，我建议的方法只会比琐碎的方法稍微快一点，甚至可能更慢。