Как язык * знать * при сортировке списка?

Question

Простите меня, если этот вопрос немой, но мне пришло в голову, что я не знаю, как язык знает список, отсортированный или нет.

Скажем, у меня есть список:

["Apple","Apricot","Blueberry","Cardamom","Cumin"] 

и я хочу, чтобы вставить "Cinnamon". AFAIK Язык, который я использую, не знает, что список отсортирован; это просто список. И у него нет поля зрения «широкого экрана», как у нас, поэтому он не знает, где заканчивается A-кусок, а C-кусок начинается из-за пределов списка. Таким образом, он проходит и сравнивает первую букву каждой строки массива с первой буквой строки вставки. Если символ вставки больше, он перемещается к следующей строке. Если символы совпадают, он переходит к следующей букве. Если он переходит к следующей строке, а символ массива больше, чем символ вставки, тогда туда вводится символ.

Мой вопрос в том, может ли язык KNOW, когда список сортируется? Если процесс расчесывания в несортированном и отсортированном списке один и тот же, и список по-прежнему повторяется, то как сортировка экономит время?

EDIT: Я понимаю, что «сортировка позволяет алгоритмы, которые полагаются на сортировку для работы»; Прошу прощения за то, что я не понимаю этого. Наверное, я спрашиваю, есть ли что-то внутреннее в сортировке внутри компьютерных языков, или если это стратегия, которую люди построили поверх нее. Я думаю, что это последнее, и вы, ребята, это подтвердили. Язык не знает, что он что-то сортирует или нет, но мы признаем разницу в производительности.

Answer 1

Вот ключ. Язык не знает/не может/не должен знать, сортируется или не сортируется ваша структура данных. На самом деле даже не важно, какова структура данных.

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

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

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

Надеюсь, что это немного улучшится.

Answer 2

может язык знать, когда список отсортирован

Вы имеете в виду интерпретатор языка? Конечно, может проверить, отсортирован ли список, просто проверяя, что каждый элемент «больше», чем предыдущий. Я сомневаюсь, что переводчики это делают; почему им должно быть интересно, отсортирован ли список или нет?

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

AFAIK Язык, я использую ...

(? Что)

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

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

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

Answer 3

Языки не знают таких вещей.

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

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

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

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