Enumerate all subsets - Where should we print the result?

#1

Hey everyone!

I have an interesting question about the power set solution:

Implement a method that takes an inputs as input a set S of n distinct elements, and prints the power set of S. Print the subsets one per line, with elements separated by commas.

In the recursion approach, we print out the subset if it’s not empty:

void generate_power_set_helper(const vector<int>& S, 
    int m, vector<int>* subset)
{
    if (!subset->empty()) {
        // Print the subset here.
    }
    ...
}

Because generate_power_set_helper will be called multiple times due to the exponential run time, to avoid heavy I/O I think a better way is use a container to store the all subsets and after recursion step print all the result (implement in Java):

void generatePowerSet(List<Integer> S) {
    if (S == null) {
        return;
    }
    List<List<Integer>> subsets = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<>();
    generatePowerSetHelper(S, 0, path, subsets);
  
    for (List<Integer> path : subsets) {
        // Print it here
    }
}

I checked our Java version PowerSetAlternative.java, but still think it’s worth to discuss iff we want to print the result instead returning it.

0 Likes
#2

Hey Carl,

In the recent revision, we decide to make a slight change to the problem description by returning the whole results instead of printing it (because you can always print that after returning it; moreover, it makes testing easier).

Let’s back to your question, I think storing it might not be a good idea because you need lots of memory during execution, and it might induce some page swaps which further increases some time overheads. On the other hand, I don’t know calling I/O in a batch fashion will reduce run time or not, and I guess it might be language dependent, even architecture dependent. As a result, I chose to printing before instead of storing it.

Please let me know what you think, and it is an interesting topic for sure.

0 Likes
#3

Thanks for your reply.

Yes, I found that we’ve changed the return type of GeneratePowerSet in cpp or generatePowerSet in java. That’s really convenient!

It’s interesting for me cause beside time complexity, we can have a deeper understanding of I/O cost in a programming language. I wanna share some understanding of STDOUT in C++ and Java.

Note: Discussion below is not related to the time complexity of this problem, check Tsung-Hsien’s explanation of the difference between printing the result and returning them back.

STDOUT in Java

For Java, System.out.pritnln(...) is thread safe. Go through the source code we can find that System.out is a PrintStream. It means that each time we call System.out.println(...), we are synchronizing the memory model, checking and waiting for a lock. So, consider a multi-thread environment, the locking can be more of an issue than the I/O.

In a single-thread application, the performance of System.out.println(...) is often limited by the I/O performance of local machine, how fast we can write a file. One thing we may consider is that each println is flushed. This causes the buffers to be cleared and triggers a Console-level write to the buffers. The amount of effort done here is implementation dependent.

STDOUT in C++

Honestly, I’m not familiar with c++, so please correct me if I’m wrong.

I didn’t find any thing about cout in C++03 standard. Jump to C++11, we can say that cout is synchronized, you can find the unofficial spec here:

Concurrent access to a synchronized standard iostream object’s formatted and unformatted input and output.

0 Likes
#4

Hey Carl,

Very good analysis from the system and language perspective. From the manual you found, repeating calls to I/O will actually have some overheads as the program is trying to acquire locks. However, calling I/O in the end will not have this issue but encounter the expense of high memory footprint during execution. As a result, I hardly see which is better unless we actually deployed experiments on it.

Tsung-Hsien

0 Likes