Some skills to reduce the complexity of program space

For programs , The important criteria to measure its quality are time complexity and space complexity . On the premise that the target task can be completed , Making the program have low time complexity and low space complexity is the goal we have been pursuing .

However, sometimes you can't have both . With less time complexity , Space complexity tends to increase , While reducing the space complexity , Time complexity tends to increase . Want to get a balance between the two , obviously , It's not easy , It can be said that you can't have both fish and bear's paw ！

ok , Let's get down to business ！

Suppose we imagine such a scenario , There is a file on our computer , The name of the fruit is saved on it , For example, some data like this , Apple , pear , Peach , watermelon , grapes , Apple , watermelon ....... Our goal is to count which of these names appears most often .

The program implementation idea is very simple , That is to initialize a dictionary , If the name does not exist , Then add the name to the dictionary , Its value is set to one , If the name already exists , Then its value is increased by one .

Program ：

fruitData={}with open('data.txt') as f:    content=f.read().splitlines() # Read entire file for fruit in content:    if fruit in fruitData:        fruitData[fruit]=fruitData[fruit]+1    else:        fruitData[fruit]=1print(fruitData)

ok , It's that simple , But when you think about it, there is a problem , That is, this is to read all the file information into memory . When the file size is small , It doesn't take much memory , Once the scale is large , such as 1000GB( Suppose it exceeds the memory of the computer used ), Then there's a problem .

Before that, read all the data at once , in fact , We can read Enter one Data , Processing a data , When processing the next data , The memory occupied by the previous data will also be released in time , In this way, the problem of too much memory is solved .

Improvement of the original program ：

​​​​​​​

fruitData={}with open('data.txt') as f:    for fruit in f:          # Read one line at a time         fruit=fruit.strip()  # Delete the line break at the end         if fruit in fruitData:            fruitData[fruit]=fruitData[fruit]+1        else:            fruitData[fruit]=1print(fruitData)

here , The space complexity has also changed from the original O(n) Down to O(1).