Обнаружил сегодня забавный момент в Python'е.

Представьте себе, что у вас есть список списков x. Например, x = [[1, 2, 3], [], [[6, 6, 6]]]. Мы хотим сконкатенировать все элементы x и получить в данном случае [1, 2, 3, [6, 6, 6]]. Наука это учит делать красиво: sum(x, []). Действительно, сложение для списков -- это просто-напросто конкатенация.

Однако, у данного подхода есть существенный недостаток. Если, к примеру, у нас k списков константной длины, то sum(x, []) будет работать за время O(k²), а не O(k), как разумеется хотелось бы. Это происходит вот почему: результат сложения списков записывается в новое место, и на выделение памяти каждый раз уходит линейное время. Проблема. Однако, простой цикл спасает положение.

result = []
for element in x: <перенос строки + таб> for item in element: <перенос строки + таб + таб> result.append(item)

Действительно, append работает за учетное время O(1).

Внимание, бонусный вопрос: как сделать конкатенацию всех элементов за время O(k) в "функциональном" стиле?