search an efficient way to handle a long list

[orunner]

Hi there,

I am using STL and have to deal with many lists (map, vector, etc) which are VERY long. I need to appy filters to a list in some orders and remove them in the reverse order. A filter may allow a certain number of elements to be visible. But there is also a type of filter which disallow a list of elements. Whenever a filter is applied, I need to visit all visible elements many times and dynamically decide what kind of filter comes next.

My problem is that it is so slow to do such operations if it is done very often and the list is simply too long. Each filter has to change different flags in the elements. The combination of flags determine wheter the element is visible. Current implementation is to go through all elements each time a filter is applied/removed. Of course, is not elegant at all.

Therefore, I'd like to ask you guys if you have a better desing for this problem.

[JohnW@Wessex]

You could maybe create a list of all the iterators to elements in a list.
You would then apply the filters via this list and delete iterators that don't apply? You would then be left with only the iterators to elements that you require.

[ltcmelo]

Hi orunner.

How exactly do you determine wheter an element is visible? Have you taken a look at the Boost Iterator Library? Particularly, at the filter_iterator ? This will probably give you a more elegant solution.

Regarding speed of your program (without knowing too much about it), I would try to figure out a strategy somehow similar to what JohnW@Wessex has proposed. In algorithms, there's usually a time x space trade-off that can be tuned in favor of your priorities. In your case, it seems that using extra auxiliary data structures to distribute responsibilities could allow you to execute the task faster (with the cost of more memory consumption).

[orunner]

You could maybe create a list of all the iterators to elements in a list.
You would then apply the filters via this list and delete iterators that don't apply? You would then be left with only the iterators to elements that you require.

Thx for ur post!

Okay, it works very good when applying a filter, I think. But how to handle it more efficiently when removing filters.

suppose the filter stack looks like this:
[enableFilter 4]
[disableFilter 3]
[disableFilter 2]
[enableFilter 1]
note: enableFilter enable a list of elements; disableFilter disable some elements.

If I remove the filter on the top, I have to recreate the cached list of iterators, i.e. going through all elements in the original container.

[orunner]

Hi orunner.

How exactly do you determine wheter an element is visible? Have you taken a look at the Boost Iterator Library? Particularly, at the filter_iterator ? This will probably give you a more elegant solution.

Regarding speed of your program (without knowing too much about it), I would try to figure out a strategy somehow similar to what JohnW@Wessex has proposed. In algorithms, there's usually a time x space trade-off that can be tuned in favor of your priorities. In your case, it seems that using extra auxiliary data structures to distribute responsibilities could allow you to execute the task faster (with the cost of more memory consumption).

Thx for ur input!

I did a cached container which contains iterators of the original elements. I works already faster than before. But I am confused a bit how to do the removing of filter more efficiently.

I will take a look at the boost libary. Unfortunately, I am not allowed to use boost stuff although it is good.

I am also wondering if there is already a "design pattern" available to handle this issue (I think this issue is very typical:-)). :-( I am not familar with design pattern.

[orunner]

I took a glance at filter iterator form Boost. It needs predicate to decide if an element is in the desired range. I did not take a close look at it. But I suppose that it goes through all elements each time iterators are requested. Am I right?

[JohnW@Wessex]

But I am confused a bit how to do the removing of filter more efficiently.

Could each filter somehow keep an 'undo' list of the iterators it deleted?

[KevinHall]

First, I'm not sure that a std::list is the right container for you. I don't know the details of your implementation, but I would consider either std::vector which will allow for faster iteration, a std::vector<std::list<> > pseudo-hash, a hash<std::list<> >, or some database-like container (since the whole filter thing sounds a lot like a database to me).

OK, here are a few ideas:

(1) Don't apply the filters right away -- only as you iterate through your container when other functions require you to iterate through the container. Thus, if you need to apply 5 filters, then iterate through the container, you will only perform the iteration once rather than 6 times. It will also be very easy to remove a filter.

(2) If you know what the types of filters are ahead of time and there are a limited number of filters (say 13 or less), then you could create a bit-mask that defines your filters. That bit-mask could act as an index for the std::vector in the pseudo-hash. Then you could easily figure out what items in the vector to search. This should allow you very fast indexing. You would have to figure out which filters apply to a particular item up-front.

(3) Again if you know what the types of filters are ahead of time and there are a limited number of filters but more than the 13 in the last idea. Then still use a bit-mask for indexing the std::list<>s, but now keep the std::list<>s in a hashed container hashing the bit-mask. The up and downsides are pretty similar here. The hashing will just cause searching to take a little longer, but still will be pretty fast.

(4) If the above options don't work for you, go find a database-like container to use. Your description screams "database" to me. Unfortunately, I'm not familiar with how databases are typically implemented, so I can't offer much more insight.

In any case, good luck. If you can, please post what your final solution is and the reasons you were attracted to that solution. I'm sure this will be of some use to someone else out there.

- Kevin

[KevinHall]

Here's an interesting thread that may offer some insight:

http://www.thescripts.com/forum/thread488315.html

In that thread, Boost Multi-Index and Boost RTL (Relational Template Library -- currently in the Boost Sandbox) are suggested. Here are some direct links:

http://www.boost.org/libs/multi_index/doc/index.html

http://visula.org/relational/

- Kevin

[JohnW@Wessex]

Your description screams "database" to me.

Yes, a database would certainly fit the bill as this is just the sort of problem that they can easily solve.

I found this on sourceforge if it's any help.

or this.