algorithm - Performance of select method in Ruby -

the select method in ruby simple , straight forward. select elements in array matching specific criteria.

for example,

>> 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] 

one problem time penalty. select has go through values in array , sequential check result run in o(n) time. there better alternative select in lesser time. space not issue me.

i talking on cases same select being used repetitively. if going use same select conditions 1000 times in loop array of size n, have operation 1000 * n times. whereas if optimized space, doing 1000 * 1 times.

thanks.

i'm not aware of way perform operation on every element in array in better linear time — idea sounds self-contradictory. memoize result if need same calculation on same array more once trade space constant-time performance on subsequent runs, think o(n) gets otherwise.