Threaded List-operations

[soul_rebel]

I am working with a lot of lists, and have started taking advantag of QtConcurrency, which is really great. However for some things I am not sure whether my solution is optimal (or I now that its not).

Situation 1: Removing duplicates in a Qlist:

naive approach:

template <typename T >
void removeDuplicates(QList<*T> list)
{
QList<*T> copylist;
foreach(T *p, list)
if (!copylist.contains(p))
copylist += p;
list = copylist;
}

What I thought would work, but does not:

template <typename T >
void removeDuplicates(QList<*T> list)
{
qSort(list.begin(), list.end(), T::LessThan); // sort
T* last = 0;
foreach(T* current, list) // go through list and mark duplicates
{
if (current == last)
current = 0; //mark vor removal
else
last = current;
}
list.removeAll(0);
}
(the last line could also be replaced with

QtConcurrent::blockingFilter(list, FilterOps::uneq0<T>); where uneq0 just checks if the ptr is null or not. Even that seems suboptimal, since the sorting is single-threaded... What do you think is best here?


Another situation is, where I want to remove from one list all elements that are also member in another list. I did it like this:


QtConcurrent::blockingFilter(firstList, NotIn(otherList));

// in some other place
struct NotIn
{
QPortList compare;
NotIn(const QPortList& list)
: compare(list) {}

typedef bool result_type;

bool operator()(QBsdPort* port)
{
return !compare.contains(port);
}
}; Is that really the most efficient way of doing it?

Thank you for you help!

[wysota]

Your code for removing dupplicates is wrong. You are never changing the original list. First of all foreach() makes a copy of the list and works on a copy, second of all in the loop you are creating a local variable storing a pointer to some item and setting that pointer to 0. This won't cause the item in the list to be set to 0 (be it the original list or the copy), only the local pointer. Third of all your method takes a copy of a list and acts on it instead of the original list so your changes (if you correct the code) would never be forwarded outside the method anyway.

Using Qt Concurrent for such a short task as checking if a pointer is null just adds overhead to the whole operation because it is more expensive to start a job, end the job and fetch the result than to simply check the pointer in the original thread.

[soul_rebel]

Thanks for your help!

Concerning RemoveDuplicates:

Ah, foreach making a copy was new to me, that would be the problem (the Header actually had a reference)!
I will try with a regular loop or non-const iterators…
I thought using threads for the latter be a bit overkill aswell, but would there be a way to use threads for the whole thing? I mean the qSort is O(n*logn), and the "setting 0" is O(n), I don't know how fast removeAll is, but it probably isn't to bad.
Still I need to do it quite heavily and really had positive experience with QtConcurrency in other List-Operations


About the second application:

Do you think thats the proper way to do it? Calling contains() so oft seems expensive to me…

[wysota]

There is a O(n lg n) implementation for getting rid of duplicates:


template <typename T> QList<T> removeDuplicates(const QList<T> &original) {
QList<T> noDuplicates;
foreach(const T &item, original){
QList<T>::iterator iter = qLowerBound(noDuplicates.begin(), noDuplicates.end());
if(iter!=noDuplicates.end() && iter.value()==item) continue;
noDuplicates.insert(iter, item);
}
return noDuplicates;
}
This will give you a sorted copy of the list with unique values. Threads wouldn't speed up the process and you can't get any faster than that.

Note that if T represents a pointer, you need to change the call to qLowerBound() and comparison operators to reflect that if needed.