Стоимость len () функция
Это на самом деле более простая проблема. Ударь его своей алгеброй начальной школы. Во-первых, небольшое понимание покажет, что вы всегда хотите, чтобы числа сортировались при переходе сверху вниз слева направо. Подойдёт либо восходящий, либо нисходящий; они изоморфны. Давайте предположим, что по возрастанию, чтобы соответствовать вашим примерам. Для набора из 9 чисел:
i1 i2 i3
i4 i5 i6
i7 i8 i9
Нам нужно сложить слагаемые
// ROWS
i2-i1 + i3-i2 +
i5-i4 + i6-i5 +
i8-i7 + i9-i8 +
// COLUMNS
i4-i1 + i7-i4 +
i5-i2 + i8-i5 +
i6-i3 + i9-i6
Это сводится к i3-i1 + i6-i4 + i9-i7 + i7-i1 + i8-i2 + i9-i3
И это становится 2 * i9 - 2 * i1 + i6 + i8 - (i2 + i4)
Начните с сортировки своих N чисел и поиска смежная подпоследовательность чисел A * B с наименьшей разницей между самой низкой и самой высокой. Затем расположите номера неугловой границы так, чтобы разница (верхняя + левая) - (нижняя + правая) была минимальной, учитывая, сколько чисел может быть между каждой парой. Наконец, заполните любым доступным способом.
Очень просто, это сводится к суммам верхнего и левого ребер, минус нижний и правый ребра. Основные углы считаются двойными; выпадают верхний правый и нижний левый углы, а также все внутренние термины.
Да, я пропустил несколько логических шагов ... Я надеюсь, что этого достаточно для вас. Он сокращает пространство поиска с A*B чисел, взятых из N, до двух смежных последовательностей чисел A+B-2 в этой последовательности из A*B.
5 ответов
It's O(1) (constant time, not depending of actual length of the element - very fast) on every type you've mentioned, plus set and others such as array.array.
Я думал, что len () в Python зависит от размера списка, поэтому я всегда сохраняю длину в переменной, если использую несколько раз. Но сегодня во время отладки я заметил атрибут __len__ в объекте списка, поэтому len () должен просто извлекать его, что усложняет O (1). Так что я просто погуглил, если кто-то уже спросил это и наткнулся на этот пост.
All those objects keep track of their own length. The time to extract the length is small (O(1) in big-O notation) and mostly consists of [rough description, written in Python terms, not C terms]: look up "len" in a dictionary and dispatch it to the built_in len function which will look up the object's __len__ method and call that ... all it has to do is return self.length
Calling len() on those data types is O(1) in CPython, the most common implementation of the Python language. Here's a link to a table that provides the algorithmic complexity of many different functions in CPython:
The below measurements provide evidence that len() is O(1) for oft-used data structures.
A note regarding timeit: When the -s flag is used and two strings are passed to timeit the first string is executed only once and is not timed.
List:
$ python -m timeit -s "l = range(10);" "len(l)"
10000000 loops, best of 3: 0.0677 usec per loop
$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 loops, best of 3: 0.0688 usec per loop
Tuple:
$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 loops, best of 3: 0.0712 usec per loop
$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 loops, best of 3: 0.0699 usec per loop
String:
$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop
$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 loops, best of 3: 0.0686 usec per loop
Dictionary (dictionary-comprehension available in 2.7+):
$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 loops, best of 3: 0.0711 usec per loop
$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 loops, best of 3: 0.0727 usec per loop
Array:
$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 loops, best of 3: 0.0682 usec per loop
$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 loops, best of 3: 0.0753 usec per loop
Set (set-comprehension available in 2.7+):
$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 loops, best of 3: 0.0754 usec per loop
$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop
Deque:
$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop
$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop