ARTS Week 31

Algorithm

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
  • Initialization method RandomizedSet(): Initialize the above-mentioned array, hash table and random number classes respectively
  • Insert method bool insert(int val): first determine whether val already exists, if so, return false, if not, insert val into the end of the array, and update the hash table map at the same time .put(val, list.size()-1);, finally return true
  • Deletion method bool remove(int val): first determine whether val already exists, if not, return false, if it exists, first obtain val through the hash table and index the index in the array, because it requires time The complexity is O(1), then the deletion method of the array cannot be used, but the value at the index position of the array is changed to the value of the last element of the array list.set(index, lastVal);, and updated at the same time. The mapping relationship in the hash table map.put(lastVal, index);, and then remove the last element of the array (this operation is O(1) complexity) and the mapping of val in the hash table, Finally returns true
  • Randomly returns an item int getRandom(): use the random class to randomly generate a number within the index range of the array, and return the number corresponding to the subscript.
class RandomizedSet {    private List<Integer> list;
private Map<Integer, Integer> map;
Random rand;
public RandomizedSet() {
list = new ArrayList<>();
map = new HashMap<>();
rand = new Random();
}

public boolean insert(int val) {
if (map.containsKey(val) == true) {
return false;
} else {
list.add(val);
map.put(val, list.size()-1);
return true;
}
}

public boolean remove(int val) {
if (map.containsKey(val) == false) {
return false;
} else {
int index = map.get(val);
int lastVal = list.get(list.size()-1);
list.set(index, lastVal);
map.put(lastVal, index);
list.remove(list.size()-1);
map.remove(val);
return true;
}
}

public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/

Review

  • These columns are read from memory or, in the worst case, from disk. This means higher resource usage and higher latency.
  • If they’re read form disk they may be cached, if they’re cached they’ll stay in the cache for a longer time. This may be a waste of memory.
  • Columns will be sent over a network. This causes more work both on the database server and the application server.
  1. Columnar databases. many databases are columnar databases, which store different columns in different data structures, so that SUM(column) is faster, while SELECT * will be slower.
  2. Covering indexes. Comparing SELECT id, surname FROM user WHERE surname < 'c'; and SELECT * FROM user WHERE surname < 'c';, if there is an index on id, the former can be quickly read through the index The corresponding content in the line is compared, but the latter does not:
  3. Strength is in numbers. when there are too many columns in a table, the data in all columns cannot be read only by id
  4. Generate column/Virtual column. When the SQL statement is executed, it will calculate and generate virtual columns. In some cases, it will be written to disk for storage. In some cases, it will be calculated immediately. When it is calculated, it will bring greater overhead.
  5. Views. Views are built on JOIN operations, selecting only required columns may ignore some unnecessary tables, making queries faster
  6. InnoDB TEXTs and BLOBs. In InnoDB (the default storage engine for MariaDB and MySQL), large variable-length text and binary columns are stored in separate memory pages. When long data is stored in separate pages, reading it requires at least one physical read. This affects performance.

Tip

: '
This is a
comment
in shell script
'

Share

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
KeepNewbie_yan

A programmer. Share knowledge of programming, operating system, Linux kernel, and reading, thinking etc. Let us maintain a beginner mend and grow together!