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

[applegame]

Цитата korvin @ 21.04.21, 11:21

Состоятелен, потому что юз-кейсы у списка и кортежа принципиально разные.

Кортеж это пример иммутабельной структуры требующей полного копирования для изменения. Кейсы тут вообще не в тему, ты же ни о каких кейсах не упоминал, когда заявил:

Цитата korvin @ 17.04.21, 07:45

В том, что любая операция добавления/изменения приводит к созданию полной копии списка.

Цитата korvin @ 21.04.21, 11:21

Без копирования? Ну-ну.

Память у тебя как у рыбки:

Цитата applegame @ 12.04.21, 07:21

Если двусвязный список сделать встроенным в язык типом, то он вполне может быть персистентным, а при добавлении новых элементов просто копировать его целиком. Бесполезно, но возможно.

Ты таки согласен, что иммутабельный двусвязный список может быть реализован, с полным копированием при добавлении/изменении? Ответь прямо без юления.

Цитата korvin @ 21.04.21, 11:21

Очевидно, 1) print здесь элемент списка, а не «операция» над элементом списка, 2) в примерах на Scheme и Java print не является ленивой функцией.

Ну если уж доёбываться, то элемент списка не сам print а результат каррирования print. Можно переделать твой пример, чтобы была операция над элементами: https://ideone.com/hPXX7o
Суть не меняется, ленивый не список, а вычисления.

Цитата korvin @ 21.04.21, 11:21

2) в примерах на Scheme и Java print не является ленивой функцией.

Вот сам придумываешь какие-то странные термины, что такое "ленивая функция"? Чем она отличается от "неленивой"?

Цитата korvin @ 21.04.21, 11:21

Вообще-то съезжать в сторону начал ты с самого начала.

Ну давай вернемся. Я с самого начала пытаюсь выяснить почему LinkedList, по словам жаба-селебрити, "совсем другое дело". Но пока от тебя так и не услышал ответа. Ты говооришь о чем угодно, кроме сути. Может таки ответишь вместо переливания в из пустого в порожнее?

Цитата korvin @ 21.04.21, 11:21

Нельзя, из-за обратной ссылки на предыдущий элемент. Ты не сможешь даже сконструировать такой список.

Ты явно путаешь принципиальную возможность создать такой список и возможность создать его средствами самого иммутабельного ФП-языка. Повторю еще раз: двусвязный список при желании можно встроить в любой иммутабельный ФП язык. В Erlang это можно сделать например при помощи NIF: создаем сначала мутабельный список, заполняем ноды данными, после чего делаем иммутабельным. В общем-то аналогично кортежам, которые в том же эрланге являются, по сути, иммутабельными массивами.
Ленивость же, как я говорил, вообще ортогональна всему этому. В том же D, я могу сделать тебе ленивый рендж, хоть односвязный (ForwardRange), хоть двусвязный (BidirectionalRange), хоть вообще массив (RandomAccessRange). Хошь мутабельный, хошь иммутабельный.

Цитата korvin @ 21.04.21, 11:21

Речь о том, что класс LinkedList оказался на практике почти бесполезен.

Интересует почему. Какое принципиальное отличие от односвязных списков в Scheme или сферических в вакууме списков в C?

Цитата korvin @ 21.04.21, 11:21

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

Односвязный список и в Африке односвязный, какая разница это C или Scheme? Можно еще говорить о разных степенях оптимизации, но автор явно абстрагировался от этого, так как упомянул C, в котором вообще не существует какой-либо стандартной реализации списка. Если бы он скажем заявил, что-то вроде "не поймите неправильно, мне нравятся связные списки, они могут быть полезны, но вот LinkedList сделан через жопу, поэтому не используйте его", то это было бы логично. Возможно автор именно это и имел в виду, но сказал нечто совершенно иное.

Цитата korvin @ 21.04.21, 11:21

Вот, например, в org.apache.commons есть двусвязный список с этим твои кэшированием нод

Молодец, просвещайся дальше. Даю подсказку: ноды еще можно не по одной аллоцировать, а сразу непрерывными блоками по несколько штук, причем можно сразу и место для данных аллоцировать внутри ноды (интрузивные списки, о которых я писал ранее, а после и ты). Особо упоротые оптимизаторы, длину этих блоков еще и с размером строки кэша процессора норовят выровнять.

Цитата korvin @ 21.04.21, 11:21

Я-то понял, только зачем ты терминологию выдумываешь?

А в чем проблема? Не нравится мой термин, предложи свой. Тем более если ты понял, то зачем цепляться? Лишь бы что-нибудь возразить?

[applegame]

Цитата korvin @ 21.04.21, 11:21

Нет. Что мешает, написал выше. Ты, конечно, можешь просто взять мой пример ленивого односвязного списка для Java и сделать двусвязный. Ну или с нуля на твоём любимом языке.

Сделал на D. И синтаксический сахар есть.
1. Вместо head - front, вместо tail - popFront. Также есть back и popBack - аналоги для другого конца списка.
Список иммутабелен. Добавление элементов (append) создает копию списка, popFront и popBack не создают копию.
Для демонстрации иммутабельности, добавляю не сразу все элементы к списку, а за два раза. Обратите внимание, что все переменные в main константные, кастов в программе нет, так что они реально иммутабельные.
Элементы вычисляются лениво. Для подтверждения этого создал структуру Int, иммитирующую обычное целое, с перегруженным оператором сложения, который печатает в консоль текст подтверждающий, что сложение реально произошло.

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

Играться тут: https://glot.io/snippets/fxwh6ktfxg

Код:

Скрытый текст

import std.stdio;
 
struct Int {
    int value;
    Int opBinary(string op: "+")(Int other) const {
        writefln("%s + %s = %s", value, other.value, value + other.value);
        return Int(value + other.value);
    }
}
 
void main() {
    const l0 = DList!Int();
    const l1 = l0.append(
        Int(1) + Int(1),
    );
    const l2 = l1.append(
        Int(2) + Int(2),
        Int(3) + Int(3),
        Int(4) + Int(4)
    );
    writeln(l2.popFront().front);
}
 
struct DList(T) {
    struct Node {
        T delegate() payload;
        Node* prev, next;
    }
 
    private Node* m_first, m_last;
 
    bool empty() const { return m_first == null; }
    T front() const { assert(!empty); return m_first.payload(); }
    T back() const { assert(!empty); return m_last.payload(); }
    const(DList) popFront() const {
        assert(!empty);
        return m_first == m_last ? const DList() : const DList(m_first.next, m_last);
    }
    const(DList) popBack() const {
        assert(!empty);
        return m_first == m_last ? const DList() : const DList(m_first, m_last.prev);
    }
 
    const(DList) append(ARGS...)(lazy ARGS args) const {
        auto list = dup();
        static foreach(arg; args) {
            if(empty) {
                list.m_first = list.m_last = new Node(&arg);
            } else {
                list.m_last.next = new Node(&arg, list.m_last);
                list.m_last = list.m_last.next;
            }
        }
        return list;
    }
 
    private DList dup() const {
        auto list = DList();
        if(!empty) {
            auto prev = new Node(m_first.payload);
            list.m_first = prev;
            const(Node)* cur = m_first.next;
            while(cur != m_last.next) {
                auto node = new Node(cur.payload, prev);
                prev.next = node;
                prev = node;
                cur = cur.next;
            }
            list.m_last = prev;
        }
        return list;
    }
}

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

Сообщение отредактировано: applegame - 21.04.21, 21:47

[korvin]

Цитата sergioK @ 21.04.21, 19:57

Я таких ArrayList не один десяток написал , разных имплементаций ,

Зачем? Руки чесались? )

Цитата sergioK @ 21.04.21, 19:57

ArrayList умножает память на 3/2 и перегрузить это нельзя в отличии от вектора,

А LinkedList умножает память на 3.

Цитата sergioK @ 21.04.21, 19:57

и это одна имлементация интерфэйса java.util.List другая это Linked List,
пользуешь когда не знаешь сколько элементов будет.

Вот тебе бенчмарк на добавление «не знаешь сколько элементов»:

Скрытый текст

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.Blackhole;
import ru.sources.collections.Collections;
 
import java.util.Collection;
import java.util.concurrent.TimeUnit;
import java.util.function.IntFunction;
 
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Fork(
        value = 3,
        jvm = "/Library/Java/JavaVirtualMachines/adoptopenjdk-15.jdk/Contents/Home/bin/java",
        jvmArgsAppend = {
                "-server",
                "-disablesystemassertions",
                //"-XX:+UseSerialGC",
                //"-XX:+UseParallelGC",
                //"-XX:+UseZGC",
                "-XX:+UseShenandoahGC",
                "-Xms8g",
                "-Xmx8g"
        })
@State(Scope.Thread)
public class CollectionsBenchmark {
 
    private static final String LINKED_LIST = "LinkedList";
    private static final String ARRAY_LIST  = "ArrayList";
 
    //@Param({"10", "100"})
    //@Param({"100", "10000", "1000000"})
    @Param({"1000", "100000", "10000000"})
    private int itemsToAdd;
 
    @Param({LINKED_LIST, ARRAY_LIST})
    private String type;
 
    private IntFunction<Collection<?>> subject;
 
    @Setup
    public void setup() {
        switch (type) {
            case LINKED_LIST -> subject = Collections::linkedList;
            case ARRAY_LIST  -> subject = Collections::arrayList;
        }
    }
 
    @Benchmark
    public void addMany(Blackhole blackhole) {
        blackhole.consume(subject.apply(itemsToAdd));
    }
}

subjects

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
 
public final class Collections {
 
    public static Collection<?> linkedList(int items) {
        final var c = new LinkedList<>();
        for (int i = 0; i < items; i++) {
            c.add(i);
        }
        return c;
    }
 
    public static Collection<?> arrayList(int items) {
        final var c = new ArrayList<>();
        for (int i = 0; i < items; i++) {
            c.add(i);
        }
        return c;
    }
}

Вот результаты с разными GC (меньше — лучше):

Serial:

Benchmark                     (itemsToAdd)               (type)  Mode  Cnt       Score       Error  Units
 
CollectionsBenchmark.addMany          1000           LinkedList  avgt   15       5.210 ±     0.053  us/op
CollectionsBenchmark.addMany          1000            ArrayList  avgt   15       3.530 ±     0.028  us/op
 
CollectionsBenchmark.addMany        100000           LinkedList  avgt   15     487.786 ±     7.153  us/op
CollectionsBenchmark.addMany        100000            ArrayList  avgt   15     361.776 ±     3.407  us/op
 
CollectionsBenchmark.addMany      10000000           LinkedList  avgt   15  114308.717 ± 24496.008  us/op
CollectionsBenchmark.addMany      10000000            ArrayList  avgt   15   74059.694 ±  1124.293  us/op

Parallel:

Benchmark                     (itemsToAdd)              (type)  Mode  Cnt       Score       Error  Units
 
CollectionsBenchmark.addMany          1000           LinkedList  avgt   15       5.191 ±     0.038  us/op
CollectionsBenchmark.addMany          1000            ArrayList  avgt   15       3.524 ±     0.042  us/op
 
CollectionsBenchmark.addMany        100000           LinkedList  avgt   15     490.742 ±     7.725  us/op
CollectionsBenchmark.addMany        100000            ArrayList  avgt   15     364.297 ±     7.221  us/op
 
CollectionsBenchmark.addMany      10000000           LinkedList  avgt   15  145307.026 ± 35319.645  us/op
CollectionsBenchmark.addMany      10000000            ArrayList  avgt   15   71625.532 ±  3860.046  us/op

ZGC:

Benchmark                     (itemsToAdd)              (type)  Mode  Cnt       Score        Error  Units
 
CollectionsBenchmark.addMany          1000           LinkedList  avgt   15       5.714 ±     0.548  us/op
CollectionsBenchmark.addMany          1000            ArrayList  avgt   15       5.573 ±     0.298  us/op
 
CollectionsBenchmark.addMany        100000           LinkedList  avgt   15     553.497 ±    38.279  us/op
CollectionsBenchmark.addMany        100000            ArrayList  avgt   15     583.829 ±    33.537  us/op
 
CollectionsBenchmark.addMany      10000000           LinkedList  avgt   15  136561.101 ± 62714.469  us/op
CollectionsBenchmark.addMany      10000000            ArrayList  avgt   15  147221.840 ± 65372.420  us/op

Senandoah:

Benchmark                     (itemsToAdd)              (type)  Mode  Cnt      Score       Error  Units
 
CollectionsBenchmark.addMany          1000           LinkedList  avgt   15      4.516 ±     0.100  us/op
CollectionsBenchmark.addMany          1000            ArrayList  avgt   15      3.904 ±     0.123  us/op
 
CollectionsBenchmark.addMany        100000           LinkedList  avgt   15    453.895 ±     6.612  us/op
CollectionsBenchmark.addMany        100000            ArrayList  avgt   15    359.160 ±     7.098  us/op
 
CollectionsBenchmark.addMany      10000000           LinkedList  avgt   15  59037.699 ±  9332.316  us/op
CollectionsBenchmark.addMany      10000000            ArrayList  avgt   15  56993.428 ±  3011.366  us/op

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

Добавлено 21.04.21, 22:52

Цитата applegame @ 21.04.21, 21:13

Кортеж это пример иммутабельной структуры требующей полного копирования для изменения. Кейсы тут вообще не в тему, ты же ни о каких кейсах не упоминал, когда заявил:

А по-твоему, списки они сферические в вакууме?

Цитата applegame @ 21.04.21, 21:13

Память у тебя как у рыбки:

Наоборот же, у тебя, не говоря уж, о твоих проблемах с чтением:

Цитата

Насчёт двусвязных списков не скажу, но как минимум их, например, нельзя просто сделать иммутабельными и/или ленивыми, в отличие от односвязных.

на второй странице.

Цитата applegame @ 21.04.21, 21:13

Ты таки согласен, что иммутабельный двусвязный список может быть реализован, с полным копированием при добавлении/изменении? Ответь прямо без юления.

С полным копированием можно что угодно сделать иммутабельным, только это не «просто». Тебе же не нужно показывать, как делается иммутабельный односвязный список?

Цитата applegame @ 21.04.21, 21:13

Вот сам придумываешь какие-то странные термины, что такое "ленивая функция"? Чем она отличается от "неленивой"?

Э-э… у тебя раздвоение личности? Я тебя спросил, какая операция там ленивая, ты ответил «print». print — это функция, т.е. ты же и назвал её ленивой

Цитата applegame @ 21.04.21, 21:13

Ну давай вернемся. Я с самого начала пытаюсь выяснить почему LinkedList, по словам жаба-селебрити, "совсем другое дело". Но пока от тебя так и не услышал ответа. Ты говооришь о чем угодно, кроме сути. Может таки ответишь вместо переливания в из пустого в порожнее?

Я тебе уже давно ответил, даже три пункта перечислил, с которыми ты же согласился, написав, что «Возможно, что LinkedList - просто корявая реализация двусвязного списка, тут спорить не буду ибо не знаю. Мои двусвязные списки (не на жабе, конечно) используют пулы, и добавляют по два указателя к каждой ноде.» (3-я страница). проверь память, я серьёзно.

Причём, вот ещё, например, кейс, вроде бы подходящий для двусвязного списка: LRU-кэш, но там нужно иметь ссылки на ноды, чтобы эффективно переставлять их в начало списка, но LinkedList не предоставляет возможности иметь ссылку на ноду, т.е. для этого кейса не подходит.

Цитата applegame @ 21.04.21, 21:13

Ты явно путаешь принципиальную возможность создать такой список и возможность создать его средствами самого иммутабельного ФП-языка.

Я нигде не писал про «принципиальную невозможность».

Цитата applegame @ 21.04.21, 21:13

Какое принципиальное отличие от односвязных списков в Scheme

двусвязность и закрытость для тебя не достаточно принципиальные отличия? Не знаю тогда. Может для тебя вообще все динамические структуры «на одно лицо»?

Цитата applegame @ 21.04.21, 21:13

сферических в вакууме списков в C?

Такая же сферическая в вакууме. Мне как-то не интересно гадать.

Цитата applegame @ 21.04.21, 21:13

Односвязный список и в Африке односвязный, какая разница это C или Scheme?

Во-первых, односвязный список можно реализовать по-разному:
– интрузивный или не интрузивный
– закрытый (объект-контейнер с внутренним приватным списком нод и предоставляющий доступ к элементов только описанными методами, инкапсулирующий манипуляции над нодами) или открытый (просто создаются сразу сами объекты нод)

Цитата applegame @ 21.04.21, 21:13

"не поймите неправильно, мне нравятся связные списки, они могут быть полезны, но вот LinkedList сделан через жопу, поэтому не используйте его"

Он именно так и написал, но ты предпочёл поСПГСить.

Цитата applegame @ 21.04.21, 21:13

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

Вопрос: если ты не манипулируешь нодами, переставляя их, то нафига тебе связный список? Используй массив. А если манипулируешь, то вся эта изначальная локальность пойдёт лесом на хоть сколько-нибудь большом списке.

Цитата applegame @ 21.04.21, 21:13

А в чем проблема? Не нравится мой термин, предложи свой. Тем более если ты понял, то зачем цепляться? Лишь бы что-нибудь возразить?

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

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

[korvin]

DEL (опечатался там)

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

[korvin]

Цитата sergioK @ 21.04.21, 19:57

ArrayList умножает память на 3/2 и перегрузить это нельзя в отличии от вектора,

Только вектор
1) растёт на константное значение, что при большом количестве операций добавления требует больше реаллокаций и мене эффективно, чем ArrayList
2) synchronized, а значит ещё и имеет оверхед на lock/unlock на каждую операцию, даже если это не нужно, т.е. в большинстве юз-кейсов.

Цитата sergioK @ 21.04.21, 19:57

ArrayList умножает память на 3/2

Ах да, ты ещё забыл, что у объекта Node в LinkedList'е помимо 3-х ссылок (elem, prev, next) есть ещё и object header, который в Java довольно жирный.

Например, для 64bit JVM без сжатия указателей получим на каждый элемент:

objectHeader.classRef = 8
+ objectHeader.mark = 8
+ object.element = 8
+ object.previous = 8
+ object.next = 8
= 40 bytes per node
/ object.element = 8
= 5x

В пять раз больше памяти на ссылки по сравнению с ArrayList, Карл!
– LinkedList на 1млн элементов будет иметь оверхед 32 мегабайта.
– ArrayList на 1млн элементов, с capacity, увеличенной в полтора раза, будет иметь оверхед в 4 мегабайта.

Для 64bit JVM с включённым сжатием указателей получим на каждый элемент:

objectHeader.classRef = 4
+ objectHeader.mark = 8 // это поле всё равно будет 8 байт на 64bit JVM
+ object.element = 4
+ object.previous = 4
+ object.next = 4
= 24 bytes per node
/ object.element = 4
= 6x

— уже в шесть раз больше. Вот так сжали… )
Понятно, что в абсолютных значения оверхед будет меньше:
– LinkedList на 1млн элементов будет иметь оверхед 20 мегабайт.
– ArrayList на 1млн элементов, с capacity, увеличенной в полтора раза, будет иметь оверхед 2 мегабайта.

А ты собрался много данных в LinkedList загружать.
1млрд элементов:
LL — +20 гигабайт с сжатием, а фактически, думаю, хип перевалит за 32 гига (ведь у нас ещё есть сами элементы и данные в них), и JVM отключит сжатие указателей и мы получим 32 гига на одни только ноды LinkedList'а, не считая ещё самих элементов и данных в них.
AL — +2 гига с сжатием. Даже под реаллокации ещё достаточно места до 32-хгигабайтного порога отключения сжатия.
Удачи тебе с LinkedList'ом в этом деле.

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

[korvin]

applegame, не понимаю, почему у тебя front и back возвращают payload, а не next и prev соответственно.

И как пройти по такому списку вперёд-назад и наоборот? Типа

void forward(const DList!Int l) {
    writeln("-- forward");
    if (l.empty()) {
        return;
    }
    
    writeln(l.front);
    forward(l.popFront());
}
 
void backward(const DList!Int l) {
    writeln("-- backward");
    if (l.empty()) {
        return;
    }
    
    writeln(l.back);
    backward(l.popBack());
}
 
void forwardBackward(const DList!Int l) {
    writeln("-- forwardBackward");
    if (l.empty()) {
        return;
    }
    
    writeln(l.front);
    
    const next = l.popFront();
    
    if (next.empty()) {
        backward(l);
    } else {
        forwardBackward(next);
    }
}
 
void backwardForward(const DList!Int l) {
    writeln("-- backwardForward");
    if (l.empty()) {
        return;
    }
    
    writeln(l.back);
    
    const prev = l.popBack();
    
    if (prev.empty()) {
        forward(l);
    } else {
        backwardForward(prev);
    }
}

вызов forwardBackward должен напечатать (условно)

1
2
3
4
3
2
1

через pop*-методы так не работает.

И вот ещё важный момент: в односвязном ленивом списке суть не в ленивости элементов, а в ленивости построения самого списка (т.е. хвоста), поэтому возможно задать бесконечный список и работать с ним, используя как генератор/inputstream.

Каноничный бесконечный ленивый список чисел фибоначчи на Хаскелле задаётся так:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Напечатать первые 10 чисел:

print $ take 10 fibs

https://ideone.com/bB92Nu

На Scheme моя реализация работает также, без модификаций: https://ideone.com/ysmTzd

На Java чуть сложнее из-за более статических пространств имён, поэтому приходится использовать небольшой костыль Cell, но никаких модификаций самой реализации списка не требуется, и все дополнительные функции (zip, take) реализуются также, как в Haskell и Scheme и всё работает: https://ideone.com/K4Z9QW

Хотя, можно обойтись и без Cell, используя просто саму функцию: https://ideone.com/DDjz1i

Соответственно ленивым у тебя должен быть не столько payload, сколько next и prev.

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

[sergioK]

Цитата korvin @ 21.04.21, 07:20

Это у тебя полное непонимание того, как работает JVM, память и процессор.

Linked List никуда не умер и нужен для вполне конкретный целей,
хватит тут теории разводить,с умным видом, JVM тут ыообще не причем, он и в STL есть,


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

Цитата korvin @ 22.04.21, 00:31

Ах да, ты ещё забыл, что у объекта Node в LinkedList'е помимо 3-х ссылок (elem, prev, next) есть ещё и object header, который в Java довольно жирный.

Я ничего не забыл, лишних 24 байта, не надо меня тут учить data structure ,

Добавлено 22.04.21, 04:26

Цитата korvin @ 22.04.21, 00:31

1) растёт на константное значение, что при большом количестве операций добавления требует больше реаллокаций и мене эффективно, чем ArrayList
2) synchronized, а значит ещё и имеет оверхед на lock/unlock на каждую операцию, даже если это не нужно, т.е. в большинстве юз-кейсов.

1) Ты сам реализуешь так как тебе нужно, теоретик млин
2) Если не подходит для данной задачи не используй, то что
в ArrayList insureCapacity private - чистой воды косяк,

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

[kopilov]

Цитата sergioK @ 22.04.21, 04:10

Linked List никуда не умер и нужен для вполне конкретный целей,
Я ничего не забыл, лишних 24 байта, не надо меня тут учить data structure

Это прекрасно, а как с джунами в итоге поступили? И один ли ты кул гай д`Артаньян?

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

[korvin]

Цитата sergioK @ 22.04.21, 04:10

хватит тут теории разводить,с умным видом

Какие теории, болезный? Я тебе вон бенчмарк скинул с твоим «практическим» примером, загрузить большое, неизвестное число объектов, где по-твоему нужно LinkedList использовать, а оказалось — не нужно.

Цитата sergioK @ 22.04.21, 04:10

JVM тут ыообще не причем, он и в STL есть,

1) во-первых, JVM тут при том, что с неё начался разговор.
2) во-вторых: https://www.youtube.com/watch?v=YQs6IC-vgmo

Цитата sergioK @ 22.04.21, 04:10

Я ничего не забыл, лишних 24 байта, не надо меня тут учить data structure ,

Ты прав, тут — не надо. Тебе бы в университет вернуться, знания подтянуть. А потом на работу нормальную устроиться джуном, практического опыта набраться. А то поназагружают миллиарды объектов в LinkedList, а потом в OutOfMemory долбятся, псевдопрактики, блин.

Цитата sergioK @ 22.04.21, 04:10

1) Ты сам реализуешь так как тебе нужно

А на практике никак не нужно. Ни при каких обстоятельствах.

Цитата sergioK @ 22.04.21, 04:10

2) Если не подходит для данной задачи не используй

Спасибо, капитан. Только он ни для какой задачи не нужен.

Цитата sergioK @ 22.04.21, 04:10

в ArrayList insureCapacity private - чистой воды косяк,

Чё, серьёзно? https://docs.oracle.com/javase/8/docs/api/j...reCapacity-int-

Цитата

public void ensureCapacity(int minCapacity)

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

[applegame]

Цитата korvin @ 21.04.21, 22:21

на второй странице.

Несколько дней споришь, а когда загнали в угол, ты внезапно нашел лазейку: оказывается ты имел ввиду, что нельзя "просто" создать. А "сложно" можно? А 100 строк это "просто" или "сложно"?
Ну ладно, главное, что согласился в конце-концов.

Цитата korvin @ 21.04.21, 22:21

С полным копированием можно что угодно сделать иммутабельным

ЧТД.

Цитата korvin @ 21.04.21, 22:21

Э-э… у тебя раздвоение личности? Я тебя спросил, какая операция там ленивая, ты ответил «print». print — это функция, т.е. ты же и назвал её ленивой

У тебя что-то с логикой. Никаких о каких ленивых функциях я не говорил. Функция не бывает ленивой, бывает ленивое выполнение функции. И в твоем примере на хаскеле, выполнение функции print как раз таки ленивое, о чем я и говорил. Согласен с претензией, что я неточно выразился говоря о ленивых операциях над элементами списка. Точнее было сказать: ленивое вычисление значений элементов списка, которое, в свою очередь, может быть, а может и не быть операцией над элементами другого списка.

Цитата korvin @ 21.04.21, 22:21

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

Конечно недостаточно. Двусвязные списки по производительности не будут отличаться от односвязных на операциях добавления/удаления в начало списка и итерации, при прочих равных. Потому что двусвязный список, по сути, включает в себя односвязный. Разве что памяти требует больше. Впрочем, XOR-списки никто не отменял.
Порывшись немного в интернетах на тему почему же LinkedList в Java умудряется сливать ArrayList и даже ArrayDeque на операциях добавления миллионов элементов, я прихожу к выводу, что это связано с какой-то наивной реализацией этого списка и особенностями работы JVM. И есть все основания полагать, что односвязный список реализованный также наивно, будут работать точно также плохо.

Цитата korvin @ 21.04.21, 22:21

Во-первых, односвязный список можно реализовать по-разному:
– интрузивный или не интрузивный
– закрытый (объект-контейнер с внутренним приватным списком нод и предоставляющий доступ к элементов только описанными методами, инкапсулирующий манипуляции над нодами) или открытый (просто создаются сразу сами объекты нод)

Ну и какой же из вариантов имел в ввиду автор говоря о списках полезных в C? О чем ты вообще тут толкуешь? Автор ни словом ни обмолвился ни о деталях реализации, даже просто оптимизацию не упомянул. Может он вообще не разбирается в этом? Кстати, интересно, в Java (JVM) возможны интрузивные списки? Ну и что там "во-вторых"?

Цитата korvin @ 21.04.21, 22:21

Он именно так и написал, но ты предпочёл поСПГСить.

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

Цитата korvin @ 21.04.21, 22:21

Вопрос: если ты не манипулируешь нодами, переставляя их, то нафига тебе связный список? Используй массив. А если манипулируешь, то вся эта изначальная локальность пойдёт лесом на хоть сколько-нибудь большом списке.

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

Цитата korvin @ 21.04.21, 22:21

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

Я говорил именно о поддержке мутабельности, а не о поддержке императивности. Мутабельность и императивность - ортогональные сущности. F# - императивный язык? А OCaml? А Erlang/Elixir? Тема для отдельного холивара.

[korvin]

Цитата applegame @ 22.04.21, 08:33

ЧТД.

Доказать, что можно реализовать любую бесполезную фигню? Ну, молодец, важное доказательство.

Цитата applegame @ 22.04.21, 08:33

Впрочем, XOR-списки никто не отменял.

Цитата

Используется довольно редко, так как существуют хорошие альтернативы, как, например, развёрнутый связный список.

Ясно-понятно.

Цитата applegame @ 22.04.21, 08:33

что это связано с какой-то наивной реализацией

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

Цитата applegame @ 22.04.21, 08:33

Автор ни словом ни обмолвился ни о деталях реализации

Наконец-то до тебя дошло. Может, теперь ты прекратишь что-то додумывать?

Цитата applegame @ 22.04.21, 08:33

Кстати, интересно, в Java (JVM) возможны интрузивные списки?

Конечно. Пример нужен?

Цитата applegame @ 22.04.21, 08:33

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

К вывод «он именно так и написал» не нужно приходить, это не вывод, а значение-по-умолчанию, как синие занавески. Бритва Оккама же.

Цитата applegame @ 22.04.21, 08:33

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

Ну вот, а LL прямой доступ к ноде не даёт, только линейный поиск с начала, что в итоге намного дороже, чем реаллокация в AL: https://www.youtube.com/watch?v=Y4XkWSAm2XU

Цитата applegame @ 22.04.21, 08:33

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

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

Цитата applegame @ 22.04.21, 08:33

Мутабельность и императивность - ортогональные сущности

Э, нет. Вся суть императивного программирования в прямом и явном изменении (мутировании) состояния. Это оно и есть, то, что ты хочешь сказать.

Цитата applegame @ 22.04.21, 08:33

F# - императивный язык? А OCaml?

Это «мультипарадигмальные» языки, поддерживающие ФП, ООП, ИП. В общем-то как и многие современные/популярные ЯП.

[applegame]

Цитата korvin @ 22.04.21, 02:05

applegame, не понимаю, почему у тебя front и back возвращают payload, а не next и prev соответственно.

Потому что front - это head. Он возвращает значение первого элемента в списке. back - тоже самое с конца.

Цитата korvin @ 22.04.21, 02:05

через pop*-методы так не работает.

У меня была ошибка в коде, вот исправленная версия: https://glot.io/snippets/fxx0z9kiam

Скрытый текст

import std.stdio;
 
struct Int {
    int value;
    Int opBinary(string op: "+")(Int other) const {
        writefln("%s + %s = %s", value, other.value, value + other.value);
        return Int(value + other.value);
    }
}
 
void main() {
    const l0 = DList!Int();
    const l1 = l0.append(
        Int(1) + Int(1),
    );
    const l2 = l1.append(
        Int(2) + Int(2),
        Int(3) + Int(3),
        Int(4) + Int(4)
    );
    writeln(l2.popFront().front);
}
 
struct DList(T) {
    struct Node {
        T delegate() payload;
        Node* prev, next;
    }
 
    private Node* m_first, m_last;
 
    bool empty() const { return m_first == null; }
    T front() const { assert(!empty); return m_first.payload(); }
    T back() const { assert(!empty); return m_last.payload(); }
    const(DList) popFront() const {
        assert(!empty);
        return m_first == m_last ? const DList() : const DList(m_first.next, m_last);
    }
    const(DList) popBack() const {
        assert(!empty);
        return m_first == m_last ? const DList() : const DList(m_first, m_last.prev);
    }
 
    const(DList) append(ARGS...)(lazy ARGS args) const {
        auto list = dup();
        static foreach(arg; args) {
            if(list.empty) {
                list.m_first = list.m_last = new Node(&arg);
            } else {
                list.m_last.next = new Node(&arg, list.m_last);
                list.m_last = list.m_last.next;
            }
        }
        return list;
    }
 
    private DList dup() const {
        auto list = DList();
        if(!empty) {
            auto prev = new Node(m_first.payload);
            list.m_first = prev;
            const(Node)* cur = m_first.next;
            while(cur != null && cur != m_last) {
                auto node = new Node(cur.payload, prev);
                prev.next = node;
                prev = node;
                cur = cur.next;
            }
            list.m_last = prev;
        }
        return list;
    }
}

Цитата korvin @ 22.04.21, 02:05

И как пройти по такому списку вперёд-назад и наоборот?

Вот так? https://glot.io/snippets/fxx116i54y

Скрытый текст

import std.stdio;
 
void forward(const DList!int l) {
    if (l.empty()) return;
    writeln(l.front);
    forward(l.popFront());
}
 
void backward(const DList!int l) {
    if (l.empty()) return;
    writeln(l.back);
    backward(l.popBack());
}
 
void forwardBackward(const DList!int l) {
    forward(l);
    backward(l.popBack());
}
 
void backwardForward(const DList!int l) {
    backward(l);
    forward(l.popFront());
}
 
void main() {
    const list = DList!int().append(1, 2, 3, 4);
    writeln("forwardBackward");
    forwardBackward(list);
    writeln("backwardForward");
    backwardForward(list);
}
 
struct DList(T) {
    struct Node {
        T delegate() payload;
        Node* prev, next;
    }
 
    private Node* m_first, m_last;
 
    bool empty() const { return m_first == null; }
    T front() const { assert(!empty); return m_first.payload(); }
    T back() const { assert(!empty); return m_last.payload(); }
    const(DList) popFront() const {
        assert(!empty);
        return m_first == m_last ? const DList() : const DList(m_first.next, m_last);
    }
    const(DList) popBack() const {
        assert(!empty);
        return m_first == m_last ? const DList() : const DList(m_first, m_last.prev);
    }
 
    const(DList) append(ARGS...)(lazy ARGS args) const {
        auto list = dup();
        static foreach(arg; args) {
            if(list.empty) {
                list.m_first = list.m_last = new Node(&arg);
            } else {
                list.m_last.next = new Node(&arg, list.m_last);
                list.m_last = list.m_last.next;
            }
        }
        return list;
    }
 
    private DList dup() const {
        auto list = DList();
        if(!empty) {
            auto prev = new Node(m_first.payload);
            list.m_first = prev;
            const(Node)* cur = m_first.next;
            while(cur != null && cur != m_last) {
                auto node = new Node(cur.payload, prev);
                prev.next = node;
                prev = node;
                cur = cur.next;
            }
            list.m_last = prev;
        }
        return list;
    }
}

[applegame]

Цитата korvin @ 22.04.21, 09:05

Доказать, что можно реализовать любую бесполезную фигню? Ну, молодец, важное доказательство.

А что поделаешь? В холиварах только и делаем, что занимаемся "важными" доказательствами.

Цитата korvin @ 22.04.21, 09:05

Используется довольно редко, так как существуют хорошие альтернативы, как, например, развёрнутый связный список.

Да, хорошая альтернатива. Я даже полагал, что ArrayDeque как раз и реализован как unrolled list, поэтому и уделывает LinkedList аки тузик грелку даже на массовом добавлении элементов:

Цитата applegame @ 11.04.21, 10:19

Но есть серьезное подозрение, что внутри этого ArrayDeque используется, сюрприз-сюрприз, двусвязный список массивов Может даже тот самый LinkedList.

Но реальность оказалась гораздо хуже

Цитата korvin @ 22.04.21, 09:05

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

Прямая, в лоб, без каких-либо оптимизаций, вроде кеширования нод или списка массивов (unrolled list). То есть тупо аллоцируем ноды по одной с двумя указателями.

Цитата korvin @ 22.04.21, 09:05

Наконец-то до тебя дошло. Может, теперь ты прекратишь что-то додумывать?

Короче, эта ветка бессмысленна и неинтересна. Я считаю, что автор сморозил ерунду, ты нет. Предлагаю на этом остановиться.

Цитата korvin @ 22.04.21, 09:05

Конечно. Пример нужен?

Не нужен. Я подозревал, что все объекты в Java (кроме примитивных типов конечно), всегда имеют ссылочную семантику, но, видимо, это не совсем так.

Цитата korvin @ 22.04.21, 09:05

Э, нет. Вся суть императивного программирования в прямом и явном изменении (мутировании) состояния. Это оно и есть, то, что ты хочешь сказать.

Не согласен. Совсем. Тот же Elixir тотально иммутабелен, но содержит изрядную долю императивщины. Я считаю, что фундаментальный признак императивности - последовательное выполнение списка действий. Википедия похоже считает также Императивное программирование. ИП часто сопровождается мутабельностью, но это не является обязательным признаком.

Если уж совсем уйти в абстрактную философию, то можно сказать, что главное отличие ФП от ИП - это течение времени. В ФП - течение времени не является чем-то особенным, просто еще одна координатная ось. А в ИП направление движения времени фундаментально: вот эта команда выполнится ПОСЛЕ вот этой.
Мы живем в мире, в котором время постоянно течет в одном направлении. Именно поэтому человеческое мышление императивно, именно поэтому база наших компьютеров императивна, именно поэтому ФП ломает мозг среднестатистическому человеку, и именно поэтому люди придумывают всякие монады, чтобы увязать свои розовые ФП-мечты с реальным императивным миром.

[korvin]

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

Я даже полагал, что ArrayDeque как раз и реализован как unrolled list, поэтому и уделывает LinkedList аки тузик грелку даже на массовом добавлении элементов:

Ну, он не уделывает прям как тузик, чуть хуже ArrayList'а вроде получается, я уже удалил результаты с ArrayDeque, могу восстановить, но не думаю, что это настолько интересно.

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

Не нужен. Я подозревал, что все объекты в Java (кроме примитивных типов конечно), всегда имеют ссылочную семантику, но, видимо, это не совсем так.

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

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

Википедия похоже считает также Императивное программирование.

Цитата

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

https://en.wikipedia.org/wiki/Imperative_programming :

Цитата

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

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

Именно поэтому человеческое мышление императивно, именно поэтому база наших компьютеров императивна, именно поэтому ФП ломает мозг среднестатистическому человеку, и именно поэтому люди придумывают всякие монады, чтобы увязать свои розовые ФП-мечты с реальным императивным миром.

Чушь, но это уже точно отдельный холивар.

Вот, собственно, добавил в бэнчмарк «сырой» открытый двусвязный список:

Скрытый текст

public final class OpenLinkedList<T> {
 
    public static <T> OpenLinkedList<T> node(T data) {
        return new OpenLinkedList<>(data, null, null);
    }
 
    private T data;
    private OpenLinkedList<T> prev;
    private OpenLinkedList<T> next;
 
    private OpenLinkedList(T data, OpenLinkedList<T> prev, OpenLinkedList<T> next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
 
    public T data() {
        return data;
    }
 
    public OpenLinkedList<T> prev() {
        return prev;
    }
 
    public OpenLinkedList<T> next() {
        return next;
    }
 
    public void setPrev(OpenLinkedList<T> list) {
        this.prev = list;
    }
 
    public void setNext(OpenLinkedList<T> list) {
        this.next = list;
    }
}

Тестируемый код:

    public static Object openLinkedList(int items) {
        if (items <= 0) {
            return null;
        }
        var list = OpenLinkedList.node(0);
        for (int i = 1; i < items; i++) {
            final var node = OpenLinkedList.node(i);
            list.setNext(node);
            node.setPrev(list);
            list = node;
        }
        return list;
    }

Результат:

Benchmark                     (itemsToAdd)          (type)  Mode  Cnt      Score       Error  Units
CollectionsBenchmark.addMany          1000      LinkedList  avgt   15      4.823 ±     0.935  us/op
CollectionsBenchmark.addMany          1000       ArrayList  avgt   15      3.642 ±     0.095  us/op
CollectionsBenchmark.addMany          1000  OpenLinkedList  avgt   15      4.012 ±     0.072  us/op
 
CollectionsBenchmark.addMany        100000      LinkedList  avgt   15    638.813 ±   409.703  us/op
CollectionsBenchmark.addMany        100000       ArrayList  avgt   15    350.063 ±    10.558  us/op
CollectionsBenchmark.addMany        100000  OpenLinkedList  avgt   15    599.069 ±   331.634  us/op
 
CollectionsBenchmark.addMany      10000000      LinkedList  avgt   15  61113.971 ± 16824.651  us/op
CollectionsBenchmark.addMany      10000000       ArrayList  avgt   15  56662.442 ±  2182.296  us/op
CollectionsBenchmark.addMany      10000000  OpenLinkedList  avgt   15  65001.029 ± 15023.551  us/op

Как видно, связный список можно использовать только если ты
[MODE=Петросян]
разрабатываешь серьёзный банковский софт для Société Générale
[/MODE]

[applegame]

Цитата korvin @ 22.04.21, 02:05

И вот ещё важный момент: в односвязном ленивом списке суть не в ленивости элементов, а в ленивости построения самого списка (т.е. хвоста), поэтому возможно задать бесконечный список и работать с ним, используя как генератор/inputstream.

Ну я бы не назвал это односвязными списками. Строго говоря, это вообще не списки. ЕМНИП, каноническое определение списка в computer science включает в себя его конечность. А то, о чем ты говоришь это stream или infinite sequence. Коллекция элементов отсутствует как таковая. Связный список - это просто одна из реализаций списков, а не внешний интерфейс.

Цитата korvin @ 22.04.21, 02:05

Каноничный бесконечный ленивый список чисел фибоначчи на Хаскелле задаётся так:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Напечатать первые 10 чисел:

print $ take 10 fibs

Это просто реккурентная функция обернутая в интерфейс списка, а не связный список. В D такое пишется, на мой взгляд, понятнее:
https://glot.io/snippets/fxx3k64atg

auto fibs = recurrence!((a, n) => a[n-1] + a[n-2])(1, 1);
writeln(fibs.take(10));

Цитата korvin @ 22.04.21, 02:05

Соответственно ленивым у тебя должен быть не столько payload, сколько next и prev.

Ну что значит "должен"? Ленивые вычисления - это всего лишь вычисления отложенные на потом. Никакой магии. Я пошел по самому очевидному для меня пути.