Friday, August 12, 2005

Exponential blowup is annoying

I've been spending the last week or so trying to clear out the last few tricky TODO items for a new aptitude release. Aside from clearing out obnoxious old bugs, I had three major features relating to the dependency resolver that I wanted to implement: guided interactive resolution, the ability to produce explanations of dependencies, and the elimination of results that make users go, "Oh, how stupid!"

The first one was pretty straightforward to implement, although it's currently only accessible from the curses UI:



Basically, you can give a thumbs-up ("accept") or thumbs-down ("reject") to individual decisions from the solution; solutions that are generated in the future will be only those that either contain or don't contain that decision. You can always go back and cancel these flags in order to see the solutions that were eliminated by your action.

The second item was also pretty straightforward, although I've only added frontend access from the command-line so far:


pysol-sound-server depends upon libsmpeg0 (>= 0.4.4-7)
-> Removing pysol-sound-server

python2.3-pygame depends upon libsmpeg0 (>= 0.4.4-7)
-> Removing python2.3-pygame

tdfsb depends upon libsmpeg0 (>= 0.4.4-7)
-> Removing tdfsb

python-pygame depends upon python2.3-pygame
-> Removing python-pygame

pathological depends upon python-pygame
-> Removing pathological

gltron depends upon libsmpeg0 (>= 0.4.4-7)
-> Installing gltron 0.70final-6 (unstable)

...


The third item involves the question of whether there's an easy way to eliminate certain types of "redundancies" from solutions: for instance, installing a dependency of a package and then later removing the same package. aptitude was already able to handle some such situations "up front" (reducing the branching factor at the same time), but it wasn't even clear to me if a general solution was possible. In fact, I was stumped on this point for weeks until I realized that the answer was, as usual, much simpler than I thought it would be; it's now implemented and described in the model paper (although I haven't updated the public PDF yet).

So, that brings us to today. I was about to sit down and work on polishing these additions, maybe even going so far as to write test cases for some of them, when I decided to bring my system up-to-date with yesterday's dinstall run.


No solution found within the allotted time. Try harder? [Y/n]


D'oh! Something about the KDE uploads yesterday triggered a pathological (i.e., exponential) case in aptitude's problem resolver. After reading a lot of of debugging output, the problem seems to be that it was spending too much effort trying to find a "good" solution -- rather than, say, sticking with a solution that just fixed lots of dependencies. Specifically, solutions were only given 300 points for fixing a dependency, and most actions taken by the resolver would actually *decrement* the score of a solution by about 30-50 points. As a result, if the configuration of dependencies was such that the resolver hadn't satisfied some dependencies within about 6-8 steps, the priority of the current "active" solution would actually drop below the priority of the next most interesting solution. As a result, the resolver was behaving more like a breadth-first search (visiting all nodes before reaching a solution) than a depth-first search. Ouch.

The solution I came up with is ad-hoc but it seems to work pretty well: since the problem is that the score drops too fast as new versions are installed, I just adjusted the way solutions are scored. Specifically, it no longer costs anything for the resolver to change the state of an automatically installed package or to install a package that isn't held.

So, how does this tweak perform?


*** Converged after 524 steps.


Not bad...and the solution it came up with is surprisingly good. I can get even faster results if I make all upgrades and keeps costless or almost costless (converges after 84 steps). Nice!

10 Comments:

At 5:19 AM, Anonymous Anonymous said...

A professional traffic company. By extension, a big piece of that web spam
appears to be links from low-quality networks.

Here is my blog post search engine companies

 
At 7:54 AM, Anonymous Anonymous said...

Players can go back and play their favorite video
Video Game Toys they played when they were alive, just wait until they are all in your" Start" space.
Sam Clayton says choosing to send his child to Quest to Learn, students not only play in gamelike environments, they
also make video video game toys. An obstacle course is
often a great way to exercise your brain, invent new things, have creative ideas and just have fun.
It is not a commercial succes but is definitely worth purchasing.


Here is my web-site - video game designer colleges

 
At 12:51 AM, Blogger Coach Factory said...

kate spade handbags, prada outlet, nike air max, louis vuitton, nike air max, louis vuitton outlet online, burberry outlet online, burberry outlet online, tiffany and co jewelry, michael kors outlet, gucci handbags, tory burch outlet, louis vuitton outlet, chanel handbags, jordan shoes, longchamp outlet online, nike shoes, louboutin shoes, red bottom shoes, coach outlet store online, kate spade outlet online, polo ralph lauren outlet, oakley vault, coach outlet, prada handbags, coach purses, louis vuitton handbags, longchamp handbags, christian louboutin outlet, oakley sunglasses, cheap oakley sunglasses, michael kors outlet online, michael kors outlet online, louis vuitton outlet, polo ralph lauren, christian louboutin shoes, michael kors outlet online, ray ban outlet, nike free, longchamp outlet, michael kors outlet store, michael kors outlet online, coach outlet, true religion, ray ban sunglasses

 
At 12:51 AM, Blogger Coach Factory said...

abercrombie and fitch, longchamp pas cher, north face, vans pas cher, nike free, nike air max, longchamp, tn pas cher, hollister, air max pas cher, michael kors canada, chaussure louboutin, oakley pas cher, sac vanessa bruno, ray ban uk, louis vuitton uk, hollister, new balance pas cher, lululemon, nike free pas cher, north face pas cher, scarpe hogan, nike trainers, air max, nike roshe, ralph lauren pas cher, barbour, nike huarache, burberry pas cher, guess pas cher, nike air max, true religion outlet, longchamp, lacoste pas cher, sac michael kors, ralph lauren, louis vuitton pas cher, michael kors uk, nike blazer pas cher, mulberry, nike air force, air jordan, hermes pas cher, louis vuitton, nike roshe run, timberland, sac louis vuitton, ray ban pas cher, converse pas cher, true religion outlet

 
At 12:52 AM, Blogger Coach Factory said...

herve leger, soccer jerseys, uggs outlet, jimmy choo shoes, lululemon outlet, nfl jerseys, canada goose pas cher, vans outlet, soccer shoes, roshe run, valentino shoes, moncler, rolex watches, chi flat iron, uggs on sale, canada goose, north face outlet, ghd, new balance outlet, north face jackets, mcm handbags, ugg soldes, moncler, canada goose uk, mont blanc pens, beats headphones, canada goose outlet, celine handbags, instyler ionic styler, ferragamo shoes, ugg boots, bottega veneta, ugg, moncler outlet, abercrombie and fitch, ugg outlet, wedding dresses, mac cosmetics, birkin bag, reebok outlet, canada goose outlet, insanity workout, moncler, giuseppe zanotti, asics shoes, hollister, canada goose outlet, babyliss pro, marc jacobs outlet, p90x workout

 
At 8:04 PM, Blogger 风骚达哥 said...

20151014 junda
Louis Vuitton Handbags Factory Store
Louis Vuitton Bags On Sale
Louis Vuitton Bags Outlet Store
cheap ugg boots
louis vuitton outlet
Michael Kors Outlet Real Handbags Online
ugg boots
Air Jordan 3 III Retro Free Shipping
louis vuitton outlet
celine
Christian Louis Vuitton Red Bottoms
coach factory outlet
ray ban sunglasses uk
Ugg Boots,Ugg Boots Outlet,Ugg Outlet,Cheap Uggs,Uggs On Sale,Ugg Boots Clearance,Uggs For Women
Coach Outlet Store Online Handbags Clearance
canada goose outlet
ugg boots outlet
Abercrombie And Fitch Kids Online
true religion outlet
cheap jordan shoes
New Louis Vuitton Handbags Outlet
cheap uggs
nfl jerseys
canada goose jackets
Abercrombie and Fitch Outlet Sale
louis vuitton outlet
canada goose outlet
uggs australia
michael kors outlet stores
Coach Factory Outlet Online Sale

 
At 8:04 PM, Blogger oakleyses said...

uggs outlet, uggs on sale, ray ban sunglasses, ray ban sunglasses, louis vuitton, michael kors outlet online, oakley sunglasses wholesale, christian louboutin outlet, louis vuitton, uggs outlet, louis vuitton outlet, polo outlet, prada handbags, nike free, chanel handbags, longchamp outlet, michael kors outlet, replica watches, louis vuitton outlet, oakley sunglasses, michael kors outlet online, prada outlet, michael kors outlet online, longchamp outlet, burberry handbags, michael kors outlet, kate spade outlet, ray ban sunglasses, longchamp outlet, louis vuitton outlet, oakley sunglasses, nike air max, oakley sunglasses, replica watches, ugg boots, polo ralph lauren outlet online, ugg boots, gucci handbags, jordan shoes, cheap oakley sunglasses, michael kors outlet online, christian louboutin uk, burberry outlet, tory burch outlet, tiffany and co, christian louboutin shoes

 
At 8:06 PM, Blogger oakleyses said...

michael kors, nike tn, ralph lauren uk, abercrombie and fitch uk, north face uk, ray ban pas cher, nike free uk, lululemon canada, michael kors, true religion jeans, coach outlet, coach outlet store online, hollister uk, sac longchamp pas cher, vans pas cher, nike blazer pas cher, louboutin pas cher, nike air max uk, michael kors pas cher, nike free run, nike air max uk, new balance, sac hermes, jordan pas cher, true religion outlet, replica handbags, nike roshe, longchamp pas cher, guess pas cher, true religion outlet, north face, polo ralph lauren, coach purses, hollister pas cher, oakley pas cher, timberland pas cher, air max, polo lacoste, nike air force, nike roshe run uk, burberry pas cher, converse pas cher, nike air max, sac vanessa bruno, mulberry uk, hogan outlet, michael kors outlet, true religion outlet, ray ban uk, kate spade

 
At 8:08 PM, Blogger oakleyses said...

beats by dre, nfl jerseys, nike trainers uk, mcm handbags, lululemon, reebok outlet, valentino shoes, wedding dresses, nike roshe run, celine handbags, ghd hair, ferragamo shoes, mont blanc pens, louboutin, giuseppe zanotti outlet, new balance shoes, timberland boots, oakley, soccer shoes, nike air max, iphone 5s cases, nike huaraches, iphone 6 plus cases, herve leger, iphone 6s plus cases, p90x workout, babyliss, vans outlet, north face outlet, iphone cases, jimmy choo outlet, iphone 6 cases, s6 case, abercrombie and fitch, bottega veneta, north face outlet, hermes belt, longchamp uk, ralph lauren, chi flat iron, insanity workout, iphone 6s cases, ipad cases, baseball bats, mac cosmetics, instyler, hollister, soccer jerseys, asics running shoes, hollister clothing

 
At 8:10 PM, Blogger oakleyses said...

doudoune moncler, pandora uk, moncler outlet, vans, converse outlet, montre pas cher, louis vuitton, moncler, moncler, canada goose, canada goose outlet, ugg uk, links of london, barbour uk, supra shoes, replica watches, lancel, nike air max, moncler, moncler, moncler outlet, coach outlet, wedding dresses, canada goose outlet, pandora jewelry, karen millen uk, ugg, marc jacobs, juicy couture outlet, converse, moncler uk, louis vuitton, ugg pas cher, swarovski, pandora jewelry, gucci, canada goose, canada goose uk, ugg,uggs,uggs canada, pandora charms, juicy couture outlet, louis vuitton, louis vuitton, ray ban, ugg,ugg australia,ugg italia, canada goose jackets, swarovski crystal, canada goose, hollister, thomas sabo, canada goose outlet, toms shoes

 

Post a Comment

<< Home