Swift 3 и индекс типа пользовательского связанного списка

В Swift 3 Collection индексы должны соответствовать Comparable вместо Equatable.

Полная история может быть прочитана здесь быстрая эволюция /0065.

Здесь соответствующая цитата:

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

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

Мне любопытно, как бы вы реализовали Comparable для связанного индекса списка с сложностью O (1)?

Единственная идея, которую я сейчас имею, - это как-то подсчитать шаги, продвигая индекс, сохраняя его в типе индекса как свойство, а затем сравнивая эти значения.

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

EDIT: Это можно сделать за счет двух дополнительных целых чисел в качестве свойств коллекции, предполагая, что один связанный список реализует переднюю вставку, переднее удаление и обратно. Любое вмешательство в середине будет в любом случае нарушать требование сложности O (1).

Ответы

Ответ 1

Здесь я принимаю это.

a) Я ввел одно свойство частного целочисленного типа в свой собственный тип Index: depth.

b) Я ввел в коллекцию два свойства частного целочисленного типа: startDepth и endDepth, которые по умолчанию равны нулю для пустого списка.

  • Каждая передняя вставка уменьшает startDepth.
  • Каждый фронт удаления увеличивает startDepth.
  • Каждое приложение назад увеличивает endDepth.

Таким образом, все индексы startIndex..<endIndex имеют отражающий целочисленный диапазон startDepth..<endDepth.

c) Всякий раз, когда коллекция обменивает индекс либо startIndex, либо endIndex, он наследует свое соответствующее значение глубины из коллекции. Когда сбор запрашивается для продвижения индекса, вызывая index(_ after:), я просто инициализирую новый экземпляр Index с увеличенным значением глубины (depth += 1).

Соответствие Comparable сводится к сопоставлению значения глубины левой стороны с правой стороной.

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

Вывод:

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

Если у кого-то есть лучшее решение, я бы с радостью посмотрел на него!

Ответ 2

У меня может быть другое решение. Если вы используете float вместо целых чисел, вы можете получить некоторую производительность O (1) вставки в середине, если вы установите sortIndex вставленного node в значение между предшественником и преемником sortIndex, Это потребует хранения (и обновления) предшественника sortIndex на ваших узлах (я думаю, это не должно быть сложно, поскольку оно изменяется только при вставке или удалении, и оно всегда может быть распространено "вверх" ).

В вашем методе index(after:) вам нужно запросить преемника node, но так как вы используете свой индекс node, это просто.

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

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