Добавить любой RSS - источник (включая журнал LiveJournal) в свою ленту друзей вы можете на странице синдикации.
Исходная информация - http://forum.sources.ru. Данный дневник сформирован из открытого RSS-источника по адресу http://forum.sources.ru/yandex.php, и дополняется в соответствии с дополнением данного источника. Он может не соответствовать содержимому оригинальной страницы. Трансляция создана автоматически по запросу читателей этой RSS ленты. По всем вопросам о работе данного сервиса обращаться со страницы контактной информации.[Обновить трансляцию]
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.
Каноничный бесконечный ленивый список чисел фибоначчи на Хаскелле задаётся так:
На Java чуть сложнее из-за более статических пространств имён, поэтому приходится использовать небольшой костыль Cell, но никаких модификаций самой реализации списка не требуется, и все дополнительные функции (zip, take) реализуются также, как в Haskell и Scheme и всё работает: https://ideone.com/K4Z9QW
ArrayList умножает память на 3/2 и перегрузить это нельзя в отличии от вектора,
Только вектор
1) растёт на константное значение, что при большом количестве операций добавления требует больше реаллокаций и мене эффективно, чем ArrayList
2) synchronized, а значит ещё и имеет оверхед на lock/unlock на каждую операцию, даже если это не нужно, т.е. в большинстве юз-кейсов.
Ах да, ты ещё забыл, что у объекта 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'ом в этом деле.
Ну и где тут преимущества LinkedList на добавление неизвестного заранее количества элементов?
С первыми двумя GC LinkedList заметно сливает, со вторыми ± одинаково получается.
Кортеж это пример иммутабельной структуры требующей полного копирования для изменения. Кейсы тут вообще не в тему, ты же ни о каких кейсах не упоминал, когда заявил:
Ты таки согласен, что иммутабельный двусвязный список может быть реализован, с полным копированием при добавлении/изменении? Ответь прямо без юления.
С полным копированием можно что угодно сделать иммутабельным, только это не «просто». Тебе же не нужно показывать, как делается иммутабельный односвязный список?
Вот сам придумываешь какие-то странные термины, что такое "ленивая функция"? Чем она отличается от "неленивой"?
Э-э… :facepalm: у тебя раздвоение личности? Я тебя спросил, какая операция там ленивая, ты ответил «print». print — это функция, т.е. ты же и назвал её ленивой
Ну давай вернемся. Я с самого начала пытаюсь выяснить почему LinkedList, по словам жаба-селебрити, "совсем другое дело". Но пока от тебя так и не услышал ответа. Ты говооришь о чем угодно, кроме сути. Может таки ответишь вместо переливания в из пустого в порожнее?
Я тебе уже давно ответил, даже три пункта перечислил, с которыми ты же согласился, написав, что «Возможно, что LinkedList - просто корявая реализация двусвязного списка, тут спорить не буду ибо не знаю. Мои двусвязные списки (не на жабе, конечно) используют пулы, и добавляют по два указателя к каждой ноде.» (3-я страница). :facepalm: проверь память, я серьёзно.
Причём, вот ещё, например, кейс, вроде бы подходящий для двусвязного списка: LRU-кэш, но там нужно иметь ссылки на ноды, чтобы эффективно переставлять их в начало списка, но LinkedList не предоставляет возможности иметь ссылку на ноду, т.е. для этого кейса не подходит.
Какое принципиальное отличие от односвязных списков в Scheme
двусвязность и закрытость для тебя не достаточно принципиальные отличия? Не знаю тогда. Может для тебя вообще все динамические структуры «на одно лицо»?
Односвязный список и в Африке односвязный, какая разница это C или Scheme?
Во-первых, односвязный список можно реализовать по-разному:
– интрузивный или не интрузивный
– закрытый (объект-контейнер с внутренним приватным списком нод и предоставляющий доступ к элементов только описанными методами, инкапсулирующий манипуляции над нодами) или открытый (просто создаются сразу сами объекты нод)
Даю подсказку: ноды еще можно не по одной аллоцировать, а сразу непрерывными блоками по несколько штук, причем можно сразу и место для данных аллоцировать внутри ноды (интрузивные списки, о которых я писал ранее, а после и ты)
Вопрос: если ты не манипулируешь нодами, переставляя их, то нафига тебе связный список? Используй массив. А если манипулируешь, то вся эта изначальная локальность пойдёт лесом на хоть сколько-нибудь большом списке.
Нет. Что мешает, написал выше. Ты, конечно, можешь просто взять мой пример ленивого односвязного списка для Java и сделать двусвязный. Ну или с нуля на твоём любимом языке.
Сделал на D. И синтаксический сахар есть.
1. Вместо head - front, вместо tail - popFront. Также есть back и popBack - аналоги для другого конца списка.
Список иммутабелен. Добавление элементов (append) создает копию списка, popFront и popBack не создают копию.
Для демонстрации иммутабельности, добавляю не сразу все элементы к списку, а за два раза. Обратите внимание, что все переменные в main константные, кастов в программе нет, так что они реально иммутабельные.
Элементы вычисляются лениво. Для подтверждения этого создал структуру Int, иммитирующую обычное целое, с перегруженным оператором сложения, который печатает в консоль текст подтверждающий, что сложение реально произошло.
В данной программе вычисляется только второй элемент списка, так как именно он выводится на экран.
Тестировал мало, возможны ошибки.
Состоятелен, потому что юз-кейсы у списка и кортежа принципиально разные.
Кортеж это пример иммутабельной структуры требующей полного копирования для изменения. Кейсы тут вообще не в тему, ты же ни о каких кейсах не упоминал, когда заявил:
Если двусвязный список сделать встроенным в язык типом, то он вполне может быть персистентным, а при добавлении новых элементов просто копировать его целиком. Бесполезно, но возможно.
Ты таки согласен, что иммутабельный двусвязный список может быть реализован, с полным копированием при добавлении/изменении? Ответь прямо без юления.
Очевидно, 1) print здесь элемент списка, а не «операция» над элементом списка, 2) в примерах на Scheme и Java print не является ленивой функцией.
Ну если уж доёбываться, то элемент списка не сам print а результат каррирования print. Можно переделать твой пример, чтобы была операция над элементами: https://ideone.com/hPXX7o
Суть не меняется, ленивый не список, а вычисления.
Вообще-то съезжать в сторону начал ты с самого начала.
Ну давай вернемся. Я с самого начала пытаюсь выяснить почему LinkedList, по словам жаба-селебрити, "совсем другое дело". Но пока от тебя так и не услышал ответа. Ты говооришь о чем угодно, кроме сути. Может таки ответишь вместо переливания в из пустого в порожнее?
Нельзя, из-за обратной ссылки на предыдущий элемент. Ты не сможешь даже сконструировать такой список.
Ты явно путаешь принципиальную возможность создать такой список и возможность создать его средствами самого иммутабельного ФП-языка. Повторю еще раз: двусвязный список при желании можно встроить в любой иммутабельный ФП язык. В Erlang это можно сделать например при помощи NIF: создаем сначала мутабельный список, заполняем ноды данными, после чего делаем иммутабельным. В общем-то аналогично кортежам, которые в том же эрланге являются, по сути, иммутабельными массивами.
Ленивость же, как я говорил, вообще ортогональна всему этому. В том же D, я могу сделать тебе ленивый рендж, хоть односвязный (ForwardRange), хоть двусвязный (BidirectionalRange), хоть вообще массив (RandomAccessRange). Хошь мутабельный, хошь иммутабельный.
Вопрос другой: как из этой фразы можно было сделать вывод, что автор имел в виду совершенно одинаковые структуры данных в двух сильно разных языках?
Односвязный список и в Африке односвязный, какая разница это C или Scheme? Можно еще говорить о разных степенях оптимизации, но автор явно абстрагировался от этого, так как упомянул C, в котором вообще не существует какой-либо стандартной реализации списка. Если бы он скажем заявил, что-то вроде "не поймите неправильно, мне нравятся связные списки, они могут быть полезны, но вот LinkedList сделан через жопу, поэтому не используйте его", то это было бы логично. Возможно автор именно это и имел в виду, но сказал нечто совершенно иное.
Вот, например, в org.apache.commons есть двусвязный список с этим твои кэшированием нод
Молодец, просвещайся дальше. Даю подсказку: ноды еще можно не по одной аллоцировать, а сразу непрерывными блоками по несколько штук, причем можно сразу и место для данных аллоцировать внутри ноды (интрузивные списки, о которых я писал ранее, а после и ты). Особо упоротые оптимизаторы, длину этих блоков еще и с размером строки кэша процессора норовят выровнять.
Допустим, есть N ящиков. Перемещения без сдвигания ящиков особо не важны и в каждой ситуации важно только, какие ящики и в какую сторону возможно сдвинуть, это - ключевые моменты. А если подумать, то наверняка можно ещё уменьшить кол-во ключевых моментов для перебора; что приходит в голову сразу: запретить двигать ящик обратно и вообще, запретить повторение ситуации. Тогда перебор точно до шахмат не дотянется и близко.
для реальных лабиринтов (10...100 ящиков) совершенно неактуально
Ну я не знаю - выше был "реальный" лабиринт с тремя ящиками. Лабиринтов на 100 ящиков я ещё не видел(если не считать старой игрухи, где много сокобанов были как бы объединены, но и там, ЕМНИП, нельзя было выкатывать ящики за экран)
Добавлено
Оу, там же указаны возможные пределы:
Цитата
На входе задана схема склада — прямоугольная сетка размером n x m (3 <= n, m <= 8).
- n не меньше трёх, вместо не больше! То есть, получается, предел возможного перебора определяется длиной строки:
Цитата
Длина строки не должна превышать 10000 символов.
- но каждый раз следующий символ выбирается не более чем из 4 вариантов.
Я таких ArrayList не один десяток написал , разных имплементаций ,
ArrayList умножает память на 3/2 и перегрузить это нельзя в отличии от вектора,
и это одна имлементация интерфэйса java.util.List другая это Linked List,
пользуешь когда не знаешь сколько элементов будет.
Саммерфилд QT4 Программирование GUI на С++
Бьерн Страуструп Язык программирования С++
М.Грабер SQL
Книги по С++ взаимозаменяемы.
Web-языки (Прохоренок Н.А. HTML, JavaScript, PHP и MySQ) - по желанию.
Ассемблер - нахер. Стандартную библиотеку - нахер (QT её заменяет).
Кормен Т. Алгоритмы: построение и анализ - нахер. Написано ужасно, непонятно ничего. Быстрее сам придумаешь алгоритм, чем поймёшь что имел в виду Кормен.
Хорошо. Давайте допустим, что я прочитал эти книги. Выучил все структуры данных, алгоритмы по Кормену, исключения выучил, констркуторы, STL. А как написать проект, который убедит того, кто будет принимать меня работу, что я не овощ в С++?
Славян: Там сложность растёт катастрофическими темпами! В SokoMind есть установка одного ящика. Где-то или видел или читал про возможность сделать установку двух ящиков. На современном железе (1 ПК) наверное можно сделать 3...4 ящика. На каком-то суперкомпьютере можно попробовать выйти на 5...7 штук. Но задача довольно быстро становится сложнее шахмат, так что для реальных лабиринтов (10...100 ящиков) совершенно неактуально, увы. :yes-sad:
Как предложите писать графические проги на С++ кроме как с помощью QT ?
Какое это имеет отношение к совету не использовать стандартную библиотеку? QT вяжет по рукам и ногам своей инфраструктурой. Это отдельный фреймворк, использующий кастрированный C++ в качестве бак-энда. Давай ещё посоветуй кому-нить использовать Delphi в режиме Object Pascal.
При том, что твой аргумент, что двусвязный список нельзя сделать иммутабельным, потому что надо его целиком копировать при, например, добавлении элемента несостоятелен.
Состоятелен, потому что юз-кейсы у списка и кортежа принципиально разные.
Суть в том, что двусвязный список тоже можно сделать с поддержкой ленивых вычислений (или просто ленивым, если тебе так хочется), не вижу никаких препятствий.
Нельзя, из-за обратной ссылки на предыдущий элемент. Ты не сможешь даже сконструировать такой список.
Я думаю, ты просто некомпетентен в этой области. Почитай про мемори пулы и вообще про низкоуровневую оптимизацию работы с памятью, инфа на эту тему есть.
Я думаю, что ты некомпетентен, но думаешь, будто компетентен. Вот и скинь ссылку на «правильную» с твоей точки зрения инфу.
А лучше сразу свой связный список с мемори пулом и примером юз-кейса для тестирования/замера.
Ну и если эти linked list так полезны в C, а LinkedList это "another matter entirely", то вероятно в Java должен существовать правильный linked list, аналогичный таковому в C и Scheme. Он существует?
В JDK — нет. В сторонних библиотеках коллекций — возможно.
По твоему мнению их можно сделать таковыми или нет? Если нет, то что именно мешает?
Нет. Что мешает, написал выше. Ты, конечно, можешь просто взять мой пример ленивого односвязного списка для Java и сделать двусвязный. Ну или с нуля на твоём любимом языке.
