Приветствую!

Значит так, задача состоит в следующем: надо инвертировать двусвязный список, скажем длинной n от места k до места i. Скорость нужна очень высокая.
Вот что я придумал:
1) просто поменять местами k<->i, k+1<->i-1, k+2<->i-2 ... k+(i-k)/2<->i-(i-k)/2 не подходит, долго работает.

2) каждому элементу в списке (структуре) добавить флаг, который бы указывал на каком из двух указателей лежит следующий элемент. Это ускорит работу где-то в два раза, т.к. функция "переворачиваниа" очень проста - с 1 на 0 и обратно и не нужно будет физически менять местами данные. Таким образом, алгоритм следующий:
Для начала объявим структуру:

Цитата

typedef struct Elem {     struct Elem Link[2];     int Data;     bool Direction; } TElem;

Во всех элементах, начиная от k и кончая i инвертировать бит направления - Direction. Для этого достаточно одной команды: not [esi].Direction. Так, если мы будем считывать после переворота список, то будем знать в какой указатель (Link[]) нам нужно идти, чтобы дойти до следующего элемента.

Но я пошел дальше...
3) Допустим, что у всех элементов, указатель Link[1] - указывает на предыдущий, а Link[0] - на следующий. Далее, если мы делаем инверсию между элементами А1 и А4 (не включаиа их), то:
Обозначим
A2=A1->Link[0] (следующий от А1)
A3=A4->Link[1] (предыдущий от А4)

Алгоритм следующий:

Цитата

I.   A1->Link[0]=A3 II.  A3->Link[0]=A1 III. A2->Link[0]=A4 IV.  A4->Link[0]=A2 V.   A3->Direction= not A3->Direction VI.  A4->Direction= not A4->Direction

Теперь попробуем прочитать этот список таким правилом: если мы натыкаемся на 1 в Direction, то меняем текущее направление на противоположное. И так рассмотрим пример для большей ясности:

A={1,2,3,4,5,6,7};

Представим как двусвязный список:

введем обозначение - [p|An|D|n]
p - указатель на предыдущий элемент;
n - указатель на следующий элемент;
An - данное в структуре (число);
D - флаг направления: 1 - инвертировать, 0 - оставить прежнее.

<-[1|A=1|0|0]<->[1|A=2|0|0]<->[1|A=3|0|0]<->[1|A=4|0|0]<->[1|A=5|0|0]<->[1|A=6|0|0]<->[1|A=7|0|0]->

Сделаем инверсию с А1 по А6 (не включая границы)
А2=2, А3=5

после выполнения алгоритма

<-[1|A=1|0|0]<->[0|A=5|1|1]<->[0|A=4|0|1]<->[0|A=3|0|1]<->[0|A=2|0|1]<->[1|A=6|1|0]<->[1|A=7|0|0]->

Как обходить такой список? А очень просто: берем переменную булевского типа и инициализируем ее нулем. Далее легко понять по какой схемме меняется направление:

если было направление 0 и в элементе флаг 0, то далее направление будет 0
если было направление 0 и в элементе флаг 1, то далее направление будет 1
если было направление 1 и в элементе флаг 0, то далее направление будет 1
если было направление 1 и в элементе флаг 1, то далее направление будет 0

т.е. простым русским языком это XOR
и так можно написать такую программу для обхода:

Цитата

bool D=0; TElem *E=head; for (int i=0; i<7; i++) {   D^=E->Direction;   E=E->Link[D]; }

Процедура инверсии работает и делает это очень быстро.
А теперь внимание, вопрос: Если в цепочке будет уже один раз перевернута подцепочка, то такая цепочка неправильно будет инверсированна. Как этого избежать? Какие ваши идеи? Заранее благодарен.

Ты не мог бы закинуть весь свой код в последней редакции ?

Это мне нужно для написания эвристик для решения транспортной задачи. Ниже я привел код своей программы (из него убраны нерелевантные участки). Не обращайте внимания на некоторые, казалось бы, ненужные функции; дело в том, что я буду их "зашивать" в DLL. Я написал пояснения к строкам, так, Вам будет много легче разбирать этот код. Программа должна оптимизировать путь через семь городов известной эвристикой 2-OPT. Проблема этой программы заключается в том же самом: цепочка, в которой уже присутствует другая инверсированная цепочка, будет инверсирована неправильно.

Цитата

#include <iostream.h> // Задает указатель на матрицу расстояний void SetDistancesMatrix(unsigned long *M); // Задает начальную последовательность городов, которую нужно оптимизировать void SetData(unsigned int *CitiesData, unsigned int N); // Возвращает оптимизированную последовательность городов int GetData(unsigned int *CitiesData); // Собственно эвристическая процедура 2-OPT пользуется указателями, которые задали в вышеуказанных функциях bool Perform2OPT(); // Структура, характеризующая город. Включает в себя все поля, которые были оговорены в описании алгоритма. typedef struct City {         unsigned int Data;         struct City *Link[2];         bool Direction; } TCity; // Указатель на начало и на конец дву-связного списка, вспомогательный указатель. TCity *Head=NULL, *Tail=NULL, *Last; // Указатель на матрицу расстояний между городами. unsigned long *Distance; // Количество городов в последовательности int Num; // Это пример использования всех этих функций. Представим себе, что они в DLL void main(void) {         const n=7; // Количество городов         // Текущая матрица расстояний между городами. Она имеет вид: D[C1][C2] - расстояние от города С1, до города С2;         unsigned long D[n*n] ={6,3,8,2,6,4,9,                                             /**/   3,2,7,1,7,2,5,                                             /**/   8,7,5,4,9,3,1,                                             /**/   2,1,4,9,8,2,4,                                             /**/   6,7,9,8,1,5,7,                                             /**/   4,2,3,2,5,3,9,                                             /**/   9,5,1,4,7,9,4};         unsigned int Cities[n]={0,1,2,3,4,5,6}; // Сама последовательность городов.         SetDistancesMatrix(D); // Задаем указатель на матрицу расстояний         SetData(Cities, n); // Задаем последовательность городов и их количество         Perform2OPT(); // Выполняем оптимизацию         GetData(Cities); // Возвращаем значения и выводим их на экран         for (int i=0;i<n; i++) {                 cout<<" "<<Cities[i];         }       cout<<endl; } void SetDistancesMatrix(unsigned long *M) {         Distance=M; } // Процедура для создания духсвязного списка в памяти для переданной последовательности void SetData(unsigned int *CitiesData, unsigned int N) {         TCity *C; Num=N; // Временная переменная, для обхода списка. Сохранение количества городов         // Создание первого элемента и последнего. Эти элементы не включаются в последовательность.         // Таким образом, количество элементов в дву-связном списке будет Num+2         Head=new TCity;  Tail=new TCity;  Last=Head;         Head->Data=0;  Tail->Data=0; // Обнуление номера города (не имеет значения)         // Установка направления: указатель в массиве :Link с индексом 0 указывает вперед, а с 1 - назад         Head->Direction=0;      Tail->Direction=0;         // Предыдущий элемент для начального не существует. Предыдущий для последнего есть первый.         Head->Link[1]=NULL;     Tail->Link[1]=Head;         // Следующий у первого есть последний. Следующего элемента у последнего не существует.         Head->Link[0]=Tail;     Tail->Link[0]=NULL;         for (int i=0; i<Num; i++) { // Цикл для вставки элементов в двусвязный список.                 C=new TCity; // Создание нового элемента в списке                 C->Data=CitiesData[i];                // Запись номера города в элемент                 // Задание направления: 0 означает, что указаель с индексом 0 - указывает на следующий и наоборот.                 C->Direction=0;                 C->Link[1]=Last;                          // Предыдущий элемент от нового                 Last->Link[0]=C;                          // Следующий элемент от предыдущего - это новый элемент                 Last=C;                                        // Продвижение указателя для добавления большего числа элементов         }         // "Приклеивание" последнего элемента.         Tail->Link[1]=Last; Last->Link[0]=Tail; } // Функция для возврата информации (оптимизированная последовательность) int GetData(unsigned int *CitiesData) {         int Idx=0; bool Direction=0; // Индекс города в массиве и начальное направление         // Временный указатель для обхода списка инициализируется первым элементом с городом         TCity *C=Head->Link[0];         while (C!=Tail) { // Пока не дошли до последнего элемента                 // Обход списка по алгоритму, указанному выше.                 CitiesData[Idx++]=C->Data; // Передача номера города в массив                 Direction^=C->Direction;       // Одновление бита направления                 C=C->Link[Direction];            // Продолжить обход         }         return Idx-1;    // возвратить количество городов, которые были записаны. } // Функция оптимизации по 2-OPT алгоритму bool Perform2OPT() {         TCity *I1, *I2, *J1, *J2;  // Указатели вместо А1, А2, А3, А4 (как было описано в алгоритме)         bool D=0, Result=false; // Бит направления и результат была ли оптимизирована последовательность или нет. Next:         I1=Head->Link[0];         // I1 указывает на первый элемент в списке         do {                 D^=I1->Direction; // Обновление направления                 I2=I1->Link[D];     // I2 указывает на следующий от I1                      D^=I2->Direction; // Обновление направления                 J1=I2->Link[D];     // J1 указывает на следующий от I2                 do {                         D^=J1->Direction; // Обновление направления                         J2=J1->Link[D];     // J2 указывает на следующий от J1                         // Следующее условие выполняется тогда, когда расстояние между городами I1-J1 в сумме                         // с расстоянием между городами I2-J2 меньше чем расстояние I1-I2 + J1-J2 (текущее),                         // то необходимо поменять местами все города между I2 и J1, включая их самих.                         if ((Distance[I1->Data*Num+J1->Data]+Distance[I2->Data*Num+J2->Data])<                                                 (Distance[I1->Data*Num+I2->Data]+Distance[J1->Data*Num+J2->Data]))                         {                                 // Вот тут то и начинается мой алгоритм...                                 // Поясню сначала, как вычисляется индекс внутри квадратных скобок. Если элемент,                                 // на который указывает I2, не находится на следующем указателе (с индексом 0) у                                 // I1, значит элемент, на который указывает I1 - перевернут. Т.е. на I2 у него                                 // указывает предыдущий указатель (с индексом 1). Значит именно его мы меняем:                                 // записываем в него адрес J1. Во всем остальном эта строка соответствует первому                                 // пункту моего алгоритма.                                 I1->Link[I1->Link[0]!=I2]=J1;                                 J1->Link[J1->Link[0]!=J2]=I1; // То же самое и для этого переназначения. Соответствует второму пункту                                 J1->Direction=~J1->Direction; // Инверсия флага направления у J1. Пункт 5 (порядок их неважен)                                 I2->Link[I2->Link[1]==I1]=J2; // Пункт 3                                 J2->Link[J2->Link[1]==J1]=I2; // Пункт 4                                 J2->Direction=~J2->Direction; // Пункт 6                                 Result=true; // Последовательность была оптимизирована                                 goto Next; // Здесь лучше плюнуть в лицо модульному программированию и использовать                                            // старые методы, т.к. эффективность повышается.                         }                         J1=J2; // Продвижение указателей J                 } while (J1!=Tail->Link[1]); // Пока J1 не дошел до предпоследнего                 I1=I2; // Продвижение указателей I         } while (I1==Tail->Link[1]->Link[~Tail->Link[1]->Direction]); // Немного сложновато и неэффективно, но если                                                                       // разобраться, то это условие означает - пока I1 не дошел до                                                                       // предпоследнего элемента. Я подумаю, как можно это покороче записать.         return Result; // Вернуть результат. }

З.Ы. Чингачгук, извиняй, что раньше не написал пояснения. Просто перевод их на русский заняло время.

Цитата

Значит так, задача состоит в следующем: надо инвертировать двусвязный список, скажем длинной n от места k до места i. Скорость нужна очень высокая.

Это мне напоминает задачи типа:

Цитата

Задача N_174: Взвесить тело имея только одну линейку. Ответ: из предыдущей задачи берем гирю и ...

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

И каждый вариант умеет столькоже преимуществ сколько и недостатков.

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

А ваще я не разбирался в проге, лень и большая и не читаема (для меня, я привык к ПроЛогу), так что может этот вариант оптимален для данной цели. Но надо точнее формулировать задачу.


Ваще этот цикл оветов посвящен алгоритмическому мышлению - с низким уровнем обобщенности.

Кто-то занимается кодированием проца, а кто-то вводом (накоплением) информации.
Кто-то занимается компиляцией, а кто-то оставляет это компилятору.

Хмм...
Во как!!
Да мне и не нужно память экономить. Скорость нужна высокая.
А что это Вы своим постом хотели сказать? Я ничего из него не понял. Какой-то набор слов...

Цитата

Уменьшилась скорость считывания

А вот сумарная скорость осталось большой? .....
А из:

Цитата

Вариантов куча: 1. менять данные, 2. менять ссылки, 3. менять способ использования ссылки (т.е. считать в конкретном месте проги, что не первая ссылка на следующий элемент, а вторая) 4. добавить элемент направления (Direction) для данного элемента 5. добавить элемент направления указывающий что с текущего элемента все ссылки считаются наоборот N. и т.д. и т.п.

Почему твой метод быстрее? Например, в сравнение с 3-им или с 5-ым?

Потому что вместо того, чтобы менять местами, скажем, 100 элементов; можно изменить значения 4-х указателей.
Да и вообще мой метод - это тот, что у тебя под пунктом 4 и 5. Это и есть мой способ!

Что ты преципился к 1-му пункту - его не существет.

Для танкистов:
Пункты 4 и 5 не пересекаются.
Т.к. для 4-го Direction считается только для текужего элемента. А в 5-м для всех последующих (ну теги в http(xml)).
Что, у тебя оба варианта используются (Зачем?)

А как насчет 3-го: (repeat:) в конкретном месте проги, в конкретной процедуре (функции) в конкретно цикле имеется дополнительная переменная (константа) указывающая на порядок считывания ссылок. Т.е. не списки "типа" инвертировать, а прогу так завернуть, чтоб они не инвертировались "на самом деле" (да и чтоб никто разобраться в коде не мог ). Ну, например, почему просто не держать номер, ссылку, на первый (последний) "типа" инвертированный элемент. Ну короче: Программа = Данные + Логика + Интерпретатор, и надо думать не только о данных, но и о логике их интерпретации.

А насчет:

Цитата

алгоритмического мышления

. Частенько просматривая "принцЫпы кодЫрования" на всяких низкоуровневых языках типа си (ну всех алгоритмических) в форумах; по постановке вороса, по отношению к проблеме, по акцентам слов (выражений), ведению разговора (<- это все чтоб не придирались) - возникает такое ощущение (мягко сказано): что чел пытается хм... всякими ухищрениями получить из двух яблок три (ловкость рук и никакого мошенничества). Нет, конечно я понимаю отношение к проблеме: выжать из системы все по максимуму (не только ПроЛог я знаю, было время). Но законы Физики не обойдешь, не поломаешь, ...
... и Соционика дает свое: челы делятся на "Искателей" недокументированных возможностях проги, функции, команды и "Системщиков" (иль "Аналитиков") окружающих "фактов", реалий окружающих явлений. У которых решение проблемы уложены в некие (довольно абстрактные) рамки алгоритма решения, у которых меняется цель: "описание" сути проблемы, а не поиск алгоритма ее достижения и "ускорении" каждого его шага. Ибо из "описания" следует глобально эффективнейший алгоритм, и для всех вариантов целей проблемы.

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

(Для сомневающихся) Эффективность проста: не делать лишних движений. (сказано в попыхах, не оговорены все понятия в предложении <- это для отката, но не отказа) Правда, может, для кого-то это звучит красиво-лаконично, но для некоторых пративно-очевидно, как "Вода мокрая".

А в "описание" входит НЕ только то, что вы думаете ...
... и кому-то это не нравится.

Вопрос все еще открыт!

Пока был только офтоп...

Безо всякого направления, это лишнее.
Если я правильно понял - обход в правильном направлении делается очень редко, в основном изменение направления.
Тогда: существует двунаправленный список, ссылки которого могут быть Null или другой элемент (как и было). Добавим дополнительное условие: следующий элемент не может быть предыдущим, т.е. если А имеет ссылку на В, В имеет ссылку на А и С, направление обхода выбирается в сторону С, т.к. предыдущий элемент был А.
Значит для изменения направления достаточно перепривязать концы цепочки.

Это сообщение отредактировал(а) ovr2000 - 20.12.2004, 13:06

Не совсем понял, а что структуру списка можно изменять, или нужно составить алгоритм непосредственно для типа

Код

typedef struct Elem {    struct Elem *Link[2];    int Data;    bool Direction; } TElem;

Цитата(3)

Не совсем понял, а что структуру списка можно изменять, или нужно составить алгоритм непосредственно для типа

менять можно.
Добавлено @ 22:32

Цитата(ovr2000 @ 20.12.2004, 12:05)

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

А чем этот вариант лучше? Надо бы обдумать этот вариает ...

Господи, ребята. Это же стандартная и довольно простая задача. Один переворот делается за O(1), и многие мои знакомые это много раз писали. Я сам это писал на чемпионате ACM.

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

Если надо - могу прокомментировать и ответить на конкретные вопросы.

Вкратце - можно ставить флажки и использовать структуру данных DEC.

1) o(1) = o(0)

2)

Цитата

Вкратце - можно ставить флажки и использовать структуру данных DEC.

С этого места можно поподробнее.

Если тебе нужно проходить какие-то куски списка в прямом направлении, какие-то в обратном тогда может помочь следующее

Код

BYTE InverseDirection; YourListPointer* Array = {Next,Prev}; YourListPointer GetNextPointer() {   return Array[InverseDirection]; }

Если изменить стурктуру, то.

Код

for(Current = Element_I; Current != Element_K && Current; ) {   Temp = Current->Next;   Current->Next = Current->Prev;   Current->Prev = Temp;   Current = Temp; } Element_I->Prev->Next = Element_K; Element_I->Next->Prev = Element_K; Element_K->Prev->Next = Element_I; Element_K->Next->Prev = Element_I;

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

Это сообщение отредактировал(а) podval - 18.2.2005, 20:04