Split a list into two parts based on a filter?

[Chris Angelico]

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.

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.

ChrisA