Results 1 to 4 of 4

Thread: Threaded List-operations

  1. #1
    Join Date
    Jan 2006
    Location
    germany
    Posts
    75
    Thanks
    9
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11

    Question Threaded List-operations

    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:
    Qt Code:
    1. template <typename T >
    2. void removeDuplicates(QList<*T> list)
    3. {
    4. QList<*T> copylist;
    5. foreach(T *p, list)
    6. if (!copylist.contains(p))
    7. copylist += p;
    8. list = copylist;
    9. }
    To copy to clipboard, switch view to plain text mode 

    What I thought would work, but does not:
    Qt Code:
    1. template <typename T >
    2. void removeDuplicates(QList<*T> list)
    3. {
    4. qSort(list.begin(), list.end(), T::LessThan); // sort
    5. T* last = 0;
    6. foreach(T* current, list) // go through list and mark duplicates
    7. {
    8. if (current == last)
    9. current = 0; //mark vor removal
    10. else
    11. last = current;
    12. }
    13. list.removeAll(0);
    14. }
    To copy to clipboard, switch view to plain text mode 
    (the last line could also be replaced with
    Qt Code:
    1. QtConcurrent::blockingFilter(list, FilterOps::uneq0<T>);
    To copy to clipboard, switch view to plain text mode 
    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:
    Qt Code:
    1. QtConcurrent::blockingFilter(firstList, NotIn(otherList));
    2.  
    3. // in some other place
    4. struct NotIn
    5. {
    6. QPortList compare;
    7. NotIn(const QPortList& list)
    8. : compare(list) {}
    9.  
    10. typedef bool result_type;
    11.  
    12. bool operator()(QBsdPort* port)
    13. {
    14. return !compare.contains(port);
    15. }
    16. };
    To copy to clipboard, switch view to plain text mode 
    Is that really the most efficient way of doing it?

    Thank you for you help!
    Quote Originally Posted by Bertolt Brecht
    What is the robbing of a bank compared to the founding of a bank?

  2. #2
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: Threaded List-operations

    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.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  3. #3
    Join Date
    Jan 2006
    Location
    germany
    Posts
    75
    Thanks
    9
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11

    Default Re: Threaded List-operations

    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…
    Quote Originally Posted by Bertolt Brecht
    What is the robbing of a bank compared to the founding of a bank?

  4. #4
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: Threaded List-operations

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

    Qt Code:
    1. template <typename T> QList<T> removeDuplicates(const QList<T> &original) {
    2. QList<T> noDuplicates;
    3. foreach(const T &item, original){
    4. QList<T>::iterator iter = qLowerBound(noDuplicates.begin(), noDuplicates.end());
    5. if(iter!=noDuplicates.end() && iter.value()==item) continue;
    6. noDuplicates.insert(iter, item);
    7. }
    8. return noDuplicates;
    9. }
    To copy to clipboard, switch view to plain text mode 
    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.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


Similar Threads

  1. Article about asynchronous operations
    By skrzypu in forum Qt Programming
    Replies: 0
    Last Post: 10th March 2010, 12:43
  2. Erratic performance of IO operations in Qt4 program
    By jcox23 in forum General Programming
    Replies: 2
    Last Post: 26th January 2010, 18:33
  3. Multithreaded per pixel operations on QImage
    By N¤X in forum Qt Programming
    Replies: 8
    Last Post: 14th September 2009, 13:29
  4. How to manage QSqlTableModel database operations?
    By Abk in forum Qt Programming
    Replies: 1
    Last Post: 19th September 2007, 11:44
  5. Graphics operations - Qt 4.1
    By hoborg in forum Newbie
    Replies: 1
    Last Post: 18th February 2006, 15:09

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.