Сколько зарабатывает Pascal программист?

Но в питоне уже есть set. Да и это выглядело бы совсем странно: множество с заданным порядком элементов. Хотя емнип в руби к «массиву» прикрутили и «интерфейс» множества, чтобы лишний раз не вставать.

Ну set там тоже не совсем set, а больше похоже на list. Впрочем, все эти названия в питоне нужно воспринимать с иронией.

А насчет определения у Кнута я погорячился. У него там вначале дается определение «linear list», которое является массивом (определения массива у него нет), потом «linked allocation», которое выделяется в отдельно определение «linked list», потом «circular linked list», в котором последний указывает на первый элемент (на промежуточные – такой вариант не рассматривается).

Наверное, такая терминология доминировала во времена расцвета лиспа, или тогда она еще переживала стадию формирования. По некоторым техническим моментам до сих пор нет единства. Сейчас, если говорят список, то подразумевают, что структура имеет базовые операции linked list, а удаление/добавление элемента имеет сложность O(1), а когда говорят массив, то подразумевают индексированное множество состоящее из однотипных элементов, последовательно пронумерованных, и доступом к его элементам по индексу со сложность O(1). Впрочем если уж master/slave переименовали, то и тут могут все переименовать…

Чем? В set нельзя положить дважды один и тот же элемент. В set нельзя получить первый элемент и вообще какой-то элемент по порядку. Какой это list?

Сейчас, если говорят список, то подразумевают, что структура имеет базовые операции linked list, а удаление/добавление элемента имеет сложность O(1), а когда говорят массив, то подразумевают индексированное множество состоящее из однотипных элементов, последовательно пронумерованных, и доступом к его элементам по индексу со сложность O(1).

Это синдром утёнка после Си++. У нормального массива, к слову, индексов может быть несколько. И O(1) не всегда. Для Си, например, скорость доступа зависит от количества индексов. Для Haskell — О(log N) от длины массива. Критично, чтобы скорость доступа не зависела от номера элемента, к которому доступ.

Наверное, такая терминология доминировала во времена расцвета лиспа, или тогда она еще переживала стадию формирования. По некоторым техническим моментам до сих пор нет единства.

Это математическая терминология. Есть «список» - упорядоченная последовательность элементов. Есть «отображение» - соответствие значения ключу. Есть «множество» - неупорядоченный набор уникальных элементов. И т.д.

А дальше уже реализации. Причём на базе одной реализации могут быть разные абстрактные типы. Одномерный массив является как «списком» так и «отображением». Отсортированный массив может быть «множеством».

Сейчас, если говорят список, то подразумевают

Так можно считать, что в Питоне и числа неправильные. Ведь в Си/Си++/Паскале когда говорят «целое число», то подразумевают int. А в Питоне бесконечные целые. Тоже, видимо, плохому учат.

Сейчас, если говорят список, то подразумевают, что структура имеет базовые операции linked list, а удаление/добавление элемента имеет сложность O(1), а когда говорят массив, то подразумевают индексированное множество состоящее из однотипных элементов, последовательно пронумерованных, и доступом к его элементам по индексу со сложность O(1).

Это синдром утёнка после Си++. У нормального массива, к слову, индексов может быть несколько. И O(1) не всегда. Для Си, например, скорость доступа зависит от количества индексов. Для Haskell — О(log N) от длины массива. Критично, чтобы скорость доступа не зависела от номера элемента, к которому доступ.

При чем тут С++? Это базовые понятия из теории алгоритмов, в любом хорошем курсе «Algorithms and Data Structures» про это говорят, без привязки к ЯП. Это то, чего ожидаем от таких типов данных с названиями «list» и «array», понятно, что реализация может быть разной и она может давать расширенный функционал.

Это математическая терминология. Есть «список» - упорядоченная последовательность элементов. Есть «отображение» - соответствие значения ключу. Есть «множество» - неупорядоченный набор уникальных элементов. И т.д.

В математике нет понятия «список - упорядоченная последовательность элементов», есть понятие множество, есть понятие линейного порядка, можно назвать список линейно упорядоченным множеством состоящим из конечного числа элементов. Но когда определяют структуру данных, то обычно (всегда?) в определение входит перечень операций, определенных на этой структуре, т.к. без этого она бесполезна.

Соответственно, [одномерным] массивом можно назвать множество, состоящие из конечного числа элементов плюс биективное отображение этого множества на отрезок целых чисел (обычно начинающийся с 0). Но опять же, без перечня операций определенных на этой структуре, это определение бесполезно.

В set нельзя положить дважды один и тот же элемент.

Не флейма ради, а просто как забавное замечание. Аксиоматика теории множеств является одним из способов ввести основания математики. Соответственно, для множеств понятие числа не нужно, и слово «дважды» еще бессмысленно. Добавление элемента это объединение множеств, изъятие элемента это взятие подможества со свойством «не содержит этот элемент».

PS: реализовано оно на python_list, соответственно, будет проявлять свойства list или array в некоторых случаях, и это может приводить к неожиданным результатам.

    B = (1, 2)
    print(B is (1, 2))

    True

    C = (1, 2)
    print(B is C)

    True

    C = tuple(list(B))
    print(B is C)

    False

    print(B is (1, 2))
    print(C is (1, 2))
    print(B)
    print(C)

    True
    False
    (1, 2)
    (1, 2)

    my_set = {1, 'abc'}
    my_set.add(B)
    my_set.add(C)
    print(my_set)

    {'abc', 1, (1, 2)}

    for item in my_set:                                                                                                                                                     
        print(item is C)

    False
    False
    False

WTF?!

PS: питон засовывает в множество оперируя операцией сравнения «==», соответственно, если какой-то объект оказался равным в смысле «==» какому-то объекту уже находящемуся в множестве, то объект добавлен не будет. Это абсолютно бесчеловечно по отношению к программисту, проверять на наличие нужно по операции is и хранить в множестве сами объекты.

При этом он действительно хранит именно САМИ объекты:

    my_set = set()                                                                                 
    my_set.add(C)                                                                                  
    print(my_set)                                                                                  
    D = my_set.pop()                                                                               
    print(D is C)
    print(D is (1, 2))

    {(1,2)}
    True
    False

PS: питон засовывает в множество оперируя операцией сравнения «==», соответственно, если какой-то объект оказался равным в смысле «==» какому-то объекту уже находящемуся в множестве, то объект добавлен не будет. Это абсолютно бесчеловечно по отношению к программисту, проверять на наличие нужно по операции is и хранить в множестве сами объекты.

В std::set то же самое. Можно, конечно, хранить адреса объектов вместо объектов, но и в Питоне можно id(C) вместо C положить.

Но когда определяют структуру данных, то обычно (всегда?) в определение входит перечень операций, определенных на этой структуре, т.к. без этого она бесполезна.

Для списка, очевидно, такой операцией является «получить элементы списка по порядку».

из конечного числа элементов плюс биективное отображение этого множества на отрезок целых чисел

Если биективное, то получить элемент по числу и получить число по элементу.

Аксиоматика теории множеств является одним из способов ввести основания математики.

>>> e= frozenset()
>>> one = frozenset([e])
>>> two = frozenset( [one, e ] )
>>> three = frozenset ( [ two, one, e ] )
>>> three

frozenset({frozenset(), frozenset({frozenset(), frozenset({frozenset()})}), frozenset({frozenset()})})

и в Питоне можно id(C) вместо C положить.

А как потом по этому id объект искать? Перебирать все существующие объекты? Идиотизм же. В std::set можно указать по какой операцией сравнения проверять совпадение объектов.

Для списка, очевидно, такой операцией является «получить элементы списка по порядку».

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

Если биективное, то получить элемент по числу и получить число по элементу.

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

А как потом по этому id объект искать? Перебирать все существующие объекты?

Как всегда. Ассоциативный массив. Или, если не пугает UB, то через ctypes.

В std::set можно указать по какой операцией сравнения проверять совпадение объектов.

Продемонстрируй на https://godbolt.org/z/13j61arjY

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

Ну почему же? Например, тебе передали пятый элемент массива, а тебе нужен предыдущий. Ты по номеру пятого элемента получаешь 5, потом уменьшаешь его на единицу и получаешь четвёртый элемент.

Но эту операцию можно получить через get_next, но питон же ее не делает!

get_next для массива = получить номер текущего элемента, увеличить на 1, получить по номеру элемент => массив является списком.

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

Прототипов ссыкономистами уже вкинуто в количестве. Помню для «Касперского» выпиливали ихний самопальный TerritoryManagement 2.0, который им запили какие-то «джава-профессионалы» (ТМ) и половина транзакций расшибалась апстену по времени или по количеству запросов («батчи почему-то падают» (ТМ) Почему-то...).

Но не для того чтоб перестать страдать фигней, а... чтоб запилить им Territory Management 3.0.

А архитектурга беспокоило что «девелоперы нарушают его гениальную архитектуру»(изобретение велосипедов для того, что уже есть в системе, нужно было просто изучить ее, а не изобретать, только велосипеды еще адски глючат, потому что не учитывают неявное зацикливание по событиям или по данным, на которые срабатывает туча хэндлеров — и тоже надо было исключать предпосылки не вкидывая всякий треш, а не героически преодолевать это «защитой от зацикливания», которую в системе с короткими транзакциями все равно полноценно не написать без сохранений в базу.

Когда он вместо чтоб послушать людей в теме настаивал на своем — ему показали в прямом эфире глубину лишних вызовов (оказывается в консоли для этого инструмент есть, графический. А он и не знал) и почему его архитектура сосед)))

Ну он хотя бы признал ошибки. В сетевых евромагазинах по раздаче еды вообще архитектор копипастил разный бред с гитхаба, чтоб «ссыкономить время» — но экономил он только свое время, т.к. девелоперам приходилось этот бред переписывать с многостраничных простыней присвоений на мапы, и с фантазий не разобравшихся в SaaS плюсистов с венгерской нотацией головного моска («как спалить виндовых программистов»), на то немногое что реально работает (т.е. выпилить нафиг все «смартфабрики» из-за которых тормозят юнит-тесты).

Ссыкономить у них ничего не вышло. Т.к. в фантазиях это звучит как «просто заюзайте это», а на деле — «просто заюзать» выливается в тормоза и глюки.

Полностью согласен.

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

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

Поэтому со списком можно работать как с динамической структурой: мы последовательно обрабатываем задания из списка и удаляем обработанные задания, чтобы получить следующее задание, мы пользуемся базовой операцией get_next(), при этом нас совершенно не волнует что происходит со списком после этих элементов – задания могут появляться, могут исчезать, и на скорость работы get_next() эти изменения не влияют. Это то, что программист ожидает, когда пишет for item in list(...).

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

Это синдром утёнка после Си++

Вообще то это ещë Вирт определял для паскаля.

плюсистов с венгерской нотацией

Они еще живы?!!

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

Системный стек по-твоему массив или список? И realloc у сишных массивов был с рождения.

В Racket и Haskell списки вообще все неизменяемые. Так что они и не списки уже?

Среди базовых операций массива нет операций добавить/удалить элемент, нет операции изменить размер массива.

std::vector не массив?

задания могут появляться, могут исчезать, и на скорость работы get_next() эти изменения не влияют.

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

int main()
{
        std::list count = {0, 1, 2, 3};
        for(auto i : count) {
                count.erase(count.begin());
                cout << i << endl;
        }
}

0
Ошибка сегментирования

Системный стек по-твоему массив или список?

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

И realloc у сишных массивов был с рождения.

У сишных массивов с рождения нет изменения длины, с рождения там int a[10];.

В Racket и Haskell списки вообще все неизменяемые. Так что они и не списки уже?

Можно сделать список неизменяемым, почему нет? Запрещаешь выполнять определенные базовые операции и все, по сути это модификатор типа.

std::vector не массив?

Это другая структура данных, она называется «динамический массив». Для нее определены дополнительные базовые операции изменения длины массива, но это не операции вставки/удаления элемента.

PS:

for(auto i : count) { это очень плохое выражение, которым не стоит пользоваться, и к счастью, пользоваться им совершенно не обязательно.

Для паскаля и фортрана эти определения тоже верны. Для более математических ЯП совсем нет.

int main()
{
        std::list count = {0, 1, 2, 3};
        for(auto k = count.begin(); k!=count.end(); k++) {
                count.erase(count.begin());
                cout << *k << endl;
        }
}

Та же ошибка.

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

У сишных массивов с рождения нет изменения длины, с рождения там int a[10];.

char *a = malloc(24);
realloc(a, 36);

Поменял. Вывод не изменился.

Это не массив, это выделение памяти и указатель.

И как называется структура данных, под которую выделена память?

Можно сделать список неизменяемым, почему нет? Запрещаешь выполнять определенные базовые операции и все, по сути это модификатор типа.

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

но это не операции вставки/удаления элемента.

std::vector::insert, std::vector::erase.

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

    for(auto k = count.begin(); k != count.end();) {
        std::cout << *k << std::endl;
        k++;
        count.pop_front();
    }
}

И как называется структура данных, под которую выделена память?

Никак. Зависит от того, как ты ее организуешь, какие будут базовые операции, как она будет хранить данные.

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

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

И да, если базовые операции медленные, то это плохая реализация структуры.

std::vector::insert, std::vector::erase.

Это расширение функциональности для структуры «динамический массив», формально они используют только базовые операции динамического массива, т.е. не создают новых сущностей; эти операции довольно медленны, их сложность O(n), в то время как для списка они O(1).

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

Откуда знаешь? Я могу сделать свою реализацию вектора с идентичным интерфейсом (то есть со всеми операциями на базе дерева, например). И даже могу обеспечить O(1) скорость чтения/записи элементов для реальных компьютеров, но insert и erase будут базовыми операциями, а не выражаться через копирование остальных элементов.

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

Я могу сделать свою реализацию вектора с идентичным интерфейсом (то есть со всеми операциями на базе дерева, например). И даже могу обеспечить O(1) скорость чтения/записи элементов, но insert и erase будут базовыми операциями, а не выражаться через копирование остальных элементов.

Какая будет сложность операций удаления и вставки в твоем случае?

PS: базовые операции это те, которые есть в определении структуры, а не те, которые ты реализуешь независимо.

PPS: Динамический массив можно реализовать на дереве, но доступ по индексу будет медленный. Можно, конечно, сделать O(logN) для доступа, и для удаления, и для вставки одновременно, с увеличенным потреблением памяти, но это будет не O(1), и работать с таким массивом во многих случаях будет неудобно. Не надо использовать иерархическую структуру там, где удобно использовать линейную.

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

Если в питоновском списке запретить базовые операции модификации списка, он станет списком с твоей точки зрения? Ведь с точки зрения наблюдения он будет неотличим от списка. Или надо будет ещё и доступ по номеру элемента обязательно запретить?

Если в питоновском списке запретить базовые операции модификации списка, он станет списком с твоей точки зрения? Ведь с точки зрения наблюдения он будет неотличим от списка. Или надо будет ещё и доступ по номеру элемента обязательно запретить?

Зачем запрещать операции модификации списка? List в питоне это список, который часто ведет себя как массив, или массив, который часто ведет себя как список, в частности, при выполнении for k in list(...). Поэтому, в этом цикле это не список, а массив, что НЕСКОЛЬКО неожиданно и приводит к описанным выше ошибкам при написании кода.

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

Какая будет сложность операций удаления и вставки в твоем случае?

Можно О(1). Но примерно в 30 раз медленнее, чем std::vector. Или O(log N).

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

Можно О(1). Но примерно в 30 раз медленнее, чем std::vector. Или O(log N).

Ты серьезно говоришь, что можешь сделать реализацию вектора так, что и вставка, и удаление, и доступ к элементам по индексу будет за O(1) ?!!

Ага. Количество памяти на компьютере не больше терабайта. Гарантирую все операции ровно за время 40 обращений к памяти вне зависимости от объёма «массива».

Не нравится Pascal? Создай свой собственный язык программирования!

Не нравится Pascal? Создай свой

получится одно из набора: Pascal, Lisp, Forth, Tcl, Bash .. они очень чётко представляют «грани» практичных ЯП с ясной и компактной внутренней архитектурой.

Pascal, Lisp, Forth, Tcl, Bash

В смысле, именно эти 5 или подразумевается все несколько тысяч существующих?

В смысле, именно эти 5 или подразумевается все несколько тысяч существующих?

они простые и буквально на разных гранях.

Pascal - строго типизированный и хорошо разобранный во всех ипостасях (от синтаксиса до интерпретации и кодогенерации см info lex,bison там даётся микро-паскаль для примеров),

Lisp - то-же самое, функциональщина на минималках через списки (то-же так-же детально всё изучено и разобрано),

Forth - конкенакативный ассемблер, любая книга Форт - об том как его сделать и какие фокусы можно вытворять :-) Joy чего стоит

Tcl - «всё есть текст» и

Bash/Sh - язык командной строки и (Flow) управления процессами.

Всё прочее действительно промежуточные между ними варианты и DSL. Если будешь пытаться «забодяжить свой язык с блек-джеком», то волей-неволей сделаешь косой промежуточный между ними вариант

Если будешь пытаться «забодяжить свой язык с блек-джеком», то волей-неволей сделаешь косой промежуточный между ними вариант

Сможешь разложить по этому базису APL, Prolog, Haskell, Smalltalk, Erlang?

Сможешь разложить по этому базису APL, Prolog, Haskell, Smalltalk?

те которые хотели сразу быть «и умными и красивыми» на все грани ? так они сдохли :-) ни шмогли..