Select items from the list according to their properties.

Question

I am developing an application designed to create a huge number of shapes. Each shape can be assigned to a specific layer.

I get the input as a list of shapes, where for each form I have a string property that represents the layer to which the form belongs.

Now I need to develop a method that allows me to select (draw) only those shapes that belong to a specific list of selected layers. In pseudo code:

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

The fact is that I would like to complete this operation as quickly as possible; so i need to choose the right data structures and the right algorithm.

The list of selected layers is a list of rows (1 ÷ 100 different levels), but if necessary, for performance reasons, it can be converted to other data types.

Forms are sorted according to their z-order.

Answer 1

The main intrusive decisions are often overlooked here in search of complex data structures and algorithms, but usually the fastest.

Assuming you have no choice but to keep the selection separate, if you want a really quick solution, keep a logical selection flag on each layer (maybe one bit). When you make a selection, in addition to forming a list, set these flags. Deselecting a level not only removes it from your selection, but sets the selection flag to false.

Then change the lines that are used to indicate the selected layers in the indices in the random access structure (for example: std::vector or even a simple old array if the size can be determined at compile time), for example (simplified):

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

... and turn shape.layer into an index (or pointer / iterator) on the layer. If you have no choice but to start from the line of the layer to determine which layer the form belongs to, because you are first inputted with the source data (for example: from the file you upload), then translate these lines into the layer index / pointer / iterator since you create shapes from these string inputs. Use a hash table or at least std :: set / map here (a string search when building the initial form should be logarithmic or better) to convert these layer strings to level indices / pointers / iterators.

If you need a layer selection list in addition to the layer selection state, you can do this (pseudo-code):

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

... if your layer choice stores indexes / pointers / iterators for layers. The insertion / deletion of the selection and deselection lists can be performed continuously (even in the worst case) without hashing the service data and while maintaining the insertion order, if you are interested in choosing a layer and using a fixed allocator (this is a complex object including placing new ones, unions and pools memory, so I will delve into it if necessary, but do not cut it for brevity for now).

Now your main pseudocode code turns into something like this:

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

... or this if you use pointers / iterators:

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

It’s hard to beat this in terms of performance, since even the most optimal hash table cannot defeat simple access to the indexed array in memory, you still have to access the hash. Now, if you can consolidate the idea of ​​“selected shapes” and pre-shape selected shapes in the process of selecting / deselecting layers, you can do this:

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

... which can be even faster if the additional cost of generating a list of selected shapes is offset by reusing it again before it changes. Note that you still want to convert these strings to indices in this case, because you do not want your list of selected shapes to be anything more than a simple array. To create a list of selected shapes:

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

... which is even cheaper to generate and access (due to the spatial locality of an ideally compact shape selection array) than the hash table due to this selection state, which we now save in layers.

This saves all the caching possibilities and avoids expensive (relatively speaking) data structures, such as hash tables, with the exception of that initial part of the line-> conversion index / pointer (which should be done only when creating a form from string input). In this case, the only place you ever need to perform any search (logarithmic or constant hash / trie) is when you convert these form level strings that you get from user input into indexes / pointers / iterators. Everything else is O (1) (even the worst complexity) and does not even require hashing.

Answer 2

I would suggest using a set instead of a list for selected layers, so a binary search can be done to determine in shape.layer in the selected layers, and inserting while maintaining order is fast. Using a list will be ineffective to maintain the order required for binary search.

Another option is to figure out the hash algorithm and just use the hash map.