Сортировка списка - удалить частичные повторы

[Ципихович Эндрю]

здравствуйте, как сделать по сабжу я в курсе

a = ["5q5", "7", "66", "77", "5", "6", "36", "9"] # сортировка списка - удалены частичные повторы
print(*filter(lambda i: all(map(lambda x: i not in x, [x for x in a if x != i])), a))  # 5q5 66 77 36 9

так и не понял как создать новый список b, чтобы он был равен ["5q5", "66", "77", "36", "9"]?
спасибо

[BDA]

b = list(filter(...))

[Ципихович Эндрю]

ок, то, что нужно:

a = ["5q5", "7", "66", "77", "5", "6", "36", "9"] # сортировка списка - удалены частичные повторы
b = list(filter(lambda i: all(map(lambda x: i not in x, [x for x in a if x != i])), a))
print(b)  # ['5q5', '66', '77', '36', '9']

[Ципихович Эндрю]

2 вариант

a = ["5q5", "7", "66", "77", "5", "6", "36", "9"]
b = [x for x in a if x not in [x for x in a for y in a if x != y and x in y]]
print(b)

скажите какой из этих двух вариантов более быстрый?
со списком размера примерно
758177
реально дождаться обработки? что-то мой ПК конца и края не видит..........

[BDA]

Из этих двух вариантов быстрее третий (чуть измененный второй):

import timeit

for code in [
    '''\
a = ["5q5", "7", "66", "77", "5", "6", "36", "9"]
b = list(filter(lambda i: all(map(lambda x: i not in x, [x for x in a if x != i])), a))
''',
    '''\
a = ["5q5", "7", "66", "77", "5", "6", "36", "9"]
b = [x for x in a if x not in [x for x in a for y in a if x != y and x in y]]
''',
    '''\
a = ["5q5", "7", "66", "77", "5", "6", "36", "9"]
c = [x for x in a for y in a if x != y and x in y]
b = [x for x in a if x not in c]
'''
]:
    #print(code)
    #exec(code + "\nprint(b)")
    print(timeit.timeit(code, number = 10000))

0.13180309999999998
0.36127600000000004
0.048267199999999955

Сообщение от Ципихович Эндрю

реально дождаться обработки

Вот с таким примером на моем ПК время на обработку списка из 750000 элементов можно грубо оценить в 19 часов.

import timeit
import string

def NumToStr(num):
    result = []
    letters = string.ascii_lowercase
    letters_len = len(letters)
    while num:
        num, rem = divmod(num - 1, letters_len)
        result[:0] = letters[rem]
    return ''.join(result)

s = '''\
c = [x for x in a for y in a if x != y and x in y]
b = [x for x in a if x not in c]
'''
for c in [10, 100, 500, 1000, 5000, 10000]:
    a = [NumToStr(i) for i in range(1, c + 1)]
    print(c, timeit.timeit(s, number = 1, globals = globals()))

10 7.80000000000225e-06
100 0.0006367999999999929
500 0.017754900000000018
1000 0.09059660000000003
5000 2.792164
10000 10.9601953

UPD. Вот такой "велосипед" справляется с миллионом элементов за 3 секунды, но что будет на реальных данных, не могу угадать.

import timeit
import string
from collections import defaultdict 

def NumToStr(num):
    result = []
    letters = string.ascii_lowercase
    letters_len = len(letters)
    while num:
        num, rem = divmod(num - 1, letters_len)
        result[:0] = letters[rem]
    return ''.join(result)

def filter_f(a):
    d = defaultdict(list)
    res = []
    known_ws = set()
    for w in a:
        d[len(w)].append(w)
    lens = sorted(d.keys(), reverse = True)
    for i, k in enumerate(lens):
        for w in d[k]:
            if w not in known_ws:
                res.append(w)
                known_ws.add(w)
                for l in lens[i + 1:]:
                    for s in range(k - l + 1):
                        known_ws.add(w[s:s + l])
    return res

s = '''\
c = [x for x in a for y in a if x != y and x in y]
b = [x for x in a if x not in c]
'''
for c in [10, 100, 500, 1000, 5000, 10000]:
    a = [NumToStr(i) for i in range(1, c + 1)]
    print(c,
        timeit.timeit(s, number = 1, globals = globals()),
        timeit.timeit("filter_f(a)", number = 1, globals = globals())
    )

for c in [50000, 100000, 500000, 1000000]:
    a = [NumToStr(i) for i in range(1, c + 1)]
    print(c,
        timeit.timeit("filter_f(a)", number = 1, globals = globals())
    )

10 8.2e-06 1.579999999999999e-05
100 0.0006411000000000001 0.0001049
500 0.018240100000000002 0.0005647999999999972
1000 0.0822098 0.0018729999999999997
5000 2.8664011 0.00890039999999992
10000 11.7256719 0.019374099999998506
50000 0.1307482000000011
100000 0.3265539999999998
500000 1.8473674999999972
1000000 2.9146336999999995

[Ципихович Эндрю]

BDA, спасибо, пока удалил лишнее, связанное с тестом:

from collections import defaultdict
 
def filter_f(a):
    d = defaultdict(list)
    res = []
    known_ws = set()
    for w in a:
        d[len(w)].append(w)
    lens = sorted(d.keys(), reverse = True)
    for i, k in enumerate(lens):
        for w in d[k]:
            if w not in known_ws:
                res.append(w)
                known_ws.add(w)
                for l in lens[i + 1:]:
                    for s in range(k - l + 1):
                        known_ws.add(w[s:s + l])
    return res

вывод
['5q5', '7', '66', '77', '5', '6', '36', '9']
['5q5', '66', '77', '36', '9']
опробую))

[Ципихович Эндрю]

на моих реальных данных скрипт падает на строке

known_ws.add(w[s:s + l])

MemoryError

[Ципихович Эндрю]

Сообщение от Ципихович Эндрю

на моих реальных данных скрипт падает на строке
Код:
known_ws.add(w[s:s + l])
MemoryError

понял свою ошибку, разберусь..........

[BDA]

Сообщение от Ципихович Эндрю

MemoryError

Вот такой вариант, вроде, должен меньше памяти тратить:

def filter_f2(a):
    d = defaultdict(set)
    res = set(a)
    for w in a:
        d[len(w)].add(w)
    lens = sorted(d.keys(), reverse = True)
    for i, k in enumerate(lens):
        for w in d[k]:
            if w in res:
                for l in lens[i + 1:]:
                    for s in range(k - l + 1):
                        ww = w[s:s + l]
                        if ww in res:
                            res.remove(ww)
    return list(res)

[Ципихович Эндрю]

ок, опробую:

a = ["5q5", "7", "66", "77", "5", "6", "36", "9"]
from collections import defaultdict
def filter_f2(a):
    d = defaultdict(set)
    res = set(a)
    for w in a:
        d[len(w)].add(w)
    lens = sorted(d.keys(), reverse = True)
    for i, k in enumerate(lens):
        for w in d[k]:
            if w in res:
                for l in lens[i + 1:]:
                    for s in range(k - l + 1):
                        ww = w[s:s + l]
                        if ww in res:
                            res.remove(ww)
    return list(res)
print(filter_f2(a))