Ctrl →

orlov · Июнь 27, 2014 12:18:26

Привет всем. Подскажите алгоритм, пожалуйста.

Есть список вида:

список = [[имя 1, кол-во],
[имя_1, кол-во],
[имя_1, кол-во],
[имя_2, кол-во],
[имя_3, кол-во],
[имя_3, кол-во],
[имя_3, кол-во],
[имя_4, кол-во],
[имя_4, кол-во],
[имя_4, кол-во]]

Необходимо подсчитать кол-во для каждого имени, чтобы получился новый список такого формата:

новый_список = [
[имя_1, суммарное_кол-во],
[имя_2, суммарное_кол-во],
[имя_3, суммарное_кол-во],
[имя_4, суммарное_кол-во]]

Пытался сравнивать значения имен, но тогда под условие не попадают уникальные имена, вроде “имя_2”.

Свой код не выкладываю, т.к. он дико кривой.
Код не нужен, нужен только алгоритм. Заранее спасибо.

Отредактировано orlov (Июнь 27, 2014 12:19:35)

JOHN_16 · Июнь 27, 2014 13:02:53

orlov
Смотрите модуль itertools а именно groupby

_________________________________________________________________________________
полезный блог о python john16blog.blogspot.com

orlov · Июнь 27, 2014 13:07:35

JOHN_16,
когда пытался решить эту проблему, как раз подумал, что здесь не хватает GROUP BY из SQL. Значит есть такая штука) Спасибо, буду пробовать.

john123 · Июнь 27, 2014 15:30:31

Джедайский вариант (в одну строчку):

#!/usr/bin/python
# encoding: utf-8
import itertools
data = [
    ["name 1", 1],
    ["name 1", 4],
    ["name 1", 2],
    ["name 2", 10],
    ["name 3", 1],
    ["name 3", 3],
    ["name 3", 1],
    ["name 4", 7],
    ["name 4", 1],
    ["name 4", 2],
]
def group_and_sum(group_by, sum_by):
    return map(
        lambda x:
            reduce(
                lambda accum, cur: [item if i != sum_by else item + cur[sum_by] for i,item in enumerate(accum)],
                x[1]
            ),
        itertools.groupby(
            sorted(data, key=lambda x: x[group_by]),
            key=lambda x: x[group_by]
        )
    )
print group_and_sum(0, 1)

Для практического применения в таком виде не рекомендуется

По поводу itertools.groupby() - функция не будет правильно работать, если перед группировкой список не отсортировать по группируемому полю.

Вообще если хотите получить более эффективный код - не используйте groupby, а лучше напишите свою функцию.

Алгоритм примерно такой:

1. Запускаете цикл по строкам списка;
2. С первой же строки создаете словарь, в котором будут храниться пары ключ->значение. При этом ключом будет являться содержимое столбца (в Вашем случае “имя_1”), а значением - сами строки (точнее ссылки на них, в питоне по-умолчанию переменные не копируются, а передаются по ссылкам);
3. В процессе итераций цикла, сверяете ключевое поле со своим словарем. Если есть совпадение, сохраняете строку (ссылку на неё) в словарь по ключу;
4. После того, как прошлись таким образом по всему списку, запускаете еще один цикл по Вашему словарю, который уже будет содержать практически те же самые данные, что и groupby;
5. В процессе прохождения каждой группы (в словаре) суммируете нужный Вам столбец (по всей группе) и возвращаете результат в виде строки, но заменяете колонку с количеством на своё значение суммы.

Вот, примерно как-то так получается. Такой алгоритм позволит избежать ненужной сортировки.

Если хотите что-то более эффективное, можете заглянуть в исходники PostgreSQL, или почитать как вообще реализован этот функционал в различных СУБД.

Отредактировано john123 (Июнь 27, 2014 15:31:48)

Shaman · Июнь 27, 2014 15:51:39

data = [
    ["name 1", 1],
    ["name 1", 4],
    ["name 1", 2],
    ["name 2", 10],
    ["name 3", 1],
    ["name 3", 3],
    ["name 3", 1],
    ["name 4", 7],
    ["name 4", 1],
    ["name 4", 2],
]
r = {}
for n, v in data:
    r[n] = r.get(n, 0) + v
print r

sqlite с хранилищем в памяти точно не подойёт?

john123 · Июнь 27, 2014 16:02:25

Shaman

data = [
    ["name 1", 1],
    ["name 1", 4],
    ["name 1", 2],
    ["name 2", 10],
    ["name 3", 1],
    ["name 3", 3],
    ["name 3", 1],
    ["name 4", 7],
    ["name 4", 1],
    ["name 4", 2],
]
r = {}
for n, v in data:
    r[n] = r.get(n, 0) + v
print r

У Вас словарь возвращается, а не список. А во-вторых, что если в строке будет больше двух колонок?

Отредактировано john123 (Июнь 27, 2014 16:03:36)

Shaman · Июнь 27, 2014 16:05:19

john123
У Вас словарь возвращается, а не список

Беда..

print r.items()

john123
А во-вторых, что если в строке будет больше двух колонок?

Это будет совсем другая история.

4kpt_II · Июнь 27, 2014 16:06:50

Shaman
Это будет совсем другая история.

Согласен. Есть четкое задание. Нужно ему и следовать.
Плюсанул в карму. Вот это действительно джедайское решение

john123 · Июнь 27, 2014 16:23:13

4kpt_II
Согласен. Есть четкое задание. Нужно ему и следовать.

Если следовать ему четко, то нужно список возвращать, а не словарь

Отредактировано john123 (Июнь 27, 2014 16:31:15)

Budulianin · Июнь 27, 2014 18:19:42

трам пам пам, туп пиду

map(lambda x: [x[0], reduce(lambda x1, x2: ['', x1[1]+x2[1]], x[1])[1]], groupby(sorted(lst, key=itemgetter(0)), key=itemgetter(0)))

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

Уведомления

#1 Июнь 27, 2014 12:18:26

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

#2 Июнь 27, 2014 13:02:53

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

#3 Июнь 27, 2014 13:07:35

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

#4 Июнь 27, 2014 15:30:31

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

#5 Июнь 27, 2014 15:51:39

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

#6 Июнь 27, 2014 16:02:25

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

#7 Июнь 27, 2014 16:05:19

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

#8 Июнь 27, 2014 16:06:50

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

#9 Июнь 27, 2014 16:23:13

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

#10 Июнь 27, 2014 18:19:42

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

Board footer