Что делать с жунами , Что делать с жунами

[korvin]

Вот с интрузивным списком совсем другой разговор:

Benchmark                     (itemsToAdd)               (type)  Mode  Cnt      Score       Error  Units
CollectionsBenchmark.addMany          1000           LinkedList  avgt   15     14.542 ±    17.000  us/op
CollectionsBenchmark.addMany          1000            ArrayList  avgt   15      3.680 ±     0.089  us/op
CollectionsBenchmark.addMany          1000       OpenLinkedList  avgt   15      4.068 ±     0.175  us/op
CollectionsBenchmark.addMany          1000  IntrusiveLinkedList  avgt   15      2.561 ±     0.027  us/op
 
CollectionsBenchmark.addMany        100000           LinkedList  avgt   15    471.286 ±    13.920  us/op
CollectionsBenchmark.addMany        100000            ArrayList  avgt   15    362.478 ±     9.120  us/op
CollectionsBenchmark.addMany        100000       OpenLinkedList  avgt   15    443.950 ±    11.291  us/op
CollectionsBenchmark.addMany        100000  IntrusiveLinkedList  avgt   15    255.955 ±     3.964  us/op
 
CollectionsBenchmark.addMany      10000000           LinkedList  avgt   15  61587.330 ± 22176.828  us/op
CollectionsBenchmark.addMany      10000000            ArrayList  avgt   15  56342.958 ±  2432.139  us/op
CollectionsBenchmark.addMany      10000000       OpenLinkedList  avgt   15  73251.613 ± 21086.066  us/op
CollectionsBenchmark.addMany      10000000  IntrusiveLinkedList  avgt   15  28434.662 ±  2616.126  us/op

Добавлено 22.04.21, 11:16

Цитата applegame @ 22.04.21, 11:10

Ну я бы не назвал это односвязными списками. Строго говоря, это вообще не списки.

Почему? Обычные односвязные списки, строящиеся по мере итерации по ним.

Цитата applegame @ 22.04.21, 11:10

ЕМНИП, каноническое определение списка в computer science включает в себя его конечность.

Не думаю, что там есть такое ограничение, но не видел этого определения.

Цитата applegame @ 22.04.21, 11:10

Коллекция элементов отсутствует как таковая.

Она присутствует, просто строится по мере необходимости, а не сразу.

Цитата applegame @ 22.04.21, 11:10

Это просто реккурентная функция обернутая в интерфейс списка, а не связный список.

Обычный ленивый связный список ))

Цитата applegame @ 22.04.21, 11:10

Ну что значит "должен"?

То и значит. Буквально.

[applegame]

Цитата korvin @ 22.04.21, 10:51

…
– данные, полученные при выполнении инструкции, могут записываться в память.
…
– использование именованных переменных;
– использование оператора присваивания;
…

Дык все это есть и в ФП языках. Например Elixir. Можно конечно долго разглагольствовать, что дескать вот это вот на самом деле не присваивание, но выглядит оно именно как присваивание:

a = foo(a)
b = foo(b)
{a, b} = {b, a}

Иммутабельная императивщина.

Цитата korvin @ 22.04.21, 10:51

In computer science, imperative programming is a programming paradigm that uses statements that change a program's state.

Ну, по мне так это какой-то булшит. Если программа (на любом языке) не меняет свое состояние, то оптимизатор может смело заменить ее на пустую функцию. Собсно продвинутые компиляторы так и делают, херя бенчмарки
Хошь покажу имеративную программу без единой мутабельной переменной? Держи :

import std.stdio;
void main() {
  foreach(const i; 0..10) writeln(i);
}

Сообщение отредактировано: applegame - 22.04.21, 11:30

[korvin]

Я предлагаю немного усложнить бенчмарк: сделать не только формирование коллекции, но и какое-то её использование.
Например: создавать упорядоченный набор значений (для простоты — числа по возрастанию), т.е. при добавлении каждого нового элемента, добавлять его не в конец, а в такую позицию, чтобы итоговый список/массив оставался упорядоченным. А в конце построить «сырой» массив int[] из элементов (UPD, нефиг зря память тратить =) ) посчитать сумму всех элементов, чтобы проитерироваться по всем элементам.

Для AL: используем бинарный поиск, потом add(index, item), который будет всегда требовать сдвига элементов и в некоторых случаях — реаллокации
Для LL: сначала проверяем первый и последний элементы, для быстрой вставки в начало и конец, иначе используем ListIterator для нахождения нужно места и вставки «во внутрь»
Для OpenLL: в целом, повторяет LL, но можно, например, отдельно хранить ноду середины, чтобы уменьшить количество проходов.
Для IntrusiveLL: повторяем алгоритм OpenLL.

Бэнчи запускаем для трёх кейсов:
– все генерируемые элементы изначально правильно упорядочены, т.е. вставка всегда идёт в начало — тут, по логике AL должен быть хуже всех.
– все генерируемые элементы изначально обратно упорядочены, т.е. вставка всегда идёт в конец.
– все элементы генерируются псевдослучайно, будем задавать одинаковый seed для ГСЧ.

Как вам такой кейс? Всё ли справедливо? Будет ли интересно?

Напишу на Java, кто захочет — напишет на своём любимом языке. Аналогичные коллекции можно взять стандартные или из библиотек, можно написать свои. )

Добавлено 22.04.21, 11:38

Цитата applegame @ 22.04.21, 11:28

Иммутабельная императивщина.

Не знаком с Elixir, где тут иммутабельность?

Цитата applegame @ 22.04.21, 11:28

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

Может. В чём тут проблема/противоречие?

Цитата applegame @ 22.04.21, 11:28

Хошь покажу имеративную программу без единой мутабельной переменной? Держи

И что это должно показать? Что состояние std.stdio не меняется?

Сообщение отредактировано: korvin - 22.04.21, 11:49

[applegame]

Цитата korvin @ 22.04.21, 11:10

Обычный ленивый связный список ))

Ну если хочется так называть, окай. Не будем впадать в терминологический спор. Но если исключить бесконечность, то ничего не мешает создать в том же D такой же ленивый BidirectionalRange, который будет лениво генерить, допустим, четные числа в заданном интервале и назвать его "обычным ленивым двусвязным списком". Пример такого ренджа, надеюсь, не надо писать?

Добавлено 22.04.21, 11:54

Цитата korvin @ 22.04.21, 11:34

Не знаком с Elixir, где тут иммутабельность?

Везде. Просто в эликсире можно, так сказать, "ребиндить" имена переменных. То есть в одной строке переменная указывает на одни данные, в другой ее можно перебиндить и она будет указывать уже на другие данные. А сами данные строго иммутабельны. В хаскеле и окамле похожее через let можно сделать, ЕМПИН.

Цитата korvin @ 22.04.21, 11:34

Может. В чём тут проблема/противоречие?

Не противоречие, а бессмыслица. Изменение состояние программы - это не признак императивного программирования. Это признак программирования вообще, в том числе и ФП. Даже генератор чисел фибоначчи написанный на Хаскеле (самый ФП язык из всех ФП языков) меняет свое состояние по мере вывода чисел на экран. Банальная функция с хвостовой рекурсией тоже меняет свое состояние (привет ген_серверам эрланга).

Цитата korvin @ 22.04.21, 11:34

И что это должно показать? Что состояние std.stdio не меняется?

Это показывает, что мутабельность/иммутабельность - не обязательный признак императивности. Если изменение stdio считать за признак императивности, то и хаскельный генератор фибоначчи императивен.

Добавлено 22.04.21, 12:12

Цитата korvin @ 22.04.21, 11:10

Обычный ленивый связный список ))

Кстати можно же на том же хацкеле кортеж из двух "встречных" списков замутить и сделать соответствующие операции над ним. Получится "обычный ленивый двусвязный список"

Сообщение отредактировано: applegame - 22.04.21, 12:12

[D_KEY]

Цитата applegame @ 22.04.21, 11:41

Просто в эликсире можно, так сказать, "ребиндить" имена переменных. То есть в одной строке переменная указывает на одни данные, в другой ее можно перебиндить и она будет указывать уже на другие данные. А сами данные строго иммутабельны.

Т.е. это "другие" a и b? Тогда не понимаю, в чем проблема.

Добавлено 22.04.21, 12:38

Цитата applegame @ 22.04.21, 11:41

Изменение состояние программы - это не признак императивного программирования. Это признак программирования вообще, в том числе и ФП.

А мне вот кажется, ты ошибаешься

Добавлено 22.04.21, 12:40
applegame, ещё ты почему-то смешиваешь языки и парадигмы. То, что в каком-то языке с поддержкой ФП, есть поддержка ИП, не делает фичи ИП фичами ФП.

[korvin]

applegame, так, пажди, ёмана, это просто создание нового скоупа, тут нет ничего императивного, то что оно записывается линейно, а не вложено — это просто синтаксический сахар, чтобы не было больших лестниц, а по сути это:

let a = 1 in
  let b = 2 in
    let (b, a) = (a, b) in
      ....

что в свою очередь тривиально преобразуется в лямбда-выражение.

Никакой императивщины тут нет.

Вот, например, в Go похожее выражение:

var a, b int
a = 1
b = 2
a, b = b, a

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

[applegame]

Цитата D_KEY @ 22.04.21, 12:36

applegame, ещё ты почему-то смешиваешь языки и парадигмы. То, что в каком-то языке с поддержкой ФП, есть поддержка ИП, не делает фичи ИП фичами ФП.

Да нет, тебе показалось. Вот главные вопросы:
Что является главным отличием ИП от ФП?
Является ли иммутабельность/мутабельность этим главным отличием?
Ну и как бонус:
Может ли ИП существовать без мутабельности?

Добавлено 22.04.21, 13:34

Цитата korvin @ 22.04.21, 13:01

applegame, так, пажди, ёмана, это просто создание нового скоупа, тут нет ничего императивного, то что оно записывается линейно, а не вложено — это просто синтаксический сахар, чтобы не было больших лестниц, а по сути это:

Ага, это был прикол. Но таки в моем примере запросто может появиться императивщина. В Elixir/Erlang функции запросто могут быть грязными с сайд эффектами, а в моем коде идет вызов функции foo(), причем два раза и в определенной ПОСЛЕДОВАТЕЛЬНОСТИ.
Я в целом считаю, что даже в хацкеле как только ты задействовал do-нотацию, считай начал писать императивно.

Сообщение отредактировано: applegame - 22.04.21, 14:07

[korvin]

Цитата applegame @ 22.04.21, 13:31

Но таки в моем примере запросто может появиться императивщина. В Elixir/Erlang функции запросто могут быть грязными с сайд эффектами, а в моем коде идет вызов функции foo(), причем два раза и в определенной ПОСЛЕДОВАТЕЛЬНОСТИ.

Вложенный вызов чистых функций в «чистом» функциональном языке

x = foo (bar (gee (qux 42)))

— тоже некоторая «последовательность», и что? Функциональный код не перестаёт таковым быть. А наличие побочных эффектов — да, делает код императивным, а побочные эффекты — это изменение состояния. Снова приходим к тому, что это ключевое отличие.

Цитата applegame @ 22.04.21, 13:31

Я в целом считаю, что даже в хацкеле как только ты задействовал do-нотацию, считай начал писать императивно.

Ну, ты, конечно, можешь считать что угодно, только действительность от этого не меняется. Потому и не рекомендуют новичкам объяснять монады вообще и монаду IO в частности с демонстрации do-нотации, т.к. это создаёт у них такое вот ложное впечатление.

[applegame]

Цитата korvin @ 22.04.21, 14:51

— тоже некоторая «последовательность», и что?

Это не последовательность, это композиция функций. ФП абстрагируется от порядка выполнения максимально, пока не придется столкнуться с реальным императивным миром и тут-то волшебные замки рушатся. Вот тебе
другой пример:
foo(bar(), baz())
Что выполнится раньше: bar() или baz()?

Цитата korvin @ 22.04.21, 14:51

Снова приходим к тому, что это ключевое отличие.

Это ФП или ИП? И есть ли тут мутабельное состояние?

bool contains(T)(const T[] arr, const T e) pure {
  foreach(const x; arr) if(x == e) return true;
  return false;
}

Цитата korvin @ 22.04.21, 14:51

Ну, ты, конечно, можешь считать что угодно, только действительность от этого не меняется. Потому и не рекомендуют новичкам объяснять монады вообще и монаду IO в частности с демонстрации do-нотации, т.к. это создаёт у них такое вот ложное впечатление.

Ох уж эта высокомерная надменность. Полная уверенность, что именно твое определение "действительность", а оппонент новичок с ложным впечатлением. При этом выпад содержит ноль аргументов.

Сообщение отредактировано: applegame - 22.04.21, 15:41

[D_KEY]

Цитата applegame @ 22.04.21, 13:31

Что является главным отличием ИП от ФП?

Если кратко, то
ИП - это подход с последовательным выполнением инструкций, которые модифицируют данные(состояние), теоретическая модель - машина Тьюринга.
ФП - это подход с вычислением функций, теоретическая модель - лямбда исчисления Черча.

Добавлено 22.04.21, 15:44

Цитата applegame @ 22.04.21, 13:31

Является ли иммутабельность/мутабельность этим главным отличием?

Одним из. Главным или нет - не понимаю вопроса.

Цитата

Может ли ИП существовать без мутабельности?

Думаю, что нет

Добавлено 22.04.21, 16:05

Цитата applegame @ 22.04.21, 15:39

Вот тебе
другой пример:
foo(bar(), baz())
Что выполнится раньше: bar() или baz()?

В ФП вопрос не имеет смысла, в ИП зависит от языка или даже компилятора.

Добавлено 22.04.21, 16:09

Цитата applegame @ 22.04.21, 15:39

Это ФП или ИП?

Это функция. Судя по всему, чистая. Значит могла бы быть и в ФП. Правда если всматриваться в тело функции, то можно увидеть инструкции, т.е. формально, наверное, не чистое ФП. Такой подход свойственнен гибридным языкам

[applegame]

Цитата D_KEY @ 22.04.21, 15:42

ИП - это подход с последовательным выполнением инструкций, которые модифицируют данные(состояние), теоретическая модель - машина Тьюринга.

А я вот останавливаюсь на последовательном выполнении инструкций. Мутабельное состояние мне представляется необязательным.

Цитата D_KEY @ 22.04.21, 15:42

В ФП вопрос не имеет смысла

Именно.

Цитата D_KEY @ 22.04.21, 15:42

Это функция. Судя по всему, чистая. Значит могла бы быть и в ФП. Правда если всматриваться в тело функции, то можно увидеть инструкции, т.е. формально, наверное, не чистое ФП. Такой подход свойственнен гибридным языкам

Ну а мутабельное состояние-то есть?

Сообщение отредактировано: applegame - 22.04.21, 17:31

[Qraizer]

Цитата sergioK @ 15.04.21, 19:47

...программист сделавший глупость юридически никак за это не отвечает

Это потому что в лицензии так написано. А не приняв оферту лицензии, не имеешь права использовать (потенциально багованное) ПО. Ты всерьёз думаешь, что лицензия поможет программисту – хотя скорее исцом будет компания, в которой программист работает, но не суть, внутренние корпоративные разборки тоже бывают по-разному оканчиваются – уйти от уголовной ответственности, если дело примет такой оборот? Сочувствую, но ты плохо себе представляешь, как работает закон и каким образом лицензии с ним взаимодействуют.

Цитата sergioK @ 15.04.21, 19:47

Вот и придумали шутку про дроздов, а в каждой шутке доля правды, as smaller as better

Это потому что никто в суды не подавал. А если и подавал, то всё обычно решалось в досудебном порядке, чтоб никто ничего никому внешне не попортил, ни в репутации, ни на физиономии. Нынче другие времена, и суды вполне себе, бывает, выигрываются. И – да, мы о бизнесе. В области высококритичного ПО понятия лицензий просто нет. Там никто не будет просить прочитать и согласиться. Там всё куда проще: спасибо за деньги, вот вам копия, циркулярный №XXX-YYY, документация во вложении; и там чёрным по-человеческому все-все-все планы, методики, правила, мануалы итд итп — всё, что касается эксплуатации такого ПО и в рамках чего поставщик отвечает за качество.
Когда-то, не спорю, программы были маленькими и простыми. Потому что компьютеры обладали малыми ресурсами, а у программистов были в использовании простые инструменты. Увы, приходилось многое перекладывать на плечи юзеров. Нынче ситуация далеко не та, время дроздов в контексте той поговорки ушло где-то уже на рубеже веков, а с тех пор ещё 20 лет прошло.

Цитата sergioK @ 15.04.21, 19:47

В вашей это в какой ? ты же програмист или нет ?

Авионика. По должности да, более подходящих в ЕТКС нет. По сфере деятельности нет. Самое короткое описание – "технический специалист". И список длиною в пол-листа в должностной инструкции. Хотя программированием занимаюсь, но не высококритичного кода как такового, а различного инструментария для его верификации и сертификации. Включая проектирование, создание и саппорт испытательных стендов с исходным аппаратным и исполнительным окружением flight-кода under inspection, тестового окружения на базе ПК и различных инструментов статистического анализа, генерации итоговой документации, управления артефактами, автоматизации процессов итп.

Добавлено 22.04.21, 18:46

Цитата sergioK @ 15.04.21, 19:47

И какая связь ? после второй прививки нельзя работать?

Можно. Но не хочется, хочется кофе и спать.

Цитата sergioK @ 15.04.21, 19:47

Таганрог это столица IT ? Или это была ирония ?

В какой-то мере да. Видосик не смотрел? Посмотри, меня тоже улыбало.

[korvin]

Цитата applegame @ 22.04.21, 15:39

Вот тебе
другой пример:
foo(bar(), baz())
Что выполнится раньше: bar() или baz()?

Странный вопрос. Для чистого ФП разницы нет (разве что одна из функций bar, baz значительно дольше вычисляется, чем другая). Для императивного зависит от порядка вычисления аргументов функции и стратегии вычисления (call-by-value vs call-by-name).

Цитата applegame @ 22.04.21, 15:39

Это ФП или ИП? И есть ли тут мутабельное состояние?

bool contains(T)(const T[] arr, const T e) pure {
  foreach(const x; arr) if(x == e) return true;
  return false;
}

Это может быть как ФП, так и ИП, внезапно.

Вот тебе другой пример:

    public static void main(String[] args) {
        System.out.println(foo(1));
    }
 
    private static int foo(int i) {
        return bar(gee(++i));
    }
 
    private static int bar(int x) {
        return ++x+1;
    }
 
    private static int gee(int x) {
        return ++x*2;
    }

— это композиция функций? ФП, значит?

Цитата applegame @ 22.04.21, 15:39

Ох уж эта высокомерная надменность.

Никакой надменности, простая констатация фактов.

Цитата applegame @ 22.04.21, 15:39

Полная уверенность, что именно твое определение "действительность", а оппонент новичок с ложным впечатлением.

Это общепринятое определение.

----------------------------------------------------------------

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

Процесс такой: составление упорядоченного набора чисел, потом фильтрация по (x < max/2), потом суммирование.
Вариантов распределения входных значений 5:
– по возрастанию
– по убыванию
– по возрастанию до середины, потом по убыванию (например: 1 2 3 4 5 4 3 2 1)
– по убыванию до середины, потом по возрастанию (например: 5 4 3 2 1 2 3 4 5)
– псевдослучайное

ожидаемо ArrayList слил во всех кейсах, кроме первого (добавление в конец):

Benchmark                      (itemMapperType)  (itemsToAdd)           (type)  Mode  Cnt    Score   Error  Units
 
CollectionsBenchmark2.addMany         ascending        100000           LinkedList  avgt   10    1998.600 ±  825.551  us/op
CollectionsBenchmark2.addMany         ascending        100000            ArrayList  avgt   10    1158.352 ±  630.132  us/op
 
CollectionsBenchmark2.addMany        descending        100000           LinkedList  avgt   10    1984.810 ±  819.924  us/op
CollectionsBenchmark2.addMany        descending        100000            ArrayList  avgt   10  380804.497 ± 4571.318  us/op
 
CollectionsBenchmark2.addMany         asc->desc        100000           LinkedList  avgt   10    2121.230 ±  736.523  us/op
CollectionsBenchmark2.addMany         asc->desc        100000            ArrayList  avgt   10  191833.039 ± 3449.825  us/op
 
CollectionsBenchmark2.addMany         desc->asc        100000           LinkedList  avgt   10    1876.418 ±  727.067  us/op
CollectionsBenchmark2.addMany         desc->asc        100000            ArrayList  avgt   10  168997.600 ± 4365.277  us/op
 
CollectionsBenchmark2.addMany            random        100000           LinkedList  avgt   10    3463.063 ±  908.374  us/op
CollectionsBenchmark2.addMany            random        100000            ArrayList  avgt   10  195038.198 ± 3059.551  us/op

Однако, если поменять алгоритм наполнения ArrayList на добавление всегда в конец с сортировкой в финале, то сливает уже LinkedList, кроме последнего метода:

Benchmark                      (itemMapperType)  (itemsToAdd)           (type)  Mode  Cnt    Score   Error  Units
 
CollectionsBenchmark2.addMany         ascending        100000           LinkedList  avgt   10    1998.600 ±  825.551  us/op
CollectionsBenchmark2.addMany         ascending        100000       ArrayList.Sort  avgt   10    1167.463 ±  521.571  us/op
 
CollectionsBenchmark2.addMany        descending        100000           LinkedList  avgt   10    1984.810 ±  819.924  us/op
CollectionsBenchmark2.addMany        descending        100000       ArrayList.Sort  avgt   10    1348.757 ±  585.568  us/op
 
CollectionsBenchmark2.addMany         asc->desc        100000           LinkedList  avgt   10    2121.230 ±  736.523  us/op
CollectionsBenchmark2.addMany         asc->desc        100000       ArrayList.Sort  avgt   10    1791.563 ±  622.418  us/op
 
CollectionsBenchmark2.addMany         desc->asc        100000           LinkedList  avgt   10    1876.418 ±  727.067  us/op
CollectionsBenchmark2.addMany         desc->asc        100000       ArrayList.Sort  avgt   10    1348.264 ±  629.691  us/op
 
CollectionsBenchmark2.addMany            random        100000           LinkedList  avgt   10    3463.063 ±  908.374  us/op
CollectionsBenchmark2.addMany            random        100000       ArrayList.Sort  avgt   10   19608.787 ±  316.377  us/op

Почему AL сливается именно на случайных элементах, мне не очень понятно, с ходу не вижу логического объяснения. Возможно, какие-то баги в коде.

И как бонус, сравнение LL с OpenLL, IntrusiveLL и TreeMap (SortedMap):

Benchmark                      (itemMapperType)  (itemsToAdd)           (type)  Mode  Cnt    Score   Error  Units
 
CollectionsBenchmark2.addMany         ascending        100000           LinkedList  avgt   10    1998.600 ±  825.551  us/op
CollectionsBenchmark2.addMany         ascending        100000       OpenLinkedList  avgt   10    1590.634 ±  771.149  us/op
CollectionsBenchmark2.addMany         ascending        100000              TreeMap  avgt   10   16178.317 ±  352.460  us/op
CollectionsBenchmark2.addMany         ascending        100000  IntrusiveLinkedList  avgt   10     958.116 ±  459.509  us/op
 
CollectionsBenchmark2.addMany        descending        100000           LinkedList  avgt   10    1984.810 ±  819.924  us/op
CollectionsBenchmark2.addMany        descending        100000       OpenLinkedList  avgt   10    1560.737 ±  783.328  us/op
CollectionsBenchmark2.addMany        descending        100000              TreeMap  avgt   10   15963.631 ±  658.773  us/op
CollectionsBenchmark2.addMany        descending        100000  IntrusiveLinkedList  avgt   10     940.864 ±  433.400  us/op
 
CollectionsBenchmark2.addMany         asc->desc        100000           LinkedList  avgt   10    2121.230 ±  736.523  us/op
CollectionsBenchmark2.addMany         asc->desc        100000       OpenLinkedList  avgt   10    1584.023 ±  841.150  us/op
CollectionsBenchmark2.addMany         asc->desc        100000              TreeMap  avgt   10   11919.388 ±  287.896  us/op
CollectionsBenchmark2.addMany         asc->desc        100000  IntrusiveLinkedList  avgt   10     947.756 ±  473.614  us/op
 
CollectionsBenchmark2.addMany         desc->asc        100000           LinkedList  avgt   10    1876.418 ±  727.067  us/op
CollectionsBenchmark2.addMany         desc->asc        100000       OpenLinkedList  avgt   10    1503.495 ±  891.668  us/op
CollectionsBenchmark2.addMany         desc->asc        100000              TreeMap  avgt   10    8444.099 ±  744.990  us/op
CollectionsBenchmark2.addMany         desc->asc        100000  IntrusiveLinkedList  avgt   10     917.276 ±  511.321  us/op
 
CollectionsBenchmark2.addMany            random        100000           LinkedList  avgt   10    3463.063 ±  908.374  us/op
CollectionsBenchmark2.addMany            random        100000       OpenLinkedList  avgt   10    1700.960 ±  795.577  us/op
CollectionsBenchmark2.addMany            random        100000              TreeMap  avgt   10   33226.797 ± 1511.600  us/op
CollectionsBenchmark2.addMany            random        100000  IntrusiveLinkedList  avgt   10    1301.572 ±  462.545  us/op

Видно, что
1) LL сливает двум «кустарным» спискам.
2) TreeMap сливает всем, что может выглядеть немного неожиданно, ведь для задачи «собрать упорядоченную коллекцию» она выглядит весьма подходящей структурой.

segioK, я, конечно, не специалист по бенчмаркам и всё такое, но если ты всё ещё считаешь, что java.util.LinkedList для чего-то будет лучшим выбором, предлагай кейс, а иначе прекрати нести чушь.

[D_KEY]

Цитата applegame @ 22.04.21, 17:30

А я вот останавливаюсь на последовательном выполнении инструкций.

А почему? И какой толк от последовательности инструкций, если мы убираем изменение состояния?

Цитата

Ну а мутабельное состояние-то есть?

Насколько я вижу, нет. Но это просто функция. Программу-то полноценную если ты начнешь писать без мутабельности, то не скатишься ли ты к функциональному стилю, по сути?

[korvin]

Цитата D_KEY @ 22.04.21, 21:30

А почему? И какой толк от последовательности инструкций, если мы убираем изменение состояния?

Присоединяюсь к вопросу.

applegame, чем это:

bool contains(T)(const T[] arr, const T e) pure {
  foreach(const x; arr) if(x == e) return true;
  return false;
}

отличается от

contains []     e = False
contains (x:xs) e = x == e || contains xs e

?

Сообщение отредактировано: korvin - 22.04.21, 22:04