Some years in the past, a buyer requested in my job to generate 1,000,000 distinctive codes for a promotion. Every code needed to be a sixteen digits alphanumeric worth following somes guidelines like having quite a few digits and so forth.
It was not a troublesome activity, however I used to be impressed when the client informed one other firm would want 24 hours of processing to generate the codes. 24 hours??? actually?
Could be the codes had been being generated utilizing this algorithm:
whereas depend < 1000000
create a code
examine if code exists by examine one after the other on a database
if not exists, retailer within the information base
depend++
finish
In that point I couldn’t know the way was it completed, however appeared an O^2 algorithm.
Whereas considering the way to enhance the algorithm, an thought occurred to me: what about utilizing a hash? Every code could possibly be saved as a key, and accessing a key in a hash is an O(1) operation (actually it relies on dealing with collisions, which information construction is used, and so on).
This concept appeared promising, so I made a decision to provide it a try to strive by writing and implementing this algorithm in python:
values = {}
whereas depend < 1000000
create a code
if values[code] not exists
values[code] = true
depend++
finish
finish
It took round one minute to generate the million codes, and taking into consideration it was executed in an previous Dell XPS laptop computer, was not unhealthy in any respect.
As soon as codes had been generated, a coworker did a check to make sure unicity: he loaded the codes right into a database and executed a question like SELECT DISTINCT(code) FROM values
It simply labored: there have been 1,000,000 of various codes.
He appeared amazed by the outcomes.
Clearly, there are extra particulars to consider: the way to generate an distinctive code (generate random string libraries), code format, and so on, however labored very nice.
As talked about earlier, I did it some years in the past, however my curiosity lead me to strive once more utilizing totally different languajes, like Ruby and Rust, and examine the execution time for them.
These are the outcomes utilizing a Ryzen 5 3600 CPU working in Debian:
Ruby
require 'securerandom'
h = {}
depend = 0
whereas depend < 1000000
random_string = SecureRandom.hex
if !h[random_string]
h[random_string] = 1
depend += 1
finish
finish
doc@Mimzy:~/tmp/keys $ time ruby keys.rb
actual 0m1,526s
person 0m1,188s
sys 0m0,336s
Rust
use std::collections::HashMap;
use rand::distributions::{Alphanumeric, DistString};
fn fundamental() {
let mut map = HashMap::new();
let mut depend = 0;
whereas depend < 1_000_000 {
let s = Alphanumeric.sample_string(&mut rand::thread_rng(), 16);
if !map.contains_key(&s.clone()) {
map.insert(s.clone(), 1);
depend += 1;
}
}
}
doc@Mimzy:~/tmp/keys $ time ./goal/launch/keys
actual 0m0,461s
person 0m0,449s
sys 0m0,012s
As you possibly can see, there’s a nice enchancment, however consider that Rust code is compiled and optimized, whereas Ruby code is interpreted.
In conclusion: discover new and other ways to unravel issues, using artistic pondering within the course of.
