Параллельное программирование



              

Нахождение последнего элемента списка - часть 2


Однако, она становится возможной, если использовать образ списка.

Модифицируем представление каждого элемента массива R, введя дополнительное поле D, в которое заносится ссылка на соответствующее поле того элемента списка, ссылка на который содержится в поле C. Строить образ списка целесообразно одновременно с формированием и изменением самого списка. Таким образом, элемент образа списка превращается в тройку (F, C, D). На рис. 1.1

структура элемента образа списка представлена в графической форме.

Элемент образа списка

Рис. 1.1.  Элемент образа списка

На рис. 1.2,а изображен список, соответствующий записи L = (A B E F G H Г) (для простоты считаем, что он не содержит подсписков).

Пошаговое нахождение последнего элемента списка (последовательное расположение элементов в памяти)

Рис. 1.2.  Пошаговое нахождение последнего элемента списка (последовательное расположение элементов в памяти)

Пусть над всеми его элементами последовательно, начиная с головы, производится следующее действие: поле D текущего элемента принимает значение того поля D, на которое указывает содержащаяся в нем ссылка (если в поле D содержится ссылка на пустой элемент, то его значение не изменяется). В результате список L примет вид, показанный на рис. 1.2,б. Вид списка L после второго прохода показан на рис. 1.2,в. И, наконец, после третьего прохода поле D головы списка будет содержать ссылку на последний элемент списка L, на чем выполнение алгоритма заканчивается (рис. 1.2,г).

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

Пошаговое нахождение последнего элемента списка (произвольное расположение элементов в памяти)

Рис. 1.3.  Пошаговое нахождение последнего элемента списка (произвольное расположение элементов в памяти)

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

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


Содержание  Назад  Вперед