Split a list into two parts based on a filter?

[Roy Smith]

In article <mailman.3032.1370971724.3114.python-list at python.org>,
 Chris Angelico <rosuav at gmail.com> wrote:

> On Wed, Jun 12, 2013 at 1:28 AM, Serhiy Storchaka <storchaka at gmail.com> wrote:
> > 11.06.13 01:50, Chris Angelico написав(ла):
> >
> >> On Tue, Jun 11, 2013 at 6:34 AM, Roy Smith <roy at panix.com> wrote:
> >>>
> >>> new_songs = [s for s in songs if s.is_new()]
> >>> old_songs = [s for s in songs if not s.is_new()]
> >>
> >>
> >> Hmm. Would this serve?
> >>
> >> old_songs = songs[:]
> >> new_songs = [songs.remove(s) or s for s in songs if s.is_new()]
> >
> >
> > O(len(songs)**2) complexity.

If I didn't want to make two passes over songs, I probably don't want 
something that's O(len(songs)^2) :-)

> Which isn't significant if len(songs) is low. We weren't told the
> relative costs - is the is_new call ridiculously expensive? Everything
> affects algorithmic choice.

Assume is_new() is cheap.  It's essentially:

return  (datetime.utcnow() - self.create_time) < [[a pre-defined timedelta]]