Добавить объект в список в R в амортизированном постоянном времени, O (1)?

245

Если у меня есть список R mylist, вы можете добавить objк нему элемент следующим образом:

mylist[[length(mylist)+1]] <- obj

Но наверняка есть и более компактный способ. Когда я был новичком в R, я пытался писать lappend()так:

lappend <- function(lst, obj) {
    lst[[length(lst)+1]] <- obj
    return(lst)
}

но, конечно, это не работает из-за семантики вызова по имени R ( lstэффективно копируется при вызове, поэтому изменения lstне видны за пределами области lappend(). Я знаю, что вы можете сделать взлом среды в функции R, чтобы выйти за пределы область действия вашей функции и видоизменение вызывающей среды, но это кажется большим молотком для написания простой функции добавления.

Кто-нибудь может предложить более красивый способ сделать это? Бонусные баллы, если он работает как для векторов, так и для списков.

Ник
источник
5
R обладает неизменяемыми характеристиками данных, которые часто встречаются в функциональных языках, я не хочу это говорить, но я думаю, что вам просто придется иметь дело с этим. У него есть свои плюсы и минусы
Дан
Когда вы говорите «вызов по имени», вы действительно имеете в виду «вызов по значению», верно?
Кен Уильямс
7
Нет, это определенно не вызов по значению, иначе это не будет проблемой. R фактически использует вызов по необходимости ( en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need ).
Ник
4
Хорошей идеей является предварительное выделение вашего вектора / списка: N = 100 mylist = vector ('list', N) для (i in 1: N) {#mylist [[i]] = ...} Избегать растущего объекты в Р.
Фернандо
Я случайно нашел ответ здесь, stackoverflow.com/questions/17046336/… Так сложно реализовать такой простой алгоритм!
КХ Ким

Ответы:

255

Если это список строк, просто используйте c()функцию:

R> LL <- list(a="tom", b="dick")
R> c(LL, c="harry")
$a
[1] "tom"

$b
[1] "dick"

$c
[1] "harry"

R> class(LL)
[1] "list"
R> 

Это работает и на векторы, так что я получу бонусные баллы?

Изменить (2015-февраль-01): эта публикация выходит в свой пятый день рождения. Некоторые добрые читатели повторяют любые недостатки с ним, поэтому непременно посмотрите некоторые комментарии ниже. Одно предложение для listтипов:

newlist <- list(oldlist, list(someobj))

В целом, R-типы могут затруднить использование одной и только одной идиомы для всех типов и применений.

Дирк Эддельбюттель
источник
19
Это не добавляет ... это объединяет. LLвсе равно будет иметь два элемента после того, C(LL, c="harry")как называется.
Ник
27
Просто переназначить LL: LL <- c(LL, c="harry").
Дирк Эддельбюттель
51
Это работает только со строками. Если a, b и c являются целочисленными векторами, поведение совершенно иное.
Александр Радемейкер
8
@Dirk: у вас парни вложены не так, как я. Мой вызов c()имеет 2 аргумента: список, к которому я пытаюсь добавить, а именно list(a=3, b=c(4, 5)), элемент, который я пытаюсь добавить, а именно c=c(6, 7). Если вы воспользуетесь моим подходом, вы увидите, что 2 элемента списка добавляются ( 6и 7с именами c1и c2) вместо одного 2-элементного вектора, названного так, cкак это явно предусмотрено!
j_random_hacker
7
Так вывод mylist <- list(mylist, list(obj))? Если да, было бы неплохо изменить ответ
Мэтью
96

ОП (в обновленной редакции вопроса от апреля 2012 г.) заинтересован в том, чтобы узнать, есть ли способ добавить в список за амортизированное постоянное время, как, например, можно сделать с помощью vector<>контейнера C ++ . Наилучший ответ (s?) Здесь пока показывает только относительное время выполнения для различных решений, заданных для задачи фиксированного размера, но не затрагивает напрямую алгоритмическую эффективность различных решений . В комментариях под многими ответами обсуждается алгоритмическая эффективность некоторых решений, но в каждом конкретном случае (по состоянию на апрель 2015 года) они приходят к неверному выводу.

Алгоритмическая эффективность учитывает характеристики роста во времени (время выполнения) или в пространстве (объем потребляемой памяти) по мере увеличения размера проблемы . Выполнение теста производительности для различных решений с учетом проблемы фиксированного размера не учитывает скорость роста различных решений. OP заинтересован в том, чтобы узнать, есть ли способ добавить объекты в список R за «постоянное время амортизации». Что это значит? Чтобы объяснить, сначала позвольте мне описать «постоянное время»:

  • Постоянный или O (1) рост:

    Если время, необходимое для выполнения данной задачи, остается таким же, как размер задачи удваивается , то мы говорим, что алгоритм имеет постоянное время рост во , или, как указано в записи «Big O», демонстрирует O (1) увеличение во времени. Когда OP говорит «амортизированное» постоянное время, он просто означает «в долгосрочной перспективе» ... то есть, если выполнение одной операции иногда занимает намного больше времени, чем обычно (например, если предварительно выделенный буфер исчерпан и иногда требует изменения размера до большего размер буфера), пока долгосрочная средняя производительность постоянна, мы все равно будем называть это O (1).

    Для сравнения я также опишу «линейное время» и «квадратичное время»:

  • Линейный или O (n) рост:

    Если время, необходимое для выполнения данной задачи, удваивается, поскольку размер задачи удваивается , то мы говорим, что алгоритм демонстрирует линейное время , или O (n) рост.

  • Квадратичный или O (n 2 ) рост:

    Если время, требуемое для выполнения данной задачи, увеличивается на квадрат размера задачи , мы говорим, что алгоритм показывает квадратичное время или рост O (n 2 ) .

Есть много других классов эффективности алгоритмов; Я перехожу к статье Википедии для дальнейшего обсуждения.

Я благодарю @CronAcronis за его ответ, так как я новичок в R, и было приятно иметь полностью сконструированный блок кода для анализа производительности различных решений, представленных на этой странице. Я заимствую его код для моего анализа, который я дублирую (обернутый в функцию) ниже:

library(microbenchmark)
### Using environment as a container
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(substitute(lab))]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj} 
runBenchmark <- function(n) {
    microbenchmark(times = 5,  
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = { 
            a <- list(0)    
            for(i in 1:n) {a <- append(a, i)} 
            a
        },
        env_as_container_ = {
            listptr <- new.env(parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)} 
            listptr
        }   
    )
}

Результаты, опубликованные @CronAcronis, определенно свидетельствуют о том, что a <- list(a, list(i))метод является самым быстрым, по крайней мере, для размера задачи 10000, но результаты для одного размера проблемы не учитывают рост решения. Для этого нам нужно запустить как минимум два теста профилирования с разными размерами проблем:

> runBenchmark(2e+3)
Unit: microseconds
              expr       min        lq      mean    median       uq       max neval
    env_with_list_  8712.146  9138.250 10185.533 10257.678 10761.33 12058.264     5
                c_ 13407.657 13413.739 13620.976 13605.696 13790.05 13887.738     5
             list_   854.110   913.407  1064.463   914.167  1301.50  1339.132     5
          by_index 11656.866 11705.140 12182.104 11997.446 12741.70 12809.363     5
           append_ 15986.712 16817.635 17409.391 17458.502 17480.55 19303.560     5
 env_as_container_ 19777.559 20401.702 20589.856 20606.961 20939.56 21223.502     5
> runBenchmark(2e+4)
Unit: milliseconds
              expr         min         lq        mean    median          uq         max neval
    env_with_list_  534.955014  550.57150  550.329366  553.5288  553.955246  558.636313     5
                c_ 1448.014870 1536.78905 1527.104276 1545.6449 1546.462877 1558.609706     5
             list_    8.746356    8.79615    9.162577    8.8315    9.601226    9.837655     5
          by_index  953.989076 1038.47864 1037.859367 1064.3942 1065.291678 1067.143200     5
           append_ 1634.151839 1682.94746 1681.948374 1689.7598 1696.198890 1706.683874     5
 env_as_container_  204.134468  205.35348  208.011525  206.4490  208.279580  215.841129     5
> 

Прежде всего, несколько слов о значениях min / lq / mean / median / uq / max: поскольку мы выполняем одну и ту же задачу для каждого из 5 циклов, в идеальном мире можно ожидать, что для этого потребуется точно то же самое количество времени для каждого запуска. Но первый запуск, как правило, смещается в сторону более длительного времени из-за того, что код, который мы тестируем, еще не загружен в кэш процессора. После первого запуска мы ожидаем, что время будет достаточно согласованным, но иногда наш код может быть удален из кэша из-за прерываний по таймеру или других аппаратных прерываний, которые не связаны с кодом, который мы тестируем. Протестировав фрагменты кода 5 раз, мы позволяем загружать код в кэш во время первого запуска, а затем даем каждому фрагменту 4 шансы на выполнение до завершения без вмешательства внешних событий. По этой причине,

Обратите внимание, что я решил сначала запустить с размером проблемы 2000, а затем 20000, поэтому размер моей проблемы увеличился в 10 раз с первого запуска до второго.

Производительность listрешения: O (1) (постоянное время)

Давайте сначала посмотрим на рост listрешения, так как сразу можем сказать, что это самое быстрое решение в обоих прогонах профилирования: в первом прогоне потребовалось 854 микросекунды (0,854 миллисекунды ) для выполнения 2000 задач «добавления». Во втором запуске потребовалось 8,746 миллисекунд для выполнения 20000 задач «добавления». Наивный наблюдатель сказал бы: «Ах, listрешение демонстрирует рост O (n), поскольку с ростом размера задачи в десять раз увеличивается и время, необходимое для выполнения теста». Проблема этого анализа заключается в том, что операционному агенту требуется скорость роста вставки одного объекта, которая , а не общую проблему. Зная это, ясно, чтоlist Решение обеспечивает именно то, что хочет OP: метод добавления объектов в список за O (1).

Производительность других решений

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

Похоже, что большинство других решений имеют производительность O (n). Например, by_indexрешение, очень популярное решение, основанное на частоте, с которой я нахожу его в других сообщениях SO, заняло 11,6 миллисекунды, чтобы добавить 2000 объектов, и 953 миллисекунды, чтобы добавить в десять раз больше объектов. Общее время проблемы выросло в 100 раз, поэтому наивный наблюдатель мог бы сказать: «Ах, by_indexрешение демонстрирует рост O (n 2 ), поскольку, поскольку размер проблемы увеличился в десять раз, время, необходимое для выполнения теста, увеличилось. в 100 раз. "Как и прежде, этот анализ имеет недостатки, поскольку OP заинтересован в росте вставки одного объекта. Если мы поделим общее увеличение времени на увеличение размера задачи, мы обнаружим, что увеличение времени добавления объектов увеличилось только в 10 раз, а не в 100 раз, что соответствует росту размера проблемы, поэтому by_indexрешение является O (п). Нет перечисленных решений, которые демонстрируют рост O (n 2 ) для добавления одного объекта.

phonetagger
источник
1
Читателю: Пожалуйста, прочитайте ответ JanKanis, который очень практично дополняет мои выводы, приведенные выше, и немного
углубляется
4
Не уверен, что опция списка реализует то, что требуется:> длина (c (c (c (список (1)), список (2)), список (3))) [1] 3> длина (список (список (список) (list (1)), list (2)), list (3))) [1] 2. Больше похоже на вложенные списки.
Picarus
@Picarus - я думаю, ты прав. Я больше не работаю с R, но, к счастью, JanKanis опубликовал ответ с гораздо более полезным решением O (1) и отмечает проблему, которую вы определили. Я уверен, что JanKanis оценят ваше мнение.
телефонный звонок
@phonetagger, вы должны отредактировать свой ответ. Не все будут читать все ответы.
Picarus
«Ни один ответ не ответил на реальный вопрос» -> Проблема в том, что исходный вопрос не был о сложности алгоритма, взгляните на редакции вопроса. ФП сначала спросил, как добавить элемент в список, а через несколько месяцев он изменил вопрос.
Карлос Синелли
41

В других ответах только listподход приводит к добавлению O (1), но это приводит к глубоко вложенной структуре списка, а не к простому единому списку. Я использовал приведенные ниже структуры данных, они поддерживают O (1) (амортизированные) добавления и позволяют преобразовать результат обратно в простой список.

expandingList <- function(capacity = 10) {
    buffer <- vector('list', capacity)
    length <- 0

    methods <- list()

    methods$double.size <- function() {
        buffer <<- c(buffer, vector('list', capacity))
        capacity <<- capacity * 2
    }

    methods$add <- function(val) {
        if(length == capacity) {
            methods$double.size()
        }

        length <<- length + 1
        buffer[[length]] <<- val
    }

    methods$as.list <- function() {
        b <- buffer[0:length]
        return(b)
    }

    methods
}

и

linkedList <- function() {
    head <- list(0)
    length <- 0

    methods <- list()

    methods$add <- function(val) {
        length <<- length + 1
        head <<- list(head, val)
    }

    methods$as.list <- function() {
        b <- vector('list', length)
        h <- head
        for(i in length:1) {
            b[[i]] <- head[[2]]
            head <- head[[1]]
        }
        return(b)
    }
    methods
}

Используйте их следующим образом:

> l <- expandingList()
> l$add("hello")
> l$add("world")
> l$add(101)
> l$as.list()
[[1]]
[1] "hello"

[[2]]
[1] "world"

[[3]]
[1] 101

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

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

namedExpandingList <- function(capacity = 10) {
    buffer <- vector('list', capacity)
    names <- character(capacity)
    length <- 0

    methods <- list()

    methods$double.size <- function() {
        buffer <<- c(buffer, vector('list', capacity))
        names <<- c(names, character(capacity))
        capacity <<- capacity * 2
    }

    methods$add <- function(name, val) {
        if(length == capacity) {
            methods$double.size()
        }

        length <<- length + 1
        buffer[[length]] <<- val
        names[length] <<- name
    }

    methods$as.list <- function() {
        b <- buffer[0:length]
        names(b) <- names[0:length]
        return(b)
    }

    methods
}

Ориентиры

Сравнение производительности с использованием кода @ phonetagger (который основан на коде @Cron Arconis). Я также добавил better_env_as_containerи изменил env_as_container_немного. Оригинал env_as_container_был сломан и на самом деле не хранит все цифры.

library(microbenchmark)
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(lab)]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj} 
env2list <- function(env, len) {
    l <- vector('list', len)
    for (i in 1:len) {
        l[[i]] <- env[[as.character(i)]]
    }
    l
}
envl2list <- function(env, len) {
    l <- vector('list', len)
    for (i in 1:len) {
        l[[i]] <- env[[paste(as.character(i), 'L', sep='')]]
    }
    l
}
runBenchmark <- function(n) {
    microbenchmark(times = 5,  
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = { 
            a <- list(0)    
            for(i in 1:n) {a <- append(a, i)} 
            a
        },
        env_as_container_ = {
            listptr <- new.env(hash=TRUE, parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)} 
            envl2list(listptr, n)
        },
        better_env_as_container = {
            env <- new.env(hash=TRUE, parent=globalenv())
            for(i in 1:n) env[[as.character(i)]] <- i
            env2list(env, n)
        },
        linkedList = {
            a <- linkedList()
            for(i in 1:n) { a$add(i) }
            a$as.list()
        },
        inlineLinkedList = {
            a <- list()
            for(i in 1:n) { a <- list(a, i) }
            b <- vector('list', n)
            head <- a
            for(i in n:1) {
                b[[i]] <- head[[2]]
                head <- head[[1]]
            }                
        },
        expandingList = {
            a <- expandingList()
            for(i in 1:n) { a$add(i) }
            a$as.list()
        },
        inlineExpandingList = {
            l <- vector('list', 10)
            cap <- 10
            len <- 0
            for(i in 1:n) {
                if(len == cap) {
                    l <- c(l, vector('list', cap))
                    cap <- cap*2
                }
                len <- len + 1
                l[[len]] <- i
            }
            l[1:len]
        }
    )
}

# We need to repeatedly add an element to a list. With normal list concatenation
# or element setting this would lead to a large number of memory copies and a
# quadratic runtime. To prevent that, this function implements a bare bones
# expanding array, in which list appends are (amortized) constant time.
    expandingList <- function(capacity = 10) {
        buffer <- vector('list', capacity)
        length <- 0

        methods <- list()

        methods$double.size <- function() {
            buffer <<- c(buffer, vector('list', capacity))
            capacity <<- capacity * 2
        }

        methods$add <- function(val) {
            if(length == capacity) {
                methods$double.size()
            }

            length <<- length + 1
            buffer[[length]] <<- val
        }

        methods$as.list <- function() {
            b <- buffer[0:length]
            return(b)
        }

        methods
    }

    linkedList <- function() {
        head <- list(0)
        length <- 0

        methods <- list()

        methods$add <- function(val) {
            length <<- length + 1
            head <<- list(head, val)
        }

        methods$as.list <- function() {
            b <- vector('list', length)
            h <- head
            for(i in length:1) {
                b[[i]] <- head[[2]]
                head <- head[[1]]
            }
            return(b)
        }

        methods
    }

# We need to repeatedly add an element to a list. With normal list concatenation
# or element setting this would lead to a large number of memory copies and a
# quadratic runtime. To prevent that, this function implements a bare bones
# expanding array, in which list appends are (amortized) constant time.
    namedExpandingList <- function(capacity = 10) {
        buffer <- vector('list', capacity)
        names <- character(capacity)
        length <- 0

        methods <- list()

        methods$double.size <- function() {
            buffer <<- c(buffer, vector('list', capacity))
            names <<- c(names, character(capacity))
            capacity <<- capacity * 2
        }

        methods$add <- function(name, val) {
            if(length == capacity) {
                methods$double.size()
            }

            length <<- length + 1
            buffer[[length]] <<- val
            names[length] <<- name
        }

        methods$as.list <- function() {
            b <- buffer[0:length]
            names(b) <- names[0:length]
            return(b)
        }

        methods
    }

результат:

> runBenchmark(1000)
Unit: microseconds
                    expr       min        lq      mean    median        uq       max neval
          env_with_list_  3128.291  3161.675  4466.726  3361.837  3362.885  9318.943     5
                      c_  3308.130  3465.830  6687.985  8578.913  8627.802  9459.252     5
                   list_   329.508   343.615   389.724   370.504   449.494   455.499     5
                by_index  3076.679  3256.588  5480.571  3395.919  8209.738  9463.931     5
                 append_  4292.321  4562.184  7911.882 10156.957 10202.773 10345.177     5
       env_as_container_ 24471.511 24795.849 25541.103 25486.362 26440.591 26511.200     5
 better_env_as_container  7671.338  7986.597  8118.163  8153.726  8335.659  8443.493     5
              linkedList  1700.754  1755.439  1829.442  1804.746  1898.752  1987.518     5
        inlineLinkedList  1109.764  1115.352  1163.751  1115.631  1206.843  1271.166     5
           expandingList  1422.440  1439.970  1486.288  1519.728  1524.268  1525.036     5
     inlineExpandingList   942.916   973.366  1002.461  1012.197  1017.784  1066.044     5
> runBenchmark(10000)
Unit: milliseconds
                    expr        min         lq       mean     median         uq        max neval
          env_with_list_ 357.760419 360.277117 433.810432 411.144799 479.090688 560.779139     5
                      c_ 685.477809 734.055635 761.689936 745.957553 778.330873 864.627811     5
                   list_   3.257356   3.454166   3.505653   3.524216   3.551454   3.741071     5
                by_index 445.977967 454.321797 515.453906 483.313516 560.374763 633.281485     5
                 append_ 610.777866 629.547539 681.145751 640.936898 760.570326 763.896124     5
       env_as_container_ 281.025606 290.028380 303.885130 308.594676 314.972570 324.804419     5
 better_env_as_container  83.944855  86.927458  90.098644  91.335853  92.459026  95.826030     5
              linkedList  19.612576  24.032285  24.229808  25.461429  25.819151  26.223597     5
        inlineLinkedList  11.126970  11.768524  12.216284  12.063529  12.392199  13.730200     5
           expandingList  14.735483  15.854536  15.764204  16.073485  16.075789  16.081726     5
     inlineExpandingList  10.618393  11.179351  13.275107  12.391780  14.747914  17.438096     5
> runBenchmark(20000)
Unit: milliseconds
                    expr         min          lq       mean      median          uq         max neval
          env_with_list_ 1723.899913 1915.003237 1921.23955 1938.734718 1951.649113 2076.910767     5
                      c_ 2759.769353 2768.992334 2810.40023 2820.129738 2832.350269 2870.759474     5
                   list_    6.112919    6.399964    6.63974    6.453252    6.910916    7.321647     5
                by_index 2163.585192 2194.892470 2292.61011 2209.889015 2436.620081 2458.063801     5
                 append_ 2832.504964 2872.559609 2983.17666 2992.634568 3004.625953 3213.558197     5
       env_as_container_  573.386166  588.448990  602.48829  597.645221  610.048314  642.912752     5
 better_env_as_container  154.180531  175.254307  180.26689  177.027204  188.642219  206.230191     5
              linkedList   38.401105   47.514506   46.61419   47.525192   48.677209   50.952958     5
        inlineLinkedList   25.172429   26.326681   32.33312   34.403442   34.469930   41.293126     5
           expandingList   30.776072   30.970438   34.45491   31.752790   38.062728   40.712542     5
     inlineExpandingList   21.309278   22.709159   24.64656   24.290694   25.764816   29.158849     5

Я добавил linkedListи expandingListи встроенную версию обоих. Это inlinedLinkedListв основном копия list_, но она также преобразует вложенную структуру обратно в простой список. Кроме того, разница между встроенной и не встроенной версиями связана с накладными расходами вызовов функций.

Все варианты expandingListи linkedListпоказывают O (1) добавляют производительность, с эталонным временем масштабирования линейно с количеством добавленных элементов. linkedListмедленнее, чем expandingList, и накладные расходы вызова функции также видны. Так что если вам действительно нужна вся скорость, которую вы можете получить (и хотите придерживаться кода R), используйте встроенную версию expandingList.

Я также взглянул на реализацию R в C, и оба подхода должны быть O (1) для любого размера до тех пор, пока у вас не закончится память.

Я также изменил env_as_container_, оригинальная версия будет хранить каждый элемент с индексом «i», перезаписывая ранее добавленный элемент. better_env_as_containerЯ добавил очень похож , env_as_container_но без deparseвещей. Оба демонстрируют производительность O (1), но их издержки немного больше, чем у связанных / расширяющихся списков.

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

В реализации CR накладные расходы составляют 4 слова и 2 дюйма на выделенный объект. linkedListПодход выделяет один список длины два в Append, в общей сложности (4 * 8 + 4 + 4 + 2 * 8 =) 56 байт на приложенном пункта на 64-разрядных компьютерах ( за исключением распределения памяти накладных, так что, вероятно ближе к 64 байт). expandingListПодход использует одно слово за приложенный пункт, плюс копию , когда удвоение длины вектора, поэтому общее использование памяти до 16 байт на элемент. Поскольку память состоит из одного или двух объектов, накладные расходы для каждого объекта незначительны. Я не изучал envиспользование памяти, но думаю, что это будет ближе к linkedList.

JanKanis
источник
Какой смысл сохранять опцию списка, если она не решает проблему, которую мы пытаемся решить?
Picarus
1
@Picarus Я не уверен, что ты имеешь в виду. Почему я сохранил это в тесте? По сравнению с другими вариантами. list_Вариант быстрее и может быть полезно , если вам не нужно преобразовать в обычный список, то есть , если вы используете результат в виде стека.
JanKanis
@Gabor Csardi опубликовал более быстрый способ преобразования сред обратно в списки по другому вопросу на stackoverflow.com/a/29482211/264177. Я оценил это и в моей системе. Это примерно в два раза быстрее better_env_as_container, но все же медленнее, чем связанный список и расширяемый список.
JanKanis
Глубоко вложенные (n = 99999) списки кажутся управляемыми и приемлемыми для определенных приложений: кто-нибудь хочет сравнить nestoR ? (Я все еще немного новичок в том, environmentчто я использовал для nestoR.) Моим узким местом почти всегда является человеческое время, потраченное на кодирование и анализ данных, но я ценю критерии, которые я нашел в этом посте. Что касается нехватки памяти, я бы не возражал, если бы в моих приложениях использовалось около килобайта на узел. Я держусь за большие массивы и т. Д.
Ана Нимбус
17

В Лиспе мы сделали это так:

> l <- c(1)
> l <- c(2, l)
> l <- c(3, l)
> l <- rev(l)
> l
[1] 1 2 3

хотя это были «минусы», а не просто «с». Если вам нужно начать со списка empy, используйте l <- NULL.

Арсений
источник
3
Превосходно! Все остальные решения возвращают какой-то странный список списков.
metakermit
4
В Лиспе добавление к списку является операцией O (1), а добавление выполняется в O (n), @flies. Необходимость реверсии перевешивается увеличением производительности. Это не относится к R. Даже в pairlist, который обычно больше всего напоминает списки List.
Палек
@Palec "Это не так в R" - я не уверен, какое "это" вы имеете в виду. Вы говорите, что добавление не O (1), или это не O (n)?
летает
1
Я говорю, что если бы вы программировали на Лиспе, ваш подход был бы неэффективным, @flies. Это замечание должно было объяснить, почему ответ написан таким, какой он есть. В R два подхода на равных с точки зрения производительности, AFAIK. Но сейчас я не уверен насчет амортизированной сложности. Не касался R с того времени, когда был написан мой предыдущий комментарий.
Палек
3
В R этот подход будет O (n). В c()Функции копирует свои аргументы в новый векторе / список и возвращает это.
JanKanis
6

Вы хотите что-то подобное, может быть?

> push <- function(l, x) {
   lst <- get(l, parent.frame())
   lst[length(lst)+1] <- x
   assign(l, lst, envir=parent.frame())
 }
> a <- list(1,2)
> push('a', 6)
> a
[[1]]
[1] 1

[[2]]
[1] 2

[[3]]
[1] 6

Это не очень вежливая функция (присваивать это parent.frame()довольно грубо), но IIUYC - это то, что вы просите.

Кен Уильямс
источник
6

Я сделал небольшое сравнение методов, упомянутых здесь.

n = 1e+4
library(microbenchmark)
### Using environment as a container
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(substitute(lab))]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj} 

microbenchmark(times = 5,  
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = { 
            a <- list(0)    
            for(i in 1:n) {a <- append(a, i)} 
            a
        },
        env_as_container_ = {
            listptr <- new.env(parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)} 
            listptr
        }   
)

Полученные результаты:

Unit: milliseconds
              expr       min        lq       mean    median        uq       max neval cld
    env_with_list_  188.9023  198.7560  224.57632  223.2520  229.3854  282.5859     5  a 
                c_ 1275.3424 1869.1064 2022.20984 2191.7745 2283.1199 2491.7060     5   b
             list_   17.4916   18.1142   22.56752   19.8546   20.8191   36.5581     5  a 
          by_index  445.2970  479.9670  540.20398  576.9037  591.2366  607.6156     5  a 
           append_ 1140.8975 1316.3031 1794.10472 1620.1212 1855.3602 3037.8416     5   b
 env_as_container_  355.9655  360.1738  399.69186  376.8588  391.7945  513.6667     5  a 
Крон Мердек
источник
Это отличная информация: никогда бы не догадался, что list = listвыиграл бы не только на 1 - 2 порядка, либо на величину!
Джавадба
5

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

push <- function(l, x) {
  assign(l, append(eval(as.name(l)), x), envir=parent.frame())
}

так:

> a <- list(1,2)
> a
[[1]]
[1] 1

[[2]]
[1] 2

> push("a", 3)
> a
[[1]]
[1] 1

[[2]]
[1] 2

[[3]]
[1] 3

> 

или для дополнительного кредита:

> v <- vector()
> push("v", 1)
> v
[1] 1
> push("v", 2)
> v
[1] 1 2
> 
Айман
источник
1
Это в основном то поведение, которое мне нужно, однако оно все еще вызывает добавление внутри, что приводит к производительности O (n ^ 2).
Ник
4

Не уверен, почему вы не думаете, что ваш первый метод не сработает. У вас есть ошибка в функции lappend: длина (список) должна быть длиной (lst). Это работает нормально и возвращает список с добавленным объектом.

Павел
источник
3
Ты абсолютно прав. В коде была ошибка, и я ее исправил. Я проверил то, lappend()что предоставил, и похоже, что оно работает так же хорошо, как c () и append (), причем все они демонстрируют поведение O (n ^ 2).
Ник
2

Я думаю, что вы на самом деле хотите передать по ссылке (указателю) на функцию - создать новую среду (которая передается по ссылке на функции) с добавленным в нее списком:

listptr=new.env(parent=globalenv())
listptr$list=mylist

#Then the function is modified as:
lPtrAppend <- function(lstptr, obj) {
    lstptr$list[[length(lstptr$list)+1]] <- obj
}

Теперь вы только изменяете существующий список (не создавая новый)

DavidM
источник
1
Похоже, это снова имеет квадратичную сложность по времени. Проблема, очевидно, в том, что изменение размера списка / вектора не реализовано так, как это обычно делается в большинстве языков.
Eold
Да, похоже, что добавление в конце очень медленное - вероятно, списки b / c являются рекурсивными, и R лучше всего подходит для векторных операций, а не операций типа цикла. Это гораздо лучше сделать:
DavidM
1
system.time (для (i в c (1: 10000) mylist [i] = i) (несколько секунд) или, что еще лучше, сделать все за одну операцию: system.time (mylist = list (1: 100000)) (менее чем за одну секунду), то изменения , что предопределенные список с для цикла также будет быстрее.
DavidM
2

Это простой способ добавить элементы в список R:

# create an empty list:
small_list = list()

# now put some objects in it:
small_list$k1 = "v1"
small_list$k2 = "v2"
small_list$k3 = 1:10

# retrieve them the same way:
small_list$k1
# returns "v1"

# "index" notation works as well:
small_list["k2"]

Или программно:

kx = paste(LETTERS[1:5], 1:5, sep="")
vx = runif(5)
lx = list()
cn = 1

for (itm in kx) { lx[itm] = vx[cn]; cn = cn + 1 }

print(length(lx))
# returns 5
Дуг
источник
Это на самом деле не добавляется. Что если у меня есть 100 объектов, и я хочу добавить их в список программно? У append()функции R есть функция, но на самом деле это конкатенационная функция, которая работает только с векторами.
Ник
append()работает с векторами и списками, и это истинное дополнение (которое в основном совпадает с конкатенацией, поэтому я не вижу, в чем ваша проблема)
hadley
8
Функция добавления должна изменять существующий объект, а не создавать новый. Истинное дополнение не будет иметь поведение O (N ^ 2).
Ник
2

на самом деле есть тонкость с c()функцией. Если вы делаете:

x <- list()
x <- c(x,2)
x = c(x,"foo")

вы получите, как и ожидалось:

[[1]]
[1]

[[2]]
[1] "foo"

но если вы добавите матрицу с x <- c(x, matrix(5,2,2), ваш список будет иметь еще 4 элемента значения 5! Вы бы лучше сделать:

x <- c(x, list(matrix(5,2,2))

Это работает для любого другого объекта, и вы получите, как и ожидалось:

[[1]]
[1]

[[2]]
[1] "foo"

[[3]]
     [,1] [,2]
[1,]    5    5
[2,]    5    5

Наконец, ваша функция становится:

push <- function(l, ...) c(l, list(...))

и это работает для любого типа объекта. Вы можете быть умнее и делать:

push_back <- function(l, ...) c(l, list(...))
push_front <- function(l, ...) c(list(...), l)
Дэвид Белло
источник
1

Есть также list.appendиз rlist( ссылка на документацию )

require(rlist)
LL <- list(a="Tom", b="Dick")
list.append(LL,d="Pam",f=c("Joe","Ann"))

Это очень просто и эффективно.

скан
источник
1
не похож на R для меня ... Python?
JD Long
1
Я сделал правку и попробовал: она чертовски медленная. Лучше использовать c()или list-метод. Оба намного быстрее.
5
Глядя на код rlist::list.append(), это по сути обертка вокруг base::c().
Нбенн
1

Для проверки я запустил тестовый код, предоставленный @Cron. Есть одно существенное отличие (в дополнение к более быстрой работе на новом процессоре i7): by_indexтеперь он работает почти так же хорошо, как list_:

Unit: milliseconds
              expr        min         lq       mean     median         uq
    env_with_list_ 167.882406 175.969269 185.966143 181.817187 185.933887
                c_ 485.524870 501.049836 516.781689 518.637468 537.355953
             list_   6.155772   6.258487   6.544207   6.269045   6.290925
          by_index   9.290577   9.630283   9.881103   9.672359  10.219533
           append_ 505.046634 543.319857 542.112303 551.001787 553.030110
 env_as_container_ 153.297375 154.880337 156.198009 156.068736 156.800135

Для справки приведем код теста, дословно скопированный из ответа @ Cron (на тот случай, если он позже изменит содержание):

n = 1e+4
library(microbenchmark)
### Using environment as a container
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(substitute(lab))]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj}

microbenchmark(times = 5,
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = {
            a <- list(0)
            for(i in 1:n) {a <- append(a, i)}
            a
        },
        env_as_container_ = {
            listptr <- new.env(parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)}
            listptr
        }
)
javadba
источник
0
> LL<-list(1:4)

> LL

[[1]]
[1] 1 2 3 4

> LL<-list(c(unlist(LL),5:9))

> LL

[[1]]
 [1] 1 2 3 4 5 6 7 8 9
Су Ли
источник
2
Я не думаю, что это тот тип добавления, который искал ОП.
Джоран
Это не добавление элементов в список. Здесь вы увеличиваете элементы целочисленного вектора, который является единственным элементом списка. В списке есть только один элемент - целочисленный вектор.
Серхио
0

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

a_list<-list()
for(i in 1:3){
  a_list<-list(unlist(list(unlist(a_list,recursive = FALSE),list(rnorm(2))),recursive = FALSE))
}
a_list

[[1]]
[[1]][[1]]
[1] -0.8098202  1.1035517

[[1]][[2]]
[1] 0.6804520 0.4664394

[[1]][[3]]
[1] 0.15592354 0.07424637
xappppp
источник
Я хочу добавить, что он дает двухуровневый вложенный список, но это все. Способ работы списков и списков рассылки мне не очень понятен, но это результат тестирования кода
xappppp
-1

mylist<-list(1,2,3) mylist<-c(mylist,list(5))

Таким образом, мы можем легко добавить элемент / объект, используя приведенный выше код

Сараванан Саминатан
источник