Применение искинов - шоссе империализма (Стенгазета русификаторов ИТ)

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.

Массив

Страница: 1

Сообщений 1 страница 17 из 17

1

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17

В языке хорошо бы иметь массивы, даже в максимально плохом языке. В РАЯ (из КуМир) они есть. Строки можно делать поверх массивов. Поэтому хорошо бы вообще в принципе описать, что же такое массив и поглубже, не только с точки зрения его изучения как концепции.

С точки зрения операций и идентичности массивы рассматриваются (слабо) в теории моделей:
1982, Барвайс, Часть 1. Теория моделей

Ассоциативный массив можно реализовать на базе хеш-таблицы (такой путь выбрал автор языка Тривиль, если я правильно запомнил), можно на базе деревьев (АВЛ, красно-чёрного и/или других).

«"Массив" - это структура данных, которая представляет собой упорядоченный набор элементов одного типа.»
[html]<a href="https://ru.wikipedia.org/wiki/Массив_(тип_данных)">https://ru.wikipedia.org/wiki/Массив_(тип_данных)</a>[/html]

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

[html]<a href="https://ru.wikipedia.org/wiki/Ассоциативный_массив">https://ru.wikipedia.org/wiki/Ассоциативный_массив</a>[/html]

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

Ассоциативные массивы ещё называют "словарями" - https://foxford.ru/wiki/informatika/slo … y-v-python
Но я не видел в интернете статей на тему "как сделать массив из словаря?"

Ранее по теме:
Кладка

См. также
Итератор

Отредактировано Лис (2024-08-12 16:43:27)

0

2

  • Автор: NuShaman
  • Автор "Солуни"
  • NuShaman
  • Откуда: Екатеринбург
  • Зарегистрирован: 2020-10-06
  • Приглашений: 0
  • Сообщений: 690
  • Уважение: [+0/-0]
  • Позитив: [+1/-0]
  • Пол: Мужской
  • Возраст: 44 [1980-08-03]
  • Провел на форуме:
    9 дней 7 часов
  • Последний визит:
    2025-01-20 14:22:14
Лис написал(а):

"Массив" - это структура данных,
которая представляет собой упорядоченный набор
элементов одного типа.

Как обычно много букоф (но это нормально,
главное это чтобы буквы не были лишними или даже бессмысленными).

Или я могу выдумать более свободную трактовку:
Массив - это структура данных переменной длины,
которая представляет собой упорядоченный набор
структур данных переменной длины.
Звучит красиво и рекурсивно,
а значит мы на правильном пути :)

0

3

  • Автор: NuShaman
  • Автор "Солуни"
  • NuShaman
  • Откуда: Екатеринбург
  • Зарегистрирован: 2020-10-06
  • Приглашений: 0
  • Сообщений: 690
  • Уважение: [+0/-0]
  • Позитив: [+1/-0]
  • Пол: Мужской
  • Возраст: 44 [1980-08-03]
  • Провел на форуме:
    9 дней 7 часов
  • Последний визит:
    2025-01-20 14:22:14

Попробую объяснить верхнее понятие массива
на практическом применении такого массива.
Допустим, что индекс массива это дата,
то есть количество дней от 1 января 1970 года.

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

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

Если события своей жизни записывать в текстовом виде,
то массив за любой период времени
будет представлять собой один текстовый файл.
Вложенность каждого элемента массива можно определять
по кол-ву пробелов от левого края до первой буквы строки.
Содержимое этого файла можно записать в одну строку большой длины.
Или это будет последовательность байтов.

Можно ввести систему категорий.
То есть каждый пункт обзывать каким-то словом из заранее известного списка слов.
Пример:
НАЗВАНИЕ: Лис
ТИП, СУЩЕСТВО: животное, лес
или
НАЗВАНИЕ: Рыжик
ТИП, СУЩЕСТВО: кот
КОТ: млекопитающее, дом
МЛЕКОПИТАЮЩЕЕ: животное, молоко
или
НАЗВАНИЕ: NuShaman
ТИП, СУЩЕСТВО: человек
или
НАЗВАНИЕ: Каравай хлеб ржаной в нарезке
ТИП, ПРОДУКТ ПИТАНИЯ: хлеб
ПРОДУКТ ПИТАНИЯ: кулинария, рот
МАССА: 380 г
ПРОИЗВОДИТЕЛЬ: Каравай
КАЛОРИЙНОСТЬ: 206 ккал
но можно калорийность вычислять по значениям БЖУ.

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

0

4

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17

Чего я хочу добиться?

Ответить на вопросы:
- как сделать массивы (опираясь на математическую традицию)?
- как массивы связаны с типами данных (точно ведь связаны)?
- если лямбда-исчисление это математический синтаксис для функций, типизированное лямбда исчисление - для типов, то что там с массивами?
- зависимые типы (dependend types) вроде как имеют отношение, но какое?
- как со всем этим связан раздел математики (он маленький) с названием "теория массивов"?
- зачем при изучении лямбда-исчисления постоянно ссылаются на теорию категорий? Ну да, векторные пространства, массивы, есть что-то общее, но как?

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

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

Отредактировано Лис (2024-08-12 22:22:45)

0

5

  • Автор: gudleifr
  • gudleifr.forum2x2.ru
  • gudleifr
  • Откуда: Питер
  • Зарегистрирован: 2024-06-21
  • Приглашений: 0
  • Сообщений: 145
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    15 дней 0 часов
  • Последний визит:
    Сегодня 02:04:51
Лис написал(а):

как сделать массивы

Нужно ответить на два вопроса http://www.compiler.su/postfiksnye-inkr … ent.php#50

0

6

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17
gudleifr написал(а):

>> Нужно ответить на два вопроса

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

Хотите разобраться?
1) Каким из двух взаимозаменяющих свойств должна обладать машина, на которой возможен "проход по массиву"?
2) Как соотносятся "итераторы" и теорема о сохранении инварианта в цикле?

Вам нужно, вы и отвечайте, разве вы не видите, что у меня вопросы другие?

0

7

  • Автор: gudleifr
  • gudleifr.forum2x2.ru
  • gudleifr
  • Откуда: Питер
  • Зарегистрирован: 2024-06-21
  • Приглашений: 0
  • Сообщений: 145
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    15 дней 0 часов
  • Последний визит:
    Сегодня 02:04:51
Лис написал(а):

у меня вопросы другие?

Вы ошибаетесь.

0

8

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17
gudleifr написал(а):

Вы ошибаетесь.

Докажите.

0

9

  • Автор: gudleifr
  • gudleifr.forum2x2.ru
  • gudleifr
  • Откуда: Питер
  • Зарегистрирован: 2024-06-21
  • Приглашений: 0
  • Сообщений: 145
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    15 дней 0 часов
  • Последний визит:
    Сегодня 02:04:51
Лис написал(а):

Массив, цикл и итератор — это понятия, связанные с программированием.

Инвариант (loop invariant) — это логическое выражение, истинное в определённые моменты времени.
Инварианты используются в теории верификации программ
для доказательства правильности результата,
полученного циклическим алгоритмом.

Инвариант цикла не надо путать с инвариантом класса.
Для инварианта цикла значение логического выражения, которое
зависит от переменных, изменяющихся в теле цикла.
Значение истинно после каждого прохода тела цикла или/и
перед началом выполнения цикла.

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

коллекция (массив), объект, конвейер, поток, система обработки.
https://bito.ai/resources/java-array-ap … explained/

итераторы представляют собой последовательность элементов,
Итераторы могут быть внешними или внутренними.
Внешние итераторы применяются для выполнения нескольких действий внутри цикла
или организации вложенных циклов. Внутренние итераторы встроены в модули,
такие как Catalog, Operation, Register и Mapping (TempTable), и просты в настройке.

конвейеры — последовательность агрегированных операций, объединяют несколько операций для обработки данных.
Конвейеризация коллекций при помощи итераторов происходит следующим образом:
- Итератор разбивает исходный массив на P конвейеров (P-количество процессоров).
- каждый конвейер выполняет цикл из ~N/P шагов (N - число элементов в коллекции).
- Внутри цикла доступны свойства каждого объекта.
- После завершения цикла процесс переходит к обработке следующих модулей.

Разумеется, за языками с итераторами будущее.

А теперь отфильтруйте, пожалуйста, главное. (То, что нам понадобится для определения массива).

Отредактировано gudleifr (2024-08-12 16:59:32)

0

10

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17
gudleifr написал(а):

что нам понадобится для определения массива

Литература два варианта на выбор предлагает (надо выбрать одно из них):
- рекурсивные домены (как семантика для списков);
- функция индексирования (но с ней похуже).

см. также
1971, Scott & Strachey, Toward a Mathematical Semantics

0

11

  • Автор: gudleifr
  • gudleifr.forum2x2.ru
  • gudleifr
  • Откуда: Питер
  • Зарегистрирован: 2024-06-21
  • Приглашений: 0
  • Сообщений: 145
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    15 дней 0 часов
  • Последний визит:
    Сегодня 02:04:51
Лис написал(а):

Литература...

Вы же пытались за инварианты... Про домены там не было.

0

12

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17
gudleifr написал(а):

Вы же пытались за инварианты...

Это был не я. Я писал, что итераторы нужны в ответ на ваше заявление, что языки с итераторами ведут в тупик.

Отредактировано Лис (2024-08-13 18:06:22)

0

13

  • Автор: gudleifr
  • gudleifr.forum2x2.ru
  • gudleifr
  • Откуда: Питер
  • Зарегистрирован: 2024-06-21
  • Приглашений: 0
  • Сообщений: 145
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    15 дней 0 часов
  • Последний визит:
    Сегодня 02:04:51
Лис написал(а):

Я писал, что итераторы нужны в ответ на ваше заявление, что языки с итераторами ведут в тупик.

Это было на другом форуме. Здесь нам важно установить 1) какие машины могут в массивы и 2) зачем нам нужны циклы (и, возможно, итераторы). Кстати, как Вы думаете, почему вопросов два?

0

14

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17
gudleifr написал(а):

Здесь нам важно установить 1) какие машины могут в массивы и 2) зачем нам нужны циклы (и, возможно, итераторы). Кстати, как

Не нам, а вам.

gudleifr написал(а):

Вы думаете, почему вопросов два?

Нет, я думаю о другом.

0

15

  • Автор: gudleifr
  • gudleifr.forum2x2.ru
  • gudleifr
  • Откуда: Питер
  • Зарегистрирован: 2024-06-21
  • Приглашений: 0
  • Сообщений: 145
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Пол: Мужской
  • Провел на форуме:
    15 дней 0 часов
  • Последний визит:
    Сегодня 02:04:51
Лис написал(а):

Не нам, а вам.

Именно Вам. Это Ваше домашнее задание.

Лис написал(а):

Нет, я думаю о другом.

Хотите ассемблер - придется думать, о чем велено.

0

16

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17
gudleifr написал(а):

Это Ваше домашнее задание

Ошибаетесь.

gudleifr написал(а):

Хотите ассемблер - придется думать, о чем велено.

Массивы это не для ассемблера, ассемблер делает другой разумный - alextretyak.
Массивы это для Солуни.

0

17

  • Автор: Лис [М]
  • Участник
  • Лис [М]
  • Зарегистрирован: 2023-03-10
  • Приглашений: 0
  • Сообщений: 1119
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    6 дней 1 час
  • Последний визит:
    2024-11-27 23:25:17

Надо найти какую-нибудь свежую статью, и оттуда посмотреть список старой литературы

2021, Benjamin Chetioui, Ole Abusdal, Magne Haveraaen, Jaakko Järvi, and Lenore Mullin. Padding in the mathematics of arrays, New York, ACM.
2017, Artjoms Šinkarovs & Sven-Bodo Scholz, Operational semantics of lambda-omega.
2009, Kai Trojahner & Clemens Grelck, Dependently typed array programs don’t go wrong. The Journal of Logic and Algebraic Programming
2006, Clemens Grelck and Sven-Bodo Scholz. SAC - A functional array language for efficient multi-threaded execution.
2005, Michael Abbott, Thorsten Altenkirch, and Neil Ghani. Containers: Constructing strictly positive types.
1999, Peter Falster & Michael Jenkins, Array Theory and Nial.
1991, Michael A. Jenkins and Lenore R. Mullin. A Comparison of Array Theory and a Mathematics of Arrays
1990, Klaus Berkling, Arrays and the Lambda Calculus. Technical Report 93, Electrical Engineering and Computer Science Technical Reports.
1988-12, Lenore M. Restifo Mullin, A Mathematics of Arrays. PhD thesis, Syracuse University,
1988-10, J. I. Glasgow & M. A. Jenkins, Array theory, logic and the nial language
1973-03, Trenchard More, Axioms and theorems for a theory of arrays. IBM Journal of Research and Development
1972-01, A. Hassitt and L. E. Lyon., Efficient evaluation of array subscripts of arrays. IBM Journal of Research and Development

В общем, с массивами всё хорошо. С типами пока не очень.

Отредактировано Лис (2024-08-14 10:48:39)

0

Страница: 1