LINUX.ORG.RU
Форум — General  

Сортировка списка из кортежей в python

 , ,


0

1

У меня есть два списка - номер элемента и его значение:

a = [(0,10.8),(1,8.2),(2,0.3)]
b = [(0,0.4),(3,20.2),(2,0.3)]

Списки имеют разный набор элементов. Я хочу просуммировать значение одинаковых элементов и отсортировать их. Я написал код, но он очень корявый. Можете помочь его сократить?

INPUT:

c = []

d = []

for i in a:
  for j in b:
    if i[0] == j [0]:
      c.append((i[0], i[1]+j[1]))
      d.append(i[0])

for i in a:
  if i[0] not in d:
    c.append(i)

for i in b:
  if i[0] not in d:
    c.append(i)

sorted(c, key=lambda x: x[1], reverse=True)

OUTPUT:

[(3, 20.2), (0, 11.200000000000001), (1, 8.2), (2, 0.6)]


Последнее исправление: bard192 (всего исправлений: 1)

У меня есть два списка - номер элемента и его значение:

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

peregrine ★★★★★
()
Последнее исправление: peregrine (всего исправлений: 4) 
xs = [(0,10.8),(1,8.2),(2,0.3)] 
ys = [(0,0.4),(3,20.2),(2,0.3)]

# нутром чую, что требования страннее, чем кажется на первый
# взгляд --- заменить лямбду на именованную функцию и все извращения 
# вынести туда
xs_and_ys = map(lambda x, y: (x[0] + y[0], x[1] + y[1]), xs, ys)

xs_and_ys_sorted = sorted(xs_and_ys, key=lambda x: x[1], reverse=True)
Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 2)

Я написал код, но он очень корявый

Нормальный код.

Можете помочь его сократить?

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

vvn_black ★★★★★
()
Ответ на: комментарий от bard192

результат не тот…

Нужно слегка доработать напильником.

P. S. Да, похоже, требования я понял не просто неправильно, а кардинально неправильно %)

Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 1)

Можете помочь его сократить?

a = [(0, 10.8), (1, 8.2), (2, 0.3)]
b = [(0, 0.4), (3, 20.2), (2, 0.3)]

c = a + b

keys = set(map(lambda x: x[0], c))
result = [*map(lambda key: (key, sum(map(lambda x: x[1],
                                         filter(lambda x: x[0] == key, c)))),
               keys), ]
print(sorted(result, key=lambda x: x[1], reverse=True))

[(3, 20.2), (0, 11.200000000000001), (1, 8.2), (2, 0.6)]
vvn_black ★★★★★
()
Последнее исправление: vvn_black (всего исправлений: 2)
Ответ на: комментарий от bard192

Буду разбираться

Общая часть:

a = [(0, 10.8), (1, 8.2), (2, 0.3)]
b = [(0, 0.4), (3, 20.2), (2, 0.3)]
c = a + b
keys = set(map(lambda x: x[0], c))

Если императивно, то

result = []
for key in keys:
    summ = 0
    for x in c:
        if x[0] == key:
            summ += x[1]
    result.append((key, summ))

Если питоник-вей то: 

result = [(key, sum([x[1] for x in c if x[0] == key])) for key in keys]

vvn_black ★★★★★
()
Последнее исправление: vvn_black (всего исправлений: 1)

Так еще можно (третий питон).

xs = [(0,10.8),(1,8.2),(2,0.3)]
ys = [(0,0.4),(3,20.2),(2,0.3)]

# словарь с просуммированными значениями
sum_dict = {x[0]: x[1] + y[1] for x in xs for y in ys if x[0] == y[0]}

# объединяем исходные словари и словарь с просуммированными значениями слева направо
result_dict = {**dict(xs), **dict(ys), **sum_dict}

# готово, вы великолепны! (и не сломали при этом мозг)
result = [(k, v) for k,v in result.items()]

# ах да, сортировка
sorted_result = sorted(result, key=lambda x: x[1], reverse=True)
sorted_result
[(3, 20.2), (0, 11.200000000000001), (1, 8.2), (2, 0.6)]
Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 4)

Я думал, мой вариант жестоко всосет по производительности (перебор комбинаций), но нет:

import timeit


iterations = 10000

xs = [(0, 10.8), (1, 8.2), (2, 0.3)]
ys = [(0, 0.4), (3, 20.2), (2, 0.3)]


def one_imperative(a, b):
    c = a + b
    keys = set(map(lambda x: x[0], c))

    result = []
    for key in keys:
        summ = 0
        for x in c:
            if x[0] == key:
                summ += x[1]
        result.append((key, summ))

    return sorted(result, key=lambda x: x[1], reverse=True)


def one_pythonic(a, b):
    c = a + b
    keys = set(map(lambda x: x[0], c))

    result = [(key, sum([x[1] for x in c if x[0] == key])) for key in keys]

    return sorted(result, key=lambda x: x[1], reverse=True)


def two(xs, ys):
    sum_dict = {x[0]: x[1] + y[1] for x in xs for y in ys if x[0] == y[0]}

    result_dict = {**dict(xs), **dict(ys), **sum_dict}

    result = [(k, v) for k,v in result_dict.items()]

    return sorted(result, key=lambda x: x[1], reverse=True)


time_one_imperative = timeit.timeit("one_imperative(xs, ys)", "from __main__ import xs, ys, one_imperative", number=iterations)
time_one_pythonic = timeit.timeit("one_pythonic(xs, ys)", "from __main__ import xs, ys, one_pythonic", number=iterations)
time_two = timeit.timeit("two(xs, ys)", "from __main__ import xs, ys, two", number=iterations)

print("One imperative: ", time_one_imperative)
print("One pythonic: ", time_one_pythonic)
print("Two: ", time_two)

One imperative:  0.18978183099534363
One pythonic:  0.25368363698362373
Two:  0.1737681599915959

Может, начнет сосать на более длинных входных данных, надо проверить.

Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 1)
Ответ на: комментарий от Nervous

Может, начнет сосать на более длинных входных данных

Так точно, сильно начёт отставать.

А на таких коротких данных самым "медленным"будет декларативный вариант «с лямбдами». Но если лямбды заменить на функции, то и он сравняется с императивным и «питоническим», .

vvn_black ★★★★★
()
Ответ на: комментарий от vvn_black

Попробовал так

data_size = 100
iterations = 1000

xs = [(x, x*x) for x in range(data_size)]
ys = [(x, x + x) for x in range(data_size)]

...

One imperative:  4.405387898004847
One pythonic:  4.029522532975534
Two:  3.1333080009790137

Окей, добавим еще данных:

data_size = 1000
iterations = 10

...

One imperative:  4.500911807001103
One pythonic:  4.287391154997749
Two:  3.0663874369929545

И еще:

data_size = 10000
iterations = 1

...

One imperative:  46.79107773100259
One pythonic:  44.19063223400735
Two:  31.2664970770129

Какая-то питонья магия %) Хотя…

 for key in keys:
        summ = 0
        for x in c:

тот же самый o(n^2) ведь.

Но что так, что этак десятки секунд на 10к элементов — это жесть. Граждане! Храните деньги в сберегаданные в правильных структурах! %)

Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 2)

Я бы сделал так:

a = [(0,10.8),(1,8.2),(2,0.3)]
b = [(0,0.4),(3,20.2),(2,0.3)]

c = list(a)
ind1 = 0
for elem in c:
  key1 = elem[0]
  ind2 = next(i for i, e in enumerate(b) if e[0] == key1)
  if not(ind2 is None):
    c[ind1] = (key1, elem[1]+b[ind2][1])
  ind1 += 1

c = sorted(c, key=lambda x: x[1], reverse=True)
Novator ★★★★★
()
Последнее исправление: Novator (всего исправлений: 2)
Ответ на: комментарий от Novator

Шота у меня c данными ТСа не работает:

def three(a, b):
    c = list(a)
    ind1 = 0
    for elem in c:
        key1 = elem[0]
        ind2 = next(i for i, e in enumerate(b) if e[0] == key1)
        if not(ind2 is None):
            c[ind1] = (key1, elem[1]+b[ind2][1])
        ind1 += 1

    return sorted(c, key=lambda x: x[1], reverse=True)


a = [(0,10.8),(1,8.2),(2,0.3)]
b = [(0,0.4),(3,20.2),(2,0.3)]


three(a, b)

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/nervous/tuples.py", line 48, in three
    ind2 = next(i for i, e in enumerate(b) if e[0] == key1)
StopIteration

Хотя с синтетическими все окей (в смысле не падает) и даже шустрее всех:

data_size = 100
iterations = 1000

xs = [(x, x*x) for x in range(data_size)]
ys = [(x, x + x) for x in range(data_size)]

...

One imperative:  4.3429664069844875
One pythonic:  4.039353622996714
Two:  3.1694852040091064
Three:  1.737760635005543
Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 4)
Ответ на: комментарий от Nervous

Точно, я ведь не запускал.

Сейчас запустил и заметил, что индексы во 2-м массиве могут быть «лишними». Переделал с учётом этого: 

a = [(0,10.8),(1,8.2),(2,0.3)]
b = [(0,0.4),(3,20.2),(2,0.3)]

c = list(a)

for elem in b:
  key2 = elem[0]
  try:
    ind1 = next(i for i, e in enumerate(c) if e[0] == key2)
  except:
    ind1 = None
  if ind1 is None:
    c.append(elem)
  else:
    c[ind1] = (key2, c[ind1][1]+elem[1])

c = sorted(c, key=lambda x: x[1], reverse=True)
print(c)

Novator ★★★★★
()
Последнее исправление: Novator (всего исправлений: 1)
Ответ на: комментарий от bard192

Разобрался? Попробуй тогда в таком варианте разобраться, он должен быть попроще:

a = [(0,10.8),(1,8.2),(2,0.3)]
b = [(0,0.4),(3,20.2),(2,0.3)]

class my_dict(dict):
    def update_from_list(self, lst):
        for i,v in lst:
            self[i] = self.get(i, 0) + v
            
    def to_sorted_list(self):
        sort_key = lambda x: -x[1]
        return sorted(self.items(), key=sort_key)

d = my_dict()
d.update_from_list(a)
d.update_from_list(b)

print(*d.to_sorted_list(), sep='\n')

Кто не разберётся — тот лох.

anonymous
()

Итак, финал:

import timeit

data_size = 1000
iterations = 10

xs = [(x, x*x) for x in range(data_size)]
ys = [(x, x + x) for x in range(data_size)]


# solution one: @vvn_black

def one_imperative(a, b):
    c = a + b
    keys = set(map(lambda x: x[0], c))

    result = []
    for key in keys:
        summ = 0
        for x in c:
            if x[0] == key:
                summ += x[1]
        result.append((key, summ))

    return sorted(result, key=lambda x: x[1], reverse=True)


def one_pythonic(a, b):
    c = a + b
    keys = set(map(lambda x: x[0], c))

    result = [(key, sum([x[1] for x in c if x[0] == key])) for key in keys]

    return sorted(result, key=lambda x: x[1], reverse=True)


# solution two: @Nervous

def two(xs, ys):
    sum_dict = {x[0]: x[1] + y[1] for x in xs for y in ys if x[0] == y[0]}

    result_dict = {**dict(xs), **dict(ys), **sum_dict}

    result = [(k, v) for k,v in result_dict.items()]

    return sorted(result, key=lambda x: x[1], reverse=True)


# solution three: @Novator

def three(a, b):
    c = list(a)

    for elem in b:
        key2 = elem[0]
        try:
            ind1 = next(i for i, e in enumerate(c) if e[0] == key2)
        except:
            ind1 = None
        if ind1 is None:
            c.append(elem)
        else:
            c[ind1] = (key2, c[ind1][1]+elem[1])

    return sorted(c, key=lambda x: x[1], reverse=True)


# solution four: @anonymous

class my_dict(dict):
    def update_from_list(self, lst):
        for i,v in lst:
            self[i] = self.get(i, 0) + v

    def to_sorted_list(self):
        sort_key = lambda x: -x[1]
        return sorted(self.items(), key=sort_key)

def four(a,b):
    d = my_dict()
    d.update_from_list(a)
    d.update_from_list(b)

    return d.to_sorted_list()



time_one_imperative = timeit.timeit("one_imperative(xs, ys)", "from __main__ import xs, ys, one_imperative", number=iterations)
time_one_pythonic = timeit.timeit("one_pythonic(xs, ys)", "from __main__ import xs, ys, one_pythonic", number=iterations)
time_two = timeit.timeit("two(xs, ys)", "from __main__ import xs, ys, two", number=iterations)
time_three = timeit.timeit("three(xs, ys)", "from __main__ import xs, ys, three", number=iterations)
time_four = timeit.timeit("four(xs, ys)", "from __main__ import xs, ys, four, my_dict", number=iterations)

print("One imperative: ", time_one_imperative)
print("One pythonic: ", time_one_pythonic)
print("Two: ", time_two)
print("Three: ", time_three)
print("Four: ", time_four)

Результаты (секунды):

One imperative:  4.398868718009908
One pythonic:  4.26980336298584
Two:  3.0925802720012143
Three:  1.5253030479943845
Four:  0.014577852009097114

Победил анонимус с самым коротким и самым производительным решением (o(n) против o(n²) у остальных).

Nervous ★★★★★
()
Ответ на: комментарий от Nervous

Победил анонимус с самым коротким и самым производительным решением (o(n) против o(n²) у остальных).

Вот, а кто-то хотел и даже пробовал анонимусов в девелопмент не пускать.

vvn_black ★★★★★
()
Ответ на: комментарий от Nervous

Невозможно остановиться

Вариант анонимуса в одну строку, медленнее в 12 раз, но быстрее остальных в 1.5 раза:

sorted(
    reduce(lambda a, c: {**a, **{c[0]: c[1] + a.get(c[0], 0)}},
           a + b, {}).items(), key=lambda x: x[0], reverse=True)
vvn_black ★★★★★
()
Ответ на: комментарий от Nervous

Победил анонимус с самым коротким и самым производительным решением (o(n) против o(n²) у остальных).

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

Novator ★★★★★
()
Ответ на: комментарий от Novator

Получается, поиск индекса в словаре происходит на два порядка быстрее, чем поиск в списке

Насколько я понимаю, примерно в n раз (O(1) против O(n) — хотя там не совсем O(1), а логарифм с большим основанием).

Мы все для каждого элемента одного списка так или иначе проходили полностью по второму списку — O(n²), а хитрый анонимус смог ограничиться одним проходом по каждому из списков — O(n). За что ему почет и уважение.

Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 5)
Ответ на: Невозможно остановиться от vvn_black

Вариант анонимуса в одну строку, медленнее в 12 раз, но быстрее остальных в 1.5 раза

Интересно, откуда такая разница - там ведь тоже только один проход по каждому списку, а производительность по замерам ближе к алгоритмам с квадратичной сложностью:

from functools import reduce

data_size = 10000
iterations = 1

def four_oneliner(a,b):
    return sorted(reduce(lambda a, c: {**a, **{c[0]: c[1] + a.get(c[0], 0)}}, a + b, {}).items(), key=lambda x: x[0], reverse=True)

...

One imperative:  46.70874344202457
One pythonic:  44.05721718602581
Two:  31.562691541970707
Three:  16.35838687903015
Four:  0.017582667991518974
Four oneliner:  13.589391865010839

Невозможно остановиться

Почему бы благородным донам не подушить питона в такой прекрасный день? %)

Nervous ★★★★★
()
Ответ на: комментарий от Nervous

там ведь тоже только один проход по каждому списку

По объединённому списку, да, один раз, а по ключам формируемого словаря? )

vvn_black ★★★★★
()
Ответ на: комментарий от vvn_black

а по ключам формируемого словаря?

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

data_size = 10000
iterations = 1

def into(adict, atuple):
    key = atuple[0]
    value = atuple[1]
    adict[key] = adict.get(key, 0) + value
    return adict

def four_oneliner_1(a, b):
    return sorted(reduce(into, a + b, {}).items(), key=lambda x: x[0], reverse=True)

One imperative:  47.0930566629977
One pythonic:  45.6742504319991
Two:  31.61444734001998
Three:  16.67398930096533
Four:  0.017567834991496056
Four oneliner:  14.656680266023614
Four oneliner, variant 1:  0.02486197801772505

Зато производительность в норме.

Nervous ★★★★★
()
Ответ на: комментарий от Nervous

А так?

sorted({i:d.update({i:d.get(i,0)+v}) or d[i] for d in [{}] for i,v in a+b}.items(), key=lambda x: -x[1])

Ещё один простенький вариант:

def simple():
    lst = [0] * (max(a+b)[0] + 1)
    for i,v in a+b:
        lst[i] += v
    return sorted(lst, key=lambda x: -x[1])
anonymous
()
Ответ на: комментарий от Novator

прогони ещё этот вариант

Кодовое имя «Three, variant 1»

One imperative:  51.71772726305062
One pythonic:  47.389383518951945
Two:  37.940367246977985
Three:  18.056043613003567
Three, variant 1:  0.0175712380441837
Four:  0.016930231009609997
Four oneliner:  26.19428977696225
Four oneliner, variant 1:  0.03499752201605588
Four oneliner, variant 2:  0.06249823002144694

Анонимусу с предыдущего поста: однострочник здесь под именем «Four oneliner, variant 2», а simple не взлетел.

return sorted(lst, key=lambda x: -x[1])
TypeError: 'int' object is not subscriptable

Хоть бы запустил разок для приличия %)

Nervous ★★★★★
()
Последнее исправление: Nervous (всего исправлений: 1)
Ответ на: комментарий от anonymous

def simple():

():

Из принципа не запускаешь? %)

Ну шо тут скажешь — O(n).

One imperative:  50.02127420500619
One pythonic:  44.79662469698815
Two:  31.809483558987267
Three:  17.70340031303931
Three, variant 1:  0.018154855992179364
Four:  0.017423724988475442
Four oneliner:  16.323466337984428
Four oneliner, variant 1:  0.02872801898047328
Four oneliner, variant 2:  0.045352499990258366
Simple:  0.020537036994937807
Nervous ★★★★★
()
Ответ на: комментарий от Nervous

Спасибо.

Да у себя-то я запускал, но у меня абсолютные значения совсем другие получаются.

А с другой стороны: если надо скорость, то лучше взять сишечку или cython какой-нибудь. На них для списка из 10к элементов даже O(n²) будет не сильно медленнее питонячьего O(n).

anonymous
()
Ответ на: комментарий от anonymous

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

ТС нам не сказал, надо ли ему скорость и какие у него объемы данных. Но короткий, понятный и производительный алгоритм в любом случае лучше длинного, непонятного и тормозного, не так ли? %)

Nervous ★★★★★
()
Ответ на: комментарий от anonymous

Вижу, что быстро, но на втором месте - значит, время тратится на суммирование массивов.

Если так, то самым быстрым будет такой вариант: 

def three(a, b):
  c = {}
  for i,v in a:
    c[i] = c.get(i, 0) + v
  for i,v in b:
    c[i] = c.get(i, 0) + v
  return sorted(c.items(), key=lambda x: x[1], reverse=True)

Без суммирования. Без подпрограмм. И поиск по словарю.

Novator ★★★★★
()
Последнее исправление: Novator (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
General