Perform password lookup ~40.000x faster
Perform password lookup ~40.000x faster

The current lookup method is a bit inefficient. For every lookup,
it has to open a file, allocate a lot of memory and iterate over an
Array.

The new method introduces two optimizations:
- memoization of all the password values. The file is small (80kB for
    10k passwords), so there is no issue with keeping it in memory
- using a Set instead of an Array. A Set performs a lookup in constant
time compared to an Array, where the worst case scenario is having to
iterate over the whole Array. With this optimisation we could hold much
more weak passwords in memory and the lookup would still take the same
amount of time.

Benchmark:

```ruby
require 'benchmark/ips'
require 'set'

PASSWORD_MATCHES = [100, 1_000, 10_000]

def common_passwords_old
  passwords_file = File.join(File.dirname(__FILE__), '..', 'lib', 'devise', 'uncommon_password', "passwords.txt")

  passwords = []
  File.open(passwords_file, "r") do |file|
    file.each { |password| passwords << password.chomp.downcase }
  end
  passwords.select! {|password| (8..128).include? password.length }
  passwords[0..$matches-1]
end

def common_passwords_new
  return @passwords if @passwords

  passwords_file = File.join(File.dirname(__FILE__), '..', 'lib', 'devise', 'uncommon_password', "passwords.txt")
  passwords = []
  File.open(passwords_file, "r") do |file|
    file.each { |password| passwords << password.chomp.downcase }
  end
  passwords.select! {|password| (8..128).include? password.length }

  # Note: We can memoize the whole list for the purpose of the spec
  @passwords = passwords.to_set
end

passwords_file = File.join(File.dirname(__FILE__), '..', 'lib', 'devise', 'uncommon_password', "passwords.txt")
weak_passwords = []

File.open(passwords_file, "r") do |file|
  file.each { |password| weak_passwords << password.chomp.downcase }
end

secure_password = 'ksdnb8283238hdsifuIAHSIh2iuh237728937*(#@(#*@#))'

PASSWORD_MATCHES.each do |matches|
  $matches = matches

  puts "Benchmarking for #{$matches} matches"
  Benchmark.ips do |bench|
    bench.report("password on weaklist - old with #{matches} matches") { common_passwords_old.include?(weak_passwords.sample) }
    bench.report("password on weaklist - new with #{matches} matches") { common_passwords_new.include?(weak_passwords.sample) }
    bench.report("password not on weaklist - old with #{matches} matches") { common_passwords_old.include?(secure_password) }
    bench.report("password not on weaklist - new with #{matches} matches") { common_passwords_new.include?(secure_password) }

    bench.compare!
  end
end
```

HCLarsen/devise-uncommon_password,HCLarsen/devise-uncommon_password,HCLarsen/devise-uncommon_password