Comment 12 for bug 398870

On the Debian mailing-list this has been dicussed here http://<email address hidden>/msg245661.html.

One solution that helped me a bit (just one or two seconds faster) is the following (taken from ):
1. $ sudo su
1. % for x in /var/lib/apt/lists/*Packages;do dpkg --merge-avail "$x";done
2. Rebuild /info (to work against fragmentaton; for me this took +3 minutes!)
  % cd /var/lib/dpkg/
  % cp -a info info.tmp
  % mv info info.orig
  % mv info.tmp info
3. Finally: % dpkg --clear-avail

_and_ reboot (for whatever reason ...)

On the mailinglist above there was also a pointer to http://people.debian.org/~seanius/dpkg-sqlite/ for a proof-of-concept sqlite powered cache, which would fix the slowness problems.