[KPhotoAlbum] Very slow delete

[Robert L Krawitz]

I think I know why deleting images is very slow:

void MainView::slotDeleteSelected()
{
    ...
    QStringList images = _thumbnailView->imageList();
    QStringList allImages = ImageDB::instance()->images();
    QStringList newSet;
    for( QStringList::Iterator it = images.begin(); it != images.end(); ++it ) {
        if ( allImages.contains( *it ) )
            newSet.append(*it);
    }
    showThumbNails( newSet );
}

It's apparently iterating over all of the thumbnails currently visible
and checking if they're in the current database -- and no doubt
allImages.contains() is linear itself.  Therefore, if all of the
images are visible in the current thumbnail view, the operation will
be quadratic in the number of images (roughly n^2/2).  With 11,000
images, that means roughly 60,000 comparisons.  No wonder it takes
well over a minute.

Someone with 50,000 images would require about 20x longer.  This
clearly needs to be improved; the question is how to do it.  Since
one's likely to delete only a few images, it would probably make sense
to reverse the sense of the comparison (create a list of deleted
images).

-- 
Robert Krawitz                                     <rlk at alum.mit.edu>

Tall Clubs International  --  http://www.tall.org/ or 1-888-IM-TALL-2
Member of the League for Programming Freedom -- mail lpf at uunet.uu.net
Project lead for Gutenprint   --    http://gimp-print.sourceforge.net

"Linux doesn't dictate how I work, I dictate how Linux works."
--Eric Crampton