When trying to reach best efficiency, and you should when using battery power, you should not be looking at any linear voltage regulator but rather a switching regulator. The reduction from 12v to 5v using a linear regulator means that you waste more power in the regulator then the arduino board is using. The example below is of a switching regulator that will allow you the best battery running duration.