Здравствуйте, Muxa, Вы писали:

S>>е занимает 0 байт?
M>читаем внимательно

Автор: Muxa
Дата: 14.08.10

M>(последняя строка)

это значит не используя дополнитольно ни одного байта (костантного значения дополнительной памяти).
т.е. имея только список и работая тольо с ним.

Очевидно что e это внешняя по отношению к списку переменная.

S>Очевидно что e это внешняя по отношению к списку переменная.
Очевидно что е изначально это указатель на первый элемент списка.
А вашу фразу я не понял.

Здравствуйте, Muxa, Вы писали:

S>>Очевидно что e это внешняя по отношению к списку переменная.
M>Очевидно что е изначально это указатель на первый элемент списка.
M>А вашу фразу я не понял.
Очевидно что e изначально не относится к списку и e занимает дополнительную память, отличную от 0-я байт. Это противоречит вашему требованию, которое я процитировал в предыдущем сообщении.

S>Очевидно что e изначально не относится к списку и e занимает дополнительную память, отличную от 0-я байт.
... слово "дополнительно" везде выше в этой ветке какбэ намекаэ.

Здравствуйте, Muxa, Вы писали:

S>>Очевидно что e изначально не относится к списку и e занимает дополнительную память, отличную от 0-я байт.
M>... слово "дополнительно" везде выше в этой ветке какбэ намекаэ.
Ну да, намекаэ на то, что эта дополнительная память не относится к памяти, отведенной под элементы списка.

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

S>Пройти по списку совсем без дополнительной памяти можно, но это будет деструктивное прохождение, т.к. как минимум одним элементом придется пожертвовать
да это понятно. у меня была идея "как бы сохранять" путь назад при помощи xor'ов где-либо (в next или value), что бы была возможность восстановить и "вернуться назад" по списку. но что-то ничего путного не придумалось.

Здравствуйте, Muxa, Вы писали:

M>это значит не используя дополнитольно ни одного байта (костантного значения дополнительной памяти).
M>т.е. имея только список и работая тольо с ним.

Какие тогда операции над списком доступны?

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

Что это за инструкции?

// модель процессора
int mem[];
int reg;

// операнды
int& dst(bool m, bool r, int offset)
{
  return m ? mem[ (r?reg:0)+offset ] : reg;
}
int src(bool m, bool r, int offset, int addend)
{
  return m ? mem[(r?reg:0)+offset]+addend : r ? reg+addend : addend;
}
// возможна какая-нибудь двойная косвенность
int src2(bool r1, int a, bool r2, int b, int c) { return src(true,r2,src(true,r1,a,b),c)); }
  // mem[mem[reg*r1+a]+reg*r2+b]+c
int dst2(bool r1, int a, bool r2, int b) { return dst(true,r2,src(true,r1,a,b)); }
  // mem[mem[reg*r1+a]+reg*r2+b]

// операции
void set(int& d, int s) { d = s; }
void add(int& d, int s) { d += s; }
void swap(int& d1, int& d2) { int t=d1; d1=d2; d2=t; }
int test(int s1, int s2) { return s1-s2; } // проверка на знак и ноль

Тогда поиск концевого узла, к примеру, выглядит так

while(test(src(1,1,0,0),src(0,0,0,0)) // while(mem[reg]==0) // while(node->next)
  set(dst(0,1,0),src(1,1,0,0));       //   reg = mem[reg];  //   node = node->next

Всё, что мы можем сделать — это исхитриться временно использовать содержимое узлов. И каким-то образом восстанавливать это содержимое...
Был бы хоть один ещё регистр...

К>Всё, что мы можем сделать — это исхитриться временно использовать содержимое узлов. И каким-то образом восстанавливать это содержимое...
все, я починил!
в общем исхитрился но уронить это очень просто. работает — вот и не трожь.

struct list_elem {
    list_elem *next;
    int *value;
};

int main(int argc, char* argv[]) {
    // формируем список
    list_elem e5; e5.next = NULL; e5.value = (int*)malloc(sizeof(int)*1); *e5.value = 5;
    list_elem e4; e4.next = &e5;  e4.value = (int*)malloc(sizeof(int)*1); *e4.value = 4;
    list_elem e3; e3.next = &e4;  e3.value = (int*)malloc(sizeof(int)*1); *e3.value = 3;
    list_elem e2; e2.next = &e3;  e2.value = (int*)malloc(sizeof(int)*1); *e2.value = 2;
    list_elem e1; e1.next = &e2;  e1.value = (int*)malloc(sizeof(int)*1); *e1.value = 1;
    list_elem e0; e0.next = &e1;  e0.value = (int*)malloc(sizeof(int)*1); *e0.value = 0;
    list_elem *e = &e0;

    // первые 4 бита адреса используем для хранения информации необходимой для прохождения списка в обратном порядке
    do {
        ((list_elem *)(((int)e->next) & 0x00FFFFFF))->next = (list_elem *)((((int)e->next ^ (int)e) << 24) | (int)((list_elem *)(((int)e->next) & 0x00FFFFFF))->next);
        e = (list_elem *)((int)e->next & 0x00FFFFFF);
    } while(e->next != NULL && ((int)((((list_elem *)(((int)e->next) & 0x00FFFFFF))->next)) & 0x00FFFFFF) != NULL);

    // обходим спискок с конца, удаляя данные из узлов
    do{
        free(((list_elem *)((int)e->next & 0x00FFFFFF))->value);
        e = (list_elem *)(((int)e->next >> 24)^((int)e & 0x00FFFFFF));
    } while (((int)e->next &0xFF000000) != NULL);
    free(e->next->value);
    free(e->value);

    return 0;
}

Здравствуйте, Muxa, Вы писали:

К>>Всё, что мы можем сделать — это исхитриться временно использовать содержимое узлов. И каким-то образом восстанавливать это содержимое...
M>все, я починил!
M>в общем исхитрился но уронить это очень просто. работает — вот и не трожь.
M>

M>    // первые 4 бита адреса используем для хранения информации необходимой для прохождения списка в обратном порядке
M>    do {
M>        ((list_elem *)(((int)e->next) & 0x00FFFFFF))->next = ...
M>}

Пишешь 4 бита, а используешь целый байт

S>Пишешь 4 бита, а используешь целый байт
да, да, да.
только подошел исправить, а тут уже подметили.
кстати, последние 2 бита адреса тоже можно приспособить, адреса-то выровнены по 4 байта.

On 15/08/10 21:18, Muxa wrote:

> все, я починил!
По-моему ты какой-то фигнёй страдаешь.

> }while(e->next != NULL&& ((int)((((list_elem *)(((int)e->next)& 0x00FFFFFF))->next))& 0x00FFFFFF) != NULL);
Вот это не удастся посчитать без промежуточного регистра.

Здравствуйте, Muxa, Вы писали:

M>предложи другой вариант без дополнительной памяти. даже без О(1).

Товарищ! Твой вариант тоже не отвечает критерию "без O(1)", ибо исполняемый код тоже занимает память.

Здравствуйте, ssp_alex, Вы писали:

_>На собеседовании задали задачку:
_>есть односвязанный список, необходимо его очистить эффективно начиная с конца без привлечения доплонительных внешних ресурсов (например дополнительной памяти).

Короче говоря, единственное нормальное решение задачи — инвертировать список, после чего пришибить от начала к концу. O(n) времени O(1) памяти. Любые другие решения являются больными. И вот закидайте меня помидорами — лучшего решения не существует в силу устройства этого вашего мира.

M>>предложи другой вариант без дополнительной (!!!!!!111!1) памяти. даже без О(1).
MS>Товарищ! Твой вариант тоже не отвечает критерию "без O(1)", ибо исполняемый код тоже занимает память.
блин, да вы чо? сговорились все что ли?

>> }while(e->next != NULL&& ((int)((((list_elem *)(((int)e->next)& 0x00FFFFFF))->next))& 0x00FFFFFF) != NULL);
.>Вот это не удастся посчитать без промежуточного регистра.
ммм, не вижу куда он (регистр) мог бы разходоваться.

Здравствуйте, Muxa, Вы писали:

>>> }while(e->next != NULL&& ((int)((((list_elem *)(((int)e->next)& 0x00FFFFFF))->next))& 0x00FFFFFF) != NULL);
.>>Вот это не удастся посчитать без промежуточного регистра.
M>ммм, не вижу куда он (регистр) мог бы разходоваться.

Для хранения результатов логических умножений, как минимум.

S>Для хранения результатов логических умножений, как минимум.
я думая это компилятор лишнего наворачивает.
посмотрим во что скомпилировалась эта строка кода:

//    } while(e->next != NULL && ((int)((((list_elem *)(((int)e->next) & 0x00FFFFFF))->next)) & 0x00FFFFFF) != NULL);

004114EA  mov         eax,dword ptr [e] 
004114ED  cmp         dword ptr [eax],0 
004114F0  je          main+157h (411507h) 
004114F2  mov         eax,dword ptr [e] 
004114F5  mov         ecx,dword ptr [eax] 
004114F7  and         ecx,0FFFFFFh 
004114FD  mov         edx,dword ptr [ecx] 
004114FF  and         edx,0FFFFFFh 
00411505  jne         main+109h (4114B9h)

это же самое можно переписать как:
(тут поправьте, если я не прав и такое невозможно)

004114EA  mov         eax,dword ptr [e] 
004114ED  cmp         dword ptr [eax],0 
004114F0  je          main+157h (411507h) 
004114F2  mov         eax,dword ptr [e] 
004114F5  mov         eax,dword ptr [eax] 
004114F7  and         eax,0FFFFFFh 
004114FD  mov         eax,dword ptr [eax] 
004114FF  and         eax,0FFFFFFh 
00411505  jne         main+109h (4114B9h)

Здравствуйте, Muxa, Вы писали:

S>>Для хранения результатов логических умножений, как минимум.
M>я думая это компилятор лишнего наворачивает.

O(x) оценивает количество алгоритмических ячеек, а не число регистров на конкретной архитектуре. Потому дело не в компиляторе и не в том, используется ли [ecx]. Для того чтобы воспользоваться результатом логического умножения в абстрактной архитектуре, требуется этот результат получить и сохранить в некоторой ячейке (неважно, регистр, стек или куча).

S>O(x) оценивает количество алгоритмических ячеек, а не число регистров на конкретной архитектуре.
это ты точке

Автор: .
Дата: 15.08.10

скажи.

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

Здравствуйте, Muxa, Вы писали:

S>>O(x) оценивает количество алгоритмических ячеек, а не число регистров на конкретной архитектуре.
M>это ты точке

Автор: .
Дата: 15.08.10

скажи.

S>>Для того чтобы воспользоваться результатом логического умножения в абстрактной архитектуре, требуется этот результат получить и сохранить в некоторой ячейке (неважно, регистр, стек или куча).
M>но ведь это может быть таже самая ячейка где у нас до этого хранился операнд.
M>(если операнд далее не нужен, мы можем его спокойно перетереть).
M>согласен?
Ты говоришь о некоторой конкретной архитектуре. А в общем случае ячейка под операнд могла и не выделяться.

Что же касается конкретной архитектуры, то ячейка под операнд — это уже дополнительная память по отношению к списку.
Хорош извращаться. Так академические задачи не решают.