Уведомления

Группа в Telegram: @pythonsu

#1 Апрель 4, 2018 08:04:42

lupanton
Зарегистрирован: 2018-03-25
Сообщения: 17
Репутация: +  0  -
Профиль   Отправить e-mail  

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

Добра всем!
Задача: удалить уникальные элементы из списка и вывести получившийся список.
Вот такое решение:

 data = [10, 9, 10, 10, 9, 8] 
a = data.copy() # создаю поверхностную копию спиcка data
# в цикле перебираю значения data, а удаляю данные из списка а, его и вывожу
for i in range(len(data)): 
    if data.count(data[i]) == 1:
        a.remove(data[i]) 
print(a)

Это работает, только не нравится мне - а без копии выдает ошибку.
 [code]data = [1, 2, 3, 4, 5] 
# в цикле перебираю значения data, удаляю данные из списка, вывожу
for i in range(len(data)): 
    if data.count(data[i]) == 1:
        data.remove(data[i]) 
print(data)
Traceback (most recent call last):
  File "<pyshell#22>", line 2, in <module>
    if data.count(data[i]) == 1:
IndexError: list index out of range[/code]
Пробую так:
 print([data.remove(data[i]) for i in range(len(data)) if data.count(data[i]) == 1])
или

 a = [data.remove(data[i]) for i in range(len(data)) if data.count(data[i]) == 1]
print(a)

Не работает.
Как сделать это красиво и почему? Помогите, люди добрые.

Отредактировано lupanton (Апрель 4, 2018 09:12:20)

Офлайн

#2 Апрель 4, 2018 09:09:26

rami
Зарегистрирован: 2018-01-08
Сообщения: 281
Репутация: +  72  -
Профиль   Отправить e-mail  

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

Так подойдёт?

 [i for i in data if data.count(i)-1]

Офлайн

#3 Апрель 4, 2018 09:17:29

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 10003
Репутация: +  857  -
Профиль   Отправить e-mail  

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

lupanton
Как сделать это красиво и почему?
Нужно один раз пройти по всему списку. Надо сделать словарь и множество: в словарь складываешь пары (встретившийся элемент, его номер в исходном списке); во множество складываешь повторившиеся элементы, которые ты переводишь из словаря, удаляя их в словаре. Когда исходный список закончится, то у тебя останется словарь уникальных элементов с их номерами в исходном списке и множество с повторившимися элементами. После этого ты сортируешь словарь по значениям (номерам в исходном списке) и берёшь только ключи словаря. Так у тебя получается выходной список с уникальными элементами.

Почему это надо сделать так - потому что меньше операций. При каждом удалении какого-то элемента из списка, чтобы его найти в списке, список надо проходить заново. То есть если в списке миллион элементов, то ты при каждом удалении будешь перебирать этот миллион элементов. Соответственно, если удалений миллион, то надо миллион раз перебирать миллион элементов.
А если ты сделаешь множества (словарь - это нагруженное множество), то ты потратишь только дополнительную память, а по операциям всё будет очень компактно.

И ещё. Тебе сейчас будут предлагать там count(), remove() и тому подобное - это всё затратные операции и их не рекомендуется применять в подобных задачах, потому что это линейные операции и они каждый раз с самого начала всё делают. То есть ты что при count(), что при remove() будешь проходить список с начала сотни раз или даже тысячи раз, что считается неграмотным подходом в алгоритмике.



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

Офлайн

#4 Апрель 4, 2018 09:25:54

lupanton
Зарегистрирован: 2018-03-25
Сообщения: 17
Репутация: +  0  -
Профиль   Отправить e-mail  

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

Спасибо! Да, так работает. А почему? В чем механика?

 i for i in data if data.count(i)-1
Как развернуть его в конструкцию вида:
 for i in data:
if data.count(i).....

Офлайн

#5 Апрель 4, 2018 10:18:07

marvellik
Зарегистрирован: 2016-05-15
Сообщения: 639
Репутация: +  73  -
Профиль   Отправить e-mail  

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

py.user.next

py.user.next
Надо сделать словарь и множество: в словарь складываешь пары (встретившийся элемент, его номер в исходном списке); во множество складываешь повторившиеся элементы, которые ты переводишь из словаря, удаляя их в словаре.
можно пример кода, что то я никак не вникну в эту суть

Офлайн

#6 Апрель 4, 2018 11:11:47

vic57
Зарегистрирован: 2015-07-07
Сообщения: 913
Репутация: +  127  -
Профиль  

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

 >>> l =[10,10,9,9, 8,9]
>>> d ={}
>>> for i in l:
	d.setdefault(i,0)
	d[i] += 1
>>> d
{10: 2, 9: 3, 8: 1}
>>> [ i for i in l if d[i] > 1]
[10, 10, 9, 9, 9]
>>> 

Офлайн

#7 Апрель 4, 2018 11:15:07

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 10003
Репутация: +  857  -
Профиль   Отправить e-mail  

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

marvellik
можно пример кода
  
>>> lst = [1, 2, 3, 1, 2, 4, 'a', 'b', 'a']
>>> 
>>> seen = {}
>>> rep = set()
>>> n = 0
>>> 
>>> for e in lst:
...     if e not in rep:
...         if e in seen:
...             rep.add(e)
...             del seen[e]
...         else:
...             seen[e] = n
...             n += 1
... 
>>> seen
{3: 2, 4: 3, 'b': 5}
>>> rep
{1, 2, 'a'}
>>>

vic57
 [ i for i
vic57 пошёл по списку второй раз. Один раз можно пройти.



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

Офлайн

#8 Апрель 4, 2018 11:49:55

vic57
Зарегистрирован: 2015-07-07
Сообщения: 913
Репутация: +  127  -
Профиль  

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

py.user.next
vic57 пошёл по списку второй раз. Один раз можно пройти.
первый проход - счетчик, второй - массив по условию

Офлайн

#9 Апрель 4, 2018 12:11:29

vic57
Зарегистрирован: 2015-07-07
Сообщения: 913
Репутация: +  127  -
Профиль  

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

lupanton
Спасибо! Да, так работает. А почему? В чем механика?

i for i in data if data.count(i)-1
в этом методе для каждого елемента списка будет будет вызываться count() - перебор всего списка
 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]]
l = list(range(10000)) + [1,2,3]
t0 = time()
l1 = f1(l)
print(time() - t0,l1)
t0 = time()
l2 = f2(l)
print(time() - t0,l2)
 1.8144128322601318 [1, 2, 3, 1, 2, 3]
0.00427699089050293 [1, 2, 3, 1, 2, 3]

Офлайн

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

marvellik
Зарегистрирован: 2016-05-15
Сообщения: 639
Репутация: +  73  -
Профиль   Отправить e-mail  

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

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

lupanton
Задача: удалить уникальные элементы из списка и вывести получившийся список
 data = [1, 2, 3, 1, 2, 4, 'a', 'b', 'a']
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 )))
 [1, 2, 1, 2, 'a', 'a']
удалены уникальные элементы 3 и b

а ваш результат {1, 2, ‘a’} это множество из списка из которого удалены уникальные элементы

Отредактировано marvellik (Апрель 4, 2018 12:13:56)

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version