bisect.insort немного быстрее, где это применимо, чем append-then-sort (если у вас нет нескольких элементов, которые нужно добавить, прежде чем вам понадобится снова отсортировать список) - измерение на моем ноутбуке выполняется как обычно ( Более быстрая машина, конечно, будет быстрее по всей доске, но соотношение должно оставаться примерно постоянным):
$ python -mtimeit -s'import random, bisect; x=range(20)' 'y=list(x); bisect.insort(y, 22*random.random())'
1000000 loops, best of 3: 1.99 usec per loop
против
$ python -mtimeit -s'import random, bisect; x=range(20)' 'y=list(x); y.append(22*random.random()); y.sort()'
100000 loops, best of 3: 2.78 usec per loop
То, насколько вы заботитесь об этой разнице, конечно, зависит от того, насколько критическим узким местом является эта операция для вашего приложения - конечно, есть ситуация, когда даже эта доля микросекунды имеет все значение, хотя они являются исключением , а не правило.
Модуль bisect не такой гибкий и настраиваемый - вы можете легко передать свой собственный компаратор для сортировки (хотя, если вы можете представить его в виде аргумента ключ =, вы сильно *) 1012 * посоветовал сделать это: в Python 3 только ключ = остается, cmp = ушел, потому что производительность просто не может быть улучшена), в то время как bisect жестко использует встроенные сравнения (так что вам придется обернуть объекты в оболочки, реализующие __cmp__ или __le__ по вашему вкусу, что также имеет важные последствия для производительности).
На вашем месте я бы начал с подхода «добавляй и сортируй» и переключился бы на менее удобный метод деления пополам, только если профилирование показало, что удар по производительности был существенным. Вспомните знаменитую цитату Кнута (и Хоара) и 1020 * Кента Бека тоже почти такую же известную! -)