В какой-то момент возникла идея переключиться на оптимизацию. Как выяснилось, с уменьшением размера программы она становится более доступной для понимания и отладки.
Это наблюдение вполне совпадает с моим опытом. И показывает, что в ассемблере не надо боятся оптимизировать на ранних стадиях разработки. Они часто помогают сделать код проще и понятнее.
Интернет вообще пытаются поставить под контролем. В России – государство, в Европе и США – корпорации. (и я не знаю что хуже).
И поставят. Так как те, которые это делают, работают осознанно и согласовано. А те, которые сопротивляются – сопротивляются вяло, разрозненно и без ясного плана.
Да, конечно. Но там говорили что возникает случайность. А мне кажется, что случайность здесь как-то не очень случайная. По крайней мере, имея "случайную комбинацию" всегда можно определить к какому из двух сетов она принадлежит.
ЕМНИП, в пятнашках нельзя получить все возможные конфигурации. Существуют два сета. Один, который можно решить до "1..2....14..15" и второй, (зеркальный, что ли?) который можно решить до "1..2....15..14" (но не до "1..14..15").
Это и есть бинарный поиск. Кто сказал, что деление должно быть в середине? Нет, деление должно быть на две части. А в середине или нет, не имеет значения.
Ну, я взял и сделал некоторые тесты. Выходит, что если поиск в 32 битовом массиве, то линейный поиск быстрее при размерах массива меньше чем 8 элементов. Примерно до размер в 10 элементов идут наравне и после этого бинарный поиск всегда быстрее.
Выглядит примерно так: (время по Y в мкс за 1 000 000 повторении)
Код (FASM/FreshLib)
include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 0
include "%lib%/freshlib.asm"
MAX_ARRAY_SIZE = 20
REPEAT_TEST = 1000000
uglobal
array rd MAX_ARRAY_SIZE
tstart dd ?
timelin dd ?
timebin dd ?
endg
start:
InitializeAll
xor ecx, ecx
.init_array:
mov [array+4*ecx], ecx
inc ecx
cmp ecx, MAX_ARRAY_SIZE
jne .init_array
xor ebx, ebx
inc ebx
mov ecx, $0fffffff
.heat1:
dec ecx
jnz .heat1
.size_loop:
stdcall GetFineTimestamp
mov [tstart], eax
mov ecx, REPEAT_TEST
xor esi, esi
.lin_repeat:
dec ecx
js .end_lin_repeat
; here esi is the value searched and ebx is the size of the array.
; ecx is the current repeat counter, preserve it!
inc esi
xor eax, eax
cmp esi, ebx
cmovae esi, eax
.search_lin:
cmp [array+4*eax], esi
je .lin_repeat ; element found
inc eax
cmp eax, ebx
jb .search_lin
jmp .lin_repeat ; element not found (not possible!)
.end_lin_repeat:
stdcall GetFineTimestamp
xchg eax, [tstart]
sub eax, [tstart]
neg eax
mov [timelin], eax
mov ecx, REPEAT_TEST
xor esi, esi
.bin_repeat:
dec ecx
js .end_bit_repeat
; here esi is the value searched and ebx is the size of the array.
; ecx is the current repeat counter, preserve it!
xor edi, edi ; start
mov edx, ebx
dec edx
inc esi
cmp esi, ebx
cmovae esi, edi
.loop_bin:
cmp edi, edx
ja .bin_repeat ; element not found (not possible!)
lea eax, [edi+edx]
shr eax, 1 ; middle.
cmp esi, [array+4*eax]
je .bin_repeat ; element found!
jb .move_end
; move the start of the interval
lea edi, [eax+1]
jmp .loop_bin
.move_end:
lea edx, [eax-1]
jmp .loop_bin
.end_bit_repeat:
stdcall GetFineTimestamp
xchg eax, [tstart]
sub eax, [tstart]
neg eax
mov [timebin], eax
; Output comma separated values.
stdcall NumToStr, ebx, ntsDec or ntsSigned
mov edx, eax
stdcall StrCat, edx, txt ", "
stdcall NumToStr, [timelin], ntsDec or ntsSigned
stdcall StrCat, edx, eax
stdcall StrDel, eax
stdcall StrCat, edx, txt ", "
stdcall NumToStr, [timebin], ntsDec or ntsSigned
stdcall StrCat, edx, eax
stdcall StrDel, eax
stdcall StrCat, edx, <txt 13, 10>
stdcall FileWriteString, [STDOUT], edx
stdcall StrDel, edx
inc ebx
cmp ebx, MAX_ARRAY_SIZE
jbe .size_loop
FinalizeAll
stdcall TerminateAll, 0
Вообще, все эти оценки производительности (О-нотация) асимптотические. То есть, это оценка производительности, когда число итерации стремиться к бесконечности.
А для малых массивов, линейный поиск будет категорично быстрее. Просто из за того что у алгоритма банально меньше инструкции.
Кстати, то же самое и даже в большей мере верно и для сортировки. Для маленьких массивов сортировка пузырьком быстрее из за простотой кода. Это известный факт, который используют например чтобы ускорить другие методы сортировки, используя метод пузырьком когда размер сортируемого отрезка меньше некоторой границы.
М-да-а-а. Заминусовали некурящие. Дискриминация чистой воды. Это курильщики самые толерантные люди. Никто и никогда не видел курильщика задирающего некурящего за то что тот не курит.
Sorry, you can't view or download this file at this time.
Too many users have viewed or downloaded this file recently. Please try accessing the file again later. If the file you are trying to access is particularly large or is shared with many people, it may take up to 24 hours to be able to view or download the file. If you still can't access a file after 24 hours, contact your domain administrator.
Продолжительность жизни особи с точки зрения эволюции (если бы вдруг у нее могла быть такая точка) крайне малозначительный параметр. Имеет значение период репродуктивной активности, а после его окончания — это просто мясо.
Конечно это именно так. Но период репродуктивной активности напрямую связан с продолжительностьи жизни. Я бы сказал, что это один и тот параметр. Можно сразу написать что Tж > Tр. Но мне кажется, что даже Тж ~ Tр + Тв (Тв — время выращивания потомства) будет верно.
Никто не знает как именно работает эволюция. Но то, что она иногда может действовать очень быстро, мне кажется уже доказано.
Например когда в городах смертность уменьшилась, сразу уменьшилась и рождаемость. Да, для каждого из этих двух явлении есть независимое и несвязанное объяснение, но в итоге популяция все равно отрегулировалась, перенаселение не получится. Может эволюция может действовать и посредствум медицины, образования и шоу индустрию?
Это наблюдение вполне совпадает с моим опытом. И показывает, что в ассемблере не надо боятся оптимизировать на ранних стадиях разработки. Они часто помогают сделать код проще и понятнее.
+1 Firefox.
Интернет вообще пытаются поставить под контролем. В России – государство, в Европе и США – корпорации. (и я не знаю что хуже).
И поставят. Так как те, которые это делают, работают осознанно и согласовано. А те, которые сопротивляются – сопротивляются вяло, разрозненно и без ясного плана.
Неясно только причем здесь "open source". Разработка закрытая, исходники никуда не публикуются, комюнити не участвует никак.
Да, конечно. Но там говорили что возникает случайность. А мне кажется, что случайность здесь как-то не очень случайная. По крайней мере, имея "случайную комбинацию" всегда можно определить к какому из двух сетов она принадлежит.
Статья – гимн переинженеринга.
ЕМНИП, в пятнашках нельзя получить все возможные конфигурации. Существуют два сета. Один, который можно решить до "1..2....14..15" и второй, (зеркальный, что ли?) который можно решить до "1..2....15..14" (но не до "1..14..15").
Это и есть бинарный поиск. Кто сказал, что деление должно быть в середине? Нет, деление должно быть на две части. А в середине или нет, не имеет значения.
Ну, я взял и сделал некоторые тесты. Выходит, что если поиск в 32 битовом массиве, то линейный поиск быстрее при размерах массива меньше чем 8 элементов. Примерно до размер в 10 элементов идут наравне и после этого бинарный поиск всегда быстрее.
Выглядит примерно так: (время по Y в мкс за 1 000 000 повторении)
Вообще, все эти оценки производительности (О-нотация) асимптотические. То есть, это оценка производительности, когда число итерации стремиться к бесконечности.
А для малых массивов, линейный поиск будет категорично быстрее. Просто из за того что у алгоритма банально меньше инструкции.
Кстати, то же самое и даже в большей мере верно и для сортировки. Для маленьких массивов сортировка пузырьком быстрее из за простотой кода. Это известный факт, который используют например чтобы ускорить другие методы сортировки, используя метод пузырьком когда размер сортируемого отрезка меньше некоторой границы.
Ну, насколько? На 382К$
Летом конечно прекрасно.
М-да-а-а. Заминусовали некурящие. Дискриминация чистой воды. Это курильщики самые толерантные люди. Никто и никогда не видел курильщика задирающего некурящего за то что тот не курит.
То что ютубе платит автору клипа, это не авторские отчисления.
Хм, красиво, конечно. Плюсанул. Но возник вопрос – А покурить у вас есть где?
Too many users have viewed or downloaded this file recently. Please try accessing the file again later. If the file you are trying to access is particularly large or is shared with many people, it may take up to 24 hours to be able to view or download the file. If you still can't access a file after 24 hours, contact your domain administrator.
Как раз, числа не "псевдослучайные", потому что участвует человек и определить заранее когда он нажмет на кнопку невозможно в принципе.
Конечно это именно так. Но период репродуктивной активности напрямую связан с продолжительностьи жизни. Я бы сказал, что это один и тот параметр. Можно сразу написать что Tж > Tр. Но мне кажется, что даже Тж ~ Tр + Тв (Тв — время выращивания потомства) будет верно.
Ну-у-у, нагрузка – не нагрузка, а женщины все-равно живут дольше. Что-то не вяжется.
Вообще-то, после 40..50, но да, это так.
Никто не знает как именно работает эволюция. Но то, что она иногда может действовать очень быстро, мне кажется уже доказано.
Например когда в городах смертность уменьшилась, сразу уменьшилась и рождаемость. Да, для каждого из этих двух явлении есть независимое и несвязанное объяснение, но в итоге популяция все равно отрегулировалась, перенаселение не получится. Может эволюция может действовать и посредствум медицины, образования и шоу индустрию?