AK
заочередить надо пару милионов элементов
не стоит,
это же простая очередь
из двух списков
Size: a a a
2020 March 19
AK
Надо поискать варианты..
AK
не стоит,
это же простая очередь
из двух списков
это же простая очередь
из двух списков
Не стоит использовать queue или не стоит использовать что то другое? :)
AK
дока говорит O(1) сложность на основные операции
AK
то что нужно
СИ
то что нужно
ты не уточнил скорость чего тебя интересует
AK
Да всего, в том числе расходы на хранение ее в стейте
ММ
так это на вставку в очередь наверное и на извлечение
AK
Да, FIFO
VS
дело вкуса, конечно,
но это классическая очередь Окасаки из двух списков,
если не смущает, что периодически будет делаться
реверс списка на 500 тыс элементов, то почему бы и нет
но это классическая очередь Окасаки из двух списков,
если не смущает, что периодически будет делаться
реверс списка на 500 тыс элементов, то почему бы и нет
ММ
а все, что между запросто может быть хоть квадратичным, хоть факториальным
ММ
дело вкуса, конечно,
но это классическая очередь Окасаки из двух списков,
если не смущает, что периодически будет делаться
реверс списка на 500 тыс элементов, то почему бы и нет
но это классическая очередь Окасаки из двух списков,
если не смущает, что периодически будет делаться
реверс списка на 500 тыс элементов, то почему бы и нет
и вот этот реверс будет саааавсем не О(1)
AK
дело вкуса, конечно,
но это классическая очередь Окасаки из двух списков,
если не смущает, что периодически будет делаться
реверс списка на 500 тыс элементов, то почему бы и нет
но это классическая очередь Окасаки из двух списков,
если не смущает, что периодически будет делаться
реверс списка на 500 тыс элементов, то почему бы и нет
Нет.. это смущает
AK
Но судя по доке все окей, реверсы только на _r функции. А альтернативы какие есть?
LL
кто нибудь работал с queue структурой, которая из одноименного модуля?
Как она по скорости? Или что то другое надо использовать для FIFO
Как она по скорости? Или что то другое надо использовать для FIFO
Нормально работает.
Суть в том, что не совсем стабильно. Если долго класть в очередь, а потом вытащить два элемента, то это будет работать долго, потому что будет разворачиваться список положенных элементов.
Суть в том, что не совсем стабильно. Если долго класть в очередь, а потом вытащить два элемента, то это будет работать долго, потому что будет разворачиваться список положенных элементов.
LL
Это классическая реализация персистентой очереди, только первый элемент (по порядку очереди) всегда лежит во втором стеке
AK
ок, спасибо, большое крамолы похоже нет, попробую
SP
У нее амортизированная сложность O(1). Но да, время от времени будет случаться llists:reverse для всей (половины?) очереди. Т.е. latency spike и много мусора в heap от reverse
СИ
У нее амортизированная сложность O(1). Но да, время от времени будет случаться llists:reverse для всей (половины?) очереди. Т.е. latency spike и много мусора в heap от reverse
а мусор (фрагментация?) от reverse почему? перелинковка же