Выполнение метода select в Ruby

Question

Метод выбора в Ruby прост и понятен.Он будет выбирать элементы в массиве, соответствующие определенным критериям.

Например,

>> x = [4,5,7,89,4,5,3,6,8,9,4,45,56,23,2,7,3,5,4,224,234,565,546,345,23,234,234,234,23466,25,54]
x = [4,5,7,89,4,5,3,6,8,9,4,45,56,23,2,7,3,5,4,224,234,565,546,345,23,234,234,234,23466,25,54]
=> [4, 5, 7, 89, 4, 5, 3, 6, 8, 9, 4, 45, 56, 23, 2, 7, 3, 5, 4, 224, 234, 565, 546, 345, 23, 234, 234, 234, 23466, 25, 54]
>> y = x.select{|m| m>20 && m<200}
y = x.select{|m| m>20 && m<200}
=> [89, 45, 56, 23, 23, 25, 54]

Одной из проблем в этом, очевидно, является штраф за время.Select должен просмотреть все значения в этом массиве и выполнить последовательную проверку, которая привела бы к этому запуску за O (n) времени.Есть ли лучшая альтернатива для выбора, которая делает это за меньшее время.Пространство для меня не проблема.

Я говорю о случаях, когда один и тот же выбор используется повторно.Если я собираюсь использовать одни и те же условия выбора 1000 раз в цикле для массива размера n, то мне придется выполнить операцию, как 1000 * n раз.Принимая во внимание, что если бы он оптимизирован для пространства, я бы делал только 1000 * 1 раз.

Спасибо.

Answer 1

Я не знаю, как выполнить операцию над каждым элементом в массиве лучше, чем за линейное время - идея звучит противоречиво.Вы можете запомнить результат, если вам нужно сделать один и тот же расчет для одного и того же массива более одного раза, чтобы обменять пространство на производительность в постоянном времени при последующих запусках, но я думаю, что O (n) так же хорош, как и иначе.