Last article, I showed a simple enumeration generator. But I needed one more flexibility. In my job, I use GPU, that is a fast processing unit, but the available memory size is one order of magnitude small compare to a decent workstation. (E.g, GPU's memory size is 2GB to 6GB, a decent workstation can have 24GB to 256GB main memory.) In this pseudo code example, the unit of memory size is GB. 64GB or 512 GB are too much to the current stare of the art GPUs in 2013. 512GB is too much for the best workstation. Therefore, our product uses a cluster, many workstations are cooperates to do a single job. Almost every customer wants to see how our products scales regarding to the number of workstations. Because they have their needs and they want to know how many workstations and how many GPU are needed for their task. Therefore, we need to demonstrate how the performance changes depends on the number of nodes. Here one more parameter, the number of nodes are added as the following.
However, most of the customer immediately understand if the memory can not hold the data, the system becomes extremely slow. Therefore, the performance graph only needs more than number of nodes that can hold the input data. When we need to generate such parameter combination, the simple idea is to filter out the unnecessary data points. Here is a for-loop implementation example.
for d in data_size_list:
Then I thought that I would like to apply the same idea to the direct product. I actually started the for-loop implementation, so this filtering idea seems simple. But I figure out that I need the filter function for each input parameter set. I actually started implementing such code, but I felt it looked way to complicated. Most of the filter function does nothing in this case. Moreover, when I extends the functionality, I found the change is too complex, I can not handle such complexity. I believe it will work, but the implementation is too complex for me. It is hard to explain my ``too complex feeling.'' Though, that is the feeling: ``Why does this simple problem needs such a complex implementation?'' I usually have a feeling when I didn't understand the problem itself well.
I re-thought the problem and tried to formalize, and asked myself: what is this problem? The number of nodes I needed is depends on the data size. Why did I use filter function? This is a generate-and-test algorithm. But do I really need the test function after generating the combination candidates? At that point, I figured out. This is just a map from data size to the number of nodes, I don't need the test function. I can have it as an input. The mathematical object I should use here is a `map' instead of a `filter'. My final implementation was the following.
gen_with_node() function generates combination lists by using data_size_node_count_map() function. This is more efficient since there is no generate and test (means discarding is included), and simpler since the input data doesn't need filter functors. I sometimes think that some people's code misuses the mathematical objects. I sometimes criticize the code from people who has high implementation ability, but less considering the mathematical objects.
I used to respect these people because of their high implementation ability. I used to try to write such code. However, often I experienced that I was be able to write a simple program if I thoroughly thought the mathematical meaning of the program. First I surprised my program is often comparable speed or sometimes faster than them. Moreover, my code tend to be simple and less bugs. This was a surprising discovery and then I tend to study more on a mathematics aspect of the program.
This time, I mistook which mathematical object to use in my program. I should review myself first.
By the way, why does it usually better that thinking mathematical object in a program? Are there any reasons? I have two hypothetical reasons. One is we can use all the mathematical research results that has a thousand years of history. Many genius thought through about many problems. They classify the problems and found many patterns to solve them. I don't surprised these genius's ideas are better than my ideas that is usually made up in a five minutes. Actually I never remember that my own idea was better than the combination of these genius's ideas. The other reason is many programming language supports these mathematical object. Many of computer language designers also found the mathematical object is useful to solve problems. Therefore, these objects are often supported. The language supports the mathematical object, it is usually efficient and simple. In this particular problem, I use a direct product and a map. For instance, map is supported in Python as `dict', lisp has `mapcar', Java has a Map in util, C++ STL has `map` template class.
This was a simple problem, but it turned out it's interesting to me.
References
[1] Hisao Tamaki, ``Introduction to probability theory for the information scientist (in Japanese)'', Saiensu, ISBN4-7819-1012-2, 2002
Implementation example code
http://sundayresearch.de/hitoshi/sundayresearch/programming/Python/20130323_math_object/enum_code_20130323.zip
data_size_list = [ 5, 64, 512, ] screen_resolution_list = [ '2560x1440', '3840x2160', ] node_count_list = [ 1, 2, 4, 8, 16, 32, 64, ]
However, most of the customer immediately understand if the memory can not hold the data, the system becomes extremely slow. Therefore, the performance graph only needs more than number of nodes that can hold the input data. When we need to generate such parameter combination, the simple idea is to filter out the unnecessary data points. Here is a for-loop implementation example.
for d in data_size_list:
for d in data_size_list:
for s in screen_resolution_list:
for n in node_count_list:
# FILTER: filter some cases.
# assume one node can handle
# 64G, but not more
if (n * 64 < d):
continue
item_list = [
d, s, n,
]
comb_list.append(item_list)
Then I thought that I would like to apply the same idea to the direct product. I actually started the for-loop implementation, so this filtering idea seems simple. But I figure out that I need the filter function for each input parameter set. I actually started implementing such code, but I felt it looked way to complicated. Most of the filter function does nothing in this case. Moreover, when I extends the functionality, I found the change is too complex, I can not handle such complexity. I believe it will work, but the implementation is too complex for me. It is hard to explain my ``too complex feeling.'' Though, that is the feeling: ``Why does this simple problem needs such a complex implementation?'' I usually have a feeling when I didn't understand the problem itself well.
I re-thought the problem and tried to formalize, and asked myself: what is this problem? The number of nodes I needed is depends on the data size. Why did I use filter function? This is a generate-and-test algorithm. But do I really need the test function after generating the combination candidates? At that point, I figured out. This is just a map from data size to the number of nodes, I don't need the test function. I can have it as an input. The mathematical object I should use here is a `map' instead of a `filter'. My final implementation was the following.
data_size_list = [ 5, 64, 512, ]
screen_resolution_list = [
'2560x1440', '3840x2160', ]
data_size_node_count_map = {
5: [1, 2, 4, 8, 16, 32, 64]
64: [8, 16, 32, 64]
512: [32, 64]
}
all_list = [
data_size_list,
screen_resolution_list,
]
comb_list = []
c_tuple = [''] * len(all_list)
def make_tuple(idx):
if(idx >= len(all_list)):
comb_list.append(
copy.deepcopy(c_tuple))
else:
for i in range(len(all_list[idx])):
c_tuple[idx] = all_list[idx][i]
make_tuple(idx + 1)
def gen_combination_list():
make_tuple(0)
for i in comb_list:
gen_with_node(i)
gen_with_node() function generates combination lists by using data_size_node_count_map() function. This is more efficient since there is no generate and test (means discarding is included), and simpler since the input data doesn't need filter functors. I sometimes think that some people's code misuses the mathematical objects. I sometimes criticize the code from people who has high implementation ability, but less considering the mathematical objects.
I used to respect these people because of their high implementation ability. I used to try to write such code. However, often I experienced that I was be able to write a simple program if I thoroughly thought the mathematical meaning of the program. First I surprised my program is often comparable speed or sometimes faster than them. Moreover, my code tend to be simple and less bugs. This was a surprising discovery and then I tend to study more on a mathematics aspect of the program.
This time, I mistook which mathematical object to use in my program. I should review myself first.
By the way, why does it usually better that thinking mathematical object in a program? Are there any reasons? I have two hypothetical reasons. One is we can use all the mathematical research results that has a thousand years of history. Many genius thought through about many problems. They classify the problems and found many patterns to solve them. I don't surprised these genius's ideas are better than my ideas that is usually made up in a five minutes. Actually I never remember that my own idea was better than the combination of these genius's ideas. The other reason is many programming language supports these mathematical object. Many of computer language designers also found the mathematical object is useful to solve problems. Therefore, these objects are often supported. The language supports the mathematical object, it is usually efficient and simple. In this particular problem, I use a direct product and a map. For instance, map is supported in Python as `dict', lisp has `mapcar', Java has a Map in util, C++ STL has `map` template class.
This was a simple problem, but it turned out it's interesting to me.
References
[1] Hisao Tamaki, ``Introduction to probability theory for the information scientist (in Japanese)'', Saiensu, ISBN4-7819-1012-2, 2002
Implementation example code
http://sundayresearch.de/hitoshi/sundayresearch/programming/Python/20130323_math_object/enum_code_20130323.zip
Comments