GNU сделать: временная сложность списка доступов

Question

В следующем фрагменте кода данного (слово) список перевернутой:

not_null=$(if $(strip $(1)),t,) 
invert_list=$(if $(call not_null,$(firstword $(1))),$(call invert_list,$(wordlist 2,1000,$(1))) $(firstword $(1))) 
$(info $(call invert_list,1 2 3 4)) 

Как вы можете видеть, я изменял, давая догадывались верхний предел списка 1000 вместо $(words $(1)) на каждой рекурсии, в надежде остаться в O (N) границах. Является ли это разумным в GNU make после всех или является функцией слов O (1)?

Answer 1

Функция words в GNU make is O (N), где N - длина строки. Все функции выполняют синтаксический анализ строки перед ними: они никогда не удерживают внутреннее состояние строки, чтобы быстрее запускать будущие вызовы.

EDIT

Я думал о чем-то вроде этого (непроверенные):

_invert_list = $(if $(strip $(firstword $2)),$(call _invert_list,$1,$(wordlist 2,$1,$2)) $(firstword $2)) 
invert_list = $(call _invert_list,$(words $1),$1) 
$(info $(call invert_list,1 2 3 4)) 

Таким образом, функция words вызывается только один раз, и результат передается в качестве первого аргумента "real" _invert_list функция.

Кстати, вы также можете взглянуть на GMSL, который имеет классные возможности, все реализованы в стандартном исполнении GNU. Не уверены в его характеристиках производительности. Похоже, что реверс GMSL использует, по сути, тот же алгоритм, что и ваша первоначальная попытка (снова вызывает words на каждой итерации).