Почему функция возвращает разные числа?

Question

[Korifa]

если в функции в range написать к примеру 6010 и вернуть число с индексом 6000, а потом в range написать число 10000 и снова вернуть число с индексом 6000, то числа разные, почему ?

def dbl_linear(n):
	integers = [1]
	for k in range(10100):
		f = integers[k] * 2 + 1
		integers.append(f)
		c = integers[k]*3+1
		integers.append(c)
	a = list(set(integers))
	a.sort()
	return a[6000]

Comments

[GavriKos]

из за сортировки ИМХО

Answer 1

[Roman K]

1. Учим основы питона. Множество (set) всегда отсортировано, если создаётся из коллекции (в твоём случае — массива). И если ты сделаешь из него массив — он тоже будет отсортирован. Нет никакого смысла делать a.sort()
2. При увеличении k голова твоего массива "a" МОЖЕТ изменяться, потому что далеко не факт, что "f" и "c" попадут в хвост массива (из-за сортировки). Я даже могу пообещать тебе, что такого не будет, потому что "f" растёт медленней, чем "c". Поэтому при разном количестве шагов будут разные числа на позиции 6000
3. Если ты хочешь удалить дубли из массива без смены позиций — нельзя использовать set. Самый очевидный способ (но при этом очень медленный) — перегнать из одного массива в другой:

a = [7, 5, 7, 7, 1, 2, 3, 2]
b = []
for i in a:
    if i not in b:
        b.append(i)

Сложность такого подхода — O(n**2)

Сократить до O(n) можно использованием множества:

a = [7, 5, 7, 7, 1, 2, 3, 2]
b = []
s = set()
for i in a:
    if i not in s:
        b.append(i)
        s.add(i)

Так как проверки по хэш-таблице в среднем за O(1), то ты получаешь линейную сложность

Доказательство того, что со множествами быстрее:

Comments

[aRegius]

Множество (set) всегда отсортировано

???

[Roman K]

aRegius, уточнил в ответе

[Korifa]

Roman Kitaev, только что попробовал без сортировки и итоговый список получился не отсортированным, и множество тоже
можно ссылку на то где это описано

[Roman K]

Korifa, Какой питон?

[Korifa]

Roman Kitaev, 3.6

[Roman K]

Korifa, покажи код. Потому что вот это всегда сортирует:

In [1]: set([8, 7, 1, 3, 0])
Out[1]: {0, 1, 3, 7, 8}

In [2]: x = [8, 7, 1, 3, 0]

In [3]: set(x)
Out[3]: {0, 1, 3, 7, 8}

[Korifa]

Roman Kitaev,

>>> import random
>>> integers = [random.randint(1, 3000) for _ in range(10**3)]
>>> a = set(integers)
>>> a
{1, 2053, 2054, 7, 2056, 2061, 15, 2065, 2068, 21, 2070, 20, 2072, 2073, 22, 30, 34, 35, 2084, 2082, 36, 39, 43, 44, 50, 52, 2101, 58, 2107, 62, 2110, 64, 68, 2117, 72, 74, 76, 77, 80, 2130, 2131, 84, 85, 2135, 2140, 93, 100, 2148, 2150, 101, 106, 2156, 109, 115, 2167, 121, 122, 123, 2171, 2169, 127, 128, 2177, 130, 129, 2179, 2178, 132, 135, 2184, 136, 2187, 144, 2193, 147, 2197, 2198, 151, 149, 2201, 153, 2202, 159, 160, 162, 2213, 2215, 172, 2224, 178, 179, 2228, 2231, 184, 185, 2234, 2233, 190, 191, 2244, 196, 2246, 199, 2248, 2245, 202, 2251, 205, 206, 2255, 2256, 2259, 213, 2265, 2267, 219, 221, 222, 220, 224, 2271, 2269, 227, 2276, 229, 2278, 2280, 2281, 2282, 238, 239, 241, 244, 2292, 2295, 248, 2297, 2300, 2301, 255, 2304, 2305, 2306, 260, 2310, 264, 265, 2314, 2315, 269, 272, 2321, 276, 2326, 278, 285, 2334, 287, 289,

[Roman K]

Korifa, хм. Это интересно поведение, которое у меня никогда не происходило. Окей, как бы то ни было, твой изначальный вопрос не об этом, остальные два моих пункта на него отвечают

Answer 2

[Игорь Статкевич]

a = list(set(integers))
вот эта функция берет список(list), преобразовывает его в множество(set), туда попадают только уникальные значения из integers, грубо говоря удаляет дубликаты и потом list(integers) преобразует обратно в список, однако список это упорядоченный масив, а вот set не упорядоченный, поэтому после преобразовывания set(integers) внутри все будет каждый раз перемешенно по разному, хотите вернуть упорядоченный, попробуйте
a = [integer for i, integer in enumerate(integers) if integer not in integers[:i]]