Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 47
Простите, не понимаю. Если у каждого элемента может быть всего один дочерний, то это просто упорядоченный массив, и там удобно, когда элементы пронумерованы, а работа только через current / next / insert выглядит неудобной. Если это все же дерево, то вообще непонятно, как этими методами обойтись..
Простите, не понимаю. Если у каждого элемента может быть всего один дочерний, то это просто упорядоченный массив, и там удобно, когда элементы пронумерованы, а работа только через current / next / insert выглядит неудобной.
Про Кнута, надо понимать, Вам не рассказывали :-)
Массив — это массив. А список это список. Вещи разные, каждая для своей цели.
Вот представте — у вас массив на 100 элементов. И нужно вам добавить туда 101-й. И не просто добавить, а вставить между 63-м и 64-м элементами. Представьте к чему это приведет — realloc + memmove. И хорошо, если это 100 элементов, а не 100 000 или 1 000 000…
Нет, я понимаю, что есть фреймворк, там все это реализовано и все работает. Но надо же понимать что вы делаете и как ваши действия скажутся на производительности системы в целом.
Лирическое отступление про производительность и эффективность
Представим себе некий абстрактный банковский сервер. На нем крутится одновременно, ну, скажем, 1 000 разных процессов, которые реализуют 1 000 «сравнительно честных способов отъема денег у населения» (с) О.И.Бендер, турецкоподданный.
А еще у банка есть процессинг — тот самый, что обеспечивает возможность клиентам расплачиваться пластиковыми картами в магазине. С точки зрения сервера это некая внешняя система, которая посылает запросы, на каждый из которых нужно дать ответ, уложившись в таймаут (не уложишься в таймаут — клиенту не дадут расплатится пластиком в магазине т.к. «нет ответа от банка»).
И тут я, такой весь умный и прошаренный в использовании различных фреймворков (но абсолютно не интересующийся а как оно там внутри устроено — мне это не нужно), пишу еще один процесс, 1 001-й. Процесс сложный, объемный. Для облегчения своего труда я использую очень навороченный фреймворк с реализацией динамических массивов и всего такого. А массивы у меня огромные — несколько сотен тысяч элементов.
И все получается красиво и элегантно. И главное модно — самый крутой фреймворк использую.
Но при установке на прод вдруг выясняется, что в периоды пиковой нагрузки мой процесс начинает жрать ресурсы как не в себя. Что приводит к замедлению других 1 000 процессов и периодическому отваливанию процессинга по таймаутам. А в результате сотни тысячлеммингов клиентов, пытающихся расплатиься в магазине пластиком моего банка получают отлупы — «нет ответа от банка» и роются по карманам в поисках кеша, зовут на кассу всемогущую «Галю» для отмены покупок т.п.
В итоге вызывают меня, умного и прошаренного, на комиссию по инцидентам и спрашивают строго — считаю ли я свою квалификацию соответствующей занимаемой должности. Ибо инцидент, произошедший по моей вине, в пределе тянет на отзыв у банка лицензии ввиду «неисполнения обязательств перед клиентами» (а как минимум штраф от регулятора со многими нулями).
Пример утрирован и гипертрофирован, но толика смысла в нем есть.
А еще у банка есть процессинг — тот самый, что обеспечивает возможность клиентам расплачиваться пластиковыми картами в магазине. С точки зрения сервера это некая внешняя система, которая посылает запросы, на каждый из которых нужно дать ответ, уложившись в таймаут (не уложишься в таймаут — клиенту не дадут расплатится пластиком в магазине т.к. «нет ответа от банка»).
И тут я, такой весь умный и прошаренный в использовании различных фреймворков (но абсолютно не интересующийся а как оно там внутри устроено — мне это не нужно), пишу еще один процесс, 1 001-й. Процесс сложный, объемный. Для облегчения своего труда я использую очень навороченный фреймворк с реализацией динамических массивов и всего такого. А массивы у меня огромные — несколько сотен тысяч элементов.
И все получается красиво и элегантно. И главное модно — самый крутой фреймворк использую.
Но при установке на прод вдруг выясняется, что в периоды пиковой нагрузки мой процесс начинает жрать ресурсы как не в себя. Что приводит к замедлению других 1 000 процессов и периодическому отваливанию процессинга по таймаутам. А в результате сотни тысяч
В итоге вызывают меня, умного и прошаренного, на комиссию по инцидентам и спрашивают строго — считаю ли я свою квалификацию соответствующей занимаемой должности. Ибо инцидент, произошедший по моей вине, в пределе тянет на отзыв у банка лицензии ввиду «неисполнения обязательств перед клиентами» (а как минимум штраф от регулятора со многими нулями).
Пример утрирован и гипертрофирован, но толика смысла в нем есть.
Массивы хороши когда вы точно знаете сколько у вас будет элементов в пределе и знаете что вам нужен будет рандомный доступ к элементам.
В том же случае, когда заранее неизвестно будет у вас 100 элементов или 100 000 (или 1 000 000) и вы уверены, что рандомный доступ потом вам не потребуется — нужно будет сначала набрать массив элементов в порядке поступления, а потом пройти по нему от первого к последнему в процессе обработки (а может быть еще и удаляя обработанные элементы с освобождением памяти) — тут удобнее список.
Последовательное прохождение списка ничуть не сложнее чем прохождение массива:
ptr = list->first;
while (ptr != nullptr) {
// тут обрабатываем элемент
...
ptr = list->next;
}
или с удалением обработанных элементов
while ((ptr = list->first) != nullptr) {
// тут обрабатываем элемент
...
list->delete(first);
}
Преимущество списка в том, что затраты времени на добавление/удаление элемента абсолютно не зависят от количества элементов и положения нового элемента в списке
Если это все же дерево, то вообще непонятно, как этими методами обойтись..
Есть альтернатива деревьям, построенная на списках.
William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees
Очень мощный и эффективный алгоритм. Позволяет быстро искать нужный элемент в списке по ключу. Есть расширения алгоритма, добавляющие «виртуальный индекс» для каждого элемента.
Так что массивы — это массивы. А списки — это списки. И то и другое имеет свои плюсы и минусы, преимущества и недостатки. И свои области применения.
Вы знаете, спасибо за экскурс в основы программирования, но мне казалось — мы тут говорим об очень высокоуровневом языке, на котором ещё и будет легко писать.
И в таком случае мне всё равно, как там «под капотом» реализованы массивы, коллекции, слайсы, списки и прочие «объекты, реализующие интерфейс IEnumerable».
Из этой статьи вы совершенно не знаете, как это реализовано и как скажется на производительности в целом. Может, там под каждый элемент списка выделяется чанк в 16Кб, на всякий случай? ))
Даже если это именно список, не иметь возможности взять из него 5-й элемент, или элементы с 1-го по 5-й без дополнительных велосипедов — нонсенс. И это должно быть на уровне языка, а не фреймворка, особенно если задумываться-таки о производительности и эффективности.
И в таком случае мне всё равно, как там «под капотом» реализованы массивы, коллекции, слайсы, списки и прочие «объекты, реализующие интерфейс IEnumerable».
Но надо же понимать что вы делаете и как ваши действия скажутся на производительности системы в целом.
Из этой статьи вы совершенно не знаете, как это реализовано и как скажется на производительности в целом. Может, там под каждый элемент списка выделяется чанк в 16Кб, на всякий случай? ))
я понимаю, что есть фреймворк, там все это реализовано и все работает.
Даже если это именно список, не иметь возможности взять из него 5-й элемент, или элементы с 1-го по 5-й без дополнительных велосипедов — нонсенс. И это должно быть на уровне языка, а не фреймворка, особенно если задумываться-таки о производительности и эффективности.
Вы знаете, спасибо за экскурс в основы программирования, но мне казалось — мы тут говорим об очень высокоуровневом языке, на котором ещё и будет легко писать.
Постановка вопроса «а зачем списки когда есть массивы» подразумевает необходимость такого экскурса.
И в таком случае мне всё равно, как там «под капотом» реализованы массивы, коллекции, слайсы, списки и прочие «объекты, реализующие интерфейс IEnumerable».
Я привел пример что бывает когда «мне все равно как оно внутри устроено».
Нет, на определенном уровне и для определенных задач оно прокатывает. До поры до времени.
Из этой статьи вы совершенно не знаете, как это реализовано и как скажется на производительности в целом. Может, там под каждый элемент списка выделяется чанк в 16Кб, на всякий случай? ))
Жопа — самый универсальный интерфейс ибо через нее можно сделать абсолютно все.
Суть списка в его динамичности. Он всегда занимает ровно столько памяти, сколько нужно под хранение текущего количества элементов. А каждый элемент занимает ровно столько памяти, сколько нужно для хранения его данных + связей с соседями. В этом кардинальное отличие списка от массива.
Если вам надо хранить разнородные элементы:
целое 2 байта
целое 4 байта
целое 8 байт
вещественное 8 байт
строка от 1 байт и более
то элемент списка будет выглядеть так:
тип элемента (целое, вещественное, строка) — допустим, 1 байт
размер элемента — допустим, 4 байта
данные элемента — N байт
связи (следующий, предыдущий) — 4+4 байта
Итого, N + 13 байт
Если все то же запихивать в массив, то там все элементы должны быть одного размера. И тогда вы, во-первых, должны ограничить максимальный размер строки, в-вторых, хранить, скажем, 2 байта целого в элементе максимального размера.
Даже если это именно список, не иметь возможности взять из него 5-й элемент, или элементы с 1-го по 5-й без дополнительных велосипедов — нонсенс.
Способы есть. Другое дело, что в большинстве случаев это не нужно. Я лично достаточно широко использую обычные двусвязные списки там, где рандомный доступ к элементам не требуется. Например, когда нужно собрать большое количество данных из разных источников, а потом обработать их (так или иначе). Сначала добавляем все данные в конец списка, затем просто проходим от первого элемента к последнему.
Если мне нужен поиск по списку, я буду использовать SkipList для пар «ключ-данные». Обычно использую это для разного рода кешей (например, когда из одной и той же таблицы в разных местах и в разное время нужно читать по ключу примерно одни данные — единожды прочитанный ключ заносится в кеш и второй раз из таблицы уже не читается.
И это должно быть на уровне языка, а не фреймворка, особенно если задумываться-таки о производительности и эффективности.
Вот это совсем не факт. Ибо что там с производительностью на уровне языка тоже большой вопрос. Мне часто приходилось отказываться от универсальных реализаций на уровне разных фреймворков и библиотек в пользу собственной реализации под конкретную задачу именно потому что универсальная реализация в силу своей универсальности проигрывала частной, построенной с учетом специфики конкретной задачи.
Но у меня так сложилось, что все, что делал за последние 25+ лет, имело повышенные требования к эффективности и скорости. Порой на уровне паранойи.
Суть списка в его динамичности. Он всегда занимает ровно столько памяти, сколько нужно под хранение текущего количества элементов.
…
Если все то же запихивать в массив, то там все элементы должны быть одного размера.
Простите, а что мешает реализовать массивы так, чтобы «под капотом» это была просто последовательность указателей на данные произвольной длины? У вашего списка явная проблема — чтобы добраться до 1000 элемента, надо пройти всю цепочку, чтобы от этого избавиться — к нему надо добавлять индекс, в результате придём опять к массиву. Ваш SkipList, как я понимаю, примерно тем и занят?
Да, для массива целых чисел (и других данных или структур фиксированной длины) можно пытаться размещать сами данные подряд в памяти, а не указатели на них. Но тут начнутся проблемы с поиск подходящего куска подряд свободной памяти, и тут снова придётся возвращаться к индексу/массиву указателей.
Но мы говорили о высокоуровневом языке, где эти подробности и «подкапотное» излишне. А вот задача быстрой выборки нужных элементов очень частая. Поэтому я так удивился, что встроенных средств для этого нет.
Простите, а что мешает реализовать массивы так, чтобы «под капотом» это была просто последовательность указателей на данные произвольной длины?
Согласен. Ничего не мешает.
У вашего списка явная проблема — чтобы добраться до 1000 элемента, надо пройти всю цепочку
Да. Поэтому списки используются там, где не нужно «добираться до 1000-го элемента».
А массивы там, где заранее известно сколько будет элементов всего и известно, что время жизни элемента совпадает со временем жизни массива. Т.е. где не будет операции «удалить элемент 563, а потом вставить три элемента в начало списка».
Фактически на списках легко реализуются такие примитивы как стек или очередь. Надеюсь, знаете что это такое и зачем.
Ваш SkipList, как я понимаю, примерно тем и занят?
SkipList не мой. Чем он занят можно понять из оригинальной статьи автора алгоритма (это первая статья с описанием базового принципа, есть дальнейшее развитие алгоритма описанное как самим автором, так и другими людьми).
Работает очень быстро:
Среднее время вычислялось по 100 000 замерам.
Время в микросекундах. Разброс значений обусловлен отчасти вероятностным характером самого алгоритма, отчасти средой выполнения — сервер, на котором одно временно работает очень много процессов и загрузка которого постоянно меняется.
Да, для массива целых чисел (и других данных или структур фиксированной длины) можно пытаться размещать сами данные подряд в памяти, а не указатели на них. Но тут начнутся проблемы с поиск подходящего куска подряд свободной памяти, и тут снова придётся возвращаться к индексу/массиву указателей.
Проблемы с массивом начнутся сразу же, как только вам потребуется вставить 10001-й элемент в середину массива, рассчитанного на 10000 элементов.
Но мы говорили о высокоуровневом языке, где эти подробности и «подкапотное» излишне.
Увы, но как только вы столкнетесь с жесткими требованиями к эффективности, знания о том как это работает под капотом становятся весьма актуальными.
А вот задача быстрой выборки нужных элементов очень частая. Поэтому я так удивился, что встроенных средств для этого нет.
Частая. Согласен. Только в моих задачах потребность формулируется обычно так — «выбрать из списка строки, начинающиеся на 'ASKJHS'» (например). как тут может помочь массив — ума не приложу.
Что касается «встроенных средств» — не надо пихать в язык все подряд. А то кому-то потребуется список, а кому-то тройной эллиптический интеграл. Все эти вещи реализуются внешними библиотеками.
А вот сортированный список, построенный на алгоритме SkipList (модификация в том, что нет выделенного ключа — сами данные являются ключом) работает на ура.
Массивы хороши когда это захардкоженная таблица каких-то справочных значений (ну например, таблица предрассчитанных значений какой-то сложной функции где индекс массива является производной от агрумента).
А когда вам надо закешировать выборку из БД, выполненную по некоторому индексу, а потом искать в ней данные (вместо того, чтобы опять лезть в БД), тут массивы ну никак не помогут — ни размер выборки неизвестен, ни поиск по данному значению ключа в массиве неэффективен.
Т.е. опять — массив это массив, список это список. Разные сущности для разных задач.
Спасибо за такой развернутый ответ!
Единственное — не логичнее все же стек делать на базе массива? Как-то он проще кажется для такой задачи… или вы имеете в виду стек произвольной длины?
Единственное — не логичнее все же стек делать на базе массива? Как-то он проще кажется для такой задачи… или вы имеете в виду стек произвольной длины?
Ну тут от задачи зависит. Есть ситуации где максимальная глубина стека заранее известна — там массив будет проще (и эффективнее).
Если же максимальна глубина стека неизвестна (например, разбор некоторой математической формулы с переводом в обратную польскую нотацию для последующего ее вычисления) — предпочтительнее сделать стек на списке.
Аналогично с очередями (например, для батчмашины) — динамический список в котором новый элемент всегда добавляется в начало очереди, а берутся элементы всегда из конца очереди (и при этом удаляются). Такое применяется при распараллеливании обработки больших объемов данных.
Есть процесс-мастер. Он занимается формированиями пакетов-заданий на обработку. После старта мастер запускает несколько процессов-обработчиков и создает очередь заданий.
Задания формируются мастером и помещаются в начало очереди (т.е. добавление в начало списка). Каждый обработчик берет задание из конца очереди (при этом оно удаляется из очереди) и выполняет его. Следующий обработчик опять берет задание из конца и выполняет… Как выполнил задание — берет следующее и так далее, пока очередь не опустеет. На практике когда заданий больше нет, мастер выкладывает в очередь несколько (по количеству обработчиков) «заглушек» — пустых заданий.
Очередной обработчик берет из очереди задание, видит что это «заглушка» и завершает работу.
Мастеру остается только дождаться пока очередь не станет пустой (это значит что все задания выполнены, все «заглушки» получены и все обработчик завершили работу), удалить очередь и самому завершить работу.
На массивах такое тоже можно (организовав массив в виде кольцевого буфера), но придется еще контролировать наличие свободного места в массиве и держать индексы первого (куда добавлять новое задание) и последнего (откуда брать задание) элементов.
Впрочем, такая организация (кольцевой буфер) используется там, где память сильно ограничена (например, различные микроконтроллеры — те же очереди отправки пакетов на хост или приема пакетов от хоста — там такой подход оправдан).
Массив — непрерывная область памяти, отсюда и название. Элементы списка могут лежать вообще где угодно, но элементы знают о своих соседях (как — зависит от направленности списка).
Если хотя бы чуть чуть в С могете, то поймете, почему в массив добавить элемент дороже чем в список. И почему доступ к злементу списка дороже чем, из массива. Причем в обоих случаях стоимость прямо пропорциональна размеру.
Если хотя бы чуть чуть в С могете, то поймете, почему в массив добавить элемент дороже чем в список. И почему доступ к злементу списка дороже чем, из массива. Причем в обоих случаях стоимость прямо пропорциональна размеру.
Окей, но массив указателей — тоже массив?
Коротко — разумеется да.
Указатель — такая же область памяти как и любая другая переменная. У него есть стандартный размер — машинное слово — соответствующий разрядности адресной шины. Обычно, ширина адресной шины определяет размер машинного слова, например если ширина 64бит то и размер машинного слова будет 64бита, т.е. 8 байт.
Массив или список это способ хранения каких-либо данных одного размера, а не какая-то фича конкретного языка.
В случае массива, указатели будут лежать согласно Array Padding для вашего ЯП. В зависимости от реализации, они могут иметь выравнивание по наибольшему или по размеру машинного слова.
Со списком вы имеете разбросанные по памяти ноды из указателей, каждый из которых указывает на соседей и хранимое значение.
Указатель — такая же область памяти как и любая другая переменная. У него есть стандартный размер — машинное слово — соответствующий разрядности адресной шины. Обычно, ширина адресной шины определяет размер машинного слова, например если ширина 64бит то и размер машинного слова будет 64бита, т.е. 8 байт.
Массив или список это способ хранения каких-либо данных одного размера, а не какая-то фича конкретного языка.
В случае массива, указатели будут лежать согласно Array Padding для вашего ЯП. В зависимости от реализации, они могут иметь выравнивание по наибольшему или по размеру машинного слова.
Со списком вы имеете разбросанные по памяти ноды из указателей, каждый из которых указывает на соседей и хранимое значение.
У вашей реализации связного списка как минимум две проблемы:
1. Очень бедный api. Как найти элемент в списке? Как вставить значения перед текущим элементом? Как получить значение предыдущего/следующего элемента, не меняя указатель на текущий?
2. Очень плохо, что методы, обозначенные существительными, что-то меняют.
Да и вообще, путаница между существительными и глаголами сразу сводит на нет удобство читаемости языка. Вместо того, чтобы «легко читать» листинги, придётся заучивать нелогичный api.
1. Очень бедный api. Как найти элемент в списке? Как вставить значения перед текущим элементом? Как получить значение предыдущего/следующего элемента, не меняя указатель на текущий?
2. Очень плохо, что методы, обозначенные существительными, что-то меняют.
Да и вообще, путаница между существительными и глаголами сразу сводит на нет удобство читаемости языка. Вместо того, чтобы «легко читать» листинги, придётся заучивать нелогичный api.
1. Реализации пока нет (см. коммент ниже), в экспериментах это выглядело примерно так:
Примеры #2 и #3 выглядят симпатично но имеют некоторые нерешенные вопросы
2. first, next, prev, last это команды действия, передвигающий указатель на текущий элемент списка — current (фактически это указатель, работающий снаружи списка как property в экземпляре класса)
#1 Удаление элемента из списка, когда их может быть несколько (в императивном стиле)
INPUT str: STRING
list.last
WHILE list.current ~= NIL LOOP
IF list.current == str THEN list.remove ELSE list.prev ENDIF
REPEAT
#2 Вставка нового элемента перед текущим
list.prev.insert "new"
#3 Запомнить указатель на текущий элемент, перейти к первому элементу и вернуться обратно
LET p = list.link
list.first.next pПримеры #2 и #3 выглядят симпатично но имеют некоторые нерешенные вопросы
2. first, next, prev, last это команды действия, передвигающий указатель на текущий элемент списка — current (фактически это указатель, работающий снаружи списка как property в экземпляре класса)
Не очень понятен смысл реализации всего этого непосредственно в языке.
Тут сразу встанет вопрос — а почему в языке реализован список, но не реализованы деревья во всем их многобразии? Дальше кому-то захочется алгоритм, скажем, фильтра Калмана еще кому-то регрессию, хотя бы линейную и т.д. и т.п.
И что из всего этого тащить непосредственно в язык?
В моем понимании язык это некоторая база, которая позволяет делать все остальное. А вот это «все остальное» — это уже расширения в виде библиотек различной направленности.
Тут сразу встанет вопрос — а почему в языке реализован список, но не реализованы деревья во всем их многобразии? Дальше кому-то захочется алгоритм, скажем, фильтра Калмана еще кому-то регрессию, хотя бы линейную и т.д. и т.п.
И что из всего этого тащить непосредственно в язык?
В моем понимании язык это некоторая база, которая позволяет делать все остальное. А вот это «все остальное» — это уже расширения в виде библиотек различной направленности.
Язык, который мы используем определяет характер нашего мышления. Эффективный язык должен доносить сообщение адресату с минимумом затрат на формирование самого сообщения.
Для языка программирования целесообразно включить полный сет встроенных возможностей для целевого использования, следовательно, например, язык, предназначенный для расчетов с математической статистикой должен иметь все необходимые встроенные методы работы с ней, чтобы не искать фреймворки на стороне (в довесок возможно еще иметь конкуренцию фреймворков, риски поддержки) или программисту не собирать из кода велосипед.
Как пример полезной эволюции языка. В ранних версиях Swift не было встроенной поддержки генерации рандомных чисел. Приходилось или подключать свою оболочку, или GameplayKit или использовать в коде довольно тяжеловесные конструкции c конверсией типов из UInt32 вида:
В версии 4.2 появилась встроенная поддержка:
Стало логично и гораздо удобнее. Язык вроде как усложнился, а программисту стало проще.
Причина экспериментов с linked list здесь на самом деле другая. Язык Hi конструируется с прицелом на гораздо более широкое применение в будущем, чем просто быстро программировать несложные задачи для начинающих в алгоритмическом стиле с дружелюбным environment.
Чтобы нам спроектировать будущий язык целесообразно [и попутно выполнить декларацию полной выполнимости исходного текстового кода в будущем], нужно пытаться на существующем языке реализовать сложные концепции, для которых он пока еще не предназначен. На примере linked list и еще некоторых примерах стало понятно, что c optionals лучше работать, чем их не иметь в языке даже в базовой версии. Соответственно теперь задача так их интегрировать в выразительные средства, чтобы было логично, просто, надежно. Работа с optionals требует продумывания обработки ситуаций с nil и т.д.
Концептуально создавать простой и понятный, функционально удобный язык очень непросто. Это означает, что в значительной мере сложность задач уходит от программиста к дизайнеру языка.
Для языка программирования целесообразно включить полный сет встроенных возможностей для целевого использования, следовательно, например, язык, предназначенный для расчетов с математической статистикой должен иметь все необходимые встроенные методы работы с ней, чтобы не искать фреймворки на стороне (в довесок возможно еще иметь конкуренцию фреймворков, риски поддержки) или программисту не собирать из кода велосипед.
Как пример полезной эволюции языка. В ранних версиях Swift не было встроенной поддержки генерации рандомных чисел. Приходилось или подключать свою оболочку, или GameplayKit или использовать в коде довольно тяжеловесные конструкции c конверсией типов из UInt32 вида:
let n = Int(arc4random_uniform(11)) // не все в начале знают, что здесь диапазон генерации от 0 до 10В версии 4.2 появилась встроенная поддержка:
let n = Int.random(in: 0…10)Стало логично и гораздо удобнее. Язык вроде как усложнился, а программисту стало проще.
Причина экспериментов с linked list здесь на самом деле другая. Язык Hi конструируется с прицелом на гораздо более широкое применение в будущем, чем просто быстро программировать несложные задачи для начинающих в алгоритмическом стиле с дружелюбным environment.
Чтобы нам спроектировать будущий язык целесообразно [и попутно выполнить декларацию полной выполнимости исходного текстового кода в будущем], нужно пытаться на существующем языке реализовать сложные концепции, для которых он пока еще не предназначен. На примере linked list и еще некоторых примерах стало понятно, что c optionals лучше работать, чем их не иметь в языке даже в базовой версии. Соответственно теперь задача так их интегрировать в выразительные средства, чтобы было логично, просто, надежно. Работа с optionals требует продумывания обработки ситуаций с nil и т.д.
Концептуально создавать простой и понятный, функционально удобный язык очень непросто. Это означает, что в значительной мере сложность задач уходит от программиста к дизайнеру языка.
Язык Hi конструируется с прицелом на гораздо более широкое применение в будущем, чем просто быстро программировать несложные задачи для начинающих в алгоритмическом стиле с дружелюбным environment.
Хорошо. Тогда в чем его преимущество перед остальными? Где он будет применяться, кто будет на нем писать, кто будет поддерживать уже написанное года через 3 хотя бы? Кто будет его развивать? И, главное, кто будет отвечать перед пользователями за возможные проблемы с языком и оперативно их решать?
Концептуально создавать простой и понятный, функционально удобный язык очень непросто.
Вот именно. И это, в том числе означает что не надо в язык пихать сущностей сверх необходимого («бритва Оккама»). Посмотрите на тот же С++ — есть сам язык, содержащий минимальный набор типов и инструкций и есть библиотеки. Как рантайм, так и STL (фактически являющаяся частью стандарта).
… не надо в язык пихать сущностей сверх необходимого («бритва Оккама»). Посмотрите на тот же С++ — есть сам язык, содержащий минимальный набор типов и инструкций и есть библиотеки.
Диалектика для «бритвы Оккама» здесь в том, что сам C++ в том числе с помощью механизма множественного наследования является почти идеальным генератором сущностей и без особой
Эти сущности генерируются вне самого языка. В том и суть — разработчику дается мощный инструмент, который он может использовать по своему усмотрению.
А если Вы изначально хотите ограничить мощность инструмента дабы разработчик, не дай бог, себе в ногу не выстрелил, то это будет очередной учебный недоязык, заранее обреченный на провал в плане промышленного использования.
А если Вы изначально хотите ограничить мощность инструмента дабы разработчик, не дай бог, себе в ногу не выстрелил, то это будет очередной учебный недоязык, заранее обреченный на провал в плане промышленного использования.
Это как раз не беспокоит. Говоря метафорами, наша будущая цель не дать вместо совка лопату [для промышленного использования], а предоставить робота с лопатой. И более интересует, чтобы робот не воткнул лопату в электрический кабель.
У вас есть хоть какое-то техническое обоснование всего этого?
Мой личный опыт говорит о том, что любая успешная разработка начинается с обоснования ее необходимости. У нас это называется BRD — задание на разработку, в котором описываются бизнес-требования того, что хочется получить и зачем все это нужно.
Дальше идет согласование BRD, которое гарантирует что требования реальны и обоснованы.
Далее, на основе BRD пишется FSD — это уже ТЗ для разработчика. В нем описывается архитектура и конкретные алгоритмы как что будет реализовано. Оно тоже согласуется — тут получаем гарантию непротиворечивости, эффективности и прочего.
И только после этого начинается собственно разработка.
С момента начала разразботки BRD и FSD фиксируется. Т.е. никакого «ой, а мы тут забыли...» от заказчика и «опа! а мы тут еще классную фичу придумали!» от разработчика. Такие вещи делают проект незаканчивающимся никогда. Более того, такие вещи легко могут порушить архитектуру проекта, которая изначально была выстроена под вполне конкретный набор требований.
Когда разработка закончена, начинается тестирование. Сначала компонентное — соответствие продукта требованиям FSD. Потом бизнес — соответствие требованиям BRD. Потом нагрузочное — эффективность. У нас еще интеграционное есть — взаимодействие с остальными компонентами системы.
Такая схема гарантирует что вы получите какой-то рабочий продукт в конечные сроки.
Но все идет от BRD — что вы хотите получить и зачем все это нужно.
Т.е. для себя вы должны определить чем ваш язык будет лучше других (и почему).
Основной риск тут в том, что вы его сейчас сделаете, а потом ваша команда разбежится и все, на нем написанное превратится в легаси, которое следующая команда будет переписывать полностью. Т.е. скатиться в хреносозидательство по причине обострения чешижопицы тут как с добрым утром.
Мой личный опыт говорит о том, что любая успешная разработка начинается с обоснования ее необходимости. У нас это называется BRD — задание на разработку, в котором описываются бизнес-требования того, что хочется получить и зачем все это нужно.
Дальше идет согласование BRD, которое гарантирует что требования реальны и обоснованы.
Далее, на основе BRD пишется FSD — это уже ТЗ для разработчика. В нем описывается архитектура и конкретные алгоритмы как что будет реализовано. Оно тоже согласуется — тут получаем гарантию непротиворечивости, эффективности и прочего.
И только после этого начинается собственно разработка.
С момента начала разразботки BRD и FSD фиксируется. Т.е. никакого «ой, а мы тут забыли...» от заказчика и «опа! а мы тут еще классную фичу придумали!» от разработчика. Такие вещи делают проект незаканчивающимся никогда. Более того, такие вещи легко могут порушить архитектуру проекта, которая изначально была выстроена под вполне конкретный набор требований.
Когда разработка закончена, начинается тестирование. Сначала компонентное — соответствие продукта требованиям FSD. Потом бизнес — соответствие требованиям BRD. Потом нагрузочное — эффективность. У нас еще интеграционное есть — взаимодействие с остальными компонентами системы.
Такая схема гарантирует что вы получите какой-то рабочий продукт в конечные сроки.
Но все идет от BRD — что вы хотите получить и зачем все это нужно.
Т.е. для себя вы должны определить чем ваш язык будет лучше других (и почему).
Основной риск тут в том, что вы его сейчас сделаете, а потом ваша команда разбежится и все, на нем написанное превратится в легаси, которое следующая команда будет переписывать полностью. Т.е. скатиться в хреносозидательство по причине обострения чешижопицы тут как с добрым утром.
То, что вы описали выше я и сам не раз объяснял юным поклонникам Agile, как технологию организацию работ в крупной компании, для которой критична надежность работы корпоративного ПО в режиме эксплуатации.
Впрочем, не всегда водопадный подход работает хорошо даже для крупных проектов. Например, разработка игр. Дело в том, что нельзя создать заведомо качественный BRD для инновационной игры, потому что слишком много неизвестного. Здесь целесообразна итерационная разработка и эксперименты с прототипами. Иногда в процессе создания игры полностью меняется исходный концепт и почти всегда он частично трансформируется. Иногда приходится досрочно завершать разработку, потому что исходные гипотезы не подтверждаются. В книгах по гейм-дизайну, это детальнее описано, например The Art of Game Design: A Book of Lenses (книга вроде есть в русском переводе).
Но в любом случае спасибо, что вы так беспокоитесь и всегда приятно читать хорошо продуманные и изложенные тексты, впрочем,
несколько портит впечатление.
Впрочем, не всегда водопадный подход работает хорошо даже для крупных проектов. Например, разработка игр. Дело в том, что нельзя создать заведомо качественный BRD для инновационной игры, потому что слишком много неизвестного. Здесь целесообразна итерационная разработка и эксперименты с прототипами. Иногда в процессе создания игры полностью меняется исходный концепт и почти всегда он частично трансформируется. Иногда приходится досрочно завершать разработку, потому что исходные гипотезы не подтверждаются. В книгах по гейм-дизайну, это детальнее описано, например The Art of Game Design: A Book of Lenses (книга вроде есть в русском переводе).
Но в любом случае спасибо, что вы так беспокоитесь и всегда приятно читать хорошо продуманные и изложенные тексты, впрочем,
скатиться в хреносозидательство по причине обострения чешижопицы тут как с добрым утром
несколько портит впечатление.
Все что пишу — выстрадано опытом.
Пришел к этому еще когда работал в одной маленькой, но гордой компании (фактически это начиналось как стартап, но тогда таких слов еще не знали), хотя проект был большой и весьма серьезный.
Сейчас это просто стандарт там, где работаю. Но тут цена ошибки очень велика. Любое падение прома — это инцидент, который выносится на комиссию. Серьезное падение, приводящее к недоступности для внешних систем (тот же процессинг) — это уже грозит штрафом от регулятора. А в особо тяжелых случаях можно и лицензию потерять с формулировкой «неисполнение обязательств перед клиентами» (вероятность крайне мала, но все же...).
А недоступность для внешних систем может случиться просто по причине резкого падения производительности из-за какого-то модуля, который начал вдруг жрать ресурсы как не в себя. Посему, эффективность у нас на уровне паранойи — любой код всегда анализируется на предмет «а можно ли сделать лучше». Ну и нагрузочное тестирование обязательно.
В общем, я примерно себе представляю что нужно сделать чтобы получить надежный и эффективный продукт.
В вашем случае (разработка языка) все еще сложнее. Ибо если использование вашего продукта в серьезном проекте приведет в факапу с материальным ущербом, все шишки повалятся на вас.
Хотя скорее всего, сторонние команды не будут использовать продукт, для которого не гарантирована серьезная круглосуточная поддержка.
А иначе, увы, не скажешь. Когда делается непонятно что непонятно зачем и непонятно для кого, просто потому что в голову ударило. Такие проекты мертворожденные изначально.
Пришел к этому еще когда работал в одной маленькой, но гордой компании (фактически это начиналось как стартап, но тогда таких слов еще не знали), хотя проект был большой и весьма серьезный.
Сейчас это просто стандарт там, где работаю. Но тут цена ошибки очень велика. Любое падение прома — это инцидент, который выносится на комиссию. Серьезное падение, приводящее к недоступности для внешних систем (тот же процессинг) — это уже грозит штрафом от регулятора. А в особо тяжелых случаях можно и лицензию потерять с формулировкой «неисполнение обязательств перед клиентами» (вероятность крайне мала, но все же...).
А недоступность для внешних систем может случиться просто по причине резкого падения производительности из-за какого-то модуля, который начал вдруг жрать ресурсы как не в себя. Посему, эффективность у нас на уровне паранойи — любой код всегда анализируется на предмет «а можно ли сделать лучше». Ну и нагрузочное тестирование обязательно.
В общем, я примерно себе представляю что нужно сделать чтобы получить надежный и эффективный продукт.
В вашем случае (разработка языка) все еще сложнее. Ибо если использование вашего продукта в серьезном проекте приведет в факапу с материальным ущербом, все шишки повалятся на вас.
Хотя скорее всего, сторонние команды не будут использовать продукт, для которого не гарантирована серьезная круглосуточная поддержка.
несколько портит впечатление.
А иначе, увы, не скажешь. Когда делается непонятно что непонятно зачем и непонятно для кого, просто потому что в голову ударило. Такие проекты мертворожденные изначально.
А иначе, увы, не скажешь.
А вот сформулировали же по другому :-)
В первой работе указано назначение языка. Полагаю, с точки зрения документов вида BRD оно выглядит нелепо. Но внутренняя логика есть, она неочевидна, так как основана на своеобразном исходном концепте, примера реализации которого, наверное, на данный момент еще нет.
Поживем, увидим. В любом случае это интересно делать.
А вот сформулировали же по другому :-)
Я имел ввиду когда что-то делается непонятно зачем, просто от нечего делать.
В первой работе указано назначение языка. Полагаю, с точки зрения документов вида BRD оно выглядит нелепо. Но внутренняя логика есть, она неочевидна, так как основана на своеобразном исходном концепте, примера реализации которого, наверное, на данный момент еще нет.
Извините, но язык, позволяющий строит очень сложные системы, но не поддерживающий внешние библиотеки — это нонсенс. Вы очень быстро наткнетесь на то, что нужно или подключать внешнюю библиотеку, или до бесконечности раздувать сам язык для поддержки все новых и новых алгоритмов.
Да еще и интерпретатор… Любая сложная система рано-поздно сталкивается с проблемой эффективности и быстродействия. Или начинает тормозить.
Претензии на некий искусственный интеллект подразумевает (в моем понимании) поддержку нейросетей, элементов нечеткой логики…
Я бы обратил внимание на Prolog особенно, на Visual Prolog и начал бы плясать оттуда, а не изобретать велосипед с нуля.
Парни, это же шутка — начиная с даты и точного времени этой публикации (сегодня же пятница) и до последнего statement.
Шутка над поклонением сарафанным представлениям (передаю очередной привет уважаемому мной Тьюрингу), шутка над изящной реализацией LinkedList в Java, шутка над дотошными читателями habr, что иногда парсят твой код в поисках нестыковок дотошней, чем старый профессор в универе, не догадываясь о вложенной мета-семантике в примерах, etc.
Конечно, переходить от элементарных типов данных к linked list нам здесь не нужно — концепт предполагает абстракцию от памяти и архитектуры компьютеров, хотя сама идея непривязанной к линейному пространству ленты с ячейками и логической головкой записи / чтения — удобная для специальных случаев.
Задачи и эксперимент на трех коротких публикациях завершен, далее на русском языке не планирую, пока будем работать в тишине и удалении.
P.S. Благодарю SpiderEkb за простое и компетентное объяснение идеи списков. Не могу поставить плюсик, так как не хватает местной «кармы». Зарабатывать мега-карму habr душещипальными историями на тему «наших бьют» не интересно, лучше продолжу учить машины смеяться, а то скоро люди, кажется, перестанут.
Шутка над поклонением сарафанным представлениям (передаю очередной привет уважаемому мной Тьюрингу), шутка над изящной реализацией LinkedList в Java, шутка над дотошными читателями habr, что иногда парсят твой код в поисках нестыковок дотошней, чем старый профессор в универе, не догадываясь о вложенной мета-семантике в примерах, etc.
Конечно, переходить от элементарных типов данных к linked list нам здесь не нужно — концепт предполагает абстракцию от памяти и архитектуры компьютеров, хотя сама идея непривязанной к линейному пространству ленты с ячейками и логической головкой записи / чтения — удобная для специальных случаев.
Задачи и эксперимент на трех коротких публикациях завершен, далее на русском языке не планирую, пока будем работать в тишине и удалении.
P.S. Благодарю SpiderEkb за простое и компетентное объяснение идеи списков. Не могу поставить плюсик, так как не хватает местной «кармы». Зарабатывать мега-карму habr душещипальными историями на тему «наших бьют» не интересно, лучше продолжу учить машины смеяться, а то скоро люди, кажется, перестанут.
Вы в вашей шутке забыли про лопату.
Лично мне концепция показалась интересной. Мне захотелось её понять. А тут такое… нелогичное.
Лично мне концепция показалась интересной. Мне захотелось её понять. А тут такое… нелогичное.
Логика такого списка контр-интуитивна.
1) зачем в списке членом хранить итератор (или что у вас там?) на какой-то элемент? В первом примере вы с таким же успехом могли вызвать last.
2) такой список не выглядит консистентным. Вместо такого «дубового» подхода логичнее использовать отдельный итератор, с методами next, prev и т.д.
3) методы insert и insertFirst семантически не соответствуют, у вас должно быть тогда insert i, pushFront, pushBack
1) зачем в списке членом хранить итератор (или что у вас там?) на какой-то элемент? В первом примере вы с таким же успехом могли вызвать last.
2) такой список не выглядит консистентным. Вместо такого «дубового» подхода логичнее использовать отдельный итератор, с методами next, prev и т.д.
3) методы insert и insertFirst семантически не соответствуют, у вас должно быть тогда insert i, pushFront, pushBack
Идея использования внешнего итератора для возможного переопределения его поведения разработчиком объяснима, но точно не является простой и понятной, тем более для концепции этого языка.
Инкапсуляция в список (то есть цепь статичных объектов с указателями друг на друга) специальных методов работы с отслеживанием текущего и предыдущего состояния, а также встроенной поддержкой указателей на отдельные интересные узлы очень удобна, особенно для списков очень большой величины, которые используются как динамичная очередь с началом и концом.
Инкапсуляция в список (то есть цепь статичных объектов с указателями друг на друга) специальных методов работы с отслеживанием текущего и предыдущего состояния, а также встроенной поддержкой указателей на отдельные интересные узлы очень удобна, особенно для списков очень большой величины, которые используются как динамичная очередь с началом и концом.
По просьбе читателей в дополнение к основной статье уточним некоторые детали исходно шуточной идеи концепта реализации linked list.
Связный список может содержать элементы одного типа или разных типов.
Объявление списка с инициацией можно делать через присвоение начальных значений с заданным сетом элементов.
Каждый конкретный экземпляр списка в каждый момент существования объекта инкапсулирует структуру данных, указатель на текущий узел и специальные методы работы со списком.
Рассмотрим их на примере. Допустим мы хотим создать свой список чтения интересных постов и статей по программированию. Так как мы имеем только одну голову, то есть можем читать в один конкретный момент времени только один элемент, определим некоторый порядок чтения, одно за другим. Обычно новые статьи мы помещаем в конец списка, впрочем, при появлении интересной работы по нашим тегам мы можем поместить её, допустим, ближе к началу списка. Прочитанные статьи, в том числе и из середины списка удаляем. Так как в мире сейчас писателей больше, чем читателей, то наш список может быть о-очень большим.
Создаем начальный список с самой интересной работы:
В первую очередь нам нужны методы по добавлению (insert) и удалению (remove) узлов.
Стоп. Последний пост нас не интересует, удалим его.
То есть наша реализация списка всегда имеет встроенный указатель на текущий, активный узел. Похожим образом в итерационных циклах мы имеем активный элемент node в конструкциях с итератором вида:
Логика работы insert и remove описана в основной статье.
В любой момент времени для не пустого списка мы может получить как сам объект, так и ссылку на него для быстрого доступа.
Ссылку мы можем использовать позднее, когда после добавления, удаления, перемещения элементов списка, решим вернуться к узлу. Разумеется, ссылка на ранее удаленный элемент списка не приводит к run time error, а переводит list.current в NIL.
Количество таких ссылок неограниченно, мы можем сделать что-то вроде мета-списка избранного чтения, допустим 100 лучших статей из нашего списка, включив линки, например, в линейный массив.
Если нам нужно заменить один элемент на другой, то мы делаем это как с property экземпляра класса в некоторых языках:
Встроенные методы для linked list включают следующие команды (прям как в музыкальном плейере):
Важное уточнение. Все команды выше могут использоваться как процедуры и как функции, возвращая релевантный элемент списка, например так:
Это как на книжной полке, мы не просто перебираем корешки книг, но сразу получаем в руки каждую из них. Если не нужна – ищем дальше, нужна – убираем с полки и кладем в карман.
В принципе, ничего не мешает нам также сделать что-то вроде словаря из отдельных tuple:
Связный список может содержать элементы одного типа или разных типов.
Объявление списка с инициацией можно делать через присвоение начальных значений с заданным сетом элементов.
VAR stringList = <”α”, “β”, “γ”>
VAR aList = <“β”, 1, 3.14>
# Вывод типа здесь осуществляется автоматически.
Каждый конкретный экземпляр списка в каждый момент существования объекта инкапсулирует структуру данных, указатель на текущий узел и специальные методы работы со списком.
Рассмотрим их на примере. Допустим мы хотим создать свой список чтения интересных постов и статей по программированию. Так как мы имеем только одну голову, то есть можем читать в один конкретный момент времени только один элемент, определим некоторый порядок чтения, одно за другим. Обычно новые статьи мы помещаем в конец списка, впрочем, при появлении интересной работы по нашим тегам мы можем поместить её, допустим, ближе к началу списка. Прочитанные статьи, в том числе и из середины списка удаляем. Так как в мире сейчас писателей больше, чем читателей, то наш список может быть о-очень большим.
Создаем начальный список с самой интересной работы:
VAR list = <"Hi Programming Language”>
В первую очередь нам нужны методы по добавлению (insert) и удалению (remove) узлов.
list.insert "Hi Programming Language: начинаем конструировать"
list.insert "Computing Machinery and Intelligence"
# Можем добавить в список сразу несколько элементов:
list.insert «SICP для занятых», «Как я научился программировать в 90 лет»
Стоп. Последний пост нас не интересует, удалим его.
list.remove # удаляет последний добавленный элементТо есть наша реализация списка всегда имеет встроенный указатель на текущий, активный узел. Похожим образом в итерационных циклах мы имеем активный элемент node в конструкциях с итератором вида:
for node in array {
…
}Логика работы insert и remove описана в основной статье.
В любой момент времени для не пустого списка мы может получить как сам объект, так и ссылку на него для быстрого доступа.
LET sicp = list.current
LET sicpMark = list.linkСсылку мы можем использовать позднее, когда после добавления, удаления, перемещения элементов списка, решим вернуться к узлу. Разумеется, ссылка на ранее удаленный элемент списка не приводит к run time error, а переводит list.current в NIL.
Количество таких ссылок неограниченно, мы можем сделать что-то вроде мета-списка избранного чтения, допустим 100 лучших статей из нашего списка, включив линки, например, в линейный массив.
Если нам нужно заменить один элемент на другой, то мы делаем это как с property экземпляра класса в некоторых языках:
list.current = “Новый комментарий в habr”Встроенные методы для linked list включают следующие команды (прям как в музыкальном плейере):
list.first # мгновенно перемещаемся на первый элемент списка
list.next # идем к следующему элементу цепочки
list.prev # возращаемся обратно к предыдущему элементу цепочки
list.last # мгновенно перемещаемся на последний элемент списка
list.go sicpMark # а это переходим к нашей ранее сохраненной закладке
Важное уточнение. Все команды выше могут использоваться как процедуры и как функции, возвращая релевантный элемент списка, например так:
LET firstArticle = list.first
LET removed = list.removeЭто как на книжной полке, мы не просто перебираем корешки книг, но сразу получаем в руки каждую из них. Если не нужна – ищем дальше, нужна – убираем с полки и кладем в карман.
В принципе, ничего не мешает нам также сделать что-то вроде словаря из отдельных tuple:
LET (value, key) = (list.insert, list.link)Ну допустим, что ваш список похож на машину Тьюринга. Возможно, это даже забавно.
Но всё равно, почему бы для обозначения действий не использовать глаголы?
Но всё равно, почему бы для обозначения действий не использовать глаголы?
почему бы для обозначения действий не использовать глаголы?
Ак как вы предлагаете именовать, допустим, list.next?
Да хоть бы и list.GotoNext. Или MovetoNext
В таком виде IMO cкорее усложняет прочтение, чем делает яснее.
Использование Goto сразу оживляет призрак Дейкстры (не путать с Дийкстра из Ведьмака) с топором в руках
Использование Goto сразу оживляет призрак Дейкстры (не путать с Дийкстра из Ведьмака) с топором в руках
Правильные названия — одна из ключевых проблем в программировании. И goto, употреблённый к месту, ничьих призраков не оживляет.
Кстати, «оживить призрака» — оксюморон. Одно слово не подходит к другому.
У вашего списка аналогичная проблема. Вы смешали работу со всем списком и работу с его элементами. От того и проблема с api и названиями.
Поясню: для всего списка существуют действия «создать», «очистить», «найти голову/хвост», «изменить указатель на текущий элемент», «изменить текущий элемент», «добавить/удалить элемент».
А элементом списка является структура из данных и двух указателей. Для элемента имеют смысл действия «получить следующий/предыдущий элемент», «изменить данные»
Кстати, «оживить призрака» — оксюморон. Одно слово не подходит к другому.
У вашего списка аналогичная проблема. Вы смешали работу со всем списком и работу с его элементами. От того и проблема с api и названиями.
Поясню: для всего списка существуют действия «создать», «очистить», «найти голову/хвост», «изменить указатель на текущий элемент», «изменить текущий элемент», «добавить/удалить элемент».
А элементом списка является структура из данных и двух указателей. Для элемента имеют смысл действия «получить следующий/предыдущий элемент», «изменить данные»
Правильные названия — одна из ключевых проблем в программировании.
Разумнее заменить слово «правильные» на «целесообразные», тогда будет корректно. Не бывает априорно «правильных» решений. Следуя вашей логике «правильного» смыслового именования следует каждый раз задумываться как именовать счетчик в циклах вида for i =…
Некоторые военные историки не без оснований считают, что в военных действиях имеет преимущество та сторона, чей язык короче. С другой стороны еще дедушка мог бы рассказать, что логику linked list хорошо знали и использовали в Советском союзе, где был даже соответствующий мем: «Следующий [list.next] — кричит заведующий [owner]».
Правильно бывает по разному, смотря на что ровнять. Так и целесообразно зависит от целей. И да, иногда и счётчик цикла иногда правильно будет назвать не i.
Ваш пример про мем — это не список, это очередь.
Ваш пример про мем — это не список, это очередь.
пример про мем — это не список, это очередь
Ладно, продолжим кружок занимательной информатики.
По очередью обычно понимают однонаправленный список (т.е. частный случай), но советская очередь это всё-таки связный список. Об этом говорят типичные фразы:
«Кто последний?» list.last
«А кто перед вами?» list.prev # очередь в информатике не имеет ссылок на пред. элементы
«Я пойду, перед мной вот эта женщина» list.remove
«Я занимала за этим мужчиной!» list.insert aWomen
«Вас здесь не видели!» IF list.current == NIL THEN…
Ну, кружок, так кружок.
Очередь и стек — частные случаи списка. Но помимо списка элементов у них есть специфичное поведение, которого от них ожидают. LIFO, FIFO — вот этим определяется стек и очередь. Можно расширить api этих классических структур, добавляя к ним что-то… лишнее. По мере добавления, в какой-то момент, у вас получится список, реализующий api стека или очереди, или того и другого вместе. Но будет ли это удобно и понятно?
На примере советских очередей, которые часто переставали быть похожи на какой-либо «нормальный» вариант списка, можно их обобщить до потока, элементы которого выбираются то по правилам, то хаотически, да и сами по себе меняются местами, добавляются, удаляются…
Тут уж стоит вспомнить классику про одну очередь по талончикам, вторую «только спросить», третью «из другого кабинета в порядке живой очереди», и периодически влетающих «я от заведующей» :)
Очередь и стек — частные случаи списка. Но помимо списка элементов у них есть специфичное поведение, которого от них ожидают. LIFO, FIFO — вот этим определяется стек и очередь. Можно расширить api этих классических структур, добавляя к ним что-то… лишнее. По мере добавления, в какой-то момент, у вас получится список, реализующий api стека или очереди, или того и другого вместе. Но будет ли это удобно и понятно?
На примере советских очередей, которые часто переставали быть похожи на какой-либо «нормальный» вариант списка, можно их обобщить до потока, элементы которого выбираются то по правилам, то хаотически, да и сами по себе меняются местами, добавляются, удаляются…
Тут уж стоит вспомнить классику про одну очередь по талончикам, вторую «только спросить», третью «из другого кабинета в порядке живой очереди», и периодически влетающих «я от заведующей» :)
Поясню: для всего списка существуют действия «создать», «очистить», «найти голову/хвост», «изменить указатель на текущий элемент», «изменить текущий элемент», «добавить/удалить элемент».
А элементом списка является структура из данных и двух указателей. Для элемента имеют смысл действия «получить следующий/предыдущий элемент», «изменить данные»
У вас «изменить указатель на текущий элемент» для списка пересекается по смыслу «получить следующий/предыдущий элемент» для элемента. Это же будет уже другой элемент. Аналогично для действия «изменить элемент». Получилась каша в смыслах. Попробуйте рядом с моим API выписать ваши многосложные варианты с разделением для «списков» и «элементов».
Нет, это у вас смешался список с его элементами.
У меня «изменить указатель» ничего не делает с элементами, меняет только одно свойство списка. «Изменить элемент» = «изменить данные» у текущего элемента. Можно и делать такой метод у списка. И никакой каши.
А вот у вас как раз смещение получается. Есть структуры списков, где работы с элементом совмещены с работой со списком элементов — это очередь и стек. Вот там очевидно и понятно, методы pop() или remove() возвращают элемент, но даже там — то глаголы.
А для связного списка есть масса хороших примеров. Например .Net LinkedList
У меня «изменить указатель» ничего не делает с элементами, меняет только одно свойство списка. «Изменить элемент» = «изменить данные» у текущего элемента. Можно и делать такой метод у списка. И никакой каши.
А вот у вас как раз смещение получается. Есть структуры списков, где работы с элементом совмещены с работой со списком элементов — это очередь и стек. Вот там очевидно и понятно, методы pop() или remove() возвращают элемент, но даже там — то глаголы.
А для связного списка есть масса хороших примеров. Например .Net LinkedList
Linked list в этой статье делает то же, что пример для С# (кстати, согласен — хороший), только еще проще, например фрагмент:
в синтаксисе Hi выглядит так:
Можно саму трансформацию выразить и одной строкой:
// Move the last node to be the first node.
mark1 = sentence.Last;
sentence.RemoveLast();
sentence.AddFirst(mark1);
Display(sentence, "Test 4: Move last node to be first node:");в синтаксисе Hi выглядит так:
sentence.last
LET last = sentence.remove
sentence.insertFirst last
PRINT "Test 4: Move last node to be first node:"Можно саму трансформацию выразить и одной строкой:
sentence.insertFirst (sentence.last.remove) Linked list в этой статье может сделать то же, что и пример для С#.
Но читать код не становится удобнее.
Да и некоторые вещи делать придётся кодом, в отличии от, к примеру, sentence.Find(«dog»);
Но читать код не становится удобнее.
Да и некоторые вещи делать придётся кодом, в отличии от, к примеру, sentence.Find(«dog»);
Добавить метод find нетрудно, тогда
будет в Hi выглядеть примерно так:
// Keep a reference to the current node, 'fox',
// and to the previous node in the list. Indicate the 'dog' node.
mark1 = current;
LinkedListNode<string> mark2 = current.Previous;
current = sentence.Find("dog");
IndicateNode(current, "Test 9: Indicate the 'dog' node:");
будет в Hi выглядеть примерно так:
mark1 = sentence.current
LET mark2 = sentence.prev
sentence.find "dog"
PRINT "Test 9: Indicate the 'dog' node:", sentence.currentответ выше
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Hi Programming Language: linked list