Python эквивалент списка?

Ответ 1

Вы можете написать небольшую функцию для этого

def maplist(func, values):
    return [map(func, values[i:]) for i in xrange(len(values))]

>>> maplist(lambda a: a* 2, [1,2,3])
[[2, 4, 6], [4, 6], [6]]

[изменить]

если вы хотите применить функцию в подсписках, вы можете изменить эту функцию следующим образом:

def maplist(func, values):
    return [func(values[i:]) for i in xrange(len(values))]

>>> maplist(lambda l: list(reversed(l)), [1,2,3])
[[3, 2, 1], [3, 2], [3]]

Ответ 2

Как упоминалось в @Cybis и других, вы не можете сохранить сложность O (N) с помощью списков Python; вам нужно создать связанный список. Рискуя доказать 10-е правило Greenspun, вот такое решение:

class cons(tuple):
    __slots__=()

    def __new__(cls, car, cdr):
        return tuple.__new__(cls, (car,cdr))

    @classmethod
    def from_seq(class_, l):
        result = None
        for el in reversed(l):
            result = cons(el, result)
        return result

    @property
    def car(self): return self._getitem(0)

    @property
    def cdr(self): return self._getitem(1)

    def _getitem(self, i):
        return tuple.__getitem__(self, i)

    def __repr__(self):
        return '(%s %r)' % (self.car, self.cdr)

    def __iter__(self):
        v = self
        while v is not None:
            yield v.car
            v = v.cdr

    def __len__(self):
        return sum(1 for x in self)

    def __getitem__(self, i):
        v = self
        while i > 0:
            v = v.cdr
            i -= 1
        return v.car

def maplist(func, values):
    result = [ ]
    while values is not None:
        result.append(func(values))
        values = values.cdr
    return result

Результаты тестирования:

>>> l = cons.from_seq([1,2,3,4])
>>> print l
(1 (2 (3 (4 None))))
>>> print list(l)
[1, 2, 3, 4]
>>> print maplistr(lambda l: list(reversed(l)), cons.from_seq([1,2,3]))
[[3, 2, 1], [3, 2], [3]]

EDIT: это решение на основе генератора, которое в основном решает одну и ту же проблему без использования связанных списков:

import itertools

def mapiter(func, iter_):
    while True:
        iter_, iter2 = itertools.tee(iter_)
        iter_.next()
        yield func(iter2)

Результаты тестирования:

>>> print list(mapiter(lambda l: list(reversed(list(l))), [1,2,3]))
[[3, 2, 1], [3, 2], [3]]

Ответ 3

Eewww... Нарезка списка - это операция с линейным временем. Все решения, опубликованные до сих пор, имеют временную сложность O (n ^ 2). Lisp maplist, я считаю, имеет O (n).

Проблема заключается в том, что тип списка Python не является связанным списком. Это динамически изменяемый размер массива (т.е. Как векторный тип "С++ STL" ).

Если для вас важна линейная временная сложность, невозможно создать функцию "списка карт" над списками Python. Было бы лучше изменить свой код для работы с индексами в списке или преобразовать список в фактический связанный список (все еще операция с линейным временем, но будет иметь много накладных расходов).

Ответ 4

это работает как ваш пример (я изменил код reyjavikvi)

def maplist(func, l):
    result=[]
    for i in range(len(l)):
        result.append(func(l[i:]))
    return result

Ответ 5

Вы можете использовать вложенные списки:

>>> def p(x): return x
>>> l = range(4)[1:]
>>> [p([i:]) for i in range(len(l))]
[[1, 2, 3], [2, 3], [3]]

Что вы можете использовать для определения самого списка:

>>> def maplist(p, l): return [p([i:]) for i in range(len(l))]
>>> maplist(p, l)
[[1, 2, 3], [2, 3], [3]]

Ответ 6

O (N) реализация maplist() для связанных списков

maplist = lambda f, lst: cons(f(lst), maplist(f, cdr(lst))) if lst else lst

Смотрите вопрос Связанный список Python.

Ответ 7

У Python есть связанный тип списка, называемый deque:

from collections import deque

def maplist(f, lst):
    linked = deque(lst)
    results = []
    while linked:
        results.append(f(linked))
        linked.popleft() # assumes left is head, as in lisp

    return results

In [134]: maplist(lambda l: list(reversed(l))*2, [1,2,3])
Out[134]: [[3, 2, 1, 3, 2, 1], [3, 2, 3, 2], [3, 3]]

Линейное время, делает то же самое, будет иметь те же характеристики производительности, что и операции над списками lisp (т.е. изменение внутренних элементов будет линейным по длине изменяемого списка) и той же семантикой (т.е. если f изменяет список, он изменяет его для всех последующих исполнений f внутри этого вызова maplist, однако, поскольку это создает копию lst, f не может изменить lst, в отличие от Common Lisp).

Ответ 8

Изменение ответа Аарона:

In [8]: def maplist(p, l): return [p([x for x in l[i:]]) for i in range(len(l))]
   ...: 

In [9]: maplist(lambda x: x + x, [1,2,3])
Out[9]: [[1, 2, 3, 1, 2, 3], [2, 3, 2, 3], [3, 3]]

Ответ 9

Я думаю, что нет, но может работать следующая функция:

def maplist(func, l):
    for i in range(len(l)):
        func(l[i:])