Самый быстрый способ найти позицию вставки для новых данных в отсортированный список дат

Question

Допустим, у меня есть список дат:

mydates = [Timestamp('2017-03-31 00:00:00'),
  Timestamp('2017-06-30 00:00:00')     
  Timestamp('2017-09-30 00:00:00'),
 Timestamp('2017-12-31 00:00:00'),
 Timestamp('2018-03-31 00:00:00')]

И я получаю новую дату и хочу знать, в какую позицию ее вставить. Если дата уже есть в списке, мы предполагаем, что мы вставим ее снова справа от существующей даты.

Т.е., '2016-12-10' будет вставлено в позицию 0, слева до Timestamp('2017-03-31 00:00:00') и т. Д.

Answer 1

В общем, лучшее, что вы можете сделать, чтобы найти местоположение, - это логарифмический поиск. Но детали зависят от того, что у тебя есть.

Также обратите внимание, что даже если вы улучшите поиск с линейного времени до логарифмического, если вы используете структуру данных, такую ​​как list или array, insert все равно будет занимать линейное время (потому что это должно сдвинуть остальную часть списка вверх). Так что вы можете оптимизировать не то.

• Для очень маленькой коллекции, например, list из 5 значений, вам, вероятно, лучше использовать линейный поиск.
• Если вы выполняете почти все вставки за одну фазу, а затем почти все поиски после того, как коллекция в основном уже построена, просто соберите все с помощью set.add или list.append, а затем sort конец фазы. Это все еще эффективное (амортизированное) время регистрации, но с гораздо лучшим множителем.
• Для list или другой простой Sequence используйте bisect из stdlib.
• Для numpy array или для чего-то похожего на панду Series: используйте numpy's searchsorted. (Если вы храните кучу объектов Pandas Timestamp, вам, вероятно, следует использовать одну из этих структур данных вместо list, если вы еще этого не сделали.)
• Если вы выполняете много операций вставки (и удаления?), Чередующихся с поисками, вы можете переключиться на логарифмическую структуру данных. Здесь есть много вариантов, но что-то вроде blist - хорошее место для начала.

Answer 2

Если у вас есть отсортированный список, вы можете вставить новую дату и отсортировать результат. Вы также можете использовать bisect .