← Сtrl

py.user.next · Апрель 4, 2018 12:14:34

vic57
первый проход - счетчик, второй - массив по условию

Да, а можно один раз пройти. Если там миллион элементов в списке, а сам код вызывается 10000 раз, это имеет значение. Поэтому стараются всегда писать однопроходные коды. У них сложность O(n), тогда как у тебя сложность O(n^2) - так называемый квадратный код, присущий новичкам.

marvellik
py.user.next так результат не соответствует заданию

Да, что-то я протупил, видимо. Если так, то словарь не нужен тогда, достаточно одного множества для неуникальных элементов и потом список по второму разу пройти и выбрать элементы, входящие во множество неуникальных. Это оптимальный алгоритм.

Тут всё равно список нужно до конца пройти как минимум один раз, прежде чем выбирать неуникальные элементы, потому что может быть так, что первый элемент будет 1, потом будет миллион элементов 0, а потом в конце будет опять элемент 1. И пока до последнего элемента не дойдёшь, никак не определишь, что первая еденица должна сохраняться в списке вывода. То есть ты не можешь на ходу это лепить, поэтому однопроходный алгоритм здесь не прокатит.

Отредактировано py.user.next (Апрель 4, 2018 12:27:53)

marvellik · Апрель 4, 2018 12:28:10

py.user.next можно и с словарем но результаты говорят сами за себя

 from time import time
def f_1(dat):
    dict_data = {}
    for i,x in enumerate(data):
        dict_data[x] = dict_data.get(x,0)+1
    print(list(filter(lambda x : dict_data.get(x) > 1,data )))
def f_2(data):
    print(list(filter(lambda x : data.count(x) > 1 ,data)))

 [1, 2, 1, 2, 'a', 'a']
0.01300048828125
[1, 2, 1, 2, 'a', 'a']
0.00500035285949707

vic57 · Апрель 4, 2018 12:39:41

marvellik
результаты говорят сами за себя

именно

 from time import time
def f1(lst):
    return [i for i in lst if lst.count(i)-1]
def f2(lst):
    d = {}
    for i in lst:
        d.setdefault(i,-1)
        d[i] += 1
    return [i for i in lst if d[i]]
def f_1(data):
    dict_data = {}
    for i,x in enumerate(data):
        dict_data[x] = dict_data.get(x,0)+1
    return list(filter(lambda x : dict_data.get(x) > 1,data ))
def f_2(data):
    return list(filter(lambda x : data.count(x) > 1 ,data))
l = list(range(10000)) + [3,2,1,4]
t0 = time()
l1 = f1(l)
print('f1',time() - t0,l1)
t0 = time()
l2 = f2(l)
print('f2',time() - t0,l2)
t0 = time()
l2 = f_1(l)
print('f_1',time() - t0,l2)
t0 = time()
l2 = f_2(l)
print('f_2',time() - t0,l2)

f1 1.8496160507202148 [1, 2, 3, 4, 3, 2, 1, 4]
f2 0.006292819976806641 [1, 2, 3, 4, 3, 2, 1, 4]
f_1 0.011389970779418945 [1, 2, 3, 4, 3, 2, 1, 4]
f_2 1.859050989151001 [1, 2, 3, 4, 3, 2, 1, 4]

Отредактировано vic57 (Апрель 4, 2018 12:40:59)

py.user.next · Апрель 4, 2018 12:43:03

Короче, получился вариант, эквивалентный варианту vic57

  
>>> lst = [1, 2, 3, 1, 2, 4, 'a', 'b', 'a']
>>> 
>>> seen = {}
>>> 
>>> for e in lst:
...     seen[e] = seen.get(e, 0) + 1
... 
>>> out = [i for i in lst if seen[i] > 1]
>>> out
[1, 2, 1, 2, 'a', 'a']
>>>

marvellik
py.user.next можно и с словарем но результаты говорят сами за себя

Побольше элементов возьми и enumerate() там не нужен.

lupanton · Апрель 4, 2018 12:59:18

py.user.next Спасибо! Вот что у меня получилось: Список проходится один раз, нет итерационных count(), remove(). Теперь нужно вникнуть в запись покороче)))

 data = [10, 6, 9, 10, 10, 9, 8, 4]
dict = {}
a = set()
for i in range(len(data)):
    if data[i] not in dict:
        if data[i] not in a:
            dict[data[i]] = i
        else:
            a.add(data[i])
    else:
        a.add(data[i])
        dict.pop(data[i])
for value in sorted(dict.values(), reverse = True):
    data.pop(value)
print(data)

marvellik · Апрель 4, 2018 19:56:24

vic57 да точно на больших списках с словарем работает быстрее

py.user.next
Короче, получился вариант, эквивалентный варианту vic57

но все равно код vic57 из всех вариантов самый быстрый на 2-3 сотых быстрее

vic57 · Апрель 4, 2018 20:46:04

marvellik
но все равно код vic57 из всех вариантов самый быстрый на 2-3 сотых быстрее

я читал что dict.setdefault() быстрее чем dict.get()
быстрее всего collections->Counter

 from time import time
from collections import Counter
def f1(lst):
    d = {}
    for i in lst:
        d.setdefault(i,-1)
        d[i] += 1
    return [i for i in lst if d[i]]
def f2(lst):
    c = Counter(lst)
    return [i for i in lst if c[i] != 1]
l = list(range(100000)) + [3,2,1]
t0 = time()
l1 = f1(l)
print(time() - t0,l1)
t0 = time()
l1 = f2(l)
print(time() - t0,l1)

 0.042214155197143555 [1, 2, 3, 3, 2, 1]
0.03288602828979492 [1, 2, 3, 3, 2, 1]

py.user.next · Апрель 5, 2018 01:33:47

marvellik
но все равно код vic57 из всех вариантов самый быстрый на 2-3 сотых быстрее

Рассматриваем только разницу в скорости в два раза. Если код быстрее хотя бы в два раза, то он быстрее, иначе это всё погрешности.

Python-сообщество

Уведомления

#1 Апрель 4, 2018 12:14:34

Перебор списка с удалением элемента по условию

#2 Апрель 4, 2018 12:28:10

Перебор списка с удалением элемента по условию

#3 Апрель 4, 2018 12:39:41

Перебор списка с удалением элемента по условию

#4 Апрель 4, 2018 12:43:03

Перебор списка с удалением элемента по условию

#5 Апрель 4, 2018 12:59:18

Перебор списка с удалением элемента по условию

#6 Апрель 4, 2018 19:56:24

Перебор списка с удалением элемента по условию

#7 Апрель 4, 2018 20:46:04

Перебор списка с удалением элемента по условию

#8 Апрель 5, 2018 01:33:47

Перебор списка с удалением элемента по условию

Board footer