im not sure what is the fastest, i would compare a few. try file_exists() and fsockopen()
but its going to be slow no matter what because your having to request the file from remote servers.
you may want to consider caching the results. like using a database to store each link, and have a flag for whether its valid or not.
set up another script via cron and run it every 30 min or whatever interval is suitable, and have that script update the db.
that way you can just query your db instead of doing an http request.