<bgdev />free

Вход

Претърсване на дърво с 12 инструкции и само един регистър.
0

#55517 (ツ) johnfound
Създадено на 07.01.2022, видяно: 502 пъти.

Задачата е по дадено листо от дървото, да се намери следващото листо. Ако няма следващо, зарежда първото, тоест върти в кръг. Ако дървото има само един елемент, връща него.

Структурата на дървото е в двойно свързан списък със следене на началото и на края:

struct TObject
  .__parent dd ?       ; родителски елемент
  .__first_child dd ?  ; начало на списъка с дъщерни елементи
  .__last_child  dd ?  ; край на списъка с дъщерни елементи

  .__next   dd ?       ; следващ елемент
  .__prev   dd ?       ; предишен елемент
ends

Измислих супер код от 12 инструкции с използването само на един регистър:

; EAX == начален елемент

.next:
        cmp     [eax+TObject.__next], 0
        cmovne  eax, [eax+TObject.__next]
        jne     .down_to_leaf

        cmp     [eax+TObject.__parent], 0
        cmovne  eax, [eax+TObject.__parent]
        jne     .next

.back_to_first:
        cmp     [eax+TObject.__prev], 0
        cmovne  eax, [eax+TObject.__prev]
        jne     .back_to_first

.down_to_leaf:
        cmp     [eax+TObject.__first_child], 0
        cmovne  eax, [eax+TObject.__first_child]
        jne     .down_to_leaf

; EAX == следващ елемент.
#55518 (ツ) Rabin
Създадено на 07.01.2022, видяно: 499 пъти.

Време е да се засватите с оня Учителя, Теодоси Теодосиев. Единия побърква децата от задачи по физика, от 9 сабалем до 12 нощта. Тизе решаваш проблеми от времето на феритните памети.

Микс между вашите науки ще роди хибрид м/у въшка и светулка. Да се пощим у тъмното без да хабим свещи.

#55521 (ツ) johnfound
Създадено на 07.01.2022, видяно: 494 пъти.
Rabin

Време е да се засватите с оня Учителя, Теодоси Теодосиев. Единия побърква децата от задачи по физика, от 9 сабалем до 12 нощта. Тизе решаваш проблеми от времето на феритните памети.

Микс между вашите науки ще роди хибрид м/у въшка и светулка. Да се пощим у тъмното без да хабим свещи.

Я ни покажи как се прави на Java.

#55525 (ツ) Rabin
Създадено на 07.01.2022, видяно: 492 пъти.
johnfound
Rabin

Време е да се засватите с оня Учителя, Теодоси Теодосиев. Единия побърква децата от задачи по физика, от 9 сабалем до 12 нощта. Тизе решаваш проблеми от времето на феритните памети.

Микс между вашите науки ще роди хибрид м/у въшка и светулка. Да се пощим у тъмното без да хабим свещи.

Я ни покажи как се прави на Java.

Жаварите не се занимаваме с такива неща, имаме по-смислени занимания, примерно да ти направим банковата транзакция, или застраховането. Всичко туй дето те мъчи няма сми дори за embedded, в момента orange pi zero е нещо като 7 $, има повече мощ от виртуалката ти.

#55527 (ツ) johnfound
Създадено на 07.01.2022, видяно: 486 пъти.
Rabin

Жаварите не се занимаваме с такива неща, имаме по-смислени занимания

Проблема не е в това дали се занимавате или не. Проблемът е в това, че даже игла с ваксина да ви опрат, пак няма да можете да го направите. :-P

#55533 (ツ) Rabin
Създадено на 07.01.2022, видяно: 481 пъти.
johnfound
Rabin

Жаварите не се занимаваме с такива неща, имаме по-смислени занимания

Проблема не е в това дали се занимавате или не. Проблемът е в това, че даже игла с ваксина да ви опрат, пак няма да можете да го направите. :-P

И инокулат да ми опрат - не мога да свира на хармоника, говоря през стомаха си, и правя шпагат.

Няма сми от твойте задачки. Като почнат да ме занимават с такива по интервюта почвам да се правя на улав и се махам по най-бързия начин. Инак ако ме вземат после няма да можем да се гледаме.

#55534 (ツ) BIGBUGEX
Последно редактирано на 07.01.2022 от BIGBUGEX, видяно: 479 пъти.

__last_child не е ли излишно в случая? В смисъл __last_child == __first_child -> __prev. Без него се получават точно 4 двойни думи за логистика. По-добро подравняване.

#55541 (ツ) johnfound
Последно редактирано на 07.01.2022 от johnfound, видяно: 460 пъти.
BIGBUGEX

last_child не е ли излишно в случая? В смисъл last_child == first_child –> prev. Без него се получават точно 4 двойни думи за логистика. По-добро подравняване.

В конкретния случай, да, не се използва и не е нужно това поле. Просто исках да дам цялата структура на дървото.

А иначе, не е излишно за други задачи. Например, ако искаш да търсиш в обратната посока, кода ще е същият, но с разменени .__next с .__prev и .__first_child с .__last_child.

И въобще, тази структура е част от по-голяма, с много други полета, така че размера така или иначе ще е далеч по-голям.

П.П. А, да. Списъка от елементи е двойно свързан списък, но не е цикличен. Тоест, __last_child != __first_child->__prev, а __first_child->__prev == 0 винаги.

Претърсване на дърво с 12 инструкции и само един регистър.
0

AsmBB v3.0 (check-in: a316dab8b98d07d9); SQLite v3.42.0 (check-in: 831d0fb2836b71c9);
©2016..2023 John Found; Licensed under EUPL. Powered by Assembly language Created with Fresh IDE