根据列表的属性从列表中选择元素

Question

我正在开发一个旨在渲染大量形状的应用程序.每个形状都可以分配给特定图层.

我将输入数据作为形状列表获取,其中对于每个形状,我有一个string属性,表示形状所属的层.

现在,我需要开发一种方法,允许我只选择(绘制)属于给定选定图层列表的那些形状.在伪代码中:

void draw_if(sorted_list shapes, list<string> selected_layers)
{
   for each shape in shapes
   {
      if (shape.layer in selected_layers)
        shape.draw();
   }
}

关键是我想尽快执行此操作; 因此,我需要选择正确的数据结构和正确的算法.

所选图层列表是一个字符串列表(1÷100个不同的图层),但如果出于性能原因需要,可以将其转换为其他数据类型.

形状根据其z顺序排序.

Answer 1

在寻找复杂的数据结构和算法时，基本的侵入式解决方案经常被忽视，但通常是最快的。

假设您别无选择，只能将选择分开，如果您想要一个真正快速的解决方案，请在每个层中存储一个布尔选择标志（可以是一个位）。当您形成选择时，除了形成列表之外，还要设置这些标志。取消选择图层不仅会将其从选择中删除，还会将该选择标志设置为 false。

接下来，将用于指示选定层的那些字符串转换为随机访问结构的索引（例如：std::vector如果可以在编译时确定大小，则甚至是普通的旧数组），如下所示（简化）：

struct Layer
{
    string name;

    // Set this to true when the layer is selected, false 
    // when it is deselected. Use atomics if thread safety 
    // is required.
    bool selected;
};

...并变成shape.layer层的索引（或指针/迭代器）。如果您别无选择，只能从图层字符串开始来识别形状属于哪个图层，因为您最初会获得字符串输入（例如：来自正在加载的文件），然后将这些字符串转换为图层索引/指针/迭代器当您从这些字符串输入创建形状时。在这里使用哈希表或至少使用 std::set/map （初始形状构造上的字符串搜索应该是对数或更好）将这些图层字符串转换为图层索引/指针/迭代器。

如果除了图层选择状态之外还需要图层选择列表，那么您可以这样做（伪代码）：

void select(Layer layer, LayerList& layer_selection)
{
     if (!layer.selected)
     {
          layer.selected = true;
          layer_selection.insert(&layer);
     }
}

void deselect(Layer layer, LayerList& layer_selection)
{
     if (layer.selected)
     {
          layer.selected = false;
          layer_selection.erase(&layer);
     }
}

...您的图层选择存储图层的索引/指针/迭代器的位置。如果您喜欢层选择并使用固定分配器，则选择和取消选择列表插入/删除都可以在恒定时间内完成（即使在最坏情况下），无需散列开销，同时保留插入顺序（这是一个复杂的主题）涉及放置 new、联合和内存池，因此如果需要，我将深入研究它，但为了简洁起见，暂时忽略它）。

现在你的主要伪代码变成这样：

void draw_if(list shapes, list layers)
{
   for each shape in shapes
   {
      if (layers[shape.layer].selected)
        shape.draw();
   }
}

...或者如果您使用指针/迭代器：

void draw_if(list shapes, list layers)
{
   for each shape in shapes
   {
      if (shape.layer->selected)
        shape.draw();
   }
}

就性能而言，这是很难击败的，因为即使是最优化的哈希表也无法击败对内存的简单索引数组访问，您仍然需要使用哈希来访问。现在如果你能巩固“选定形状”的思想，通过选择/取消选择图层的过程提前形成选定形状，那么你可以这样做：

void draw_selected(list selected_shapes)
{
   for each shape in selected_shapes
       shape.draw();
}

...如果形成所选形状列表的额外成本可以通过在必须更改之前重复使用它来补偿，那么速度可能会更快。请注意，在这种情况下，您仍然希望将这些字符串转换为索引，因为您不希望“选定的形状”列表不仅仅是一个简单的数组。要形成选定的形状列表：

ShapeList selected_shapes(ShapeList all_shapes, LayerList layers)
{
     // Forming this in advance will help if it is reused for
     // numerous drawing frames before it needs to change (ex:
     // before the Z-order changes, before new elements are inserted
     // or existing ones removed, before the layer selection changes).
     ShapeList results;
     for each shape in all_shapes:
          if layers[shape.layer].selected)
             results.push_back(shape);
     return results;
}

...由于我们现在存储在层中的选择状态，它的形成和访问仍然比哈希表更便宜（由于完美紧凑的形状选择数组的空间局部性）。

这使所有内容都对缓存友好，并避免使用昂贵的（相对而言）数据结构，例如哈希表，除非在初始字符串->索引/指针转换部分期间（仅在从字符串输入创建形状时才需要执行此操作）。在这种情况下，唯一需要执行任何类型的搜索（对数或恒定时间哈希/特里）的地方是将从用户输入获得的形状层字符串转换为索引/指针/迭代器。其他一切都是 O(1)（即使是最坏情况的复杂性），甚至不需要哈希。